基于密度分布的社區發現算法研究*

常富蓉

（喀什師范學院 信息工程技術系，新疆 喀什844006）

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

圖1 三社區網絡

網絡社區發掘對于了解網絡結構和分析網絡特征具有重要的意義，目前已經提出了具有基于節點集劃分的社區發現算法，例如基于貪婪算法原理的Kernighan-Lin算法、基于譜思想的譜平分算法、基于分裂思想的GN算法和基于凝聚思想的Newman快速算法等[5-7]。網絡社區發現的最終目的就是將網絡劃分為若干個互相獨立的社區，這些算法對研究社區發現都產生了重大的影響。

1 算法設計

由于網絡社區中節點之間的聯系相對緊密，社區之間節點的聯系相對稀疏，根據這一特性，本文提出了基于密度分布的社區發現算法。在實際網絡中，存在一些節點與其他節點的聯系非常緊密，即該節點的度最大，稱為“密度吸引點”，其他節點以“密度吸引點”為中心，從而形成社區。該算法的基本思想是以密度吸引點為初始社區，然后找出對該吸引點影響最大的節點依次加入到社區，一個網絡中存在可能不止一個吸引點，因此在網絡中可能存在多個社區，在計算節點影響度時要考慮對多個社區的影響。直到所有的節點都被分到了各自的社區中。同時要考慮不同社區之間的影響度，如果兩個社區之間的相互影響度非常大，就認為這兩個社區為一個社區，則合并這兩個社區。

1.1 相關知識

在這里影響函數可以由某個網絡鄰域內兩個節點的距離決定。

(2)密度函數：在網絡中，一個節點x的密度函數被定義為在社區中所有節點影響函數的平均值，給定n個節點的網絡D={x1，…，xn}?Fd，在x上密度函數定義為：

(3)密度吸引點：指在整個網絡中密度最大的節點。一個節點x是被一個密度吸引點x*吸引的，如果存在一組點(x0，x1，…，xk)，x0=x，xk=x*，對于 0＜i＜k，xi-1的梯 度在xi的方向上。在這里密度吸引點為度數最大的節點。

1.2 算法描述

本算法中，假設社區內部度數越大則社區密度越大；密度越大的社區對其周圍節點的吸引力越大；對在同一個層次即相對密度吸引點來說密度相同的節點的吸引力相同。

(1)初始化網絡，將網絡中的每個節點看成是獨立的社區，計算社區的密度，每個社區的初始密度為節點的度數；

(2)找出網絡中密度最大的社區，該社區為密度吸引點；

(3)根據影響函數，計算與密度吸引點相鄰社區對密度吸引點的影響度，找出影響度最大的社區，此處認為這個社區與密度吸引點為同一個社區（影響度最大的社區可能不止一個）；

(4)再次計算網絡中所有社區的密度，此時應用密度函數進行計算，并找出密度最大的社區作為密度吸引點；

(5)重復步驟(3)、步驟(4)，直到所有的社區都合并完成，算法結束。

算法流程圖如圖2所示。

圖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所示。

圖3 Zachary′s Karate Club Network

圖4 社區收斂速度與冪率分布對比圖

2.2 隨機無標度網絡

在現實網絡中，大部分網絡都符合復雜網絡特性，因此在第二個實驗中，隨機截取了網絡中節點相互關聯的一部分隨機的無標度網絡作為實驗對象，該網絡中共有62個節點，400條邊，節點代表其相應的網頁，邊代表網頁之間相互的連接關系，其網絡結構如圖5所示。

在實驗過程中，對該網絡節點用1～62進行了隨機的標注，通過應用密度分布社區發現算法，成功地將社區分成了兩個部分，社區收斂速度與冪率分布對比如圖6所示。

圖5 隨機無標度網絡圖

圖6 隨機網絡社區收斂速度與冪率分布對比圖

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

圖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.