改進(jìn)的動(dòng)態(tài)圖社區(qū)演化關(guān)系分析方法

羅香玉 ，李嘉楠 ，羅曉霞 ，王 佳

（1. 西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安710054； 2. 西安交通大學(xué)電子與信息工程學(xué)部，西安710049）

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和用戶(hù)對(duì)網(wǎng)絡(luò)的訪問(wèn)增加，人們的社會(huì)關(guān)系從現(xiàn)實(shí)世界映射到了虛擬網(wǎng)絡(luò)世界。許多社會(huì)關(guān)系和生物系統(tǒng)都可以表示為復(fù)雜網(wǎng)絡(luò)［1］，其中節(jié)點(diǎn)表示實(shí)體，邊用來(lái)模擬實(shí)體之間的交互［2］。復(fù)雜網(wǎng)絡(luò)在各領(lǐng)域廣泛存在，在研究復(fù)雜網(wǎng)絡(luò)的過(guò)程中人們發(fā)現(xiàn)了社區(qū)結(jié)構(gòu)屬性。在社區(qū)結(jié)構(gòu)中，網(wǎng)絡(luò)節(jié)點(diǎn)以一個(gè)組的形式緊密地連接在一起，而組之間的連接特別松散。對(duì)于現(xiàn)實(shí)生活中的社交網(wǎng)絡(luò)來(lái)說(shuō)，網(wǎng)絡(luò)中的成員和成員之間的關(guān)系和社區(qū)結(jié)構(gòu)都會(huì)不斷變化，社區(qū)結(jié)構(gòu)動(dòng)態(tài)特征的分析和預(yù)測(cè)引起了不少研究者的關(guān)注［3-4］。

社區(qū)結(jié)構(gòu)是社交網(wǎng)絡(luò)［5］中一個(gè)十分重要的基礎(chǔ)結(jié)構(gòu)，社區(qū)結(jié)構(gòu)的動(dòng)態(tài)演化對(duì)網(wǎng)絡(luò)的變化有著很大的影響［6］。很多科研機(jī)構(gòu)和研究者在這一領(lǐng)域展開(kāi)了深入的研究。目前有大量的方法來(lái)分析和預(yù)測(cè)動(dòng)態(tài)社區(qū)的演化。在追蹤社區(qū)演化關(guān)系時(shí)，目前的主要方法是對(duì)相鄰時(shí)間片內(nèi)社區(qū)結(jié)構(gòu)的關(guān)系進(jìn)行比較分析。但這類(lèi)方法中存在很多問(wèn)題，如：1）數(shù)據(jù)質(zhì)量會(huì)影響計(jì)算結(jié)果的有效性；2）時(shí)間窗口設(shè)定影響是否能在可接受的計(jì)算復(fù)雜度范圍內(nèi)捕捉全面的社區(qū)演化信息；3）對(duì)社區(qū)質(zhì)量和社區(qū)的演化情況缺乏一個(gè)統(tǒng)一的標(biāo)準(zhǔn)來(lái)評(píng)判；4）網(wǎng)絡(luò)是不斷變化的，分析動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)對(duì)計(jì)算性能帶來(lái)了很大的挑戰(zhàn)［7］；5）社區(qū)演化關(guān)系刻畫(huà)的完備性問(wèn)題。

本文通過(guò)實(shí)驗(yàn)證實(shí)，僅對(duì)相鄰時(shí)間片內(nèi)社區(qū)結(jié)構(gòu)的關(guān)系進(jìn)行分析，無(wú)法完備地刻畫(huà)社區(qū)演化過(guò)程；現(xiàn)有的方法在描述社區(qū)演化過(guò)程中，會(huì)忽視一些不明顯但真實(shí)存在的社區(qū)關(guān)系。針對(duì)這些問(wèn)題，本文提出了一種改進(jìn)的方法，可為描述社區(qū)演化關(guān)系提供更豐富的信息。

1 相關(guān)工作

目前解決追蹤社區(qū)演化關(guān)系的社區(qū)檢測(cè)和匹配方法是將靜態(tài)社區(qū)檢測(cè)方法［8］應(yīng)用于動(dòng)態(tài)案例。這類(lèi)方法也被稱(chēng)為兩階段法，基本思想是獨(dú)立地在每個(gè)時(shí)間片檢測(cè)社區(qū)，然后基于社區(qū)之間的相似性將這些社區(qū)與它相鄰的時(shí)間片中的社區(qū)進(jìn)行比較。這類(lèi)方法旨在通過(guò)動(dòng)態(tài)網(wǎng)絡(luò)生命周期中可能出現(xiàn)的關(guān)鍵事件來(lái)跟蹤社區(qū)的演化［9］。

Hopcroft 等［10］使用靜態(tài)網(wǎng)絡(luò)時(shí)間片跟蹤社區(qū)［11］隨時(shí)間演變，提出了一種使用層次聚類(lèi)來(lái)識(shí)別和跟蹤穩(wěn)定聚類(lèi)的方法。Asur等［12］提出了一種基于匹配方法的簡(jiǎn)單直觀的社區(qū)事件識(shí)別方法，該方法首先應(yīng)用馬爾可夫聚類(lèi)算法［13］來(lái)發(fā)現(xiàn)社區(qū)，然后在連續(xù)時(shí)間片中比較每對(duì)社區(qū)的大小和是否重疊，并確定涉及這些社區(qū)的事件；但是它們并沒(méi)有涵蓋特定社區(qū)生命周期中可能發(fā)生的所有形式的事件。

Greene 等［14］提出了一個(gè)模型，該模型使用靜態(tài)算法跟蹤社區(qū)隨時(shí)間的演化，以檢測(cè)每個(gè)時(shí)間片上的社區(qū)，描述了一個(gè)加權(quán)的二分匹配來(lái)映射社區(qū)，然后用一系列事件來(lái)表征每個(gè)社區(qū)。然而，文章中并沒(méi)有提供明確的公式來(lái)定義事件。模型引入了有效的社區(qū)匹配策略，用于在多個(gè)時(shí)間片中有效地識(shí)別和跟蹤動(dòng)態(tài)社區(qū)。Takaffoli 等［15］提供了一個(gè)基于事件的框架，以在兩個(gè)連續(xù)時(shí)間片中捕捉社區(qū)之間的所有過(guò)渡。

Bródka 等［16］提出了一種社區(qū)進(jìn)化發(fā)現(xiàn)方法，不僅使用社區(qū)成員的對(duì)等來(lái)匹配社區(qū)，還考慮到了節(jié)點(diǎn)的位置，及其在社區(qū)中的重要性，以便識(shí)別連續(xù)時(shí)間片中的社區(qū)演化。這種匹配方式既尊重了社區(qū)成員的數(shù)量，也尊重了社區(qū)成員的重要性。

Sun 等［17］提出了一種輕量級(jí)進(jìn)化事件監(jiān)測(cè)算法來(lái)尋找相鄰時(shí)間片之間的社區(qū)進(jìn)化模式，從統(tǒng)計(jì)學(xué)上來(lái)說(shuō)，這可以顯示整個(gè)網(wǎng)絡(luò)的進(jìn)化趨勢(shì)，應(yīng)用Louvain算法在每個(gè)時(shí)間片中找到社區(qū)，然后，建立了一個(gè)相關(guān)矩陣來(lái)描述時(shí)間步長(zhǎng)t和t + 1中社區(qū)之間相對(duì)于時(shí)間片的關(guān)系，并根據(jù)該矩陣定義了檢測(cè)進(jìn)化事件的規(guī)則。Zhu 等［18］描述了一個(gè)事件重建框架，用于分析社區(qū)結(jié)構(gòu)的動(dòng)態(tài)特征；提出了社區(qū)屬性的概念，并基于社區(qū)屬性的觀點(diǎn)重構(gòu)了Asur等［12］提出的事件框架。

Liu 等［19］提出了一種動(dòng)態(tài)社交網(wǎng)絡(luò)中基于引力關(guān)系和社區(qū)結(jié)構(gòu)的追蹤社區(qū)演化方法，通過(guò)構(gòu)造基本節(jié)點(diǎn)來(lái)初始化社區(qū)，其他節(jié)點(diǎn)迭代搜索劃分到相應(yīng)的社區(qū)，分析社區(qū)進(jìn)化。Wang等［20］提出了一種基于拓?fù)鋭?shì)場(chǎng)中的影響范圍分析，增量更新動(dòng)態(tài)社區(qū)結(jié)構(gòu)，根據(jù)拓?fù)鋭?shì)場(chǎng)中核心節(jié)點(diǎn)的變化來(lái)跟蹤社區(qū)演化事件。徐兵等［21］提出了一種基于關(guān)聯(lián)群演化相似度的社區(qū)追蹤算法，通過(guò)對(duì)社區(qū)、核心成員的相似度進(jìn)行加權(quán)，引入多部圖來(lái)分析社區(qū)演化序列。

目前的研究工作主要針對(duì)連續(xù)相鄰時(shí)間片之間的社區(qū)關(guān)系進(jìn)行分析，忽視了不相鄰時(shí)間片之間社區(qū)的關(guān)系。本文在現(xiàn)有研究的基礎(chǔ)之上，利用社區(qū)演化中可能會(huì)發(fā)生的事件來(lái)追蹤社區(qū)的演化，考慮任意不相同時(shí)間片之間社區(qū)的演化關(guān)系，從而收集更多的社區(qū)演化關(guān)系，以更完整地描述社區(qū)的演化過(guò)程。

2 定義

在說(shuō)明社區(qū)演化關(guān)系之前，需要描述一些與社交網(wǎng)絡(luò)有關(guān)的一般概念，如時(shí)間社交網(wǎng)絡(luò)、社區(qū)定義和社區(qū)演化。

2.1 時(shí)間社交網(wǎng)絡(luò)

時(shí)間社交網(wǎng)絡(luò)G 是時(shí)間片Ti的集合，每個(gè)時(shí)間片實(shí)際上是一個(gè)單一的社交網(wǎng)絡(luò)Ni(V，E)，其中：V 是一組頂點(diǎn)，E 是一組有向邊。

2.2 社區(qū)的定義

隨著人們對(duì)網(wǎng)絡(luò)研究的深入，根據(jù)網(wǎng)絡(luò)的物理性質(zhì)和數(shù)學(xué)特性，人們發(fā)現(xiàn)了真實(shí)網(wǎng)絡(luò)中的一個(gè)共同的性質(zhì)，即網(wǎng)絡(luò)中都存在一種結(jié)構(gòu)——社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)是指：在社區(qū)內(nèi)部節(jié)點(diǎn)之間的連接比較緊密，社區(qū)之間的連接相對(duì)稀疏。網(wǎng)絡(luò)可以用若干個(gè)社區(qū)的組合來(lái)表示。在網(wǎng)絡(luò)中可以通過(guò)算法來(lái)確定社區(qū)，在本文中可以使用任何社區(qū)挖掘算法來(lái)提取社區(qū)。

經(jīng)過(guò)近些年的研究，研究人員已從各種不同的角度提出了很多社區(qū)挖掘算法。其中K-團(tuán)滲透法（Cluster Percolation Method，CPM）［22］和 標(biāo) 簽 傳 播 算 法（Label Propagation Algorithm，LPA）［23］是兩個(gè)比較經(jīng)典的社區(qū)挖掘算法。

1）K-團(tuán)滲透法。

K-團(tuán)滲透法是第一個(gè)能夠發(fā)現(xiàn)重疊社區(qū)的社區(qū)挖掘算法，重疊社區(qū)是指節(jié)點(diǎn)可以同時(shí)屬于多個(gè)社區(qū)。重疊社區(qū)在現(xiàn)實(shí)生活是很有意義的，因?yàn)槊總€(gè)人都有著多種的社交關(guān)系。

團(tuán)是指：團(tuán)中任意兩個(gè)節(jié)點(diǎn)之間都有邊連接，并且該團(tuán)不被其他的團(tuán)所包含。K-團(tuán)滲透法的思想是首先找出網(wǎng)絡(luò)中所有大小至少為K的團(tuán)，然后構(gòu)建一個(gè)團(tuán)圖，每個(gè)最大團(tuán)都是團(tuán)圖中的一個(gè)節(jié)點(diǎn)，如果兩個(gè)團(tuán)的節(jié)點(diǎn)集合C1與C2共享Min(C1，C2)- 1個(gè)鄰居的話，它們?cè)谛聢D中的節(jié)點(diǎn)之間就存在邊。最后團(tuán)圖中的每一個(gè)連通單元就是一個(gè)節(jié)點(diǎn)的社區(qū)，而它可能是重疊的。

2）標(biāo)簽傳播算法。

標(biāo)簽傳播算法是不重疊社區(qū)挖掘的經(jīng)典算法之一。各個(gè)社區(qū)節(jié)點(diǎn)的集合沒(méi)有交集的被稱(chēng)為非重疊社區(qū)。

LPA 的過(guò)程：初始時(shí)，給每一個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽；每個(gè)節(jié)點(diǎn)使用其鄰居節(jié)點(diǎn)的標(biāo)簽中最多的標(biāo)簽來(lái)更新自身的標(biāo)簽；反復(fù)執(zhí)行，直到每個(gè)節(jié)點(diǎn)標(biāo)簽不再發(fā)生變化為止。標(biāo)簽相同的節(jié)點(diǎn)在同一個(gè)社區(qū)。

2.3 社區(qū)演化

社區(qū)演化是一系列社區(qū)事件的變化，它們?cè)谏缃痪W(wǎng)絡(luò)中的連續(xù)時(shí)間片內(nèi)彼此連續(xù)。社區(qū)事件的定義是描述社區(qū)演化的基礎(chǔ)。

2.3.1 社區(qū)事件

研究社區(qū)演化的目的是分析和預(yù)測(cè)社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)特性，通常考慮和使用元素是社交網(wǎng)絡(luò)的節(jié)點(diǎn)和邊緣［13］。社區(qū)事件是指社區(qū)在演化過(guò)程中經(jīng)歷的變化。在追蹤社區(qū)演化時(shí)，可以根據(jù)它的節(jié)點(diǎn)的情況，依據(jù)社區(qū)間的公共節(jié)點(diǎn)數(shù)量關(guān)系來(lái)表示社區(qū)事件。

2.3.2 社區(qū)事件分類(lèi)

本文將社區(qū)事件分類(lèi)為7 種事件，它們代表在兩個(gè)不同時(shí)刻的時(shí)間片中社區(qū)的變化狀態(tài)，如圖1。令S表示社區(qū)節(jié)點(diǎn)的集合，用社區(qū)節(jié)點(diǎn)集合之間的關(guān)系來(lái)表示不同的社區(qū)事件。

1）社區(qū)繼承（continuing）：兩個(gè)社區(qū)相同，或者兩個(gè)社區(qū)僅有少數(shù)節(jié)點(diǎn)不同但大小保持不變。

2）社區(qū)縮小（shrinking）：社區(qū)中的部分節(jié)點(diǎn)離開(kāi)，使得社區(qū)規(guī)模比先前小。

如果和中部分節(jié)點(diǎn)相同，且的規(guī)模小于的規(guī)模，則稱(chēng)是的縮小。社區(qū)縮小可以表示某一個(gè)事物的熱度降低等。

3）社區(qū)擴(kuò)大（growing）：社區(qū)中加入新的節(jié)點(diǎn)，使得社區(qū)規(guī)模比先前大。

如果和中部分節(jié)點(diǎn)相同，且的規(guī)模大于的規(guī)模，則稱(chēng)是的擴(kuò)大。社區(qū)擴(kuò)大可以表示某一個(gè)事物 +y受到的關(guān)注越來(lái)越多等。

圖1 社區(qū)事件示例Fig. 1 Community event examples

4）社區(qū)分裂（splitting）：一個(gè)社區(qū)中的一些節(jié)點(diǎn)或邊消失，使社區(qū)分裂成多個(gè)部分。

如果和的并集與中部分節(jié)點(diǎn)相同，且和的規(guī)模小于的規(guī)模，則稱(chēng)和由分裂而來(lái)。社區(qū)分裂可以表示在一個(gè)大的研究領(lǐng)域中，不同的人對(duì)這個(gè)研究領(lǐng)域下的某一個(gè)更細(xì)致的研究領(lǐng)域更感興趣。

5）社區(qū)合并（merging）：多個(gè)社區(qū)合并成一個(gè)社區(qū)。

如果和的并集與中部分節(jié)點(diǎn)相同，且和的規(guī)模大于的規(guī)模，社區(qū)合并可以表示不同種類(lèi)的群組，為了完成某一個(gè)任務(wù)，而合并在一起共同合作。

6）社區(qū)消失（dissolving）：一個(gè)社區(qū)從網(wǎng)絡(luò)中消失，該社區(qū)原本包含的節(jié)點(diǎn)不再屬于該社區(qū)。t+y時(shí)刻中沒(méi)有Sit+y使得

和中沒(méi)有足夠多的相同節(jié)點(diǎn)，則稱(chēng)在t+y時(shí)刻消失。社區(qū)消失可以表示一個(gè)臨時(shí)的工作群組在工作完成之后，各自又回到原來(lái)的工作崗位等。

7）社區(qū)形成（forming）：出現(xiàn)了在先前時(shí)刻不存在的社區(qū)。t時(shí)刻中沒(méi)有使得

和中沒(méi)有足夠的相同節(jié)點(diǎn)，則稱(chēng)在t+y時(shí) 刻形成。社區(qū)的形成通常意味著新事物、新話題或新團(tuán)體的起源，“形成”事件有助于分析和把握網(wǎng)絡(luò)的發(fā)展。

每一種社區(qū)事件的定義在現(xiàn)實(shí)中都有它獨(dú)特且實(shí)際的意義，對(duì)應(yīng)動(dòng)態(tài)圖可以很好地對(duì)社區(qū)的演化進(jìn)行描述，從而分析動(dòng)態(tài)圖的發(fā)展。

3 問(wèn)題描述

先前的研究將社區(qū)事件分類(lèi)為多種類(lèi)型，但只將它們用來(lái)描述連續(xù)相鄰時(shí)間片之間一個(gè)社區(qū)或者多個(gè)社區(qū)的狀態(tài)。雖然可以刻畫(huà)出社區(qū)的演化過(guò)程，但這種刻畫(huà)是不完備的，僅根據(jù)連續(xù)時(shí)間片之間的社區(qū)事件，無(wú)法推算出一些社區(qū)之間的關(guān)系?，F(xiàn)舉例進(jìn)行說(shuō)明。

以3 個(gè)相鄰時(shí)間片和“擴(kuò)大”“縮小”事件為例。圖2 是3個(gè)相鄰時(shí)間片中的某一個(gè)社區(qū)演化過(guò)程，箭頭表示它們之間發(fā)生的社區(qū)事件。

圖2 社區(qū)演化關(guān)系Fig. 2 Community evolution relationships

圖2 （a）中，社區(qū)A 到社區(qū)B 經(jīng)歷了“縮小”事件，社區(qū)B 到社區(qū)C經(jīng)歷了“縮小”事件。根據(jù)社區(qū)點(diǎn)集之間的關(guān)系可以推導(dǎo)出，社區(qū)C是由社區(qū)A“縮小”之后得來(lái)。

圖2（b）中，社區(qū)A 到社區(qū)B 經(jīng)歷了“擴(kuò)大”事件，社區(qū)B 到社區(qū)C經(jīng)歷了“擴(kuò)大”事件。根據(jù)社區(qū)點(diǎn)集之間的關(guān)系可以推導(dǎo)出，社區(qū)C是由社區(qū)A“擴(kuò)大”之后得來(lái)。

圖2（c）中，社區(qū)A 到社區(qū)B 經(jīng)歷了“縮小”事件，社區(qū)B 到社區(qū)C經(jīng)歷了“擴(kuò)大”事件。如果僅根據(jù)點(diǎn)集之間的關(guān)系來(lái)推導(dǎo)社區(qū)A 和社區(qū)C 之間的關(guān)系，則會(huì)如圖3 有三種情況：①社區(qū)C 與社區(qū)A 相同；②社區(qū)C 與社區(qū)A 是同一個(gè)社區(qū)，但社區(qū)C規(guī)模大于社區(qū)A；③社區(qū)C與社區(qū)A是同一個(gè)社區(qū)，但社區(qū)C規(guī)模小于社區(qū)A。此時(shí)已經(jīng)無(wú)法僅根據(jù)它們之間的點(diǎn)集關(guān)系推導(dǎo)出來(lái)社區(qū)A與社區(qū)C之間的關(guān)系。

圖2（d）中，社區(qū)A 到社區(qū)B 經(jīng)歷了“擴(kuò)大”事件，社區(qū)B 到社區(qū)C 經(jīng)歷了“縮小”事件。社區(qū)A 與社區(qū)C 的關(guān)系同樣無(wú)法僅由推導(dǎo)得出。如圖4所示，也有三種情況。

傳統(tǒng)方法獲得的社區(qū)演化關(guān)系，可以描繪出動(dòng)態(tài)社區(qū)的演化過(guò)程，但描繪不夠全面。若遇到如圖3 與圖4 的情況，無(wú)法僅由推導(dǎo)得出社區(qū)之間的關(guān)系，而需要重新計(jì)算來(lái)確定兩個(gè)社區(qū)之間的關(guān)系。社區(qū)演化過(guò)程描述得越詳細(xì)完整，在分析社區(qū)演化時(shí)可利用的信息就越多，社區(qū)演化關(guān)系是分析社區(qū)演化的基礎(chǔ)，所以在分析社區(qū)演化關(guān)系時(shí)要考慮到社區(qū)之間存在的各種關(guān)系。

圖3 社區(qū)C與社區(qū)A的演化關(guān)系（a）Fig. 3 Evolution relationships（a）between community C and A

圖4 社區(qū)C與社區(qū)A的演化關(guān)系（b）Fig. 4 Evolution relationships（b）between community C and A

4 改進(jìn)的社區(qū)演化分析方法

在傳統(tǒng)方法中，首先需要對(duì)動(dòng)態(tài)社區(qū)進(jìn)行社區(qū)挖掘，本文則將靜態(tài)社區(qū)檢測(cè)方法用于動(dòng)態(tài)網(wǎng)絡(luò)，然后比較相鄰時(shí)間片之間社區(qū)的狀態(tài)來(lái)確定一個(gè)社區(qū)事件。本文在傳統(tǒng)方法的基礎(chǔ)之上也考慮了不相鄰時(shí)間片內(nèi)社區(qū)之間的關(guān)系。

1）將網(wǎng)絡(luò)的演化用時(shí)間片的集合來(lái)表示，將動(dòng)態(tài)網(wǎng)絡(luò)離散化為n個(gè)連續(xù)的時(shí)間片，每一個(gè)時(shí)間片都代表動(dòng)態(tài)網(wǎng)絡(luò)在某一個(gè)時(shí)刻的狀態(tài)。

2）使用已有的靜態(tài)社區(qū)挖掘算法對(duì)每一個(gè)時(shí)間片進(jìn)行社區(qū)挖掘，本文中使用的靜態(tài)社區(qū)挖掘算法為K-團(tuán)滲透法。

社區(qū)挖掘結(jié)束后，根據(jù)社區(qū)事件類(lèi)型的定義，匹配兩個(gè)相應(yīng)時(shí)間片內(nèi)社區(qū)之間發(fā)生的事件。算法步驟如下：

步驟1 將時(shí)間社交網(wǎng)絡(luò)G用若n個(gè)時(shí)間片T進(jìn)行表示，時(shí)間片表示動(dòng)態(tài)社交網(wǎng)絡(luò)某一時(shí)刻的狀態(tài)。時(shí)間窗口需要根據(jù)社交網(wǎng)絡(luò)的結(jié)構(gòu)特征和用戶(hù)期望來(lái)劃分，保證時(shí)間片之間能夠獲取重要的變化信息，同時(shí)盡可能減少計(jì)算復(fù)雜度。

步驟2 將步驟1 中劃分的時(shí)間片按照其時(shí)間戳的先后順序排列，記為G=｛T1，T2，…，Tn｝。

步驟3 使用靜態(tài)社區(qū)挖掘算法對(duì)劃分的每一個(gè)時(shí)間片進(jìn)行社區(qū)挖掘，挖掘出各個(gè)時(shí)間片中所有的社區(qū)結(jié)構(gòu)。

步驟4 獲取每個(gè)時(shí)間片內(nèi)的社區(qū)結(jié)構(gòu)C，用社區(qū)集合的形式表示對(duì)應(yīng)的時(shí)間片，記為T(mén)=｛C1，C2，…，Ck｝，其中C為社區(qū)結(jié)構(gòu)內(nèi)節(jié)點(diǎn)的集合。

步驟7 根據(jù)記錄信息，描繪社區(qū)演化關(guān)系圖。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證本文方法的有效性，利用兩種數(shù)據(jù)集對(duì)傳統(tǒng)方法和本文方法進(jìn)行比較。數(shù)據(jù)集描述如下：

第一組數(shù)據(jù)集為Contacts in a workplace［24］，該數(shù)據(jù)集為法國(guó)一棟辦公樓中測(cè)得的個(gè)人之間的接觸網(wǎng)絡(luò)。該網(wǎng)絡(luò)共88個(gè)節(jié)點(diǎn)，9 827條邊，將數(shù)據(jù)集按時(shí)間戳的先后順序劃分為5個(gè)時(shí)間片，每個(gè)時(shí)間片代表24 h內(nèi)個(gè)人之間的交流情況。

第二組數(shù)據(jù)集為2009 年法國(guó)會(huì)議數(shù)據(jù)集［25］，該數(shù)據(jù)集以社交網(wǎng)絡(luò)的形式描述了405 位參與者2009 年6 月4 日到5 日在法國(guó)尼斯舉行會(huì)議的面對(duì)面互動(dòng)情況。該社交網(wǎng)絡(luò)共405個(gè)點(diǎn)，70 216 條邊，將數(shù)據(jù)集按時(shí)間戳的先后順序劃分為4 個(gè)時(shí)間片，每個(gè)時(shí)間片代表5 h內(nèi)參與者的互動(dòng)情況。

5.2 實(shí)驗(yàn)方法

首先，針對(duì)兩個(gè)數(shù)據(jù)集，分別使用K-團(tuán)滲透算法來(lái)挖掘每個(gè)時(shí)間片內(nèi)的社區(qū)結(jié)構(gòu)。表1為使用K-團(tuán)滲透算法在每個(gè)時(shí)間片中挖掘出的社區(qū)數(shù)量。

表1 社區(qū)挖掘結(jié)果Tab. 1 Community mining results

然后分別使用傳統(tǒng)方法及本文方法來(lái)分析社區(qū)的演化關(guān)系，實(shí)驗(yàn)結(jié)果如圖5～8所示，其中：圖5、6為采用數(shù)據(jù)集1時(shí)的結(jié)果；圖7、8為采用數(shù)據(jù)集2時(shí)的結(jié)果。圖中每個(gè)節(jié)點(diǎn)并非代表原始數(shù)據(jù)集里的節(jié)點(diǎn)，而是代表某個(gè)時(shí)間片里所挖掘出的一個(gè)社區(qū)。節(jié)點(diǎn)由其所屬時(shí)間片和該時(shí)間片內(nèi)社區(qū)的序號(hào)共同標(biāo)識(shí)。例如2#0041，表示該節(jié)點(diǎn)為時(shí)間片2 中編號(hào)為41 的社區(qū)。節(jié)點(diǎn)之間的有向邊代表兩個(gè)社區(qū)之間所發(fā)生的社區(qū)事件；若節(jié)點(diǎn)沒(méi)有邊連接，則說(shuō)明該社區(qū)只存在于某一時(shí)間片內(nèi)。

按照事件類(lèi)型，對(duì)上述社區(qū)演化關(guān)系圖中發(fā)生的社區(qū)事件數(shù)量分別進(jìn)行統(tǒng)計(jì)，結(jié)果如表2、3所示。

5.3 實(shí)驗(yàn)結(jié)論

由兩個(gè)社區(qū)演化圖比較得出，傳統(tǒng)方法對(duì)社區(qū)演化關(guān)系的描述不夠全面，而本文方法在描繪社區(qū)演化關(guān)系時(shí)提供了更多的信息。對(duì)于數(shù)據(jù)集1，本文方法的社區(qū)事件總數(shù)是傳統(tǒng)方法的2.56倍；對(duì)于數(shù)據(jù)集2，本文方法中社區(qū)事件總數(shù)是傳統(tǒng)方法的2.04倍。

圖5 傳統(tǒng)方法獲得的數(shù)據(jù)集1的社區(qū)演化關(guān)系圖Fig. 5 Community evolution relationship graph of dataset 1 detected by traditional method

圖6 本文方法獲得的數(shù)據(jù)集1的社區(qū)演化關(guān)系圖Fig. 6 Community evolution relationship graph of dataset 1 detected by proposed method

圖7 傳統(tǒng)方法獲得的數(shù)據(jù)集2的社區(qū)演化關(guān)系圖Fig. 7 Community evolution relationship graph of dataset 2 detected by traditional method

圖8 本文方法獲得的數(shù)據(jù)集2的社區(qū)演化關(guān)系圖Fig. 8 Community evolution relationship graph of dataset 2 detected by proposed method

表2 傳統(tǒng)方法時(shí)間片間社區(qū)事件數(shù)Tab. 2 Number of community events in time slices detected by traditional method

表3 本文方法時(shí)間片間社區(qū)事件數(shù)Tab. 3 Number of community events in time slices obtained by proposed method

6 結(jié)語(yǔ)

動(dòng)態(tài)圖社區(qū)演化關(guān)系是分析動(dòng)態(tài)圖演化規(guī)律的一個(gè)重要環(huán)節(jié)。目前已經(jīng)有大量的算法來(lái)分析動(dòng)態(tài)圖社區(qū)演化關(guān)系，但僅考慮相鄰時(shí)間片社區(qū)之間的關(guān)系。這對(duì)于刻畫(huà)動(dòng)態(tài)社區(qū)的演化過(guò)程是不全面的，會(huì)遺漏一些比較重要的社區(qū)演化信息。本文針對(duì)這一問(wèn)題提出了一種改進(jìn)的社區(qū)演化關(guān)系分析方法，考慮任意不同時(shí)間片間社區(qū)演化關(guān)系。實(shí)驗(yàn)結(jié)果表明，本文方法可捕捉更多的社區(qū)演化關(guān)系，使社區(qū)的演化過(guò)程展現(xiàn)得更全面，也使一些不明確的社區(qū)關(guān)系明確，從而為更加準(zhǔn)確地分析和預(yù)測(cè)動(dòng)態(tài)圖社區(qū)演化規(guī)律奠定了基礎(chǔ)。