摘 要： 基于密度吸引點和其對相鄰節(jié)點的影響度，提出了一種密度分布社區(qū)發(fā)現(xiàn)算法,。該算法以節(jié)點度數(shù)最大的密度吸引點為初始社區(qū),，訪問社區(qū)的相鄰節(jié)點，把對社區(qū)影響度最大的節(jié)點加入到社區(qū)中,，如果有些節(jié)點對多個社區(qū)都有影響,，則把它歸屬為影響度最大的那個社區(qū)中，同時如果兩個社區(qū)之間的相互影響度很大,，可以將這兩個社區(qū)合并為一個社區(qū),。將該算法應用到Zachary空手道俱樂部網絡和隨機無標度網絡中,，實驗表明該算法能夠很好地分出網絡中的社區(qū)，同時實驗還發(fā)現(xiàn)社區(qū)的收斂速度與冪率分布特性近似成反比,。
關鍵詞： 復雜網絡,；冪率分布；社區(qū)發(fā)現(xiàn),；密度分布,；影響度
所謂社區(qū)，是指具有共同興趣,、愛好的人或者學有專精的專業(yè)人士,，通過一定的方式聚集在一起，彼此之間可以溝通,、交流,、分享相關信息。在現(xiàn)實世界中,，存在著很多這樣的社區(qū),，例如社會關系網絡[1]、神經網絡,、食物鏈網絡,、城市交通網絡等。在這些社區(qū)中,，有著復雜的內部結構,，用節(jié)點表示實體，用連線表示實體間的聯(lián)系,，社區(qū)內部節(jié)點之間的聯(lián)系非常緊密,，社區(qū)之間的聯(lián)系相對稀疏。近幾年,，隨著網絡的急速發(fā)展，網絡社區(qū)也成為一個研究熱點,，同時取得了很重要的進展,，并且發(fā)現(xiàn)了網絡社區(qū)的很多特點，其中包括小世界特性(即網絡中節(jié)點之間的平均距離很短,，對數(shù)依賴于網絡中的節(jié)點數(shù)),、無標度特性(即網絡中節(jié)點的度分布右偏斜，具備冪函數(shù)或指數(shù)函數(shù)的形式),、聚集性或網絡傳遞性以及社區(qū)結構特性,，大量實證研究表明，許多網絡是異構的,，即復雜網絡不是大批性質相同節(jié)點的隨機連接,，而是許多類型節(jié)點的組合,，其中相同類型的節(jié)點存在較多的連接，而不同類型節(jié)點的連接則相對較少,。把同一類型節(jié)點以及這些節(jié)點之間的邊所構成的子圖稱為網絡中的社區(qū),。社區(qū)如圖1所示，圖中的小型網絡中包含3個社區(qū),，對應圖中的3個橢圓,，在這些社區(qū)內部，節(jié)點與節(jié)點之間的聯(lián)系非常緊密,，而社區(qū)之間的聯(lián)系則比較稀疏[2-4],。
網絡社區(qū)發(fā)掘對于了解網絡結構和分析網絡特征具有重要的意義，目前已經提出了具有基于節(jié)點集劃分的社區(qū)發(fā)現(xiàn)算法,，例如基于貪婪算法原理的Kernighan-Lin算法,、基于譜思想的譜平分算法、基于分裂思想的GN算法和基于凝聚思想的Newman快速算法等[5-7],。網絡社區(qū)發(fā)現(xiàn)的最終目的就是將網絡劃分為若干個互相獨立的社區(qū),，這些算法對研究社區(qū)發(fā)現(xiàn)都產生了重大的影響。
1 算法設計
由于網絡社區(qū)中節(jié)點之間的聯(lián)系相對緊密,，社區(qū)之間節(jié)點的聯(lián)系相對稀疏,，根據(jù)這一特性，本文提出了基于密度分布的社區(qū)發(fā)現(xiàn)算法,。在實際網絡中,，存在一些節(jié)點與其他節(jié)點的聯(lián)系非常緊密，即該節(jié)點的度最大,，稱為“密度吸引點”,，其他節(jié)點以“密度吸引點”為中心，從而形成社區(qū),。該算法的基本思想是以密度吸引點為初始社區(qū),，然后找出對該吸引點影響最大的節(jié)點依次加入到社區(qū)，一個網絡中存在可能不止一個吸引點,，因此在網絡中可能存在多個社區(qū),，在計算節(jié)點影響度時要考慮對多個社區(qū)的影響。直到所有的節(jié)點都被分到了各自的社區(qū)中,。同時要考慮不同社區(qū)之間的影響度,，如果兩個社區(qū)之間的相互影響度非常大，就認為這兩個社區(qū)為一個社區(qū),，則合并這兩個社區(qū),。
1.2 算法描述
本算法中，假設社區(qū)內部度數(shù)越大則社區(qū)密度越大,；密度越大的社區(qū)對其周圍節(jié)點的吸引力越大,；對在同一個層次即相對密度吸引點來說密度相同的節(jié)點的吸引力相同,。
(1)初始化網絡，將網絡中的每個節(jié)點看成是獨立的社區(qū),，計算社區(qū)的密度,，每個社區(qū)的初始密度為節(jié)點的度數(shù)；
(2)找出網絡中密度最大的社區(qū),，該社區(qū)為密度吸引點,；
(3)根據(jù)影響函數(shù)，計算與密度吸引點相鄰社區(qū)對密度吸引點的影響度,，找出影響度最大的社區(qū),，此處認為這個社區(qū)與密度吸引點為同一個社區(qū)（影響度最大的社區(qū)可能不止一個）；
(4)再次計算網絡中所有社區(qū)的密度,，此時應用密度函數(shù)進行計算,，并找出密度最大的社區(qū)作為密度吸引點；
(5)重復步驟(3),、步驟(4),，直到所有的社區(qū)都合并完成，算法結束,。
算法流程圖如圖2所示,。
2 算法驗證
為了驗證本算法的有效性，將本算法應用到Zachary′s Karate Club Network[9]和隨機的無標度網絡,。實驗結果表明,，本算法可以將網絡劃分為大小不同的社區(qū)，且具有較好的效果,。
2.1 Zachary′s Karate Club Network
在復雜網絡社區(qū)結構的研究中,，Zachary′s Karate Club Network是經常被使用的經典數(shù)據(jù)集，它是20世紀70年代初期Zachary用了兩年的時間觀察得到的美國一所大學中空手道俱樂部成員的相互社會關系網絡,。在這個網絡數(shù)據(jù)集中包含了34個節(jié)點和78條邊,，其中節(jié)點表示俱樂部成員，邊表示成員之間的社會關系,，網絡結構如圖3所示,。
通過應用密度分布社區(qū)發(fā)現(xiàn)算法，可以將該經典網絡準確地分為兩個社區(qū),，社區(qū)分布節(jié)點為：第一個社區(qū)(1，2,，3,，4，5,，6,，7,，8，11,，12,，13，14,，17,，18，20,，22),，第二個社區(qū)(9，10,，15,，16，19,，21,，23，24,，25,，26，27,，28,，29，30,，
31,，32，33,，34),。同時還發(fā)現(xiàn)由于網絡節(jié)點的分布遵循冪率分布定律，因此社區(qū)合并的速度正好與冪率分布呈反比,，即社區(qū)密度越小,，社區(qū)收斂的越快。比較結果如圖4所示,。
2.2 隨機無標度網絡
在現(xiàn)實網絡中,，大部分網絡都符合復雜網絡特性，因此在第二個實驗中,，隨機截取了網絡中節(jié)點相互關聯(lián)的一部分隨機的無標度網絡作為實驗對象,，該網絡中共有62個節(jié)點，400條邊，節(jié)點代表其相應的網頁,，邊代表網頁之間相互的連接關系,，其網絡結構如圖5所示。
在實驗過程中,，對該網絡節(jié)點用1~62進行了隨機的標注,，通過應用密度分布社區(qū)發(fā)現(xiàn)算法，成功地將社區(qū)分成了兩個部分,，社區(qū)收斂速度與冪率分布對比如圖6所示,。
實驗結果表明本算法可以準確地將隨機無標度網絡分為兩個社區(qū)，實驗結果如圖7所示,。
本文提出的基于密度分布的社區(qū)發(fā)現(xiàn)算法, 根據(jù)聚類算法中的密度分布函數(shù),，利用密度吸引點，通過計算影響函數(shù),，對網絡進行聚類,，完成網絡社區(qū)的劃分。利用兩個數(shù)據(jù)集對本算法進行了有效性驗證,，結果表明,，該算法能準確地找出網絡中存在的社區(qū)，并且發(fā)現(xiàn)社區(qū)收斂時與冪率分布的規(guī)律,。本算法僅對部分社區(qū)進行了實驗,，關于時間復雜度等并沒有進行精確的計算，以后還需要進一步對該算法進行驗證和改進,。
參考文獻
[1] KERNIGHAN B W,，LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970,，49(2)：291-307.
[2] 馬興福,，王紅.一種新的重疊社區(qū)發(fā)現(xiàn)算法[J].計算機應用研究，2012,，29(3)：844-846.
[3] 林友芳,，王天宇，唐銳,，等.一種有效的社會網絡社區(qū)發(fā)現(xiàn)模型和算法[J].計算機研究與發(fā)展,，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] 韓家煒,，坎伯.數(shù)據(jù)挖掘概念與技術[M].范明，孟小峰,，譯. 北京：機械工業(yè)出版社,，2001.
[9] 汪小帆，李翔,，陳關榮.復雜網絡及其應用[M].北京：清華大學出版社,，2006.