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

韓路，張海

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

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

韓路，張海

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

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

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

1　前言

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

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

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

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

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

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

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

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

3　實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

4　結(jié)論

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

國(guó)家自然科學(xué)基金(11171272).

韓路(1990-)，碩士生，研究方向：機(jī)器學(xué)習(xí).

2010 MSC:91D30