基于分組的動態(tài)加權(quán)網(wǎng)絡(luò)關(guān)鍵節(jié)點算法研究.pdf

1、關(guān)鍵節(jié)點的測度問題本質(zhì)上可歸結(jié)為節(jié)點重要性測度及排序問題，該問題的有效解決有助于指導(dǎo)金融、電力、供應(yīng)鏈、互聯(lián)網(wǎng)等多方面的應(yīng)用開展。而當(dāng)前的研究大多針對無權(quán)、靜態(tài)社會網(wǎng)絡(luò)，在動態(tài)加權(quán)網(wǎng)絡(luò)中的研究則比較少，顯然進一步的研究是很有必要的。
　　 考慮到現(xiàn)實中單一因素測度節(jié)點重要性的局限性，給出了等效點權(quán)概念，一方面，點權(quán)作為一個基本的因素，它的確在局部上反映了節(jié)點的重要程度，另一方面，點權(quán)對其它節(jié)點的擴散效應(yīng)，距離越遠(yuǎn)，影響越小，考慮

2、到全局網(wǎng)絡(luò)中節(jié)點的點權(quán)對中心節(jié)點影響，給出了基于等效點權(quán)的節(jié)點重要性排名方法，從而進一步提高了測度結(jié)果的準(zhǔn)確性。
　　 考慮到現(xiàn)實加權(quán)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特性，給出了先分組后計算的思想，經(jīng)典的社區(qū)分組算法能在無權(quán)圖中有很好的效果，在加權(quán)圖中卻與預(yù)期的結(jié)果有一些差距，為了解決該問題，給出了基于距離增量矩陣的分組概念模型，考慮到兩社區(qū)在合并前后路徑矩陣的變化情況，給出了評價分組質(zhì)量的距離增量指標(biāo)，針對直接計算路徑矩陣時間代價大的不足，采用

3、了動態(tài)更新的方式來縮短計算時間，從而使該分組測度算法能適用于更大規(guī)模的網(wǎng)絡(luò)。
　　 考慮到現(xiàn)實加權(quán)網(wǎng)絡(luò)隨時間變化的動態(tài)特性，針對其中的路徑矩陣給出了動態(tài)式更新的方法，針對加入節(jié)點、刪除節(jié)點、邊權(quán)的變化等情況給出了不同的更新方法，大大縮短了計算開銷，同時給出了一種計算節(jié)點間最短路徑的新方法，使其能更好的滿足實際動態(tài)網(wǎng)絡(luò)應(yīng)用的需求。
　　 最后，綜合以上三方面，給出了基于距離增量矩陣分組求節(jié)點重要性的動態(tài)算法（a dynam