付東煒

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

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

中圖分類號：TP293 文獻標識碼：A 文章編號：1672-3791（2017）04（a）-0223-02

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

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

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

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

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

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

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

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

該文提出了在現(xiàn)實網(wǎng)絡(luò)中關(guān)于最短路徑規(guī)律的一個假設(shè)，在實際研究發(fā)現(xiàn)對于全局關(guān)鍵節(jié)點，到各點的距離仍然也是存在不可預(yù)測性，因此，提出到各個社區(qū)的關(guān)鍵節(jié)點，局部關(guān)鍵節(jié)點的最短路徑問題研究?？梢蕴岣呔W(wǎng)絡(luò)的傳播速率和效率，也可降低信息不成功到達率，從而提高用戶的滿意度。便于對社區(qū)結(jié)構(gòu)更加了解，先要確定在社區(qū)中連接處部社區(qū)的最短路徑的通路，在圖1中，A社區(qū)中A16節(jié)點與B社區(qū)中B7相連接，實現(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é)點的到各社區(qū)關(guān)鍵節(jié)點的最短路徑必定在這些社區(qū)中最短路徑的鏈路中的節(jié)點上。

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

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

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

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

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

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

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

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

3 結(jié)語

該文提出一種在社交網(wǎng)絡(luò)中的社區(qū)關(guān)鍵節(jié)點的最短路徑算法，從而對整個社交網(wǎng)絡(luò)的傳播帶來時間上效率并能夠以最快的速度得以實現(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.