基于三角形子圖的復(fù)雜網(wǎng)絡(luò)過濾壓縮算法
發(fā)布時間：2021-08-15 06:23
為高效地挖掘和分析復(fù)雜網(wǎng)絡(luò),提出一種基于三角形子圖的復(fù)雜網(wǎng)絡(luò)過濾壓縮算法NIIET。設(shè)計一種節(jié)點重要性排序算法NRSA選取高、低重要性節(jié)點并進行過濾,以降低計算規(guī)模并縮短壓縮時間。列出邊兩端的節(jié)點及其共同節(jié)點集組成三角形子圖集合,在此基礎(chǔ)上,解析三角形子圖集合完成復(fù)雜網(wǎng)絡(luò)壓縮。實驗結(jié)果表明,NRSA算法的排序結(jié)果合理且可靠,相對Nodeiterator算法,NIIET算法能夠縮短壓縮時間,提高壓縮率,且能保留原網(wǎng)絡(luò)的大部分結(jié)構(gòu)和信息。
【文章來源】：計算機工程. 2020,46(05)北大核心CSCD
【文章頁數(shù)】：8 頁
【部分圖文】：
簡單無向網(wǎng)絡(luò)示意圖
由圖2可以看出,節(jié)點重要性值的分布十分不均勻,多數(shù)節(jié)點的重要性非常低,小部分節(jié)點的重要性很高。特別地,高重要性與低重要性節(jié)點之間含有的共同鄰接節(jié)點非常少,但尋找它們之間的三角形子圖卻占用大量的計算時間。因此,在計算三角形子圖前過濾掉高、低重要性節(jié)點,可以減小計算規(guī)模,且能避免較高的計算代價,從而得到高效的三角形子圖集合。本文將帶過濾性質(zhì)的三角形子圖壓縮算法定義為NIIET(Node Importance In Edge Triangle)。NIIET算法在壓縮時只需要訪問鄰接列表,鄰接列表中包含邊的方向性,可應(yīng)用于有向圖和無向圖。圖3是一個包含8個節(jié)點、16條邊的簡單無向網(wǎng)絡(luò)圖,其中,線上數(shù)字表示線的編號。如表1、表2所示,邊迭代算法可以得到一個包含42個三角形的三角形子圖集合,會產(chǎn)生27條邊的冗余。假如存儲一個三角形子圖的邊需要2個單位,則會產(chǎn)生54個單位的冗余。因此,可以通過過濾掉高、低重要性節(jié)點來降低三角形子圖集合的冗余,從而提高壓縮算法的效率。
圖3是一個包含8個節(jié)點、16條邊的簡單無向網(wǎng)絡(luò)圖,其中,線上數(shù)字表示線的編號。如表1、表2所示,邊迭代算法可以得到一個包含42個三角形的三角形子圖集合,會產(chǎn)生27條邊的冗余。假如存儲一個三角形子圖的邊需要2個單位,則會產(chǎn)生54個單位的冗余。因此,可以通過過濾掉高、低重要性節(jié)點來降低三角形子圖集合的冗余,從而提高壓縮算法的效率。表1 原始網(wǎng)絡(luò)節(jié)點重要性統(tǒng)計結(jié)果Table 1 Statistic results of original network node importance 節(jié)點 重要性值 節(jié)點 重要性值 4 1.000 000 000 00 2 0.630 033 038 70 0 0.772 326 740 38 6 0.424 424 327 58 1 0.772 326 740 38 5 0.195 828 400 67 3 0.763 622 551 24 7 0.000 000 000 00
【參考文獻】：
期刊論文
[1]基于LeaderRank和節(jié)點相似性的多標(biāo)簽傳播重疊社團挖掘算法[J]. 王林,饒仁杰. 計算機系統(tǒng)應(yīng)用. 2018(06)
[2]基于非重要節(jié)點拆分融合的網(wǎng)絡(luò)層次壓縮算法[J]. 李政廉,吉立新,黃瑞陽,劉樹新. 計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2018(02)
[3]基于節(jié)點中心性的時變復(fù)雜網(wǎng)絡(luò)布局算法[J]. 周弦,梁霄,黃廷磊. 系統(tǒng)工程與電子技術(shù). 2017(10)
[4]科研合作網(wǎng)絡(luò)中知識源中心性對知識擴散效率的影響[J]. 涂靜,楊中華,張志清. 情報理論與實踐. 2017(05)
[5]一種有效的基于三角結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)節(jié)點影響力度量模型[J]. 韓忠明,陳炎,李夢琪,劉雯,楊偉杰. 物理學(xué)報. 2016(16)
[6]基于k-core的大規(guī)模復(fù)雜網(wǎng)絡(luò)壓縮布局算法[J]. 李甜甜,盧罡,許南山,郭俊霞. 計算機工程. 2016(05)
[7]具有時滯的SIR計算機病毒傳播模型[J]. 胡寶安,李兵,李亞玲. 計算機工程. 2016(05)
[8]圖數(shù)據(jù)表示與壓縮技術(shù)綜述[J]. 張宇,劉燕兵,熊剛,賈焰,劉萍,郭莉. 軟件學(xué)報. 2014(09)
[9]基于社區(qū)節(jié)點重要性的社會網(wǎng)絡(luò)壓縮方法[J]. 李泓波,張健沛,楊靜,白勁波,初妍,張樂君. 北京大學(xué)學(xué)報(自然科學(xué)版). 2013(01)
[10]基于多尺度幾何分析的復(fù)雜網(wǎng)絡(luò)壓縮策略[J]. 王曉華,楊新艷,焦李成. 電子與信息學(xué)報. 2009(04)
碩士論文
[1]基于壓縮與聚類分析的復(fù)雜網(wǎng)絡(luò)可視化技術(shù)研究[D]. 仇樺.江蘇大學(xué) 2017
本文編號：3344033
【文章來源】：計算機工程. 2020,46(05)北大核心CSCD
【文章頁數(shù)】：8 頁
【部分圖文】：
簡單無向網(wǎng)絡(luò)示意圖
由圖2可以看出,節(jié)點重要性值的分布十分不均勻,多數(shù)節(jié)點的重要性非常低,小部分節(jié)點的重要性很高。特別地,高重要性與低重要性節(jié)點之間含有的共同鄰接節(jié)點非常少,但尋找它們之間的三角形子圖卻占用大量的計算時間。因此,在計算三角形子圖前過濾掉高、低重要性節(jié)點,可以減小計算規(guī)模,且能避免較高的計算代價,從而得到高效的三角形子圖集合。本文將帶過濾性質(zhì)的三角形子圖壓縮算法定義為NIIET(Node Importance In Edge Triangle)。NIIET算法在壓縮時只需要訪問鄰接列表,鄰接列表中包含邊的方向性,可應(yīng)用于有向圖和無向圖。圖3是一個包含8個節(jié)點、16條邊的簡單無向網(wǎng)絡(luò)圖,其中,線上數(shù)字表示線的編號。如表1、表2所示,邊迭代算法可以得到一個包含42個三角形的三角形子圖集合,會產(chǎn)生27條邊的冗余。假如存儲一個三角形子圖的邊需要2個單位,則會產(chǎn)生54個單位的冗余。因此,可以通過過濾掉高、低重要性節(jié)點來降低三角形子圖集合的冗余,從而提高壓縮算法的效率。
圖3是一個包含8個節(jié)點、16條邊的簡單無向網(wǎng)絡(luò)圖,其中,線上數(shù)字表示線的編號。如表1、表2所示,邊迭代算法可以得到一個包含42個三角形的三角形子圖集合,會產(chǎn)生27條邊的冗余。假如存儲一個三角形子圖的邊需要2個單位,則會產(chǎn)生54個單位的冗余。因此,可以通過過濾掉高、低重要性節(jié)點來降低三角形子圖集合的冗余,從而提高壓縮算法的效率。表1 原始網(wǎng)絡(luò)節(jié)點重要性統(tǒng)計結(jié)果Table 1 Statistic results of original network node importance 節(jié)點 重要性值 節(jié)點 重要性值 4 1.000 000 000 00 2 0.630 033 038 70 0 0.772 326 740 38 6 0.424 424 327 58 1 0.772 326 740 38 5 0.195 828 400 67 3 0.763 622 551 24 7 0.000 000 000 00
【參考文獻】：
期刊論文
[1]基于LeaderRank和節(jié)點相似性的多標(biāo)簽傳播重疊社團挖掘算法[J]. 王林,饒仁杰. 計算機系統(tǒng)應(yīng)用. 2018(06)
[2]基于非重要節(jié)點拆分融合的網(wǎng)絡(luò)層次壓縮算法[J]. 李政廉,吉立新,黃瑞陽,劉樹新. 計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2018(02)
[3]基于節(jié)點中心性的時變復(fù)雜網(wǎng)絡(luò)布局算法[J]. 周弦,梁霄,黃廷磊. 系統(tǒng)工程與電子技術(shù). 2017(10)
[4]科研合作網(wǎng)絡(luò)中知識源中心性對知識擴散效率的影響[J]. 涂靜,楊中華,張志清. 情報理論與實踐. 2017(05)
[5]一種有效的基于三角結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)節(jié)點影響力度量模型[J]. 韓忠明,陳炎,李夢琪,劉雯,楊偉杰. 物理學(xué)報. 2016(16)
[6]基于k-core的大規(guī)模復(fù)雜網(wǎng)絡(luò)壓縮布局算法[J]. 李甜甜,盧罡,許南山,郭俊霞. 計算機工程. 2016(05)
[7]具有時滯的SIR計算機病毒傳播模型[J]. 胡寶安,李兵,李亞玲. 計算機工程. 2016(05)
[8]圖數(shù)據(jù)表示與壓縮技術(shù)綜述[J]. 張宇,劉燕兵,熊剛,賈焰,劉萍,郭莉. 軟件學(xué)報. 2014(09)
[9]基于社區(qū)節(jié)點重要性的社會網(wǎng)絡(luò)壓縮方法[J]. 李泓波,張健沛,楊靜,白勁波,初妍,張樂君. 北京大學(xué)學(xué)報(自然科學(xué)版). 2013(01)
[10]基于多尺度幾何分析的復(fù)雜網(wǎng)絡(luò)壓縮策略[J]. 王曉華,楊新艷,焦李成. 電子與信息學(xué)報. 2009(04)
碩士論文
[1]基于壓縮與聚類分析的復(fù)雜網(wǎng)絡(luò)可視化技術(shù)研究[D]. 仇樺.江蘇大學(xué) 2017
本文編號：3344033
本文鏈接：http://www.sikaile.net/kejilunwen/yysx/3344033.html
最近更新
教材專著
