劉大有，楊建寧，楊 博，趙學華，金 弟

（1.吉林大學 計算機科學與技術學院，長春 130012；2.吉林大學 符號與知識工程教育部重點實驗室 長春 130012；3.天津大學 計算機科學與技術學院，天津 300072）

網(wǎng)絡簇結構是復雜網(wǎng)絡最普遍、最重要的拓撲結構屬性之一，具有同簇結點相互連接密集，異簇結點相互連接稀疏的特點。復雜網(wǎng)絡聚類方法旨在揭示出復雜網(wǎng)絡中真實存在的網(wǎng)絡簇結構［1］。目前已存在很多復雜網(wǎng)絡社區(qū)挖掘算法，基本可分為三類：基于啟發(fā)式的社區(qū)挖掘算法［2-7］，基于優(yōu)化的社區(qū)挖掘算法［8-12］和基于概率生成模型的社區(qū)挖掘算法［13-16］?；趩l(fā)式的社區(qū)挖掘算法通常是給出社區(qū)挖掘的啟發(fā)式信息，通過這些啟發(fā)式知識來劃分社區(qū)。如MFC算法［17］，HITS 算 法［2］，GN 算 法［3］及 多 種 變 種［4-5］以及WH算法［6］?；趦?yōu)化的社區(qū)挖掘算法通常定義劃分社區(qū)的目標函數(shù)，并優(yōu)化目標函數(shù)使其達到最大值或接近目標函數(shù)的最大值進而得到社區(qū)的劃分結果。如譜方法［8-9］，圖分割 KL算法［10］，F(xiàn)N 算法［11］以及 GA 算法［12］?；诟怕噬赡Ｐ偷姆椒ㄍㄟ^建立網(wǎng)絡生成模型，并根據(jù)極大似然原理生成模型中的參數(shù)，從而得到網(wǎng)絡的社區(qū)劃分。典型代表是基于隨機塊模型（stochastic block model）的方法［14-15，18-19］。

如何合理地確定社區(qū)個數(shù)是很多復雜網(wǎng)絡社區(qū)挖掘方法面臨的難題。如何設計出能客觀評價社區(qū)結構優(yōu)劣的目標函數(shù)是現(xiàn)有方法特別是基于優(yōu)化的方法所面臨的另一個主要問題。Newman等人［20］提出網(wǎng)絡模塊度Q函數(shù)是最廣泛采用的一種優(yōu)化目標，但研究發(fā)現(xiàn)Q函數(shù)存在分辨率極限等問題［21］。

2004年Radicchi等人［4］提出了連接聚類系數(shù)，認為簇間邊應很少出現(xiàn)在短回路中，否則短回路中其他多數(shù)連接也可能成為簇間連接，從而顯著增加簇間連接密度。文獻［4］將連接聚類系數(shù)定義為包含該鏈接的短回路數(shù)目，并認為簇間連接的連接聚類系數(shù)應小于簇內(nèi)連接，在算法每次迭代中刪除網(wǎng)絡中連接系數(shù)最小的連接，直到劃分出合理的社區(qū)。但算法時間復雜度較高。

本文屬于基于啟發(fā)式的社區(qū)挖掘算法，所用啟發(fā)性知識與文獻［4］相同，但提出了更為有效的短回路搜索策略和基于該策略的社區(qū)挖掘方法，并通過實驗對環(huán)路與社區(qū)之間的聯(lián)系做了更為細致的分析。

1 環(huán)路緊密度算法（LTA）

1.1 算法基本思想

通過一次遍歷圖中所有的邊（假設研究的是無權無向圖），若i結點到j結點有兩條完全不重合的路徑，則說明i，j同屬于一個環(huán)路。若環(huán)路上結點的個數(shù)p小于某個特定的值α，則認為此環(huán)路緊密。認為緊密環(huán)路內(nèi)結點僅包含于一個社區(qū)，否則環(huán)路內(nèi)大部分邊會成為社區(qū)間連接，這樣會大大增加社區(qū)間的連接密度［4］。且認為不在同一社區(qū)中的結點，即使結點之間存在兩條完全不重合的路徑，但這樣的兩條路徑所構成的環(huán)路一般周長較長，即此環(huán)路一般是疏松的。通過合理設計算法，可通過一次遍歷網(wǎng)絡得到網(wǎng)絡中所有的緊密環(huán)路。表1為算法描述中使用的符號和定義。

表1 算法描述中用到的符號及說明Table 1 Symbols and description used in algorithm

步驟一：利用廣度優(yōu)先遍歷算法遍歷全圖。在當前訪問結點集合中選取要訪問的結點。若結點之前未被訪問，則將其前向結點記錄，并將該結點的鄰居結點（不包含其前向結點）加入下次訪問結點集合，轉步驟四；若結點已被訪問，則必存在至少兩條不同的路徑能訪問到當前結點，故存在環(huán)路，轉步驟二。

步驟二：找出遍歷到當前結點的兩條不同的路徑，得到環(huán)路。判斷環(huán)路結點個數(shù)p是否滿足條件p≤α，若滿足則環(huán)路足夠緊密，轉步驟三；若不滿足條件，轉步驟四。

步驟三：若在所有環(huán)路中有兩個緊密環(huán)路有邊重合，則將兩個環(huán)路合并，將兩個環(huán)路合并后稱為一個核，若是當前找到的緊密環(huán)路與某個核有邊重合，則將該環(huán)路合并到核內(nèi)，若在合并過程中引起某核與核之間有邊重合，同樣進行合并。以此類推，得到最終的核；若該緊密環(huán)路不與任何環(huán)路或是核有邊重合，則做為獨立的核存在。

步驟四：若當前訪問結點集合不空，在當前訪問結點集合中選取一個結點做為下一次訪問的結點，轉步驟一；若當前訪問結點集合為空，轉步驟五。

步驟五：若待訪問結點集合為空，算法結束。轉步驟六。

步驟六：最后將不在任何核中的結點通過計算其與各個核的緊密程度，取與各個核中最為緊密的的核作為其社區(qū)歸屬。

算法只需一次遍歷整個圖，便可以得到圖中的所有最小環(huán)路，通過合并環(huán)路與環(huán)路、環(huán)路與核、核與核，最終得到核的個數(shù)作為社區(qū)的個數(shù)。

1.2 基本的LTA算法

S表示結點結合，Sg表示從S0開始算起，第g代待訪問結點的集合，即從種子結點，遍歷g步得到的結點集合，?i，Si∈S。從V中選取種子結點seed，把seed加入到S0中。算法的偽代碼如算法1（應用于非加權網(wǎng)絡）所示。

算法1：

1.3 擴展的LTA算法

LTA算法對α值較敏感，若要得到真實的社區(qū)劃分，需設定恰當?shù)摩林?。把算法擴展到有權無向圖中，使算法的應用范圍更廣。

擴展后算法的主要目的是尋找在加權網(wǎng)絡中的緊密環(huán)路以及各個社區(qū)的核結點。其中計算環(huán)路緊密性包括兩方面：

式（1）與式（2）分別表示加權圖環(huán)路緊密值和環(huán)路周長。對Cfk，pk限制條件亦改為兩方面：

特別地，當圖中邊的權重都為1（無權無向圖）時，Cfk＝pk。

根據(jù)以上內(nèi)容對LTA算法進行擴展，如算法2（應用于加權網(wǎng)絡）所示。

算法2：

此修改使得LTA不能找到所有環(huán)路，為找到所有環(huán)路，可采用多次LTA，對每次LTA得到的結果進行合并，亦可達到很好的效果。例如洪泛得到的兩個核集分別用X，Y 表示。X中含有個 核，Y 中 含 有個 核。則 對 （?i，?j）combine（Xi，Yj）。用cooccuri，j來表示核Xi和核Yj之間共現(xiàn)的結點數(shù)，若或則執(zhí)行合并Xi和Yj。若Xi和Yj未能執(zhí)行合并操作，則將Xi∩Yj中結點社區(qū)歸屬均置為空，在1.1節(jié)步驟六中作為未被加入到核結構的結點做算法后處理。

1.4 算法后處理

通過LTA算法計算得到C，將C中每個核作為一個社區(qū)，而C并不包含圖G中所有的結點，會有一些結點本身就不在環(huán)路中（如該結點的度為1），此時要對LTA算法運行的結果進行后處理。處理辦法是計算各社區(qū)中包含該結點鄰居數(shù)最多的社區(qū)，并將其作為其本身的社區(qū)歸屬，見算法3（LTA的后處理算法）。

算法3：

1.5 算法效率分析

算法利用寬度優(yōu)先遍歷策略遍歷圖中每一條邊，故時間復雜度為O（m）；算法在檢測到某結點存在于環(huán)路中時，計算環(huán)路周長以及Cf值的時間復雜度為O（αnlog（n））；故總體上算法的時間復雜度為：O（m＋αnlog（n）），對于稀疏網(wǎng)絡為：O（αnlog（n））。

2 實驗與評估

論文中實驗設備為個人PC，中央處理器為Intel（R）Core（TM）2Duo CPU E8400 ＠3.00GHz 2.99GHz，內(nèi)存為 4.00GB（3.46GB usable），操作系統(tǒng)為 Windows 732b。所用編程語言是Matlab。

2.1 人工合成網(wǎng)絡

為了評估算法的有效性，論文利用文獻［22］提出的Lancichinetti model基準數(shù)據(jù)模型作為數(shù)據(jù)生成器，該模型提供了豐富的網(wǎng)絡屬性參數(shù)設置，包括最大度，平均度，度分布，網(wǎng)絡社區(qū)最大規(guī)模，網(wǎng)絡社區(qū)最小規(guī)模，網(wǎng)絡社區(qū)重疊比例，結點個數(shù)，網(wǎng)絡社區(qū)多重度分布和網(wǎng)絡社區(qū)多重規(guī)模分布的設置。論文采用normalized mutual information（NMI）對算法挖掘社區(qū)的精度進行評估。

采用Lancichinetti model共生成3組數(shù)據(jù)，皆為無權無向圖。第1組數(shù)據(jù)用來分析環(huán)路結點個數(shù)閾值α對社區(qū)挖掘效果的影響。第2組數(shù)據(jù)用來測試算法挖掘網(wǎng)絡社區(qū)的精度。第3組數(shù)據(jù)用來測試算法挖掘網(wǎng)絡的效率。

（1）第1組網(wǎng)絡數(shù)據(jù)。設置結點個數(shù)n為128，社區(qū)最小規(guī)模Cmin為10（網(wǎng)絡社區(qū)規(guī)模指其中包含的網(wǎng)絡結點數(shù)目），網(wǎng)絡最大規(guī)模Cmax為50，網(wǎng)絡結點最大度dmax為20，網(wǎng)絡結點平均度davg設置為4到13，社區(qū)間重疊結點比例μ設置為0.05。網(wǎng)絡結點度分布指數(shù)τ1設置為－1，網(wǎng)絡社區(qū)規(guī)模分布指數(shù)τ2設置為－1。共10小組不同的設置，且根據(jù)每小組的數(shù)據(jù)設置，重復生成10個網(wǎng)絡，共100個網(wǎng)絡。

（2）第2組網(wǎng)絡數(shù)據(jù)。設置n為128，Cmin為50，Cmax為70，dmax為20，davg為15，τ1為－1，τ2為－1，μ為從0.05到0.5共10小組不同的設置。特別地，當μ設置為0時，表示社區(qū)間沒有邊連接，相當于各個社區(qū)是獨立的連通子圖，其挖掘精準度應為1。且根據(jù)每小組的數(shù)據(jù)設置重復生成10個網(wǎng)絡，共100個網(wǎng)絡。

③第3組網(wǎng)絡數(shù)據(jù)。n為從500到5000，Cmin為20，Cmax為100，dmax為20，davg設為15，τ1為－1，τ2為－1，μ為0.05，共10小組不同的數(shù)據(jù)。特別地，當n設置為0時，表示網(wǎng)絡沒有結點，則算法運行時間應為0s。

LTA算法中主要的參數(shù)為α和β，鑒于Lancichinetti model未提供生成加權人工數(shù)據(jù)的功能，實驗只對α做分析。試驗中，α分別取3到9共7個值?；鶞示W(wǎng)絡平均度davg為4到13，隨著davg的增加，網(wǎng)絡稠密度增加，則理論上社區(qū)間連接更加緊密，若要正確挖掘網(wǎng)絡中的社區(qū)，則對α值的要求應愈加嚴格。如圖1所示。算法在davg分別取4，5和α取3到6時，算法挖掘社區(qū)的精度均能達到90%以上，隨著davg的增大，網(wǎng)絡稠密度增加，社區(qū)挖掘的高精度對α的要求越來越苛刻。所幸的是，在圖1中可以看到當α＝3時，能從容面對davg在所有取值下的人工網(wǎng)絡。此結論也從另一方面說明同處于α＝3的緊密環(huán)路的結點在很大程度上處于同一網(wǎng)絡社區(qū)。

圖1 不同α取值情況下的NMI變化情況Fig.1 NMI variations in terms ofα

圖2 不同網(wǎng)絡對應的NMI變化情況Fig.2 NMI variations in terms of different networks

利用第2組數(shù)據(jù)進行實驗得到的結果如圖2所示。圖2中y軸表示每小組網(wǎng)絡執(zhí)行LTA結果的NMI精度值，x軸表示每小組網(wǎng)絡對應的μ值。圖中紅色曲線表示10組網(wǎng)絡執(zhí)行結果NMI精度平均值曲線。從圖2中可知，當μ為0、0.05和0.1時算法挖掘精度接近為1，隨著μ值的增大，網(wǎng)絡社區(qū)結構越來越不明顯，挖掘精度也隨之下降。算法較適合社區(qū)間連接稀疏的網(wǎng)絡。

為了更好地對算法的執(zhí)行效率進行分析，現(xiàn)對結點數(shù)目從500到5000的網(wǎng)絡逐一測試，所得結果如圖3所示。

圖3 LTA算法運行時間圖Fig.3 Running time of the LTA

2.2 真實基準網(wǎng)絡數(shù)據(jù)集

為了進一步驗證算法的可行性，算法使用無權無向圖Dolphin網(wǎng)絡［23］對LTA進行實驗。另采用Karate加權無向網(wǎng)絡［24］對擴展LTA進行實驗。

2.2.1 Dolphin網(wǎng)絡

圖4中所示的紅色結點和藍色結點分別表示LTA算法找到的兩個核，白色結點表示未加入核的結點。分析發(fā)現(xiàn)結點dn63在環(huán)內(nèi)，但未被加入到核中，這是因為其處于兩社區(qū)邊緣區(qū)域，如前文分析，這種情況的出現(xiàn)對社區(qū)的劃分有促進作用，更有助于準確進行社區(qū)挖掘。對圖4中填充色為白色的結點進行后處理，依據(jù)算法GetGroup對圖4中結果后處理所得結果如圖5所示。此實驗結果完全符合Dolphin網(wǎng)絡的實際社區(qū)劃分情況。

圖4 Dolphin網(wǎng)絡的核結構圖Fig.4 The cores structure of the Dolphin network

圖5 Dolphin網(wǎng)絡的社區(qū)結構圖Fig.5 The communities structure of the Dolphin network

2.2.2 Karate網(wǎng)絡

為了驗證LTA對加權圖擴展算法的可行性，用加權Karate網(wǎng)絡作為測試數(shù)據(jù)。實驗前的鄰接矩陣和結構圖分別如圖6和圖7所示，其中圖6中X軸和Y軸表示對應結點的編號，藍色點表示對應結點之間的邊。

執(zhí)行算法LTA，得到網(wǎng)絡核結構對應的鄰接矩陣和結構圖分別如圖8和圖9所示。圖8中紅色（藍色）正方形內(nèi)中的藍色點表示得到的一個核結構所包含的邊集，稱為紅色（藍色）核。圖9所示為所得兩個核的結構圖，其中未加入核的結點未在圖中繪出。

依據(jù)算法GetGroup進行后處理所得結果的鄰接矩陣和結構圖分別如圖10和圖11所示。圖10中紅色（藍色）正方形中所含邊集對應圖8，圖9中的紅色（藍色）核。圖11表示對應的紅色社區(qū)與藍色社區(qū)結構圖。所得結果與真實社區(qū)劃分完全相同。

圖6 Karate網(wǎng)絡的鄰接矩陣圖Fig.6 The adjacency matrix of Karate network

對于Karate網(wǎng)絡，其結構圖利用Netdraw工具畫出，且此工具包含對圖的faction分析。其中faction分析包含兩種模式：Quality模式和Speed模式。利用faction分析中的Quality模式分析得到的圖與論文中LTA算法實驗得到的結果完全相同。而在Speed模式下，結點16被分到圖中的紅色社區(qū)。仔細研究結點16發(fā)現(xiàn)，其處于社區(qū)的邊緣，故將其劃分到任一社區(qū)皆可，其效果如圖12所示。

圖7 Karate網(wǎng)絡的結構圖Fig.7 The structure of the Karate club network

圖8 Karate網(wǎng)絡的核鄰接矩陣圖Fig.8 The adjacency matrix of the cores of Karate

圖9 Karate網(wǎng)絡的核結構圖Fig.9 The cores structure of the Karate club network

圖10 Karate網(wǎng)絡的社區(qū)鄰接矩陣圖Fig.10 The adjacency matrix of Karate network

圖11 Karate網(wǎng)絡的核結構圖Fig.11 The communities structure of the Karate club network

圖12 利用Netdraw工具對Karate網(wǎng)絡的分析結果Fig.12 The results of using Netdraw to analyze the Karate club network

3 結束語

針對社區(qū)挖掘問題，研究了網(wǎng)絡中環(huán)路緊密度與社區(qū)結構的關系，進而提出了基于環(huán)路緊密度的社區(qū)挖掘算法LTA。LTA算法的一個主要優(yōu)點是不需事先指定社區(qū)個數(shù)K。實驗結果表明：LTA算法挖掘精度較高，且算法穩(wěn)定性較好；同時，還驗證了處于同一緊密環(huán)路中的兩個結點處于同一社區(qū)的概率較大，處于不同社區(qū)的兩個結點處于不同環(huán)路的概率較大這一思想；此外發(fā)現(xiàn)當LTA算法將參數(shù)α設置為3時，處于同一緊密環(huán)路中的結點會以極大概率出現(xiàn)在同一社區(qū)中。

［1］楊博，劉大有，Liu Ji－ming，等.復雜網(wǎng)絡聚類方法［J］.軟件學報，2009，20（1）：54－66.Yang Bo，Liu Da－you，Liu Ji－ming，et al.Complex network clustering algorithms［J］.Journal of Software，2009，20（1）：54－66.

［2］Kleinberg J M.Authoritative sources in a hyperlinked environment［J］.Journal of the ACM （JACM），1999，46：604－632.

［3］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences，2002，99：7821.

［4］Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2004，101：2658.

［5］Tyler J R，Wilkinson D M，Huberman B A.Email as spectroscopy：Automated discovery of community structure within organizations［J］.The Information Society，2005，21（2）：143－153.

［6］Wu F，Huberman B A.Finding communities in linear time：aphysics approach［J］.The European Physical Journal B－Condensed Matter and Complex Systems，2004，38：331－338.

［7］Yang B，Cheung W K，Liu J.Community mining from signed social networks［J］.IEEE Transactions on.Knowledge and Data Engineering，2007，19：1333－1348.

［8］Pothen A，Simon H D，Liou K P.Partitioning sparse matrices with eigenvectors of graphs［J］.Siam J Matrix Anal Applic，1990，11：430－452.

［9］Fiedler M.Algebraic connectivity of graphs［J］.Czech－oslovak Mathematical Journal，1973，23：298－305.

［10］Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs［J］.Bell System Technical Journal，1970，49：291－307.

［11］Newman MEJ.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69：066133.

［12］Guimera R，Amaral L A N.Functional cartography of complex metabolic networks［J］.Nature 2005，433：895－900.

［13］Xing E P，Jordan M I，Russell S.A Generalized Mean Field Algorithm for Variational Inference in Exponential Families.Uncertinty in AI 2003.

［14］Fu W，Song L，Xing E P.Dynamic mixed membership blockmodel for evolving networks［C］∥In Proceedings of the 26th Annual International Conference on Machine learning，2009：329－336.

［15］Airoldi E M，Blei D M，F(xiàn)ienberg S E，et al.Mixed membership stochastic blockmodels［J］.The Journal of Machine Learning Research，2008，9：1981－2014.

［16］Wang Y J，Wong G Y.Stochastic blockmodels for directed graphs［J］.Journal of the American Statistical Association，1987：8－19.

［17］Flake G W，Lawrence S，Giles C L，et al.Self－organization and identification of web communities［J］.Computer，2002；35：66－70.

［18］Hofman J M，Wiggins C H.Bayesian approach to network modularity［J］.Physical Review Letters，2008，100：258701.

［19］Holland P W，Leinhardt S.Local structure in social networks［J］.Sociological methodology 1976，7：1－45.

［20］Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69（2）：026113.

［21］Guimera R，Sales－Pardo M，Amaral L A N.Modularity from fluctuations in random graphs and complex networks［J］.Physical Review E，2004，70：025101.

［22］Lancichinetti A，F(xiàn)ortunato S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］.Physical Review E，2009，80：016118.

［23］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long－lasting associations［J］.Behavioral Ecology and Sociobiology，2003，54：396－405.

［24］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977：452－473.