一種基于社交網(wǎng)絡(luò)的社區(qū)關(guān)鍵節(jié)點(diǎn)的最短路徑算法

付東煒

摘 要：隨著社交網(wǎng)絡(luò)的興起，對(duì)于社交網(wǎng)絡(luò)分析算法的性能提出了更高的要求和現(xiàn)實(shí)網(wǎng)絡(luò)中最短路徑的分布規(guī)律。提出一種基于社交網(wǎng)絡(luò)的社區(qū)關(guān)鍵節(jié)點(diǎn)最短路徑算法，該算法對(duì)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，確定每個(gè)社區(qū)內(nèi)的核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)的最短路徑，再與其它社區(qū)進(jìn)行相關(guān)聯(lián)，最終確定全局最短路徑就在這些社區(qū)間的核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)的鏈路上。

關(guān)鍵詞：社交網(wǎng)絡(luò) 最短路徑 社區(qū)劃分 核心節(jié)點(diǎn)

中圖分類號(hào)：TP293 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2017）04（a）-0223-02

社交網(wǎng)絡(luò)可以描述為圖的應(yīng)用，基于此類算法來分析社交網(wǎng)絡(luò)的相關(guān)性質(zhì)，而分析的基礎(chǔ)為計(jì)算社交網(wǎng)絡(luò)中的最短路徑，計(jì)算過程具有復(fù)雜性和性能方面等問題。

Milgram[1]提出的“六度分離”性質(zhì)，就是對(duì)社會(huì)網(wǎng)絡(luò)最短路徑長(zhǎng)度的假設(shè)；許多聚類算法也需要節(jié)點(diǎn)之間的距離或最短路徑信息[2]，如Girvan-Newman 算法[3]等.都是典型的最短路徑查找問題。

1 社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)定義

社交網(wǎng)絡(luò)最理想的核心節(jié)點(diǎn)，即認(rèn)為與網(wǎng)絡(luò)中所有節(jié)點(diǎn)均有邊相連接的節(jié)點(diǎn)為最重要的核心節(jié)點(diǎn)，如星形網(wǎng)中的中心節(jié)點(diǎn)顯然是網(wǎng)絡(luò)中最重要的“核心節(jié)點(diǎn)”，可以通過重點(diǎn)保護(hù)這些核心節(jié)點(diǎn)提高整個(gè)網(wǎng)絡(luò)的可靠性，也可以通過攻擊這些“薄弱環(huán)節(jié)”達(dá)到摧毀整個(gè)網(wǎng)絡(luò)的目的。然而在社交網(wǎng)絡(luò)是一個(gè)稀疏矩陣，各個(gè)社區(qū)之間的連接少，而社區(qū)內(nèi)信息交流量大。

定義：如果一個(gè)節(jié)點(diǎn)屬于整個(gè)社交網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)也屬于某個(gè)社區(qū)的關(guān)鍵節(jié)點(diǎn)；同理，如果一個(gè)節(jié)點(diǎn)屬于某個(gè)社區(qū)的關(guān)鍵節(jié)點(diǎn)，一定屬于全局關(guān)鍵節(jié)點(diǎn)集。關(guān)鍵節(jié)點(diǎn)集用Ps，而社區(qū)中關(guān)鍵節(jié)點(diǎn)集用Pik，節(jié)點(diǎn)用Pi來表示。

Pi∈Pik<=> Pi∈Ps （1）

其中k表示社區(qū)號(hào)，i表示節(jié)點(diǎn)號(hào)，一般一個(gè)社區(qū)至少有一個(gè)關(guān)鍵節(jié)點(diǎn)。

2 基于社區(qū)關(guān)鍵節(jié)點(diǎn)的Dijkstra算法

該文提出了在現(xiàn)實(shí)網(wǎng)絡(luò)中關(guān)于最短路徑規(guī)律的一個(gè)假設(shè)，在實(shí)際研究發(fā)現(xiàn)對(duì)于全局關(guān)鍵節(jié)點(diǎn)，到各點(diǎn)的距離仍然也是存在不可預(yù)測(cè)性，因此，提出到各個(gè)社區(qū)的關(guān)鍵節(jié)點(diǎn)，局部關(guān)鍵節(jié)點(diǎn)的最短路徑問題研究。可以提高網(wǎng)絡(luò)的傳播速率和效率，也可降低信息不成功到達(dá)率，從而提高用戶的滿意度。便于對(duì)社區(qū)結(jié)構(gòu)更加了解，先要確定在社區(qū)中連接處部社區(qū)的最短路徑的通路，在圖1中，A社區(qū)中A16節(jié)點(diǎn)與B社區(qū)中B7相連接，實(shí)現(xiàn)了A社區(qū)與B社區(qū)的相連，這A1到A16的路徑，B7到B1的路徑都是最短路徑，其它社區(qū)也是類似。如果社區(qū)中存在多條與其它社區(qū)相連的連接，那么在這些多條連接線中選擇一條兩者相加最短的那條。如圖2所示，D（A1，A18）+D（B1，B17）< D（A1，A8）+D（B1，B7），則選擇A1—A18—B17—B1作為最優(yōu)路徑。

定理：社區(qū)網(wǎng)絡(luò)中節(jié)點(diǎn)的到各社區(qū)關(guān)鍵節(jié)點(diǎn)的最短路徑必定在這些社區(qū)中最短路徑的鏈路中的節(jié)點(diǎn)上。

證明：假設(shè)在D社區(qū)中存在一個(gè)節(jié)點(diǎn)D18到其它的關(guān)鍵節(jié)點(diǎn)的最短路徑D（D18，D8）+D（D18，D1）> D（D1，D8），很顯然，D8比D18的距離更短，所以說明社區(qū)網(wǎng)絡(luò)中節(jié)點(diǎn)的到各社區(qū)關(guān)鍵節(jié)點(diǎn)的最短路徑必定在這些社區(qū)中最短路徑的鏈路中的節(jié)點(diǎn)上。

Dijkstra算法用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。該文的基本思想就是在社區(qū)網(wǎng)絡(luò)到各中關(guān)鍵節(jié)點(diǎn)之間的最短路徑的求法，具體算法如下：

Step1：確定社區(qū)的分類。

Step2：利用PangRank算法求社區(qū)的關(guān)鍵節(jié)點(diǎn)。

Step3：確定社區(qū)中關(guān)鍵節(jié)點(diǎn)與其它社區(qū)連接的最短路徑。

Step4：確定到關(guān)鍵節(jié)點(diǎn)的最短路徑的節(jié)點(diǎn)必在這些社區(qū)中最短路徑中的節(jié)點(diǎn)。

Step5：確定序列由這些關(guān)鍵節(jié)點(diǎn)和非關(guān)鍵節(jié)點(diǎn)連接的鏈路中，那個(gè)節(jié)點(diǎn)到其它路徑的距離最短。

Step6：確定了到社區(qū)中各個(gè)關(guān)鍵節(jié)點(diǎn)的最短的節(jié)點(diǎn)后，以此節(jié)點(diǎn)進(jìn)行社交傳播，來比較其傳播效率和相關(guān)時(shí)間。

3 結(jié)語

該文提出一種在社交網(wǎng)絡(luò)中的社區(qū)關(guān)鍵節(jié)點(diǎn)的最短路徑算法，從而對(duì)整個(gè)社交網(wǎng)絡(luò)的傳播帶來時(shí)間上效率并能夠以最快的速度得以實(shí)現(xiàn)。

參考文獻(xiàn)

[1] Milgram S.The small world problem[J].Psychology Today，1967，1（1）：60-67.

[2] Yang B，Liu DY，Liu JM，et al.Complex network clustering algorithms[J].Journal of Software，2009，20（1）：54-66.

[3] Girvan M，Newman MEJ.Community structure in social and biological networks[J].National Academy of Sciences of the UnitedStates of America，2002，99（12）：7821-7826.