摘  要： 基于密度吸引點和其對相鄰節點的影響度，提出了一種密度分布社區發現算法。該算法以節點度數最大的密度吸引點為初始社區，訪問社區的相鄰節點，把對社區影響度最大的節點加入到社區中，如果有些節點對多個社區都有影響，則把它歸屬為影響度最大的那個社區中，同時如果兩個社區之間的相互影響度很大，可以將這兩個社區合并為一個社區。將該算法應用到Zachary空手道俱樂部網絡和隨機無標度網絡中，實驗表明該算法能夠很好地分出網絡中的社區，同時實驗還發現社區的收斂速度與冪率分布特性近似成反比。
 關鍵詞： 復雜網絡；冪率分布；社區發現；密度分布；影響度

所謂社區，是指具有共同興趣、愛好的人或者學有專精的專業人士，通過一定的方式聚集在一起，彼此之間可以溝通、交流、分享相關信息。在現實世界中，存在著很多這樣的社區，例如社會關系網絡[1]、神經網絡、食物鏈網絡、城市交通網絡等。在這些社區中，有著復雜的內部結構，用節點表示實體，用連線表示實體間的聯系，社區內部節點之間的聯系非常緊密，社區之間的聯系相對稀疏。近幾年，隨著網絡的急速發展，網絡社區也成為一個研究熱點，同時取得了很重要的進展，并且發現了網絡社區的很多特點，其中包括小世界特性(即網絡中節點之間的平均距離很短，對數依賴于網絡中的節點數)、無標度特性(即網絡中節點的度分布右偏斜，具備冪函數或指數函數的形式)、聚集性或網絡傳遞性以及社區結構特性，大量實證研究表明，許多網絡是異構的，即復雜網絡不是大批性質相同節點的隨機連接，而是許多類型節點的組合，其中相同類型的節點存在較多的連接，而不同類型節點的連接則相對較少。把同一類型節點以及這些節點之間的邊所構成的子圖稱為網絡中的社區。社區如圖1所示，圖中的小型網絡中包含3個社區，對應圖中的3個橢圓，在這些社區內部，節點與節點之間的聯系非常緊密，而社區之間的聯系則比較稀疏[2-4]。

    網絡社區發掘對于了解網絡結構和分析網絡特征具有重要的意義，目前已經提出了具有基于節點集劃分的社區發現算法，例如基于貪婪算法原理的Kernighan-Lin算法、基于譜思想的譜平分算法、基于分裂思想的GN算法和基于凝聚思想的Newman快速算法等[5-7]。網絡社區發現的最終目的就是將網絡劃分為若干個互相獨立的社區，這些算法對研究社區發現都產生了重大的影響。
1 算法設計
    由于網絡社區中節點之間的聯系相對緊密，社區之間節點的聯系相對稀疏，根據這一特性，本文提出了基于密度分布的社區發現算法。在實際網絡中，存在一些節點與其他節點的聯系非常緊密，即該節點的度最大，稱為“密度吸引點”，其他節點以“密度吸引點”為中心，從而形成社區。該算法的基本思想是以密度吸引點為初始社區，然后找出對該吸引點影響最大的節點依次加入到社區，一個網絡中存在可能不止一個吸引點，因此在網絡中可能存在多個社區，在計算節點影響度時要考慮對多個社區的影響。直到所有的節點都被分到了各自的社區中。同時要考慮不同社區之間的影響度，如果兩個社區之間的相互影響度非常大，就認為這兩個社區為一個社區，則合并這兩個社區。

1.2 算法描述
    本算法中，假設社區內部度數越大則社區密度越大；密度越大的社區對其周圍節點的吸引力越大；對在同一個層次即相對密度吸引點來說密度相同的節點的吸引力相同。
    (1)初始化網絡，將網絡中的每個節點看成是獨立的社區，計算社區的密度，每個社區的初始密度為節點的度數；
    (2)找出網絡中密度最大的社區，該社區為密度吸引點；
    (3)根據影響函數，計算與密度吸引點相鄰社區對密度吸引點的影響度，找出影響度最大的社區，此處認為這個社區與密度吸引點為同一個社區（影響度最大的社區可能不止一個）；
    (4)再次計算網絡中所有社區的密度，此時應用密度函數進行計算，并找出密度最大的社區作為密度吸引點；
    (5)重復步驟(3)、步驟(4)，直到所有的社區都合并完成，算法結束。
    算法流程圖如圖2所示。

2 算法驗證
    為了驗證本算法的有效性，將本算法應用到Zachary′s Karate Club Network[9]和隨機的無標度網絡。實驗結果表明，本算法可以將網絡劃分為大小不同的社區，且具有較好的效果。
2.1 Zachary′s Karate Club Network
    在復雜網絡社區結構的研究中，Zachary′s Karate Club Network是經常被使用的經典數據集，它是20世紀70年代初期Zachary用了兩年的時間觀察得到的美國一所大學中空手道俱樂部成員的相互社會關系網絡。在這個網絡數據集中包含了34個節點和78條邊，其中節點表示俱樂部成員，邊表示成員之間的社會關系，網絡結構如圖3所示。
    通過應用密度分布社區發現算法，可以將該經典網絡準確地分為兩個社區，社區分布節點為：第一個社區(1，2，3，4，5，6，7，8，11，12，13，14，17，18，20，22)，第二個社區(9，10，15，16，19，21，23，24，25，26，27，28，29，30，
31，32，33，34)。同時還發現由于網絡節點的分布遵循冪率分布定律，因此社區合并的速度正好與冪率分布呈反比，即社區密度越小，社區收斂的越快。比較結果如圖4所示。

2.2 隨機無標度網絡
    在現實網絡中，大部分網絡都符合復雜網絡特性，因此在第二個實驗中，隨機截取了網絡中節點相互關聯的一部分隨機的無標度網絡作為實驗對象，該網絡中共有62個節點，400條邊，節點代表其相應的網頁，邊代表網頁之間相互的連接關系，其網絡結構如圖5所示。
    在實驗過程中，對該網絡節點用1~62進行了隨機的標注，通過應用密度分布社區發現算法，成功地將社區分成了兩個部分，社區收斂速度與冪率分布對比如圖6所示。

    實驗結果表明本算法可以準確地將隨機無標度網絡分為兩個社區，實驗結果如圖7所示。

    本文提出的基于密度分布的社區發現算法, 根據聚類算法中的密度分布函數，利用密度吸引點，通過計算影響函數，對網絡進行聚類，完成網絡社區的劃分。利用兩個數據集對本算法進行了有效性驗證，結果表明，該算法能準確地找出網絡中存在的社區，并且發現社區收斂時與冪率分布的規律。本算法僅對部分社區進行了實驗，關于時間復雜度等并沒有進行精確的計算，以后還需要進一步對該算法進行驗證和改進。
參考文獻
[1] KERNIGHAN B W，LIN S.An efficient heuristic procedure  for partitioning graphs[J].Bell System Technical Journal，1970，49(2)：291-307.
[2] 馬興福，王紅.一種新的重疊社區發現算法[J].計算機應用研究，2012，29(3)：844-846.
[3] 林友芳，王天宇，唐銳，等.一種有效的社會網絡社區發現模型和算法[J].計算機研究與發展，2012，49(2)：337-345.
[4] 李峻金，向陽，牛鵬，等.一種新的復雜網絡聚類算法[J]. 計算機應用研究，2010，27(6)：2097-2099.
[5] CAPOCCI A，SERVEDIO V D P，CALDARELLI G，et al.  Detecting communities in large networks[J].Physica A，2005，352(2-4)：669-676.
[6] NEWMAN M E，GIRVAN M.Finding and evaluating community structure in networks[J].Phys.Rev.E，2004，69(2): 026113.
[7] DUCH J，ARENAS A.Community detection in complex  networks using extreme optimization[J].Phys.Rev.E，2005，72(2)：027104.
[8] 韓家煒，坎伯.數據挖掘概念與技術[M].范明，孟小峰，譯. 北京：機械工業出版社，2001.
[9] 汪小帆，李翔，陳關榮.復雜網絡及其應用[M].北京：清華大學出版社，2006.