許宇光 蔣 飛 朱恩強(qiáng) 潘驚治 謝惠揚(yáng)

?

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

許宇光①蔣 飛①朱恩強(qiáng)①潘驚治①謝惠揚(yáng)*②

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

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

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

1 引言

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

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

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

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

2 基本概念與記號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 PDG算法

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

[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é)旗. 在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計(jì)算機(jī)學(xué)報(bào), 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é)報(bào), 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

謝惠揚(yáng) xhyang@bjfu.edu.cn

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0800700)

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

許宇光： 男，1984年生，博士，研究方向?yàn)橛?jì)算機(jī)軟件與理論.

蔣 飛： 男，1989年生，博士，研究方向?yàn)橛?jì)算機(jī)軟件與理論.

朱恩強(qiáng)： 男，1983年生，博士，研究方向?yàn)橛?jì)算機(jī)軟件與理論.

潘驚治： 女，1992年生，碩士，研究方向?yàn)樯缃痪W(wǎng)絡(luò).

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