基于社區(qū)劃分與連邊逆序放回的網(wǎng)絡(luò)分解算法

王志曉，張磊，孫成成，芮曉彬，黃珍珍，3，張孫賢

1 引言

影響力最大化［1，2］和網(wǎng)絡(luò)分解［3］是社交網(wǎng)絡(luò)分析領(lǐng)域兩個(gè)重要的研究分支，前者通過選擇種子節(jié)點(diǎn)進(jìn)行信息傳播，使得最終的影響范圍最大. 后者則通過刪除網(wǎng)絡(luò)中最小規(guī)模的節(jié)點(diǎn)或連邊，將網(wǎng)絡(luò)破壞成一系列小規(guī)模、不連通的分支. 網(wǎng)絡(luò)分解可以應(yīng)用于輿情控制［4］，蛋白質(zhì)結(jié)構(gòu)解析以及交通線路防護(hù)［5，6］等領(lǐng)域.

網(wǎng)絡(luò)分解算法主要有兩類：基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解算法［3，4，7，8］和基于連邊刪除的網(wǎng)絡(luò)分解算法［9，11］. 前者利用中心性指標(biāo)迭代刪除網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，直到網(wǎng)絡(luò)中最大連通分支［7］（Giant Connected Components，GCC）的規(guī)模小于事先設(shè)定的閾值. 大多數(shù)研究將該閾值設(shè)定為整個(gè)網(wǎng)絡(luò)規(guī)模的0.01［7，8］. 現(xiàn)有基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解方法大多不考慮刪除代價(jià).Ren 等人［4］指出網(wǎng)絡(luò)分解過程中每個(gè)節(jié)點(diǎn)的刪除代價(jià)是不同的，節(jié)點(diǎn)度值越大，連邊越多，其刪除代價(jià)越大. 基于連邊刪除的網(wǎng)絡(luò)分解方法是一類考慮刪除代價(jià)的方法，該類方法迭代刪除影響網(wǎng)絡(luò)連通性的關(guān)鍵連邊，直到網(wǎng)絡(luò)中最大連通分支的規(guī)模小于事先設(shè)定的閾值. 大多數(shù)此類研究也將閾值設(shè)定為0.01［9，11］. 基于連邊刪除的網(wǎng)絡(luò)分解可以進(jìn)一步細(xì)分為基于邊中心性指標(biāo)的方法［9］和基于最大連通分量劃分的方法［11］. 基于連邊刪除的網(wǎng)絡(luò)分解方法存在以下不足：（1）基于邊中心性指標(biāo)的方法需要在整個(gè)網(wǎng)絡(luò)范圍內(nèi)計(jì)算每條連邊的中心性值，復(fù)雜性較高，不適合大規(guī)模網(wǎng)絡(luò)；（2）基于最大連通分量劃分的方法需要迭代劃分網(wǎng)絡(luò)中的最大連通分支，連邊刪除缺乏針對(duì)性，容易刪除一些不必要的連邊.

社區(qū)劃分技術(shù)已經(jīng)成功應(yīng)用于社區(qū)結(jié)構(gòu)識(shí)別［12，13］以及蛋白質(zhì)復(fù)合物識(shí)別［14，15］等諸多領(lǐng)域. 在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)中，社區(qū)內(nèi)節(jié)點(diǎn)間的連邊稠密，不同社區(qū)間的連邊稀疏. 如果先利用社區(qū)劃分技術(shù)對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，就可以區(qū)分出社區(qū)內(nèi)的連邊和社區(qū)間的連邊，針對(duì)兩類連邊的特點(diǎn)分別進(jìn)行處理，從而達(dá)到快速分解網(wǎng)路的目的. 鑒于此，本文將社區(qū)劃分技術(shù)與連邊逆序放回策略相結(jié)合，提出了一種基于連邊刪除的網(wǎng)絡(luò)分解算法CD-IRE（Network Dismantling Based on Community Detection and Inverse Reinsertion of Edges）. 首先，利用社區(qū)劃分算法挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu). 社區(qū)劃分不但能將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)小規(guī)模的社區(qū)，而且能有效識(shí)別影響社區(qū)間連通性的連邊，刪除這些連邊即可將網(wǎng)絡(luò)分解為多個(gè)獨(dú)立的社區(qū). 然后，采用逆序放回策略進(jìn)行社區(qū)內(nèi)的分解：先移除社區(qū)內(nèi)的所有連邊，接著依次放回使社區(qū)內(nèi)部GCC 規(guī)模增長(zhǎng)最小的連邊，直到放回任何一條連邊都會(huì)使社區(qū)內(nèi)GCC 規(guī)模超過設(shè)定閾值.最后，刪除那些未被放回的連邊，即可完成社區(qū)分解，進(jìn)而實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的分解. 逆序放回策略能準(zhǔn)確識(shí)別并刪除對(duì)社區(qū)內(nèi)GCC 增長(zhǎng)貢獻(xiàn)最大的連邊，從而有效破壞社區(qū)內(nèi)部的連通性.

真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，相比較于其他典型網(wǎng)絡(luò)分解算法，本文方法刪除較小規(guī)模的連邊就能將網(wǎng)絡(luò)分解至設(shè)定閾值；人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，隨著網(wǎng)絡(luò)規(guī)模的變化、網(wǎng)絡(luò)結(jié)構(gòu)的變化以及GCC 閾值的變化，本文方法均表現(xiàn)出較強(qiáng)的穩(wěn)定性.

2 算法描述

首先，挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，刪除社區(qū)之間的所有連邊，使網(wǎng)絡(luò)分解成一個(gè)個(gè)互不相連的局部區(qū)域. 然后，采用逆序放回策略分解每個(gè)社區(qū)，最終實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的分解.

2.1 社區(qū)劃分

Louvain［16］是一種基于模塊度的社區(qū)劃分方法，具有準(zhǔn)確性高、復(fù)雜度低等優(yōu)點(diǎn). 本文借鑒Louvain 算法思想完成社區(qū)結(jié)構(gòu)挖掘. 首先，將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都分配到不同的社區(qū)中，對(duì)每一個(gè)節(jié)點(diǎn)i，計(jì)算將它加入到其鄰居節(jié)點(diǎn)所在社區(qū)所帶來的模塊度變化，加入模塊度增益最大的社區(qū). 若加入所有鄰居節(jié)點(diǎn)所在社區(qū)的模塊度增益均為0，則節(jié)點(diǎn)i保持在原來的社區(qū)內(nèi).重復(fù)上述操作，直到網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)不再變化為止. 劃分社區(qū)后，連接不同社區(qū)的連邊清晰地顯露出來，刪除這些連邊即可以最小的代價(jià)快速地將整個(gè)網(wǎng)絡(luò)分解為一個(gè)個(gè)小規(guī)模的局部區(qū)域，從而極大地破壞整個(gè)網(wǎng)絡(luò)的連通性.

如圖1所示，劃分出的社區(qū)C1和C2內(nèi)部的連邊非常密集，兩個(gè)社區(qū)則通過邊E連接在一起. 僅僅刪除邊E就可以徹底破壞社區(qū)C1和C2間的連通性，邊E即是具有非常強(qiáng)連通性的連邊［9］，起連接兩個(gè)連邊密集社區(qū)的作用.

圖1 社區(qū)間的連邊示意圖

2.2 社區(qū)內(nèi)部連邊逆序放回

破壞社區(qū)間的連通性后，需要進(jìn)一步破壞每個(gè)社區(qū)內(nèi)部的連通性才能完成整個(gè)網(wǎng)絡(luò)的分解. 本文采用一種逆向策略來解決這一問題，即連邊逆序放回IRE（Inverse Reinsertion of Edges），該策略依次放回對(duì)社區(qū)內(nèi)連通性影響最小的連邊直到GCC超過事先設(shè)定的閾值.

連邊逆序放回策略的步驟如下：

步驟1：將社區(qū)i內(nèi)部的連邊全部刪除放入集合E0（i）中，社區(qū)中僅剩下一個(gè)個(gè)互不相連的孤立節(jié)點(diǎn)；

步驟2：從集合E0（i）中選擇一條使社區(qū)內(nèi)GCC 規(guī)模增長(zhǎng)最小的連邊放回社區(qū)；

步驟3：若存在多條連邊放回后都能使GCC規(guī)模增長(zhǎng)最小，則從這些連邊中選擇兩端所連節(jié)點(diǎn)度值之和最小的連邊放回社區(qū)；

步驟4：若滿足步驟3的連邊仍然有多條，則從這些連邊中選擇兩端所連節(jié)點(diǎn)度值之差絕對(duì)值最小的連邊放回社區(qū)；

步驟5：重復(fù)步驟1~4，直到從E0（i）中選擇任何一條連邊放回原社區(qū)都會(huì)使社區(qū)內(nèi)GCC 的規(guī)模大于設(shè)定閾值.

步驟6：刪除E0（i）集合中的剩余連邊，完成社區(qū)內(nèi)的分解.

上述逆序放回策略盡可能地將位于社區(qū)邊緣、連接節(jié)點(diǎn)度值較小，且對(duì)社區(qū)內(nèi)部連通性影響小的連邊保留下來，從而最大限度地刪除處于中心位置、連接節(jié)點(diǎn)度值較大、對(duì)社區(qū)內(nèi)部連通性影響較大的連邊.

下面舉例說明逆序放回策略的執(zhí)行過程. 圖2狀態(tài)1是一個(gè)節(jié)點(diǎn)規(guī)模為400的網(wǎng)絡(luò)劃分完社區(qū)之后得到的一個(gè)社區(qū)，該社區(qū)包含6個(gè)節(jié)點(diǎn)和10條連邊，每條連邊旁邊的數(shù)字表示該連邊的編號(hào).GCC的閾值設(shè)定為0.01. 采用逆序放回策略的第一步是將全部連邊放入E0，此時(shí)，放回任何一條連邊GCC規(guī)模的增長(zhǎng)都相同，因此，按照步驟3選擇兩端所連節(jié)點(diǎn)的度值之和最小的連邊，即編號(hào)為1的連邊，將其首先放回. 以此類推，后面依次放回編號(hào)為4，7，3，8，9，10的連邊. 此后，如果繼續(xù)放回，則GCC的規(guī)模將大于設(shè)定的閾值0.01，放回過程結(jié)束. 此時(shí)，E0中剩余的連邊為｛2，5，6｝，予以刪除，從而完成對(duì)該社區(qū)的分解，見圖2狀態(tài)2. 算法描述如算法1所示.

圖2 連邊逆序放回過程示意圖

2.3 算法時(shí)間復(fù)雜度分析

本文所提出的網(wǎng)絡(luò)分解算法包含兩個(gè)階段：社區(qū)劃分和連邊逆序放回. 社區(qū)劃分階段采用Louvain 算法將整個(gè)網(wǎng)絡(luò)劃分為k個(gè)社區(qū)，刪除社區(qū)間的所有連邊，時(shí)間復(fù)雜度是O(N+N′)，N是網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模，N′是迭代節(jié)點(diǎn)的個(gè)數(shù). 逆序放回階段，完成單個(gè)社區(qū)i分解的時(shí)間復(fù)雜度是O(miNi)，mi表示社區(qū)i內(nèi)的連邊數(shù)量，Ni代表社區(qū)i內(nèi)的節(jié)點(diǎn)數(shù)量. 在最壞情況下，k個(gè)社區(qū)都需要進(jìn)行分解，那么，完成k個(gè)社區(qū)連邊逆序放回的時(shí)間復(fù)雜度就是這樣一來，整個(gè)算法的時(shí)間復(fù)雜度為

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

3.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)所用數(shù)據(jù)包括真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò). 真實(shí)網(wǎng)絡(luò)如表1所示，n代表網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模，從幾百到幾萬不等.m代表網(wǎng)絡(luò)連邊總數(shù)，c代表網(wǎng)絡(luò)節(jié)點(diǎn)的平均連邊數(shù)（平均度值）. 人工網(wǎng)絡(luò)有兩類，一類是ER（Erd?s-Rényi）人工網(wǎng)絡(luò)，節(jié)點(diǎn)規(guī)模分別是2000、4000、6000 和10000，對(duì)于給定規(guī)模的ER網(wǎng)絡(luò)，平均連邊數(shù)（平均度值）c的變化區(qū)間為［3，10］. 另一類是BA（Barabási-Albert）人工網(wǎng)絡(luò)，節(jié)點(diǎn)規(guī)模最小是1000，最大是10000，對(duì)于給定規(guī)模的BA網(wǎng)絡(luò)，平均連邊數(shù)（平均度值）c的取值為4、6和8. 真實(shí)網(wǎng)絡(luò)來源于http：//konect.uni-koblenz.de/，評(píng)價(jià)指標(biāo)包括最大連通分支規(guī)模GCC和網(wǎng)絡(luò)分解代價(jià)Cost.

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

GCC評(píng)價(jià)指標(biāo)定義如式（1）.

其中，NGCC是最大連通分支GCC 中的節(jié)點(diǎn)數(shù)量，n是網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù).

代價(jià)Cost 表示完成網(wǎng)絡(luò)分解需要?jiǎng)h除的連邊數(shù)量占整個(gè)網(wǎng)絡(luò)連邊總數(shù)的比例：

其中，dl 是分解過程中被刪除的連邊數(shù)量，m是網(wǎng)絡(luò)的連邊總數(shù).

3.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

3.2.1 與基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解方法性能對(duì)比

實(shí)驗(yàn)中選取5種基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解算法，包括GND（Generalized Network Dismantling）算法［4］、GN?DR（Generalized Network Dismantling with Reinsertion）算法［4］、EGP（Equal Graph Partitioning）算法［17］、Min-Sum 算法［3］和BPD（Belief Propagation-guided Decimation）算法［7］.Min-Sum和BPD是典型的基于去環(huán)的方法，相關(guān)參數(shù)均按照原文的最優(yōu)值進(jìn)行設(shè)置：Min-Sum 算法第一個(gè)閾值C1=0.5%，第二個(gè)閾值C2=1%.BPD權(quán)重參數(shù)x=12.

首先，分析最大連通分支規(guī)模GCC 隨刪除代價(jià)Cost 增大的變化情況. 圖3 顯示了所選算法在Crime 和Power-Grid 網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，橫坐標(biāo)代表網(wǎng)絡(luò)分解代價(jià)Cost，縱坐標(biāo)代表最大連通分支規(guī)模GCC. 從圖3可以看出，隨著網(wǎng)絡(luò)分解代價(jià)Cost 的增大（刪除連邊的數(shù)量增多），最大連通分支規(guī)模GCC 呈現(xiàn)下降趨勢(shì). 相對(duì)于其他5種算法，CD-IRE算法刪除較小規(guī)模的連邊就能最大限度地破壞網(wǎng)絡(luò)的連通性，性能最優(yōu). 以Crime 網(wǎng)絡(luò)為例，CD-IRE 算法僅花費(fèi)不到0.1%的代價(jià)就可以將網(wǎng)絡(luò)分解至GCC 小于0.1，GND 算法實(shí)現(xiàn)這個(gè)目標(biāo)需要0.2%的代價(jià)，其余4種算法的代價(jià)均超過0.5.

CD-IRE算法在Power-Grid網(wǎng)絡(luò)上的這一優(yōu)勢(shì)表現(xiàn)得更為突出.

然后，進(jìn)一步分析達(dá)到網(wǎng)絡(luò)分解閾值（即0.01）時(shí)不同網(wǎng)絡(luò)分解算法需要的刪除代價(jià)Cost. 表2顯示了上述6 種算法分解Crime、Corruption、Petster-hamster、Power-Grid、Political Blogs 和Autonomous Systems 網(wǎng)絡(luò)所需要的代價(jià)Cost. 可以看出，本文的CD-IRE 算法只需要?jiǎng)h除較小規(guī)模的連邊就可以完成對(duì)6個(gè)網(wǎng)絡(luò)的分解，表現(xiàn)出最好的性能. GNDR 算法也表現(xiàn)出了不錯(cuò)的性能，BPD 算法緊隨其后. 另外，從表2 可以看出，無論何種算法，分解Corruption 網(wǎng)絡(luò)和Political Blogs 網(wǎng)絡(luò)的代價(jià)Cost都超過0.92，原因是這兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的平均連邊數(shù)（平均度值）非常大，分別達(dá)到了21.24 和27.36（見表1），從而導(dǎo)致網(wǎng)絡(luò)分解的難度較大.

表2 CD?IRE算法與基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解方法Cost對(duì)比

3.2.2 與基于連邊刪除的網(wǎng)絡(luò)分解方法性能比較

實(shí)驗(yàn)中選取4種基于連邊刪除的網(wǎng)絡(luò)分解算法，分別是Ncut算法［11］、Bond percolation 算法［18］、Betweenness算法［10］和Bridgeness算法［9］.

首先，分析最大連通分支規(guī)模GCC 隨刪除代價(jià)Cost 增大的變化情況. 圖4 顯示了所選算法在Autono?mous-Systems 和Petster-hamster 網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果. 隨著Cost 的增加，CD-IRE 算法的GCC 值快速下降，這一現(xiàn)象與圖3 中的結(jié)果類似，說明刪除社區(qū)間的連邊可以極大地破壞整個(gè)網(wǎng)絡(luò)的連通性.Ncut 算法采用了譜平分思想，每次迭代將網(wǎng)絡(luò)近似分為大小相等的兩部分，因此Ncut 算法也能使GCC 值快速下降.CD-IRE 算法刪除當(dāng)前社區(qū)的全部外部連邊后才會(huì)更新GCC 的值，因此會(huì)導(dǎo)致GCC 值的更新略微滯后. 總體而言，CD-IRE 算法和Ncut 算法性能接近，明顯優(yōu)于Bond per?colation 算法、Betweenness 算法和Bridgeness 算法.

圖3 CD-IRE算法與基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解方法性能對(duì)比

圖4 CD-IRE算法與基于連邊刪除的網(wǎng)絡(luò)分解方法性能對(duì)比

然后，進(jìn)一步分析達(dá)到網(wǎng)絡(luò)分解閾值0.01 時(shí)不同網(wǎng)絡(luò)分解算法需要的刪除代價(jià)Cost. 表3 顯示了上述5種算 法分 解Crime、Corruption、Petster-hamster、Power-Grid、Political Blogs 和Autonomous Systems 網(wǎng)絡(luò)所需要的代價(jià)Cost. CD-IRE 算法在Crime、Corruption、Political Blogs 和Autonomous Systems 等4 個(gè)網(wǎng)絡(luò)上表現(xiàn)出最好的性能，在Petster-hamster 和Power-Grid 網(wǎng)絡(luò)上的性能僅次于Ncut 算法，這一結(jié)果與圖4 中對(duì)CD-IRE 算法和Ncut算法性能的分析一致.

3.2.3 GCC閾值對(duì)網(wǎng)絡(luò)分解算法性能的影響

此處選取上述實(shí)驗(yàn)中性能突出的CD-IRE 算法、GNDR 算法、Min-Sum 算法、BPD 算法和Ncut 算法，分析GCC 閾值對(duì)網(wǎng)絡(luò)分解算法性能的影響. 選取的真實(shí)網(wǎng)絡(luò)包括PPI、Power-Grid 和Authors. GCC 的閾值分別設(shè)定為0.2、0.4、0.6和0.8.

表4~表6分別展示了所選算法在PPI、Power-Grid和Authors 網(wǎng)絡(luò)上的Cost 值. 可以看出，隨著GCC 閾值變小，網(wǎng)絡(luò)分解標(biāo)準(zhǔn)逐漸提高，絕大多數(shù)算法的Cost 呈現(xiàn)增大趨勢(shì). 在PPI網(wǎng)絡(luò)中，CD-IRE算法和Ncut算法性能相當(dāng)，優(yōu)于其他算法. 在Power-Grid 網(wǎng)絡(luò)中，CD-IRE 算法最優(yōu)，GNDR 算法緊隨其后. Ncut 算法以0.0302 的Cost代價(jià)直接將Power-Grid網(wǎng)絡(luò)的GCC降至0.2以下，因此0.2以上的閾值變化對(duì)該算法沒有影響（見表5）. 總體而言，隨著GCC閾值的變化，CD-IRE算法始終能夠保持良好的性能，以較小的代價(jià)完成網(wǎng)絡(luò)分解.

表3 CD?IRE算法與基于連邊刪除的網(wǎng)絡(luò)分解方法Cost對(duì)比

3.3 人工網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果分析

3.3.1 ER網(wǎng)絡(luò)

此處選取上述實(shí)驗(yàn)中性能突出的CD-IRE 算法、GND 算法、GNDR 算法和Ncut 算法，分析網(wǎng)絡(luò)規(guī)模和結(jié)構(gòu)特性對(duì)其性能的影響.ER 網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模分別取2000、4000、6000 和10000，平均連邊數(shù)（平均度值）c從3 變化到10，步長(zhǎng)為1.

GCC 閾值為0.01. 考慮到所生成人工網(wǎng)絡(luò)的隨機(jī)性，實(shí)驗(yàn)取48 次結(jié)果的平均值.

圖5 顯示了ER 網(wǎng)絡(luò)上的相應(yīng)結(jié)果. 在不同的網(wǎng)絡(luò)規(guī)模下，隨著平均連邊數(shù)（平均度值）c的增大，網(wǎng)絡(luò)分解的代價(jià)Cost逐漸增加. 很顯然，節(jié)點(diǎn)鄰居數(shù)量變多增大了網(wǎng)絡(luò)分解的難度. 但是，無論節(jié)點(diǎn)規(guī)模和平均連邊數(shù)（平均度值）c如何變化，CD-IRE 算法和Ncut 算法均表現(xiàn)出良好的性能，優(yōu)于其他算法. 另外，從這兩種算法曲線的位置變化可以看出，它們對(duì)網(wǎng)絡(luò)規(guī)模不敏感.

圖5 ER人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

表4 GCC閾值對(duì)網(wǎng)絡(luò)分解算法性能的影響（PPI網(wǎng)絡(luò)）

表5 GCC閾值對(duì)網(wǎng)絡(luò)分解算法性能的影響（Power-Grid網(wǎng)絡(luò)）

表6 GCC閾值對(duì)網(wǎng)絡(luò)分解算法性能的影響（Authors網(wǎng)絡(luò)）

3.3.2 BA網(wǎng)絡(luò)

BA 網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模在1000 至10000 間遞增，每次增加1000個(gè)節(jié)點(diǎn). 平均連邊數(shù)（平均度值）c分別取4、6和8. 考慮到Ncut算法和CD-IRE算法性能最接近，此處僅分析這兩種算法在BA網(wǎng)絡(luò)上的性能.

同樣地，圖6 顯示了48 組實(shí)驗(yàn)的平均值. CD-IREc4中的“c4”表示平均連邊數(shù)（平均度值）為4，其余曲線標(biāo)識(shí)的含義類似. 可以看出，兩種算法在BA 網(wǎng)絡(luò)上的性能非常穩(wěn)定. 當(dāng)平均連邊數(shù)（平均度值）c為6和8時(shí)，CD-IRE 算法的性能優(yōu)于Ncut 算法. 當(dāng)平均連邊數(shù)（平均度值）c為4時(shí)，兩個(gè)算法的性能相當(dāng).

圖6 BA人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

4 結(jié)論

網(wǎng)絡(luò)分解是社交網(wǎng)絡(luò)分析中的重要問題，其研究成果在很多領(lǐng)域都有著廣泛應(yīng)用，包括控制計(jì)算機(jī)病毒在通信網(wǎng)絡(luò)中的傳播范圍、干預(yù)謠言在社交網(wǎng)絡(luò)中的擴(kuò)散程度等［19，20］. 本文提出了基于社區(qū)發(fā)現(xiàn)與連邊逆序放回的網(wǎng)絡(luò)分解算法，該算法借助社區(qū)劃分將網(wǎng)絡(luò)分解為若干個(gè)局部社區(qū)，刪除社區(qū)間的連邊，破壞社區(qū)間的連通性. 然后，采用逆序放回策略，以最小的代價(jià)進(jìn)一步破壞社區(qū)內(nèi)部的連通性，最終完成對(duì)整個(gè)網(wǎng)絡(luò)的分解. 實(shí)驗(yàn)結(jié)果表明，本文算法以刪除較小規(guī)模的連邊為代價(jià)，就能將網(wǎng)絡(luò)分解至事先設(shè)定閾值. 并且，隨著網(wǎng)絡(luò)規(guī)模的變化、網(wǎng)絡(luò)結(jié)構(gòu)的變化以及設(shè)定閾值的變化表現(xiàn)出較強(qiáng)的穩(wěn)定性.