国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2022-05-11 08:26王志曉張磊孫成成芮曉彬黃珍珍張孫賢
電子學(xué)報 2022年3期
關(guān)鍵詞:度值連通性代價

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

1 引言

影響力最大化[1,2]和網(wǎng)絡(luò)分解[3]是社交網(wǎng)絡(luò)分析領(lǐng)域兩個重要的研究分支,前者通過選擇種子節(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è)定為整個網(wǎng)絡(luò)規(guī)模的0.01[7,8]. 現(xiàn)有基于節(jié)點(diǎn)刪除的網(wǎng)絡(luò)分解方法大多不考慮刪除代價.Ren 等人[4]指出網(wǎng)絡(luò)分解過程中每個節(jié)點(diǎn)的刪除代價是不同的,節(jié)點(diǎn)度值越大,連邊越多,其刪除代價越大. 基于連邊刪除的網(wǎng)絡(luò)分解方法是一類考慮刪除代價的方法,該類方法迭代刪除影響網(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)的方法需要在整個網(wǎng)絡(luò)范圍內(nèi)計算每條連邊的中心性值,復(fù)雜性較高,不適合大規(guī)模網(wǎng)絡(luò);(2)基于最大連通分量劃分的方法需要迭代劃分網(wǎng)絡(luò)中的最大連通分支,連邊刪除缺乏針對性,容易刪除一些不必要的連邊.

社區(qū)劃分技術(shù)已經(jīng)成功應(yīng)用于社區(qū)結(jié)構(gòu)識別[12,13]以及蛋白質(zhì)復(fù)合物識別[14,15]等諸多領(lǐng)域. 在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)中,社區(qū)內(nèi)節(jié)點(diǎn)間的連邊稠密,不同社區(qū)間的連邊稀疏. 如果先利用社區(qū)劃分技術(shù)對網(wǎng)絡(luò)進(jìn)行社區(qū)劃分,就可以區(qū)分出社區(qū)內(nèi)的連邊和社區(qū)間的連邊,針對兩類連邊的特點(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ū)劃分不但能將整個網(wǎng)絡(luò)劃分為多個小規(guī)模的社區(qū),而且能有效識別影響社區(qū)間連通性的連邊,刪除這些連邊即可將網(wǎng)絡(luò)分解為多個獨(dú)立的社區(qū). 然后,采用逆序放回策略進(jìn)行社區(qū)內(nèi)的分解:先移除社區(qū)內(nèi)的所有連邊,接著依次放回使社區(qū)內(nèi)部GCC 規(guī)模增長最小的連邊,直到放回任何一條連邊都會使社區(qū)內(nèi)GCC 規(guī)模超過設(shè)定閾值.最后,刪除那些未被放回的連邊,即可完成社區(qū)分解,進(jìn)而實現(xiàn)整個網(wǎng)絡(luò)的分解. 逆序放回策略能準(zhǔn)確識別并刪除對社區(qū)內(nèi)GCC 增長貢獻(xiàn)最大的連邊,從而有效破壞社區(qū)內(nèi)部的連通性.

真實網(wǎng)絡(luò)上的實驗結(jié)果表明,相比較于其他典型網(wǎng)絡(luò)分解算法,本文方法刪除較小規(guī)模的連邊就能將網(wǎng)絡(luò)分解至設(shè)定閾值;人工網(wǎng)絡(luò)上的實驗結(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ò)分解成一個個互不相連的局部區(qū)域. 然后,采用逆序放回策略分解每個社區(qū),最終實現(xiàn)對整個網(wǎng)絡(luò)的分解.

2.1 社區(qū)劃分

Louvain[16]是一種基于模塊度的社區(qū)劃分方法,具有準(zhǔn)確性高、復(fù)雜度低等優(yōu)點(diǎn). 本文借鑒Louvain 算法思想完成社區(qū)結(jié)構(gòu)挖掘. 首先,將網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都分配到不同的社區(qū)中,對每一個節(jié)點(diǎn)i,計算將它加入到其鄰居節(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ū)的連邊清晰地顯露出來,刪除這些連邊即可以最小的代價快速地將整個網(wǎng)絡(luò)分解為一個個小規(guī)模的局部區(qū)域,從而極大地破壞整個網(wǎng)絡(luò)的連通性.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 數(shù)據(jù)集和評價指標(biāo)

實驗所用數(shù)據(jù)包括真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò). 真實網(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,對于給定規(guī)模的ER網(wǎng)絡(luò),平均連邊數(shù)(平均度值)c的變化區(qū)間為[3,10]. 另一類是BA(Barabási-Albert)人工網(wǎng)絡(luò),節(jié)點(diǎn)規(guī)模最小是1000,最大是10000,對于給定規(guī)模的BA網(wǎng)絡(luò),平均連邊數(shù)(平均度值)c的取值為4、6和8. 真實網(wǎng)絡(luò)來源于http://konect.uni-koblenz.de/,評價指標(biāo)包括最大連通分支規(guī)模GCC和網(wǎng)絡(luò)分解代價Cost.

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

GCC評價指標(biāo)定義如式(1).

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

代價Cost 表示完成網(wǎng)絡(luò)分解需要刪除的連邊數(shù)量占整個網(wǎng)絡(luò)連邊總數(shù)的比例:

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

3.2 真實網(wǎng)絡(luò)實驗結(jié)果分析

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

實驗中選取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 算法第一個閾值C1=0.5%,第二個閾值C2=1%.BPD權(quán)重參數(shù)x=12.

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

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

然后,進(jìn)一步分析達(dá)到網(wǎng)絡(luò)分解閾值(即0.01)時不同網(wǎng)絡(luò)分解算法需要的刪除代價Cost. 表2顯示了上述6 種算法分解Crime、Corruption、Petster-hamster、Power-Grid、Political Blogs 和Autonomous Systems 網(wǎng)絡(luò)所需要的代價Cost. 可以看出,本文的CD-IRE 算法只需要刪除較小規(guī)模的連邊就可以完成對6個網(wǎng)絡(luò)的分解,表現(xiàn)出最好的性能. GNDR 算法也表現(xiàn)出了不錯的性能,BPD 算法緊隨其后. 另外,從表2 可以看出,無論何種算法,分解Corruption 網(wǎng)絡(luò)和Political Blogs 網(wǎng)絡(luò)的代價Cost都超過0.92,原因是這兩個網(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對比

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

實驗中選取4種基于連邊刪除的網(wǎng)絡(luò)分解算法,分別是Ncut算法[11]、Bond percolation 算法[18]、Betweenness算法[10]和Bridgeness算法[9].

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

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

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

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

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

此處選取上述實驗中性能突出的CD-IRE 算法、GNDR 算法、Min-Sum 算法、BPD 算法和Ncut 算法,分析GCC 閾值對網(wǎng)絡(luò)分解算法性能的影響. 選取的真實網(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)增大趨勢. 在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代價直接將Power-Grid網(wǎng)絡(luò)的GCC降至0.2以下,因此0.2以上的閾值變化對該算法沒有影響(見表5). 總體而言,隨著GCC閾值的變化,CD-IRE算法始終能夠保持良好的性能,以較小的代價完成網(wǎng)絡(luò)分解.

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

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

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

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

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

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

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

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

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

表6 GCC閾值對網(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個節(jié)點(diǎn). 平均連邊數(shù)(平均度值)c分別取4、6和8. 考慮到Ncut算法和CD-IRE算法性能最接近,此處僅分析這兩種算法在BA網(wǎng)絡(luò)上的性能.

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

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

4 結(jié)論

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

猜你喜歡
度值連通性代價
探討公路項目路基連續(xù)壓實質(zhì)量檢測技術(shù)
植被覆蓋度和降雨侵蝕力變化對小流域泥沙連通性的影響
中國自然保護(hù)地連通性的重要意義與關(guān)鍵議題
基于空間句法的沈陽市北陵公園可達(dá)性分析
去2 度點(diǎn)后不滿足Pósa- 條件的圖的Z3- 連通性
閘壩對撫河流域連通性的影響研究
基于互信息量和自回歸模型的鏡頭分割方法
愛的代價
幸災(zāi)樂禍的代價
代價