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

1 引言

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

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

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

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

2 算法描述

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

2.1 社區(qū)劃分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法時間復雜度分析

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

3 實驗與結果分析

3.1 數據集和評價指標

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

表1 真實網絡數據集

GCC評價指標定義如式（1）.

其中，NGCC是最大連通分支GCC 中的節(jié)點數量，n是網絡節(jié)點總數.

代價Cost 表示完成網絡分解需要刪除的連邊數量占整個網絡連邊總數的比例：

其中，dl 是分解過程中被刪除的連邊數量，m是網絡的連邊總數.

3.2 真實網絡實驗結果分析

3.2.1 與基于節(jié)點刪除的網絡分解方法性能對比

實驗中選取5種基于節(jié)點刪除的網絡分解算法，包括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)的方法，相關參數均按照原文的最優(yōu)值進行設置：Min-Sum 算法第一個閾值C1=0.5%，第二個閾值C2=1%.BPD權重參數x=12.

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

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

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

表2 CD?IRE算法與基于節(jié)點刪除的網絡分解方法Cost對比

3.2.2 與基于連邊刪除的網絡分解方法性能比較

實驗中選取4種基于連邊刪除的網絡分解算法，分別是Ncut算法［11］、Bond percolation 算法［18］、Betweenness算法［10］和Bridgeness算法［9］.

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

圖3 CD-IRE算法與基于節(jié)點刪除的網絡分解方法性能對比

圖4 CD-IRE算法與基于連邊刪除的網絡分解方法性能對比

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

3.2.3 GCC閾值對網絡分解算法性能的影響

此處選取上述實驗中性能突出的CD-IRE 算法、GNDR 算法、Min-Sum 算法、BPD 算法和Ncut 算法，分析GCC 閾值對網絡分解算法性能的影響. 選取的真實網絡包括PPI、Power-Grid 和Authors. GCC 的閾值分別設定為0.2、0.4、0.6和0.8.

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

表3 CD?IRE算法與基于連邊刪除的網絡分解方法Cost對比

3.3 人工網絡實驗結果分析

3.3.1 ER網絡

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

GCC 閾值為0.01. 考慮到所生成人工網絡的隨機性，實驗取48 次結果的平均值.

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

圖5 ER人工網絡上的實驗結果

表4 GCC閾值對網絡分解算法性能的影響（PPI網絡）

表5 GCC閾值對網絡分解算法性能的影響（Power-Grid網絡）

表6 GCC閾值對網絡分解算法性能的影響（Authors網絡）

3.3.2 BA網絡

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

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

圖6 BA人工網絡上的實驗結果

4 結論

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