基于鄰域信息的社區發現方法

韓路，張海

(西北大學數學學院，陜西 西安　710127)

基于鄰域信息的社區發現方法

韓路，張海

(西北大學數學學院，陜西 西安710127)

考慮含有節點鄰域信息的新模塊度函數的社區發現方法和最優分組下標度參數的選擇問題，通過譜松弛方法求解模塊度函數的最大化問題，最終利用新算法快速求解，并通過真實網絡數據驗證算法能更好的發現社區.

模塊度函數；鄰域信息；譜方法

1　前言

復雜網絡作為一種數據關系的表達方法，成為目前機器學習領域的熱點之一.其中，網絡中的節點表示研究問題的對象，邊表示對象和對象之間的一種屬性關系.在現實世界中，復雜網絡常分為以下幾種類型，如技術網絡，社交網絡，信息網絡和生物網絡等[1-2].社區描述網絡的結構，它是指在一個較大的網絡中，網絡的結構特征通過節點位于不同組表現出來.比如組內邊的聯接比較緊密，組間邊的聯接比較稀疏.如何有效發現網絡中的社區，對于理解網絡功能和結構有著重要意義.例如，在一個學術關系網絡中，節點表示作者，邊表示每兩位作者之間是否有合作發表論文.此網絡中的社區可能由一些研究方向相同或相近的作者組成，形成不同特征的社區.因此，如何發現此類社區并預測網絡中某一位作者所屬的社區，對于研究網絡的行為具有實際意義.近年來，社區發現是網絡研究的熱點之一[3-4].

Newman和Girvan[5]第一次提出模塊度函數Q用于社區發現.盡管模塊度函數自提出后得到廣泛應用，發展了很多以該函數為目標函數的新算法.如Newman[6]提出的一種貪婪策略下的快速聚合算法，White和Smyth[7]提出的一種譜聚類方法等.但是該函數Q并沒有利用節點的鄰域信息，對于很多有節點信息的真實網絡，則該模塊度函數Q并不能很好地度量該網絡的社區結構.因此，研究結合節點信息的社區發現方法有著重要意義.而文獻[8]利用了節點的鄰域信息，擴展并提出了新的模塊度函數QDist，它度量了節點的鄰域信息，QDist不但適合節點有額外信息的網絡，而且可以得到不同標度下的社區結構.雖然該文章給出了在特定標度下的最優分組結果，但是并沒有給出如何選取此標度的方法.通常地，基于模塊度函數方法發現社區有許多典型的算法，如何利用并推廣現有算法到結合了節點信息的新模塊度函數發現社區，同時如何選取最優分組時的標度是本文關注的問題.

譜分析方法早在20世紀70、80年代就已經被提出[9]，該方法后來被發展成許多不同的譜聚類方法[10].其基本思想是通過對鄰接矩陣形成的拉普拉斯矩陣或者標準拉普拉斯矩陣的特征值與特征向量進行分析，從而進行網絡的社區發現.而Newman[11-12]將譜分析方法與模塊度函數最大化相結合，提出一種譜方法并應用于社區發現.

本文研究將Newman所提出的譜方法推廣到新的模塊度，同時解決新模塊度函數最優分組時標度參數的選擇問題.通過將最大化QDist問題轉化為譜松弛問題，進而提出一種二分的譜算法，同時給出了最優分組時標度的選取方法.最后，通過在三個真實網絡數據上進行實驗，結果表明該算法能夠有效的給出實際網絡二分的社區結構.

2　模塊度函數 QDist最大化及算法

一個網絡通常包括兩組信息，節點個數n和鄰接矩陣A=(Aij)1≤i，j≤n.其中，Aij取值為1或者0.當Aij=1時，表示節點i和j之間有邊連接，當Aij=0時，表示節點i和j之間沒有邊連接.模塊度函數的定義如下：

上述三種距離分別描述兩節點之間的聯接強度，不同距離的選擇包含網絡中不同的結構信息.例如，Jaccard距離[13-14]包含網絡的節點的鄰域信息，歐式距離包含網絡的節點的屬性信息，最短距離包含網絡的拓撲信息.

一般地，對于一個網絡，當知道網絡的真實分組時，可以計算QDist的值，并且QDist的值越大，社區結構越明顯.本文僅考慮無向網絡的兩分社區情況，使得QDist最大化.對于節點i，若si的值為1，則表示節點i屬于組1，若si的值為?1，則表示節點i屬于組2，那么δ(li，lj)可以化為(sisj+1)/2.則

3　實驗

本節通過對真實數據Zachary空手道俱樂部網絡，海豚社交網絡和美國政治書籍網絡試驗說明算法的有效性.本實驗中的相似距離 dij都采用 Jaccard距離.即這里Γ(i)表示節點i的鄰居節點.

實驗一本實驗通過對 Zachary空手道俱樂部網絡[15]進行實驗，該網絡是 Zachary 在1970年代初，研究了一所美國大學的空手道俱樂部成員的社交網絡.網絡中的節點代表34位俱樂部成員，邊代表每個成員之間的友誼關系.但是由于在是否漲學費問題上的分歧，俱樂部主席(節點34)和教練(節點1)的之間發生了沖突，俱樂部自發形成了支持管理者和教練的兩組成員.不同的分組按紅色和藍色區分.現在的問題是在只知道鄰接矩陣的情況下，能否正確檢測出空手道俱樂部網絡真實的社區結構？本實驗參數ε=10?3.

實驗分析圖1(b)表示空手道俱樂部網絡在利用本文算法得出分組的QLaplace值的情況，當σ∈(0，0.20)和σ=1.04時，網絡的分組結果如圖1(a)所示，由圖1(b)可知，此時網絡的分組的QLaplace值最高(忽略了0值，因為此時的分組是全部節點分成一組)，和真實分組比較，除了節點3與真實網絡分組不同之外，其他節點的分組完全相同.

圖1　空手道俱樂部網絡

實驗二本實驗通過對海豚社交網絡[16-17]進行實驗，該網絡是Lusseau在神奇灣觀察62只海豚后建立的.網絡中的節點代表62只海豚，如果兩只海豚之間有邊，則表示這兩只海豚被觀察在一起次數多于期望的次數，代表海豚之間某種親密關系.但是由于一只海豚的暫時離開導致海豚群體分成了20只和 42只兩個組.不同的分組按紅色和藍色區分.本實驗參數ε=10?3.

實驗分析圖 2(c)表示海豚社交網絡在利用本文算法得出分組的 QLaplace值的情況. 當σ∈(0，0.34)和σ∈(0.72，+∞)時，網絡的分組結果如圖2(a)所示.和真實分組比較發現，除了節點31和節點40與真實網絡分組不同之外，其他節點的分組完全相同.當σ=0.4時，網絡的分組情況如圖2(b)所示，由圖2(c)可知，此時網絡分組的QLaplace值最高(忽略了0值，因為此時的分組是全部節點分成一組)，和真實分組比較發現，只有節點40和真實網絡分組不同，此時的分組結果比其他QLaplace值的結果都要好.

圖2　海豚社交網絡

實驗三本實驗通過對美國政治書籍網絡進行實驗.該網絡節點表示在亞馬遜網站銷售的105本關于美國政治的書籍，邊表示兩本書經常被同一消費者購買.該書籍被Mark Newman劃分為關于自由黨和保守黨兩種書籍，還有少部分書籍被劃分為中間派書籍.不同的分組按紅色和藍色區分.本實驗參數ε=10?2.

實驗分析圖3(c)表示美國政治書籍網絡在利用本文算法得出分組的QLaplace值的情況. 當σ∈(0，0.32)和σ∈(1.34，+∞)時，美國政治書籍網絡的分組結果如圖3(a)所示.該結果將節點59和節點78錯分.但是當σ∈(0.88，1.06)時，該網絡分組結果如圖3(b)所示.由圖3(c)可知，此時網絡分組的QLaplace值最高，該結果同圖3(a)的結果相比較，節點53的分組結果不同.此時把節點53錯分.節點53的5個鄰居節點中有3個被分為自由黨，2個被分為保守黨，所以將節點53錯分了.

4　結論

本文研究了網絡的社區結構問題，通過將包含鄰域信息的模塊度函數QDist的最大化問題轉化為譜松弛問題，同時提出一種二分的譜算法進行求解.將Newman的二分譜方法推廣到新模塊度函數模型上，同時解決的新模塊度函數下網絡最優分組時的標度選取問題.最后，通過實驗證明了新算法可以有效的辨識網絡的二分社區結構.

[1]Newman M E J.Networks：An Introduction[M].New York：Oxford University Press，2010.

[2]Albert R，Barabsi A.Statistical mechanics of complex networks[J].Reviews of Modern Physics，2002，74：47-97.

[3]Newman M E J.The structure and function of complex networks[J].SIAM Review，2003，45：167-256.

[4]Newman M E J，Leicht E.Mixture models and exploratory analysis in networks[J].Proceedings of the National Academy of Sciences，2007，104：9564-9569.

[5]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Phys.Rev.E.，2004，69：026113.

[6]Newman M E J.Fast algorithm for detecting community structure in networks[J].Phys.Rev.E.，2004，69：066133.

[7]White S，Smyth P.A spectral clustering approach to finding communities in graphs[J].In：Kamath C，Goodman A，eds.Proc.of the 5th SIAM Int Conf.on Data Mining.Philadelphia：SIAM，2005，76-84.

[8]Liu X，Murara T，Wakita K.Extending modularity by capturing the similarity attraction feature in the null model[J].2013，arXiv：1210.4007 v3[cs.SI].

[9]Fiedler M.Algebraic connectivity of graphs[J].Czech Math J.，1973，23(98)：298-305.

[10]Von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17：395-416.

[11]Newman M E J.Modularity and community structure in networks[J].Proc.Natl.Acad.Sci.USA，2006，103(23)：8577-8582.

[12]Newman M E J.Spectral methods for network community detection and graph partitioning[J].Phys.Rev. E.，2013，88：042822.

[13]Levandowsky M，Winter D.Distance between sets[J].Nature，1971，234：34-35.

[14]Jaccard P.Etude comparative de la distribution florale dans une portion des alpes et des jura[J].Bull.Soc. Vaudoise Sci.Nat.，1901，37：547-579.

[15]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research，1977，33：452-473.

[16]Lusseau D.The emergent properties of a dolphin social network[J].Proceedings of the Royal Society of London Series B，2003，270：S186-S188.

[17]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.

Community detection based on neighborhood information

Han Lu，Zhang Hai
(College of Mathematics，Northwest University，Xi′an710127，China)

Community detection based on modularity is a widely used method，but it does not use neighborhood information of nodes，then it fails to be a good representation of real-world community structure.A new modularity with neighborhood information could detect the community structure of real-world networks，but it didn’t show parameter selection of the best community division.The paper aimed at the maximization and parameter selection of the new modularity with neighborhood information，then reformulate the maximization as a spectral relaxation issue.Finally，we solve the problem by a new bisection spectral algorithm and prove the effectiveness of our algorithm by experimental results.

modularity，neighborhood information，spectral method

O233，TP391.41

A

1008-5513(2015)01-0085-08

10.3969/j.issn.1008-5513.2015.01.010

2014-11-05.

國家自然科學基金(11171272).

韓路(1990-)，碩士生，研究方向：機器學習.

2010 MSC:91D30