韓路，張海

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

基于鄰域信息的社區(qū)發(fā)現(xiàn)方法

韓路，張海

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

考慮含有節(jié)點鄰域信息的新模塊度函數(shù)的社區(qū)發(fā)現(xiàn)方法和最優(yōu)分組下標度參數(shù)的選擇問題，通過譜松弛方法求解模塊度函數(shù)的最大化問題，最終利用新算法快速求解，并通過真實網(wǎng)絡數(shù)據(jù)驗證算法能更好的發(fā)現(xiàn)社區(qū).

模塊度函數(shù)；鄰域信息；譜方法

1　前言

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

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

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

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

2　模塊度函數(shù) QDist最大化及算法

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

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

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

3　實驗

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

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

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

圖1　空手道俱樂部網(wǎng)絡

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

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

圖2　海豚社交網(wǎng)絡

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

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

4　結(jié)論

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

[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