節(jié)點(diǎn)的中介度（Betweenness Centrality）是度量節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中重要程度的一種重要指標(biāo);計(jì)算節(jié)點(diǎn)中介度在社交網(wǎng)絡(luò)分析、交通網(wǎng)絡(luò)治理、網(wǎng)絡(luò)安全管理等廣泛應(yīng)用中起著關(guān)鍵性作用。傳統(tǒng)節(jié)點(diǎn)中介度計(jì)算方法大多數(shù)僅關(guān)注小規(guī)模和靜態(tài)圖,然而在實(shí)際應(yīng)用中網(wǎng)絡(luò)規(guī)模巨大且具有動(dòng)態(tài)特征,因此如何在這樣的網(wǎng)絡(luò)上計(jì)算中介度受到了研究界的關(guān)注。本文研究動(dòng)態(tài)圖中介度和Top-k節(jié)點(diǎn)中介度的計(jì)算方法,包含針對(duì)動(dòng)態(tài)圖的節(jié)點(diǎn)中介度增量計(jì)算方法、針對(duì)靜態(tài)圖的Top-k節(jié)點(diǎn)近似中介度計(jì)算方法,以及針對(duì)動(dòng)態(tài)圖Top-k節(jié)點(diǎn)近似中介度計(jì)算方法。論文主要研究的內(nèi)容如下:（1）動(dòng)態(tài)圖中節(jié)點(diǎn)中介度計(jì)算的增量式算法。為精確計(jì)算動(dòng)態(tài)圖中各節(jié)點(diǎn)中介度,基于經(jīng)典的針對(duì)靜態(tài)圖的Brandes算法,提出了一種增量式算法。該算法利用增量式單源最短路徑計(jì)算技術(shù),維護(hù)中間結(jié)果,快速計(jì)算發(fā)生改變的中介度。在Email-Eu-core、Facebook和bitcoin-alpha等數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出算法的高效性;相比其他算法,所提出算法速度提升10倍左右;在不同稀疏度和不同規(guī)模的圖上,所提出算法的速度比傳統(tǒng)靜態(tài)算法快2倍以上。... 

【文章來(lái)源】：西北農(nóng)林科技大學(xué)陜西省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：69 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１－１技術(shù)路線圖??Ｆｉｇ．?１－１?Ｔｅｃｈｎｏｌｏｇｙ?Ｒｏａｄｍａｐ??

數(shù)量。然后，設(shè)ｗ為ｖ?ｅ?Ｐｓ（ｈ〇的任何節(jié)點(diǎn)。在從ｓ到??ｗ的ｃｒｓｗ最短路徑中，？很多先從５■到Ｖ然后使用（Ｖ，?Ｗ）。因此，從＞５■到某些？：＾?Ｗ的??最短路徑包含Ｖ和（Ｖ，Ｗ）。因此，對(duì)Ｖ和（Ｖ，Ｗ）的５■和？的依賴(lài)關(guān)系是：??Ｍｖ，（ｖ，ｗ））?＝?｜＾：，＾ｔ（ｗ）?（２－６）??Ｖ．?＾ＳＷ?Ｃｓｔ?９??（＾（ｖ）＞０僅適用于那些ｆｅｗ，?Ｖ位于從５到？的至少一條最短路徑上，并注意??在任何這樣的路徑上只有一條邊（ｖ，ｗ）對(duì)于ｖ?ｅ?ｉ＾ｗ）。這種稍微復(fù)雜的情況如圖２－１所??？（扣１）??圖２－１依賴(lài)關(guān)系??Ｆｉｇ．?２－１?Ｄｅｐｅｎｄｅｎｃｙ??故，依賴(lài)關(guān)系可改寫(xiě)為：??＆，．（Ｖ）?＝?２?Ｍｖ）＝?Ｚ?Ｚ?＾ｆ（ｖ，（ｖ，ｗ））＝?ｚ?ｚ?５ｓｔ｛ｖ，?（ｖ，ｗ））??ｔ￡Ｖ?ｔ＆Ｖ?ｗ：ｖｇＰｓ（ｗ）?ｗ：ｖｅＰｓ（ｗ）?ｔ￡Ｖ??＝ｙ?１＾ｌ＋?ｙ，．？（叫?（２－７）??ｗ：ｖ＾（ｗ）ｒ＾?ｔ＾＼ｗ?＾?＾?Ｉ??這樣傳統(tǒng)算法的第一步就從節(jié)點(diǎn)對(duì)計(jì)算這樣繁復(fù)的方法簡(jiǎn)化為了針對(duì)單個(gè)樞軸計(jì)算，??使得Ｂｒａｎｄｅｓ算法計(jì)算中介度的實(shí)踐復(fù)雜度為０（ｎｍ?＋?ｎ２?ｌｏｇ？），所需空間為Ｃ？（ｎ?＋?ｍ）。??該算法的偽碼為算法１。??２．３增量算法??２．３．１增量圖算法??評(píng)估算法時(shí)間復(fù)雜度常用的方法是漸進(jìn)最差分析的方式，并將計(jì)算成本表示為輸??入規(guī)模的函數(shù)。但是，對(duì)于增量算法，這種分析有時(shí)候并不是很有用。Ｒａｍａｌｉｎｇａｍ等??１０??

?西北農(nóng)林科技大學(xué)碩士學(xué)位論文???圖３－１有向無(wú)環(huán)圖的減邊關(guān)系??Ｆｉｇ．?３－１?Ｒｅｄｕｃｔｉｏｎ?ｏｆ?Ｄｉｒｅｃｔｅｄ?Ａｃｙｃｌｉｃ?Ｇｒａｐｈｓ??本文針對(duì)第一階段進(jìn)行增量時(shí)間復(fù)雜度分析。循環(huán)［９］－［２１］需要次ＩＡＦＦＥＣＴＥＤＪ??迭代，因?yàn)樾枰来吮闅v節(jié)點(diǎn)ｖ，？的所有子孫節(jié)點(diǎn)。其中［１８］－［２０］因?yàn)槊總�(gè)具體節(jié)點(diǎn)需??要將后繼節(jié)點(diǎn)Ｖ刪除相應(yīng)最短路徑數(shù)，故花費(fèi)因此第一階段的增量復(fù)??雜度為時(shí)間復(fù)雜度?〇（Ｚｖｅ？ＣＴＥＤ?Ｆｍ？：（ｖ）｜）?＝?ＣＫＩＩＡＦＦＥＣＴＥＤＪＩ）。??階段２：更新最短路徑距離??是Ｄｉｊｋｓｔｒａ批量最短路徑算法的一種改進(jìn)，它使用次序優(yōu)先搜索來(lái)計(jì)算受影響節(jié)點(diǎn)??的新最短路徑距離。??與（Ｒａｍａｌｉｎｇａｍ?ａｎｄ?Ｒｅｐｓ?１９９６）中的思路相同，本文在圖３－２的第二階段Ｇ；為原有??向無(wú)環(huán)圖刪除受影響邊后的圖，為ｄｅｌｅｔｅ＿ｎ〇ｄｅＳ中所有節(jié)點(diǎn)尋找新的最短路徑距離。因??此將此問(wèn)題簡(jiǎn)化為ＳＳＳＰ＞０問(wèn)題的批處理實(shí)例，即獲得的圖如下所示的ＳＳＳＰ＞０問(wèn)題：??首先在ｄｅｌｅｔｅ＿ｎｏｄｅｓ集合中將所有可能連接到組成按其值大小排列的最短路徑距??離最小節(jié)點(diǎn)ｐｒｉｏｒｉｔｙ＿ｑｕｅｕｅ堆找；然后每次將距離最小的節(jié)點(diǎn)退出堆梭并添加到Ｇ丨中，??最后尋找此節(jié)點(diǎn)的可能后繼節(jié)點(diǎn)按距離值放入堆棧中。??考慮圖假設(shè)對(duì)于集合Ｇ丨中的每個(gè)節(jié)點(diǎn)ｖ；，從源點(diǎn)到節(jié)點(diǎn)ｖ；的最短路徑距離已知，??且由ｄ（ｖ７．）給出。算法需要計(jì)算剩余節(jié)點(diǎn)集合ｄｅｌｅｔｅ＿ｎｏｄｅｓ中每個(gè)節(jié)點(diǎn)ｖ的從最短路徑??距離。考慮通過(guò)將“凝練”到一個(gè)新的源點(diǎn)得到的圖：也就是說(shuō)，算法用一個(gè)新源??點(diǎn)代替Ｇ：，并且算

【參考文獻(xiàn)】：
期刊論文
[1]復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性[J]. 榮莉莉,郭天柱,王建偉.  上海理工大學(xué)學(xué)報(bào). 2008(03)



本文編號(hào)：3529625