基于個體穩(wěn)定度博弈的動態(tài)社區(qū)發(fā)現(xiàn)算法研究

許宇光 蔣 飛 朱恩強 潘驚治 謝惠揚

?

基于個體穩(wěn)定度博弈的動態(tài)社區(qū)發(fā)現(xiàn)算法研究

許宇光①蔣 飛①朱恩強①潘驚治①謝惠揚*②

①(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)②(北京林業(yè)大學(xué)理學(xué)院 北京 100083)

在動態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是一個復(fù)雜而又有重要意義的課題。該文針對動態(tài)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題，提出一種基于個體穩(wěn)定度的博弈論方法(PDG)。在該博弈方法中，網(wǎng)絡(luò)中的每個節(jié)點都是一個獨立個體。個體會根據(jù)網(wǎng)絡(luò)中的其他個體的狀態(tài)，使用最佳應(yīng)對策略進行社區(qū)的選擇。針對網(wǎng)絡(luò)演化過程中的社區(qū)更新問題，該文提出了格局檢測(Configuration checking)等優(yōu)化策略，從而大大提高了演化網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)的效率。最后，在真實演化網(wǎng)絡(luò)的實驗中，與最新的靜態(tài)和動態(tài)社區(qū)發(fā)現(xiàn)方法進行對比，驗證了PDG方法的效率和效果。

動態(tài)社區(qū)發(fā)現(xiàn)；穩(wěn)定度；模塊度；博弈論；格局檢測

1 引言

近年來，隨著計算機技術(shù)的不斷發(fā)展和移動互聯(lián)時代的到來，網(wǎng)絡(luò)科學(xué)，特別是社交網(wǎng)絡(luò)的研究引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。其中，社區(qū)發(fā)現(xiàn)問題是網(wǎng)絡(luò)科學(xué)研究中的一個關(guān)鍵問題。社區(qū)是網(wǎng)絡(luò)中相互連接緊密的節(jié)點集合。在不同類型的網(wǎng)絡(luò)中，社區(qū)有著不同的含義。例如，社交網(wǎng)絡(luò)中，社區(qū)通常代表著具有共同興趣的群 體[8]。社區(qū)結(jié)構(gòu)是在中觀層面上理解網(wǎng)絡(luò)結(jié)構(gòu)的有效途徑。社區(qū)發(fā)現(xiàn)問題無論在理論上還是在應(yīng)用上都有著十分重要的意義[9]。

社區(qū)發(fā)現(xiàn)問題是一個非常復(fù)雜而繁瑣的問題。它的復(fù)雜性體現(xiàn)在以下幾方面：不同類型網(wǎng)絡(luò)的結(jié)構(gòu)特性與統(tǒng)計特性都有著很大差異[10]，因此，對于這些網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)進行統(tǒng)一的量化定義是十分困難的；不同類型的社區(qū)發(fā)現(xiàn)的需求，例如：非重疊社區(qū)發(fā)現(xiàn)(disjoint)、重疊社區(qū)發(fā)現(xiàn)(overlapping)、層次社區(qū)發(fā)現(xiàn)(hierarchical)、動態(tài)社區(qū)發(fā)現(xiàn)(dynamic)[11]、基于流圖的社區(qū)發(fā)現(xiàn)(based on graph stream)；各種類型的社區(qū)發(fā)現(xiàn)問題都是NP難問題[6]，因此，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，社區(qū)發(fā)現(xiàn)方法的效率是必須要考慮的問題。針對動態(tài)社區(qū)發(fā)現(xiàn)問題，本文設(shè)計了一種基于個體穩(wěn)定度博弈的動態(tài)社區(qū)發(fā)現(xiàn)算法(Permanence Dynamic Game, PDG)。穩(wěn)定度是一種新的衡量社區(qū)劃分結(jié)果的指標(biāo)[12]。穩(wěn)定度指標(biāo)考慮了個體在社區(qū)內(nèi)部的度和在其他社區(qū)的最大度，并結(jié)合了個體在社區(qū)內(nèi)的聚集系數(shù)，是一種較理想的社區(qū)評價指標(biāo)。博弈中效益函數(shù)基于個體穩(wěn)定度與模塊度[13,14]思想設(shè)計，能有效避免模塊度指標(biāo)所具有的分辨率限制(resolution limit)，因此能夠發(fā)現(xiàn)適當(dāng)規(guī)模的社區(qū)。

社區(qū)發(fā)現(xiàn)問題以各種形式出現(xiàn)在不同學(xué)科的研究中，相關(guān)研究人員從不同角度給出了解決傳統(tǒng)的靜態(tài)社區(qū)發(fā)現(xiàn)問題的方法。其中，Palla等人[15]提出團滲透的方法解決社區(qū)發(fā)現(xiàn)問題，并定義在團特征圖中有個節(jié)點相同的團具有連接關(guān)系。Rosvall等人[16,17]提出了一種基于信息編碼的社區(qū)發(fā)現(xiàn)算法Infomap。大量文獻的結(jié)果證明，該方法能夠得到良好的社區(qū)發(fā)現(xiàn)結(jié)果。Raghavan等人[18]提出使用標(biāo)簽傳播的方法進行社區(qū)發(fā)現(xiàn)。Chen等人[19]提出基于博弈論的社區(qū)發(fā)現(xiàn)算法，并證明了算法的可終止性，在此基礎(chǔ)上Alvari等人設(shè)計了更加優(yōu)化的效益函數(shù)，并能夠發(fā)現(xiàn)重疊社區(qū)。此外，還有基于概率模型、同步理論、局部優(yōu)化等其他方法，更加詳細的綜述請參照文獻[6,20,21]。

近年來，動態(tài)社區(qū)發(fā)現(xiàn)受到了廣泛關(guān)注。Sun等人[22]提出了一種基于信息壓縮理論的非參數(shù)的動態(tài)社區(qū)劃分方法GraphScope。文中提出了圖片段(graph segment)的概念。圖片段由多個連續(xù)時間片構(gòu)成。同一個圖片段中的網(wǎng)絡(luò)應(yīng)該具有容易壓縮的性質(zhì)，否則應(yīng)放到不同圖片段中。這種壓縮的方法不僅能將不同的時間片進行分段，而且在壓縮過程中自然形成了社區(qū)結(jié)構(gòu)。Xie等人[23]提出一種基于標(biāo)簽傳播理論的動態(tài)社區(qū)劃分方法——LabelRankT。該方法是一種增量式方法，不僅保證了社區(qū)發(fā)現(xiàn)算法的速度，而且在一定程度上避免了標(biāo)簽傳播方法的不穩(wěn)定性。此外，其他研究人員也提出了一些解決動態(tài)社區(qū)發(fā)現(xiàn)問題的方法[24,25]。本文的創(chuàng)新性主要有3點：提出了一種基于博弈論[26]的動態(tài)社區(qū)發(fā)現(xiàn)算法，該方法能更好地模擬個體在演化網(wǎng)絡(luò)中的行為，從而能達到更好的社區(qū)發(fā)現(xiàn)效果。該算法更加適用于在線社交網(wǎng)絡(luò)等不斷演化的網(wǎng)絡(luò)；提出了一種結(jié)合個體穩(wěn)定度和模塊度的效益函數(shù)。該效益函數(shù)能高效地發(fā)現(xiàn)重疊社區(qū)并且消除了模塊度所具有的分辨率限制；提出格局檢測策略和其他優(yōu)化策略。

2 基本概念與記號

為了方便表述，我們將在這一節(jié)中介紹本文所使用的符號，并闡述評價社區(qū)結(jié)果的兩個重要指標(biāo)：模塊度(modularity)、穩(wěn)定度(permanence)。弄清這兩個指標(biāo)的不同特性將有助于我們理解PDG博弈算法。

為了引入本文博弈模型中的效益函數(shù)，本小節(jié)將介紹兩個評價社區(qū)結(jié)構(gòu)的指標(biāo)。其中，最為廣泛使用的指標(biāo)是模塊度[27]。模塊度計算的是每一社區(qū)內(nèi)任意兩點連邊與否和隨機連邊概率的差值。模塊度的計算公式為

模塊度只能衡量社區(qū)內(nèi)的連接情況較隨機連接的偏離程度，并不能反映其他社區(qū)對該社區(qū)內(nèi)節(jié)點的吸引程度。對于某一固定社區(qū)結(jié)構(gòu)，計算模塊度時，社區(qū)與社區(qū)之間的連邊將不會被考慮。針對此問題，Chakraborty等人[12]提出另一社區(qū)結(jié)構(gòu)評價指標(biāo)穩(wěn)定度。穩(wěn)定度指標(biāo)不僅考慮節(jié)點在社區(qū)內(nèi)的作用，同時考慮節(jié)點被其他社區(qū)的吸引程度。節(jié)點的穩(wěn)定度計算公式為

3 穩(wěn)定度博弈算法PDG

社交網(wǎng)絡(luò)中的個體的行為都是自發(fā)的，他們出于自身考慮加入社區(qū)，并從社區(qū)中獲得信息、訓(xùn)練、樂趣等。這正好和博弈論中的參與者的行為吻合，即每個參與者都想要在博弈中最大化自己的收益。本文提出一種基于博弈論框架的動態(tài)社區(qū)發(fā)現(xiàn)算法PDG。其中，在每一個靜態(tài)的時間片下，每個節(jié)點都被認為是一個理性的、自私的博弈參與者。然后在一定的規(guī)則下，讓參與者在網(wǎng)絡(luò)中進行自由的博弈，最終達到個體收益的最大值。社區(qū)劃分的最終狀態(tài)將是一個局部的納什均衡。

3.1穩(wěn)定度博弈框架

在穩(wěn)定度博弈中，參與者為網(wǎng)絡(luò)中的節(jié)點。為方便陳述，在不混淆語義的情況下，我們將不對節(jié)點、參與者、個體加以嚴(yán)格區(qū)分。我們規(guī)定，穩(wěn)定度博弈中個體的策略為其所歸屬社區(qū)的集合。全局策略空間定義如下：

對應(yīng)于真實的社區(qū)形成過程，每個個體在博弈時可以選擇的策略由5種動作生成，分別是加入社區(qū)、離開社區(qū)、更換社區(qū)、建立社區(qū)、無動作。博弈中的另一個要素是效益函數(shù)，穩(wěn)定度博弈的效益函數(shù)由兩部分組成，即增益函數(shù)和損失函數(shù)。增益函數(shù)和損失函數(shù)對社區(qū)發(fā)現(xiàn)結(jié)果的好壞起著決定性作用。

從式(3)中可以看出，個體的增益函數(shù)由兩部分組成。前半部分為個體的內(nèi)度與最大外度之比的歸一化結(jié)果。式(3)的后半部分可以理解為節(jié)點的實際連邊情況與隨機連邊概率的差值。與模塊度不同的是，這里的隨機連邊只對節(jié)點的鄰居進行。它可以視為是一種改進的模塊度。這種改進既便于快速計算，又能得到良好的結(jié)果。

為了便于理解，我們給出一個簡單的例子。如圖1所示，網(wǎng)絡(luò)中有3個社區(qū)。節(jié)點歸屬于社區(qū)時，,。由于節(jié)點在社區(qū)中的度為2，所以。如式(3)中的后半部分為計算節(jié)點在社區(qū)內(nèi)的改進模塊度，其中求和符號展開后應(yīng)為4項，每一項對應(yīng)節(jié)點的一條邊所帶來的模塊度的增加。

從式(4)中可以看出，損失函數(shù)也由兩部分組成。其中一部分在于節(jié)點加入的社區(qū)并不能增加社區(qū)的聚集性，它通過節(jié)點在社區(qū)內(nèi)的聚集系數(shù)體現(xiàn)。另一部分是由于其他社區(qū)對節(jié)點的吸引力使得節(jié)點處于當(dāng)前社區(qū)的穩(wěn)定性下降，它通過節(jié)點的最大外社區(qū)的吸引力體現(xiàn)。

定義4中的效益函數(shù)針對于節(jié)點加入單一社區(qū)的情況，但真實網(wǎng)絡(luò)往往存在重疊社區(qū)。當(dāng)加入多個社區(qū)可以使參與者的收益值增加時，參與者將加入多個社區(qū)，以此形成重疊社區(qū)劃分。加入多個社區(qū)會消耗一定的代價，例如：費用、時間、精力等。針對重疊社區(qū)的情況，我們定義效益函數(shù)如下：

3.2優(yōu)化策略及格局檢測策略

我們只考慮節(jié)點加入兩個社區(qū)的情況，多于兩個社區(qū)的情況可以依次類推。

定理1可以用于快速判斷是否加入重疊社區(qū)，并有效地進行剪枝。當(dāng)節(jié)點加入重疊社區(qū)時，絕大多數(shù)情況將滿足定理2中的條件，即加入的兩個社區(qū)是包含其邊數(shù)最多的社區(qū)。這時，定理2可以幫助我們快速計算效益值，以用于后續(xù)博弈。作為動態(tài)社區(qū)發(fā)現(xiàn)方法的一部分，我們引入格局檢測策略。在最近的文獻中，格局檢測策略在解決NP完全問題上的有效性被證實[30]。一方面用于將上一時間片的社區(qū)發(fā)現(xiàn)結(jié)果傳遞到下一時間片，以用于下一時間片的穩(wěn)定度博弈的初始化。另一方面，格局檢測策略可以用來判斷節(jié)點是否處于均衡狀態(tài)，以用于選擇博弈的候選參與者。我們定義一個節(jié)點的鄰居和鄰居的社區(qū)歸屬為節(jié)點的格局。具體定義如下：

在某一靜態(tài)時間片下，格局檢測是檢測某一節(jié)點當(dāng)前時刻的格局與上一時刻的格局是否相同。如不同，則節(jié)點可能處于非均衡狀態(tài)，該節(jié)點將被當(dāng)作博弈的候選參與者。另外，在完成上一時間片的社區(qū)發(fā)現(xiàn)進行下一時間片的初始化時，存在于上一時間片并具有與上一時間片相同格局的節(jié)點將保持上一時間片的策略。

基于個體穩(wěn)定度博弈的動態(tài)社區(qū)發(fā)現(xiàn)算法示于表1。

在穩(wěn)定度博弈中，每次博弈我們從候選參與者中隨機選擇一個非均衡節(jié)點。對于一個靜態(tài)時間片下，穩(wěn)定度博弈算法最終會達到一個局部的納什均衡，即任何個體都無法通過單方面改變自己的策略而獲得效益的提升。這里的局部性體現(xiàn)在我們只允許節(jié)點加入鄰居所處的社區(qū)，而不能加入鄰居沒有加入的社區(qū)。

表1 PDG算法

具體地，對于一個新的時間片，首先使用格局檢測策略對全局策略進行初始化(2~8行)，即和上個時間片格局相同的節(jié)點保持原有策略。對于新出現(xiàn)的節(jié)點，執(zhí)行建立孤立社區(qū)的動作。

如果存在非均衡節(jié)點，隨機選擇一個節(jié)點。以該節(jié)點為參與者，進行穩(wěn)定度博弈，即在其他節(jié)點的策略不變的情況下，選擇最佳應(yīng)對動作，以最大化自身效益(10~13行)。需要注意的是，如果該節(jié)點滿足定理1的條件，則其不用執(zhí)行加入社區(qū)動作，以達到降低復(fù)雜度的目的。但它可以進行更換社區(qū)、建立社區(qū)動作；如果該節(jié)點已經(jīng)歸屬于多個社區(qū)，則它還可以執(zhí)行離開社區(qū)動作(12行)。當(dāng)執(zhí)行一個最佳動作會帶來效益的提升時，節(jié)點就會執(zhí)行該最佳動作，然后根據(jù)格局檢測策略更新非均衡節(jié)點隊列(14~17行)；否則，節(jié)點會保持原有策略不變。不斷地選擇非均衡節(jié)點進行穩(wěn)定度博弈，直到整個網(wǎng)絡(luò)處于局部的納什均衡狀態(tài)。

4 實驗結(jié)果與分析

為了定量驗證我們穩(wěn)定度博弈算法的效果，我們在真實動態(tài)網(wǎng)絡(luò)中與先進的靜態(tài)社區(qū)發(fā)現(xiàn)、動態(tài)社區(qū)發(fā)現(xiàn)算法進行了對比實驗。實驗環(huán)境是一臺處理器主頻為2.5 GHz，內(nèi)存大小為4 GB的PC。本文提出的PDG算法以及實驗相關(guān)代碼見如下網(wǎng)址：https://github.com/Jafree/Permanence-Dynamic-Game。

4.1動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集

本文使用的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集來源于斯坦福的開源數(shù)據(jù)平臺SNAP。本文使用的數(shù)據(jù)集為AS- Internet。該數(shù)據(jù)集由于具有大量的時間片，因此能夠很好地反映社區(qū)發(fā)現(xiàn)的效果。我們將在該數(shù)據(jù)集上進行與靜態(tài)社區(qū)發(fā)現(xiàn)算法和動態(tài)社區(qū)發(fā)現(xiàn)算法的對比實驗。AS-Internet數(shù)據(jù)集的具體描述如下：

AS-Internet：該數(shù)據(jù)集是由跟蹤因特網(wǎng)中的邊界路由的信息交換而生成的通信網(wǎng)絡(luò)。它采集于1997年11月到2000年1月，由733個時間片構(gòu)成。相鄰的時間片可能會出現(xiàn)節(jié)點加入和離開、邊添加和刪除。AS-Internet數(shù)據(jù)集中有些時間片的變化十分劇烈，因此，好的社區(qū)發(fā)現(xiàn)算法應(yīng)該能反映出這種變化。每個時間片的節(jié)點數(shù)、邊數(shù)，相鄰時間片下節(jié)點的變化數(shù)(加入和離開)和邊的變化數(shù)(添加和刪除)如圖1所示。

圖1(a1)，圖1(a2)分別反映了不同時間片下的節(jié)點數(shù)和邊數(shù)，圖1(b1)，圖1(b2)分別反映了相鄰時間片下節(jié)點集合的變化數(shù)和邊集合的變化數(shù)?？梢钥闯?，大約在400個時間片之前，網(wǎng)絡(luò)中的節(jié)點數(shù)和邊數(shù)逐漸增加，節(jié)點集合和邊集合的變化也比較緩慢。之后，節(jié)點數(shù)和邊數(shù)驟減，網(wǎng)絡(luò)結(jié)構(gòu)產(chǎn)生了大幅度的變化。最后時刻的時間片也出現(xiàn)連續(xù)的顯著變化。一個好的動態(tài)社區(qū)發(fā)現(xiàn)算法應(yīng)該不僅能夠在網(wǎng)絡(luò)平穩(wěn)變化時準(zhǔn)確地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)、保持社區(qū)結(jié)構(gòu)的穩(wěn)定性，而且還應(yīng)在網(wǎng)絡(luò)劇烈變化時通過社區(qū)結(jié)構(gòu)的變化體現(xiàn)出網(wǎng)絡(luò)結(jié)構(gòu)的劇變。

4.2與靜態(tài)、動態(tài)社區(qū)發(fā)現(xiàn)算法對比

我們將PDG算法與先進的靜態(tài)社區(qū)發(fā)現(xiàn)算法和動態(tài)社區(qū)發(fā)現(xiàn)算法進行對比。靜態(tài)社區(qū)發(fā)現(xiàn)算法把動態(tài)網(wǎng)絡(luò)中每一時間片當(dāng)作一個靜態(tài)網(wǎng)絡(luò)進行社區(qū)劃分。兩種靜態(tài)社區(qū)發(fā)現(xiàn)算法如下：

Infomap[16]：使用信息編碼的方法進行社區(qū)劃分。經(jīng)過大量文獻的報道，該方法可以在較快的速度下獲得很好的社區(qū)劃分結(jié)果。

LabelPro[18]：基于標(biāo)簽傳播理論的代表方法。此方法基于局部信息，收斂速度快，并可以在一些網(wǎng)絡(luò)上，獲得良好的社區(qū)發(fā)現(xiàn)結(jié)果。

對于動態(tài)社區(qū)發(fā)現(xiàn)算法，我們將與LabelRankT算法進行對比。通過對比實驗，我們將看到PDG算法不僅能保持社區(qū)結(jié)構(gòu)演化的穩(wěn)定性，更能夠獲得很好社區(qū)結(jié)果。

LabelRankT[24]：基于標(biāo)簽傳播理論的改進，是一種動態(tài)社區(qū)發(fā)現(xiàn)算法。該方法較靜態(tài)標(biāo)簽傳播方法具有更高的穩(wěn)定性。LabelRankT算法有多個較難設(shè)置的參數(shù)，我們將在實驗中使用文獻[15]所推薦的可以得到最好結(jié)果的參數(shù)。

對于沒有真實(groud-truth)社區(qū)劃分結(jié)果的網(wǎng)絡(luò)，就不能使用歸一化互信息(NMI)進行結(jié)果的評價。尤其是對于動態(tài)網(wǎng)絡(luò)來說，真實社區(qū)劃分是很難獲得的。因此，對于動態(tài)重疊社區(qū)劃分，我們選擇改進的模塊度作為評價指標(biāo)。另外，將PDG算法中的重疊損失系數(shù)設(shè)為足夠高，例如令，就可以用于非重疊社區(qū)發(fā)現(xiàn)。

如圖2所示，PDG算法的社區(qū)結(jié)果要優(yōu)于其他3個算法。PDG算法所得到的模塊度隨著網(wǎng)絡(luò)的不斷變化穩(wěn)步增高，且優(yōu)于其他3個算法。然而，在中期，模塊度出現(xiàn)一個較大的下降，并快速恢復(fù)。在最后階段，PDG的模塊度出現(xiàn)一定程度的下降，并低于Infomap的結(jié)果。通過仔細觀察圖1和圖2我們可以發(fā)現(xiàn)PDG算法的結(jié)果的變化趨勢正是反映了網(wǎng)絡(luò)結(jié)構(gòu)的變化，與我們的預(yù)期一致。Infomap算法獲得了較好的結(jié)果，也是最穩(wěn)定的結(jié)果，但是它幾乎與網(wǎng)絡(luò)結(jié)構(gòu)無關(guān)。LabelPro算法的結(jié)果顯示出了標(biāo)簽傳播方法慣有的缺點，即不穩(wěn)定性。LabelRankT作為動態(tài)的標(biāo)簽傳播方法，在一定程度上克服了不穩(wěn)定的缺點，但其結(jié)果稍劣于PDG算法。經(jīng)過計算，以模塊度為評價指標(biāo)，PDG算法的效果較LabelRankT提高了23%，較Infomap提高了5%，較LabelPro提高了42%。

為了更加清晰地看到各種算法與網(wǎng)絡(luò)結(jié)構(gòu)變化的關(guān)系，我們繪制出了不同時間片下社區(qū)數(shù)目的變化，如圖3所示。其中，Infomap算法的社區(qū)數(shù)目穩(wěn)定，但圖1網(wǎng)絡(luò)的后期有劇烈變化，因此，該算法基本不能反映網(wǎng)絡(luò)結(jié)構(gòu)的變化。LabelPro算法的社區(qū)數(shù)目比較少，且處于無規(guī)則震蕩。LabelRankT算法結(jié)果中的社區(qū)數(shù)目適中，雖能部分反映網(wǎng)絡(luò)結(jié)構(gòu)的變化，但也有較強的無規(guī)則性。PDG算法所發(fā)現(xiàn)的社區(qū)數(shù)目在前期穩(wěn)定，并逐漸減少，這說明了社區(qū)演化時存在社區(qū)合并的現(xiàn)象。而中后期社區(qū)數(shù)目出現(xiàn)較大的波動，恰好反映了網(wǎng)絡(luò)結(jié)構(gòu)的劇變。

上文中提到，基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)算法具有分辨率限制，即小規(guī)模社區(qū)不能夠被發(fā)現(xiàn)，即使它們是團[29]。本文中博弈的效益函數(shù)，結(jié)合了穩(wěn)定度和模塊度的優(yōu)點，從而避免了分辨率的限制。圖4描述了網(wǎng)絡(luò)中最大社區(qū)規(guī)模的變化，即最大社區(qū)中的節(jié)點數(shù)。PDG算法具有較小的最大社區(qū)規(guī)模，并且網(wǎng)絡(luò)演化過程中最大社區(qū)較穩(wěn)定。結(jié)合圖3和圖4, PDG算法結(jié)果中具有較多的社區(qū)數(shù)目和較小的最大社區(qū)規(guī)模，充分說明了PDG算法能夠發(fā)現(xiàn)小規(guī)模的社區(qū)。Infomap算法在這一點上也表現(xiàn)出較好的結(jié)果。

圖2 PDG算法與其他算法的結(jié)果對比

圖3 社區(qū)數(shù)目隨網(wǎng)絡(luò)結(jié)構(gòu)變化的對比圖

我們繪制出各算法在不同時間片下穩(wěn)定度指標(biāo)(permanence)的變化，如圖5所示。穩(wěn)定度指標(biāo)下，各算法所表現(xiàn)出的特性與在模塊度指標(biāo)下基本相同。但是各算法在該指標(biāo)下區(qū)分度并不大。LankRankT算法表現(xiàn)出較好的結(jié)果，但仍然會出現(xiàn)較強的震蕩現(xiàn)象。LabelPro算法由于穩(wěn)定度值為負，因此沒有在圖5中畫出。PDG算法和Infomap算法表現(xiàn)出較穩(wěn)定的結(jié)果。

由于基于節(jié)點博弈的方法不易給出確切的時間復(fù)雜度，因此，我們給出PDG算法在AS-Internet網(wǎng)絡(luò)中，對每一個時間片進行社區(qū)劃分的平均時間，并給出Infomap算法的時間以作為基準(zhǔn)。我們給出PDG算法的兩個版本，即不帶優(yōu)化策略的版本PDG-Restart和結(jié)合優(yōu)化策略后的版本PDG-Optimized。PDG算法具有很高的效率，特別是優(yōu) 化策略的使用大大降低了PDG算法的時間復(fù)雜度。

5 結(jié)束語

博弈論是研究個體在博弈過程中如何在競爭與合作間選擇合理策略的理論和方法。網(wǎng)絡(luò)中的個體直接或者間接地尋求自身利益最大化的行為與博弈論的核心思想是一致的。本文提出了一種基于個體穩(wěn)定度博弈的動態(tài)社區(qū)發(fā)現(xiàn)算法。與其他靜態(tài)、動態(tài)社區(qū)發(fā)現(xiàn)算法相比，PDG算法的社區(qū)劃分結(jié)果不僅能夠反映真實的網(wǎng)絡(luò)結(jié)構(gòu)，還可以保持良好的穩(wěn)定性。在模塊度指標(biāo)下，PDG算法較LabelRankT動態(tài)社區(qū)發(fā)現(xiàn)算法的效果提高了23%。此外，效益函數(shù)和優(yōu)化策略的設(shè)計大大提高了PDG算法的效率。如何進一步加快PDG算法的速度和提高算法的精度是下一步的主要研究工作；另外，目前缺少具有真實社區(qū)劃分的動態(tài)網(wǎng)絡(luò)，這影響了動態(tài)社區(qū)劃分結(jié)果的評價。我們將嘗試建立可以生成具有真實社區(qū)劃分的動態(tài)網(wǎng)絡(luò)生成模型。

圖4 最大社區(qū)規(guī)模的對比圖

圖5 穩(wěn)定度指標(biāo)隨網(wǎng)絡(luò)結(jié)構(gòu)變化的對比圖

[1] BARABáSI A and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512. doi: 10.1126/ science.286.5439.509.

[2] WATTS D J, DODDS P S, and NEWMAN M E. Identity and search in social networks[J]., 2002, 296(5571): 1302. doi: 10.1126/science.1070120.

[3] WU X, ZHU X, WU G Q,. Data mining with big data[J].&, 2014, 26(1): 97-107. doi: 10.1109/TKDE.2013.109.

[4] BURKE M, MARLOW C, LENTO T. Social network activity and social well-being[C]. International Conference on Human Factors in Computing Systems, Atlanta, Georgia, USA, 2010: 1909-1912. doi: 10.1145/1753326. 1753613.

[5] GIRVAN M and NEWMAN M E. Community structure in social and biological networks[J]., 2002, 99(12): 7821-7826. doi: 10.1073/pnas.12653799.

[6] FORTUNATO S. Community detection in graphs[J]., 2009, 486(3/5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.

[7] XIN Y, XIE Z Q, YANG J,. An adaptive random walk sampling method on dynamic community detection[J]., 2016, 58: 10-19. doi: 10.1016/ j.eswa.2016.03.033.

[8] PALLA G and VICSEK T. Quantifying social group evolution[J]., 2007, 446(7136): 664-667. doi: 10.1038/ nature05670.

[9] ZAKRZEWSKA A. A dynamic algorithm for local community detection in graphs[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015: 559-564. doi: 10.1145/2808797. 2809375.

[10] NEWMAN M E J. The structure and function of complex networks[J]., 2003, 45(1/2): 40-45. doi: 10.1137 /S003614450342480.

[11] 王莉, 程學(xué)旗. 在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計算機學(xué)報, 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015. 00219.

WANG Li and CHENG Xueqi. Dynamic community in online social networksp[J]., 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015.00219.

[12] CHAKRABORTY T, SRINIVASAN S, GANGULY N,. On the permanence of vertices in network communities[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, USA, 2014: 1396-1405. doi: 10. 1145/2623330.2623707.

[13] NEWMAN M E. Modularity and community structure in networks[J]., 2006, 103(23): 8577-8582. doi: 10.1073/pnas.0601602103.

[14] CHEN M, KUZMIN K, SZYMANSKI B K,. Community detection via maximization of modularity and its variants[J]., 2015, 1(1): 46-65. doi: 10.1109/TCSS.2014.2307458.

[15] PALLA G, DERéNYI I, FARKAS I,. Uncovering the overlapping community structure of complex networks in nature and society[J]., 2005, 435(7043): 814-818. doi: 10.1038/nature03607.

[16] ROSVALL M and BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]., 2008, 105(4): 1118-1123. doi: 10.1073/ pnas.0706851105.

[17] HELD P, KRAUSE B, KRUSE R,. Dynamic clustering in social networks using Louvain and Infomap method[J]., 2016, arXiv: 1603.02413.

[18] RAGHAVAN U N, ALBERT R, KUMARA S,. Near linear time algorithm to detect community structures in large-scale networks[J].&, 2007, 76(3 Pt 2): 036106. doi: 10.1103/PhysRevE.76.036106.

[19] ALVARI H, HASHEMI S, and HAMZEH A. Detecting Overlapping Communities in Social Networks by Game Theory and Structural Equivalence Concept[M]. Iran, Springer Berlin Heidelberg, 2011: 620-630. doi: 10.1007/978- 3-642-23887-1_79.

[20] 冷作福. 基于貪婪優(yōu)化技術(shù)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究[J]. 電子學(xué)報, 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112. 2014.04.016.

LENG Zuofu. Community detection in complex networks based on greedy optimization[J]., 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112.2014.04. 016.

[21] XIE J, KELLEY S, SZYMANSKI B K,Overlapping community detection in networks: The state-of-the-art and comparative study[J]., 2011, 45(4): 115-123. doi: 10.1145/2501654.2501669.

[22] SUN J, FALOUTSOS C, PAPADIMITRIOU S,. GraphScope: Parameter-free mining of large time-evolving graphs[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, 2007: 687-696. doi: 10.1145/1281192.1281266.

[23] XIE J, CHEN M, and SZYMANSKI B K. LabelRankT: Incremental community detection in dynamic networks via label propagation[C]. The Workshop on Dynamic Networks Management and Mining, 2013: 25-32. doi: 10.1145/2489247. 2489249.

[24] CAZABET R, AMBLARD F, HANACHI C,. Detection of overlapping communities in dynamical social networks[C]. IEEE Second International Conference on Social Computing, Socialcom/IEEE International Conference on Privacy, Security, Risk and Trust, Passat 2010, Minneapolis, Minnesota, USA, 2010: 309-314. doi: 10.1109/SocialCom. 2010.51.

[25] LIN Y R, CHI Y, ZHU S,. FacetNet: A framework for analyzing communities and their evolutions in dynamic networks[C]. Proceedings of the 17th International Conference on World Wide Web, Beijing, China, 2008: 685-694. doi: 10.1145/1367497.1367590.

[26] L? Q D, YONG H C, SOONG B H,. An Introduction to Game Theory[M]. Switzerland, Potential Game Theory. Springer International Publishing, 2016, Chapter 1. doi: 1007/978-3-319-30869-2_1.

[27] NEWMAN M E and GIRVAN M. Finding and evaluating community structure in networks[J].&, 2004, 69(2 Pt 2): 026113-026113. doi: 10.1103/PhysRevE.69.026113.

[28] BARTHELEMY M and FORTUNATO S. Resolution limit in community detection[J]., 2007, 104(1): 36-41. doi: 10.1073/pnas.0605965104.

[29] AGARWAL G and KEMPE D. Modularity-maximizing graph communities via mathematical programming[J].er, 2008, 66(3): 409-418. doi: 10. 1140/epjb/e2008-00425-1.

[30] CAI S and SU K. Local search for Boolean satisfiability with configuration checking and subscore[J]., 2013, 204(9): 75-98. doi: 10.1016/j.artint.2013.09.001.

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

XU Yuguang①JIANG Fei①ZHU Enqiang①PAN Jingzhi①XIE Huiyang②

①(,,100871,)②(,,100083,)

In dynamic networks, detecting community structure is a complicated and vital issue. With respect to the community detection problem in dynamic networks, a novel game-theoretic algorithm based on the permanence of agents called Permanence Dynamic Game (PDG) is proposed. In PDG algorithm, each node in the dynamic network is regarded as a self-fish agent. Every agent chooses the best response strategy to select communities he will belong to according to the statuses of other agents. For the evolution of community structure in dynamic networks, the optimization strategy of configuration checking is applied. The configuration checking strategy have many improves the efficiency of the original algorithm. Finally, to verify the effectiveness and efficiency of the proposed method, the method is compared with the state-of-art community detection algorithms on real dynamic networks.

Dynamic community detection; Permanence; Modularity; Game theory; Configuration checking

TP393

A

1009-5896(2017)04-0763-07

10.11999/JEIT161077

2016-10-13；

改回日期：2017-02-22；

2017-03-07

謝惠揚 xhyang@bjfu.edu.cn

國家重點研發(fā)計劃項目(2016YFB0800700)

National Key Research and Development Project of China (2016YFB0800700)

許宇光： 男，1984年生，博士，研究方向為計算機軟件與理論.

蔣 飛： 男，1989年生，博士，研究方向為計算機軟件與理論.

朱恩強： 男，1983年生，博士，研究方向為計算機軟件與理論.

潘驚治： 女，1992年生，碩士，研究方向為社交網(wǎng)絡(luò).

謝惠揚： 女，1963年生，教授，研究方向為應(yīng)用數(shù)學(xué).