• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

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

    王志曉,張磊,孫成成,芮曉彬,黃珍珍,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)定性.

    猜你喜歡
    逆序度值連通性
    偏序集及其相關(guān)拓?fù)涞倪B通性?
    探討公路項(xiàng)目路基連續(xù)壓實(shí)質(zhì)量檢測(cè)技術(shù)
    有界線性算子的Drazin逆的逆序律
    擬莫比烏斯映射與擬度量空間的連通性
    關(guān)于矩陣廣義BottDuffin逆的逆序律
    新中國70年漢語逆序詞研究(1949—2019)
    對(duì)外漢語教學(xué)中AB-BA式逆序詞教學(xué)分析
    河道-灘區(qū)系統(tǒng)連通性評(píng)價(jià)研究
    無線傳輸中短碼長(zhǎng)噴泉碼的度分布優(yōu)化算法*
    微博網(wǎng)絡(luò)較大度值用戶特征分析
    科技傳播(2016年17期)2016-10-10 01:46:58
    国产免费福利视频在线观看| 一级黄片播放器| 伊人久久国产一区二区| 亚洲久久久国产精品| 国产成人精品久久久久久| 日韩精品有码人妻一区| 免费观看性生交大片5| 亚洲国产色片| 国产成人aa在线观看| 欧美日韩av久久| 精品久久久精品久久久| 免费观看无遮挡的男女| 青青草视频在线视频观看| 男女高潮啪啪啪动态图| 亚洲国产精品一区三区| 中文字幕av电影在线播放| 制服人妻中文乱码| 成人影院久久| av在线播放精品| 欧美日韩国产mv在线观看视频| 日本欧美国产在线视频| 精品少妇一区二区三区视频日本电影 | 大片免费播放器 马上看| 久久久久精品性色| 久久精品aⅴ一区二区三区四区 | 久久午夜福利片| 99热全是精品| 宅男免费午夜| 亚洲av国产av综合av卡| 久久久久人妻精品一区果冻| 久久精品久久久久久久性| 老女人水多毛片| 伦理电影大哥的女人| 婷婷色综合大香蕉| 一二三四中文在线观看免费高清| 国产深夜福利视频在线观看| 最近中文字幕2019免费版| 亚洲精品,欧美精品| 欧美人与性动交α欧美精品济南到 | 国产成人精品在线电影| 美女xxoo啪啪120秒动态图| 中文精品一卡2卡3卡4更新| 精品一区在线观看国产| 久久 成人 亚洲| 99九九在线精品视频| 欧美日韩精品网址| 国产无遮挡羞羞视频在线观看| 久久精品国产亚洲av天美| 91成人精品电影| 黄片小视频在线播放| 国产精品一区二区在线观看99| 人成视频在线观看免费观看| 欧美日韩视频精品一区| 最近最新中文字幕免费大全7| 黑人猛操日本美女一级片| 亚洲色图综合在线观看| 亚洲,一卡二卡三卡| 卡戴珊不雅视频在线播放| 国产在视频线精品| 国产精品国产三级国产专区5o| 熟妇人妻不卡中文字幕| 亚洲成人av在线免费| 精品国产一区二区久久| 久久精品久久精品一区二区三区| 黄色 视频免费看| 亚洲,欧美,日韩| 在线观看免费日韩欧美大片| 久久97久久精品| 亚洲国产欧美日韩在线播放| 岛国毛片在线播放| 日本av免费视频播放| 一级毛片电影观看| 久久精品夜色国产| 欧美变态另类bdsm刘玥| freevideosex欧美| 丰满迷人的少妇在线观看| 水蜜桃什么品种好| 人人妻人人爽人人添夜夜欢视频| 国产 一区精品| 国产成人av激情在线播放| 天堂俺去俺来也www色官网| 亚洲三级黄色毛片| 电影成人av| 色哟哟·www| 亚洲欧美中文字幕日韩二区| 国产不卡av网站在线观看| 1024视频免费在线观看| 久久久久久久精品精品| 亚洲精品国产av蜜桃| 国产成人精品福利久久| 国产成人91sexporn| 咕卡用的链子| 国产精品香港三级国产av潘金莲 | 久久久欧美国产精品| 91午夜精品亚洲一区二区三区| 欧美中文综合在线视频| 国产精品久久久久久精品古装| 高清视频免费观看一区二区| 一区在线观看完整版| 校园人妻丝袜中文字幕| 亚洲美女搞黄在线观看| 欧美xxⅹ黑人| 又粗又硬又长又爽又黄的视频| 色婷婷久久久亚洲欧美| 欧美老熟妇乱子伦牲交| 日韩精品有码人妻一区| 在线 av 中文字幕| 少妇被粗大的猛进出69影院| 国产极品天堂在线| 啦啦啦中文免费视频观看日本| 三上悠亚av全集在线观看| www.av在线官网国产| 久久精品久久久久久噜噜老黄| 久久国产亚洲av麻豆专区| 伊人久久大香线蕉亚洲五| 亚洲国产日韩一区二区| 制服丝袜香蕉在线| 伊人亚洲综合成人网| 纵有疾风起免费观看全集完整版| 国产精品偷伦视频观看了| 国产成人免费观看mmmm| 久久99热这里只频精品6学生| 黄色视频在线播放观看不卡| 午夜激情av网站| 亚洲欧美精品综合一区二区三区 | 久久这里有精品视频免费| 国产 精品1| 久久精品久久久久久久性| 国产日韩欧美亚洲二区| 久久av网站| 免费高清在线观看日韩| av线在线观看网站| 国产成人精品一,二区| 欧美+日韩+精品| 久久久久久久久久人人人人人人| 成人毛片a级毛片在线播放| 亚洲人成电影观看| 人人妻人人添人人爽欧美一区卜| 亚洲美女搞黄在线观看| 电影成人av| 成人18禁高潮啪啪吃奶动态图| 精品国产超薄肉色丝袜足j| 日韩,欧美,国产一区二区三区| 亚洲美女视频黄频| 国产老妇伦熟女老妇高清| 18+在线观看网站| 国产一区二区三区av在线| 免费观看性生交大片5| 高清在线视频一区二区三区| 午夜日本视频在线| 91精品伊人久久大香线蕉| tube8黄色片| av网站免费在线观看视频| 国产亚洲最大av| 国产成人欧美| 国产av精品麻豆| 国产精品人妻久久久影院| 9热在线视频观看99| 国产av一区二区精品久久| 久久免费观看电影| 国产精品免费大片| 18禁观看日本| 天天躁夜夜躁狠狠久久av| 色视频在线一区二区三区| 亚洲成国产人片在线观看| 亚洲欧美中文字幕日韩二区| 伦理电影大哥的女人| av又黄又爽大尺度在线免费看| 黄色视频在线播放观看不卡| 国产成人精品在线电影| 国产高清国产精品国产三级| 男人舔女人的私密视频| 男女啪啪激烈高潮av片| 中文字幕av电影在线播放| 一级爰片在线观看| 69精品国产乱码久久久| 欧美日韩国产mv在线观看视频| 久久婷婷青草| 精品一区二区免费观看| a 毛片基地| 极品少妇高潮喷水抽搐| 国产精品.久久久| 成人黄色视频免费在线看| 亚洲国产精品一区三区| 亚洲精品第二区| 国产成人免费无遮挡视频| 欧美精品国产亚洲| 人人澡人人妻人| 午夜激情av网站| 巨乳人妻的诱惑在线观看| 色网站视频免费| 两性夫妻黄色片| 成年女人在线观看亚洲视频| 精品亚洲成国产av| 免费高清在线观看日韩| 一区二区av电影网| 天堂8中文在线网| 最近2019中文字幕mv第一页| 18禁动态无遮挡网站| 久久毛片免费看一区二区三区| 久久精品国产亚洲av涩爱| 国产福利在线免费观看视频| 免费在线观看黄色视频的| 久久人人爽av亚洲精品天堂| 亚洲欧美一区二区三区国产| 成年女人在线观看亚洲视频| 亚洲第一区二区三区不卡| 国产一区二区在线观看av| 一区二区三区四区激情视频| 欧美亚洲日本最大视频资源| 国产成人一区二区在线| 欧美精品一区二区大全| 免费不卡的大黄色大毛片视频在线观看| 日日摸夜夜添夜夜爱| 亚洲欧美清纯卡通| 1024香蕉在线观看| 成人国语在线视频| 久久久精品区二区三区| 午夜福利在线观看免费完整高清在| 一级片'在线观看视频| 韩国高清视频一区二区三区| 男女免费视频国产| 男男h啪啪无遮挡| 一区二区日韩欧美中文字幕| 精品国产一区二区久久| 妹子高潮喷水视频| 天天躁夜夜躁狠狠久久av| 美女福利国产在线| 黄片小视频在线播放| 亚洲av.av天堂| 中文乱码字字幕精品一区二区三区| 一本一本久久a久久精品综合妖精 国产伦在线观看视频一区 | 在线观看国产h片| av线在线观看网站| 午夜av观看不卡| 亚洲精品国产av成人精品| 伦精品一区二区三区| av又黄又爽大尺度在线免费看| 婷婷成人精品国产| 日韩av不卡免费在线播放| 精品国产国语对白av| 欧美老熟妇乱子伦牲交| 爱豆传媒免费全集在线观看| 毛片一级片免费看久久久久| 亚洲精品中文字幕在线视频| 国产一区二区在线观看av| 黑人欧美特级aaaaaa片| 啦啦啦在线免费观看视频4| av不卡在线播放| 久久久久精品性色| 久久久久久久大尺度免费视频| av有码第一页| 日本wwww免费看| 一级毛片我不卡| tube8黄色片| 成人毛片60女人毛片免费| 多毛熟女@视频| 欧美成人午夜精品| 91精品三级在线观看| 久久精品久久久久久噜噜老黄| 亚洲婷婷狠狠爱综合网| 波多野结衣av一区二区av| 在线天堂最新版资源| 9色porny在线观看| 久热这里只有精品99| 性少妇av在线| 18禁观看日本| av免费观看日本| 日韩 亚洲 欧美在线| 国产在线免费精品| 校园人妻丝袜中文字幕| 赤兔流量卡办理| 久久久久久伊人网av| 免费看av在线观看网站| 亚洲av中文av极速乱| 午夜福利影视在线免费观看| 国产在线视频一区二区| 91久久精品国产一区二区三区| 天天躁狠狠躁夜夜躁狠狠躁| 极品人妻少妇av视频| 另类精品久久| 亚洲激情五月婷婷啪啪| 欧美日韩精品网址| 永久免费av网站大全| 午夜91福利影院| 国产在线视频一区二区| 国产成人av激情在线播放| 午夜福利乱码中文字幕| 自拍欧美九色日韩亚洲蝌蚪91| 久久久久久人人人人人| 久久精品亚洲av国产电影网| 亚洲精品第二区| 永久网站在线| 欧美人与性动交α欧美软件| 最近中文字幕2019免费版| 午夜精品国产一区二区电影| 伊人亚洲综合成人网| 在线观看免费高清a一片| 国产毛片在线视频| 欧美精品av麻豆av| 久久这里有精品视频免费| 亚洲综合色惰| www.自偷自拍.com| 少妇被粗大猛烈的视频| 欧美日韩av久久| 亚洲欧美色中文字幕在线| av网站免费在线观看视频| 国产片内射在线| 麻豆精品久久久久久蜜桃| 国产成人精品福利久久| av免费在线看不卡| 色婷婷久久久亚洲欧美| 另类亚洲欧美激情| 亚洲色图 男人天堂 中文字幕| 毛片一级片免费看久久久久| 少妇精品久久久久久久| 男的添女的下面高潮视频| 久久ye,这里只有精品| 亚洲成人一二三区av| 亚洲经典国产精华液单| 色吧在线观看| 亚洲五月色婷婷综合| 1024香蕉在线观看| 在线观看免费日韩欧美大片| 日日爽夜夜爽网站| 亚洲精品中文字幕在线视频| 中文字幕人妻丝袜一区二区 | 日韩在线高清观看一区二区三区| 亚洲av日韩在线播放| 国产国语露脸激情在线看| 777米奇影视久久| 777久久人妻少妇嫩草av网站| 久久久国产精品麻豆| 男女边吃奶边做爰视频| 成人二区视频| 蜜桃在线观看..| 久久久久久久久久久久大奶| 成人漫画全彩无遮挡| 亚洲精品中文字幕在线视频| 岛国毛片在线播放| 一区二区av电影网| 水蜜桃什么品种好| 黄色一级大片看看| 爱豆传媒免费全集在线观看| 免费黄色在线免费观看| 性高湖久久久久久久久免费观看| 又粗又硬又长又爽又黄的视频| 美女视频免费永久观看网站| 波野结衣二区三区在线| 亚洲欧洲日产国产| 韩国高清视频一区二区三区| 亚洲成色77777| 久久久国产一区二区| 亚洲三区欧美一区| 人人妻人人澡人人爽人人夜夜| 大码成人一级视频| 久久久精品区二区三区| 90打野战视频偷拍视频| 国产亚洲欧美精品永久| 超碰97精品在线观看| 精品国产乱码久久久久久男人| 国产精品 欧美亚洲| 国产日韩欧美在线精品| 亚洲av福利一区| 久久久a久久爽久久v久久| 电影成人av| 国产免费一区二区三区四区乱码| 亚洲综合色网址| 国产白丝娇喘喷水9色精品| 免费人妻精品一区二区三区视频| xxxhd国产人妻xxx| 国产一区有黄有色的免费视频| 91午夜精品亚洲一区二区三区| 国产精品久久久久久av不卡| 午夜免费男女啪啪视频观看| 国产成人91sexporn| 亚洲三区欧美一区| 成年动漫av网址| 男女啪啪激烈高潮av片| 久久久久久久久免费视频了| 女人被躁到高潮嗷嗷叫费观| 欧美最新免费一区二区三区| 欧美少妇被猛烈插入视频| 亚洲图色成人| 亚洲一区二区三区欧美精品| 国产免费视频播放在线视频| 日韩欧美一区视频在线观看| 女人精品久久久久毛片| 女的被弄到高潮叫床怎么办| 2022亚洲国产成人精品| 超碰成人久久| 在线精品无人区一区二区三| 亚洲av.av天堂| 热99国产精品久久久久久7| av线在线观看网站| 日韩一区二区三区影片| h视频一区二区三区| 成年美女黄网站色视频大全免费| 国产日韩一区二区三区精品不卡| 国产精品久久久久久久久免| 免费高清在线观看视频在线观看| 久久久久网色| 青春草视频在线免费观看| 美女大奶头黄色视频| 亚洲一级一片aⅴ在线观看| 女人被躁到高潮嗷嗷叫费观| 亚洲一码二码三码区别大吗| xxxhd国产人妻xxx| 亚洲精品中文字幕在线视频| 寂寞人妻少妇视频99o| 中文字幕色久视频| 亚洲三区欧美一区| 国产熟女欧美一区二区| videossex国产| 人人妻人人爽人人添夜夜欢视频| 成人国产av品久久久| 免费黄频网站在线观看国产| 黄色配什么色好看| 免费久久久久久久精品成人欧美视频| 男人爽女人下面视频在线观看| 亚洲成av片中文字幕在线观看 | 精品卡一卡二卡四卡免费| 国产野战对白在线观看| 欧美日韩精品成人综合77777| av国产久精品久网站免费入址| 亚洲国产看品久久| 日韩人妻精品一区2区三区| 啦啦啦中文免费视频观看日本| 日韩电影二区| 一级毛片 在线播放| 97在线视频观看| 丰满乱子伦码专区| 三上悠亚av全集在线观看| 天堂中文最新版在线下载| 边亲边吃奶的免费视频| 免费播放大片免费观看视频在线观看| √禁漫天堂资源中文www| 一本大道久久a久久精品| 欧美97在线视频| 亚洲天堂av无毛| 免费在线观看视频国产中文字幕亚洲 | 男女高潮啪啪啪动态图| 人妻少妇偷人精品九色| 考比视频在线观看| 日本vs欧美在线观看视频| 妹子高潮喷水视频| 日韩av不卡免费在线播放| 人妻人人澡人人爽人人| 国产精品二区激情视频| √禁漫天堂资源中文www| 涩涩av久久男人的天堂| 国产欧美日韩综合在线一区二区| 亚洲一区中文字幕在线| 九草在线视频观看| 多毛熟女@视频| 美女中出高潮动态图| 最新中文字幕久久久久| 一级a爱视频在线免费观看| 国产成人精品久久二区二区91 | 亚洲精品乱久久久久久| 99久久人妻综合| 日本色播在线视频| 亚洲一区中文字幕在线| 国产熟女欧美一区二区| 9191精品国产免费久久| 亚洲国产日韩一区二区| 搡老乐熟女国产| 国产xxxxx性猛交| 69精品国产乱码久久久| 9热在线视频观看99| 亚洲中文av在线| 少妇的丰满在线观看| 老汉色∧v一级毛片| 日韩人妻精品一区2区三区| 夜夜骑夜夜射夜夜干| 久久久久国产网址| 中国国产av一级| 亚洲第一av免费看| 制服诱惑二区| a 毛片基地| av.在线天堂| 一二三四中文在线观看免费高清| 久久久久国产网址| 青春草亚洲视频在线观看| 国产乱人偷精品视频| 最黄视频免费看| 超碰97精品在线观看| 汤姆久久久久久久影院中文字幕| 亚洲av免费高清在线观看| 丝袜美腿诱惑在线| 亚洲国产欧美网| 成人免费观看视频高清| 91在线精品国自产拍蜜月| 国产伦理片在线播放av一区| 成人影院久久| 久久毛片免费看一区二区三区| www.精华液| 日韩一区二区视频免费看| 亚洲内射少妇av| 美女中出高潮动态图| 免费久久久久久久精品成人欧美视频| 男人添女人高潮全过程视频| 久久久久国产一级毛片高清牌| 亚洲欧美色中文字幕在线| 亚洲成国产人片在线观看| videos熟女内射| 男女边吃奶边做爰视频| 黄色一级大片看看| 国产片特级美女逼逼视频| 如日韩欧美国产精品一区二区三区| 亚洲精品一区蜜桃| 激情五月婷婷亚洲| 国产一区二区激情短视频 | 99国产综合亚洲精品| 国产免费一区二区三区四区乱码| 老司机影院毛片| 毛片一级片免费看久久久久| 国产毛片在线视频| 中国国产av一级| 尾随美女入室| 中国国产av一级| 欧美变态另类bdsm刘玥| 少妇的丰满在线观看| 91成人精品电影| 一本—道久久a久久精品蜜桃钙片| 久久精品国产a三级三级三级| 国产熟女午夜一区二区三区| 日本欧美国产在线视频| 大香蕉久久网| av国产精品久久久久影院| 国产午夜精品一二区理论片| 国产亚洲欧美精品永久| 国产精品香港三级国产av潘金莲 | 久久婷婷青草| 日韩中字成人| 丝袜在线中文字幕| 青草久久国产| 97精品久久久久久久久久精品| 老鸭窝网址在线观看| 最近的中文字幕免费完整| 亚洲精品自拍成人| 最近2019中文字幕mv第一页| 男的添女的下面高潮视频| 国产成人aa在线观看| 亚洲精品,欧美精品| 飞空精品影院首页| 制服诱惑二区| 蜜桃国产av成人99| 街头女战士在线观看网站| 啦啦啦啦在线视频资源| 99香蕉大伊视频| 久久精品国产a三级三级三级| 精品久久久久久电影网| 日本91视频免费播放| 各种免费的搞黄视频| 久久久国产欧美日韩av| 国产精品人妻久久久影院| 亚洲伊人色综图| 26uuu在线亚洲综合色| 婷婷成人精品国产| 免费播放大片免费观看视频在线观看| 999久久久国产精品视频| 成人国产av品久久久| 成人国语在线视频| 丝袜喷水一区| 亚洲国产欧美在线一区| 久久国产精品男人的天堂亚洲| 在线观看三级黄色| 成年动漫av网址| 男的添女的下面高潮视频| 久久久久久伊人网av| 国产色婷婷99| 黄片播放在线免费| 欧美日本中文国产一区发布| 日日爽夜夜爽网站| 精品国产露脸久久av麻豆| 免费在线观看视频国产中文字幕亚洲 | 国产免费现黄频在线看| 亚洲 欧美一区二区三区| 色网站视频免费| 下体分泌物呈黄色| 国产黄频视频在线观看| 飞空精品影院首页| 波多野结衣一区麻豆| 日本猛色少妇xxxxx猛交久久| 涩涩av久久男人的天堂| 18禁裸乳无遮挡动漫免费视频| 少妇被粗大的猛进出69影院| 黄色毛片三级朝国网站| 99精国产麻豆久久婷婷| 国产在视频线精品| 亚洲一码二码三码区别大吗| 亚洲欧美精品综合一区二区三区 | 精品一区二区免费观看| 伊人久久国产一区二区| 国产男人的电影天堂91| 热99久久久久精品小说推荐| 亚洲精品av麻豆狂野| 色网站视频免费| 亚洲国产色片| 18在线观看网站| 18禁观看日本| 亚洲精品乱久久久久久| 国产午夜精品一二区理论片| 在线观看美女被高潮喷水网站| 久久精品人人爽人人爽视色| 热99国产精品久久久久久7| 日韩av在线免费看完整版不卡| 欧美成人精品欧美一级黄| 一本色道久久久久久精品综合| 久久这里有精品视频免费| 国产综合精华液| 亚洲成色77777| a 毛片基地| 26uuu在线亚洲综合色|