一種基于局部模塊度的增量式動態(tài)社區(qū)發(fā)現(xiàn)算法

荊笑鵬

摘要：為更好地適應(yīng)大規(guī)模社會網(wǎng)絡(luò)數(shù)據(jù)的應(yīng)用要求，提出一種基于局部模塊度的增量式動態(tài)社區(qū)發(fā)現(xiàn)算法。把對起始時間的社會網(wǎng)絡(luò)執(zhí)行靜態(tài)社區(qū)發(fā)現(xiàn)獲得的社區(qū)結(jié)構(gòu)和局部模塊度作為增量分析的基礎(chǔ)，把局部模塊度作為優(yōu)化的條件，使用四種原子操作，逐步演化社區(qū)結(jié)構(gòu)。使用社區(qū)結(jié)構(gòu)的局部信息，提高了算法的運行效率。避免了設(shè)定參數(shù)的條件，提高了算法的適應(yīng)性。實驗結(jié)果表明，該算法具有一定的實際應(yīng)用價值。

關(guān)鍵詞：局部模塊度；增量分析；動態(tài)社區(qū)發(fā)現(xiàn)；社區(qū)演化

中圖分類號：TP183 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）06-0191-04

1 概述

隨著社會網(wǎng)絡(luò)應(yīng)用和模型的出現(xiàn)和快速發(fā)展，例如：病毒式營銷[1]、推薦系統(tǒng)[2]、影響力擴散[3]等方面，社會網(wǎng)絡(luò)分析在這些領(lǐng)域中變得越來越重要，吸引了大量的專家學(xué)者進行研究。通常，社會網(wǎng)絡(luò)數(shù)據(jù)是代表著系統(tǒng)內(nèi)成員之間關(guān)系的一種圖結(jié)構(gòu)，其中節(jié)點代表個人，邊代表人與人之間的相互作用。例如：公司內(nèi)部職員之間的交流，學(xué)術(shù)論文之間的引用和微博用戶之間的關(guān)注等。社會網(wǎng)絡(luò)分析的目的在于從低層次的關(guān)系數(shù)據(jù)中挖掘高層次的用于描述系統(tǒng)結(jié)構(gòu)的關(guān)系模式[4]。

在過去，大部分分析社會網(wǎng)絡(luò)的方法是用于計算社會網(wǎng)絡(luò)的靜態(tài)信息，沒有考慮社會網(wǎng)絡(luò)成員之間相互作用的時間因素。但是，社會網(wǎng)絡(luò)的結(jié)構(gòu)是隨時間變化的，成員之間的互動關(guān)系同樣隨時間在變化。例如，在新浪微博中，不斷地有新用戶注冊，也有老用戶離開，用戶之間互動的頻率也在變化。因而，對動態(tài)社會網(wǎng)絡(luò)分析的研究也越來越多地被提出[5]。動態(tài)社區(qū)發(fā)現(xiàn)是在空間發(fā)現(xiàn)隱含社區(qū)結(jié)構(gòu)的基礎(chǔ)上，增加時間因素，以發(fā)現(xiàn)不同時間點或時間窗口的社區(qū)信息和社區(qū)變化情況[6]。

為了更好地適應(yīng)大規(guī)模數(shù)據(jù)集，提高發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)中社區(qū)的時間效率，同時克服參數(shù)預(yù)設(shè)的條件，本文提出一種動態(tài)社區(qū)發(fā)現(xiàn)算法。首先使用基于相似度的靜態(tài)社區(qū)發(fā)現(xiàn)算法得到開始時間的初始社區(qū)結(jié)構(gòu)，作為增量分析的基礎(chǔ)。再以初始社區(qū)結(jié)構(gòu)為基礎(chǔ)，根據(jù)不同時間片網(wǎng)絡(luò)拓撲的變化，將局部模塊度作為優(yōu)化條件，對動態(tài)社會網(wǎng)絡(luò)進行增量分析。本文是基于以下事實：大部分社區(qū)通常隨著時間的推移逐漸演變，而不會突然出現(xiàn)或消失[7]。

本文第2節(jié)介紹一些典型的動態(tài)社區(qū)發(fā)現(xiàn)算法，第3節(jié)解釋本文算法的細節(jié)，第4節(jié)對本文算法的有效性進行實驗驗證，第5節(jié)對全文進行總結(jié)和展望。

2 相關(guān)工作

動態(tài)社會網(wǎng)絡(luò)通常被認為是一系列網(wǎng)絡(luò)快照，不同的快照之間具有一定時間間隔，每一個快照是網(wǎng)絡(luò)的一個靜態(tài)圖。因而，對動態(tài)變化的社會網(wǎng)絡(luò)的每一個快照使用靜態(tài)的分析方法，然后在對得到的社區(qū)的演變進行表征就是很自然的思路。

Greene等[8]提出一種在動態(tài)社會網(wǎng)絡(luò)中跟蹤社區(qū)演化的模型，將社區(qū)表征為一系列重要的演化事件，使用社區(qū)匹配策略識別和跟蹤動態(tài)社區(qū)。

Palla等[9]使用CPM算法獲取每段時間的社區(qū)結(jié)構(gòu)，可以得到具有較高連通性的節(jié)點的子集，對比和計算每個時間段得到的社區(qū)結(jié)構(gòu)，實現(xiàn)對社區(qū)演進的分析。

增量動態(tài)社區(qū)發(fā)現(xiàn)算法通過對當(dāng)前已知的社區(qū)結(jié)構(gòu)更新，代替對每一個網(wǎng)絡(luò)快照進行計算，從而保持良好的社區(qū)結(jié)構(gòu)[10]。這種策略能夠有效降低時間復(fù)雜度，能夠適用于大規(guī)模的社會網(wǎng)絡(luò)數(shù)據(jù)。

Yang等[11]根據(jù)物理系統(tǒng)提出一種基于網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)原理的模型。在模型中，整個網(wǎng)絡(luò)作為一個四維空間，將網(wǎng)絡(luò)中邊和點的屬性作為四維空間中的物理屬性，依照萬有引力定律的思想逐輪進行增量分析，得到最終的社區(qū)劃分結(jié)果。

單波等[12]使用社會網(wǎng)絡(luò)的歷史信息和當(dāng)前的拓撲結(jié)構(gòu)來確定當(dāng)前的社區(qū)結(jié)構(gòu)，使用設(shè)定的參數(shù)控制增量相關(guān)的定點是否改變其歸屬的社區(qū)。這種方法提高了時間效率，但沒有考慮社區(qū)數(shù)目和節(jié)點數(shù)目的變化。

3 基于局部模塊度的增量式動態(tài)社區(qū)發(fā)現(xiàn)

3.1 相關(guān)概念

3.1.1 動態(tài)社會網(wǎng)絡(luò)

圖G表示為一個二元組 G（V， E），其中V表示節(jié)點的集合，E表示邊的集合。動態(tài)社會網(wǎng)絡(luò)是指圖G中的節(jié)點V或者邊E隨時間的變化而改變的，可以用序列[G1，G2，...，Gn]表示。

令[Ci1，Ci2，...，Cim]表示[Gi]的社區(qū)劃分結(jié)果，即[Ci1?Ci2?...?Cim=Gi]，其中m是社區(qū)的數(shù)量。

3.1.2 模塊度[13]

模塊度是一種定量手段，定義了發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是隨機產(chǎn)生的可能性。設(shè)一個網(wǎng)絡(luò)被劃分為k個社區(qū)，定義[k×k]的對稱矩陣e，其元素[eij]表示頂點分別在社區(qū)i和社區(qū)j中的邊。設(shè)[ai=jeij]，表示與社區(qū)i中所有頂點相連的邊，則模塊度的定義如下：

5 結(jié)束語

本文提出的基于局部模塊度的增量式動態(tài)社區(qū)發(fā)現(xiàn)算法，在現(xiàn)實網(wǎng)絡(luò)中具有一定有效性，能夠應(yīng)用于節(jié)點數(shù)量較多的社會網(wǎng)絡(luò)。該算法首先對起始時間的社會網(wǎng)絡(luò)執(zhí)行靜態(tài)的社區(qū)發(fā)現(xiàn)，并計算當(dāng)前時間社區(qū)結(jié)構(gòu)的局部模塊度，將起始時間的社區(qū)結(jié)構(gòu)和局部模塊度作為下一步算法的基礎(chǔ)，根據(jù)4種不同的原子操作，以局部相似度作為優(yōu)化的目標(biāo)，克服了需要預(yù)設(shè)參數(shù)的條件，選擇相應(yīng)的算法計算社區(qū)結(jié)構(gòu)的演化，最后可以得到結(jié)束時間的社區(qū)結(jié)構(gòu)和社區(qū)結(jié)構(gòu)的演化過程。在每一次的操作中，只計算關(guān)于社區(qū)的局部信息，提高了算法的運行效率和準(zhǔn)確率。通過對比實驗的結(jié)果也能夠證明本文的基于局部模塊度的動態(tài)社區(qū)發(fā)現(xiàn)算法在實際社會網(wǎng)絡(luò)中的有效性。本文算法目前只局限于單機運行，如何將此算法在多臺主機上并行運行是接下來的研究工作。

參考文獻：

[1] Domingos P. Mining social networks for viral marketing[J]. Journal of Retailing & Consumer Services， 2005.

[2] Bao J， Zheng Y， Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[J]. Gis， 2012：199-208.

[3] Kempe D， Kleinberg J， Tardos， &#. Maximizing the spread of influence through a social network[C]// Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2003：137--146.

[4] Seary A J， Richards W D. Spectral methods for analyzing and visualizing networks： an introduction[J]. Workshop Summary & Papers， 2000：209--228.

[5] Kumar R， Novak J， Raghavan P， et al. On the Bursty Evolution of Blogspace[J]. World Wide Web-internet & Web Information Systems， 2005， volume 8（2）：159-178（20）.

[6] 王莉， 程學(xué)旗. 在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計算機學(xué)報， 2015， 38（2）：219-237.

[7] Tantipathananandh C， Berger-Wolf T， Kempe D. A framework for community identification in dynamic social networks[C]// Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2007：717-726.

[8] Greene D， Doyle D， Cunningham P. Tracking the Evolution of Communities in Dynamic Social Networks[C]// Advances in Social Networks Analysis and Mining （ASONAM）， 2010 International Conference on. IEEE， 2010：176-183.

[9] Palla G， Barabási A L， Vicsek T. Quantifying social group evolution.[J]. Nature， 2007， 446（446）：664-7.

[10] Aynaud T， Fleury E， Guillaume J L， et al. Communities in Evolving Networks： Definitions， Detection， and Analysis Techniques[J]. Modeling and Simulation in Science， Engineering and Technology， 2013：159-200.

[11] Yang B， Liu D Y. Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network[J]. Journal of Computer Science & Technology， 2006， 21（3）：393-400.

[12] 單波， 姜守旭， 張碩，等. IC：動態(tài)社會關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的增量識別算法[C]// NDBC2009第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議. 2009.

[13] Newman M E J， Girvan M. Finding and evaluating community structure in networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2004， 69（2 Pt 2）：026113-026113.

[14] Clauset A. Finding local community structure in networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2005， 72（2Pt2）：254-271.

[15] Vinh N X， Epps J， Bailey J. Information Theoretic Measures for Clusterings Comparison： Variants， Properties， Normalization and Correction for Chance[J]. Journal of Machine Learning Research， 2010， 11（1）：2837-2854.

[16] 王慧芳， 黃林鵬， 俞晟. 一種增量式的社區(qū)發(fā)現(xiàn)算法研究[J]. 計算機仿真， 2008， 25（1）：149-152.