一種基于社交網絡的社區關鍵節點的最短路徑算法

付東煒

摘 要：隨著社交網絡的興起，對于社交網絡分析算法的性能提出了更高的要求和現實網絡中最短路徑的分布規律。提出一種基于社交網絡的社區關鍵節點最短路徑算法，該算法對社交網絡進行社區劃分，確定每個社區內的核心節點與非核心節點的最短路徑，再與其它社區進行相關聯，最終確定全局最短路徑就在這些社區間的核心節點與非核心節點的鏈路上。

關鍵詞：社交網絡 最短路徑 社區劃分 核心節點

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

社交網絡可以描述為圖的應用，基于此類算法來分析社交網絡的相關性質，而分析的基礎為計算社交網絡中的最短路徑，計算過程具有復雜性和性能方面等問題。

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

1 社交網絡關鍵節點定義

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

定義：如果一個節點屬于整個社交網絡中關鍵節點，那么這個節點也屬于某個社區的關鍵節點；同理，如果一個節點屬于某個社區的關鍵節點，一定屬于全局關鍵節點集。關鍵節點集用Ps，而社區中關鍵節點集用Pik，節點用Pi來表示。

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

其中k表示社區號，i表示節點號，一般一個社區至少有一個關鍵節點。

2 基于社區關鍵節點的Dijkstra算法

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

定理：社區網絡中節點的到各社區關鍵節點的最短路徑必定在這些社區中最短路徑的鏈路中的節點上。

證明：假設在D社區中存在一個節點D18到其它的關鍵節點的最短路徑D（D18，D8）+D（D18，D1）> D（D1，D8），很顯然，D8比D18的距離更短，所以說明社區網絡中節點的到各社區關鍵節點的最短路徑必定在這些社區中最短路徑的鏈路中的節點上。

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

Step1：確定社區的分類。

Step2：利用PangRank算法求社區的關鍵節點。

Step3：確定社區中關鍵節點與其它社區連接的最短路徑。

Step4：確定到關鍵節點的最短路徑的節點必在這些社區中最短路徑中的節點。

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

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

3 結語

該文提出一種在社交網絡中的社區關鍵節點的最短路徑算法，從而對整個社交網絡的傳播帶來時間上效率并能夠以最快的速度得以實現。

參考文獻

[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.