一种基于社交网络的社区关键节点的最短路径算法

付东炜

摘 要：随着社交网络的兴起，对于社交网络分析算法的性能提出了更高的要求和现实网络中最短路径的分布规律。提出一种基于社交网络的社区关键节点最短路径算法，该算法对社交网络进行社区划分，确定每个社区内的核心节点与非核心节点的最短路径，再与其它社区进行相关联，最终确定全局最短路径就在这些社区间的核心节点与非核心节点的链路上。

关键词：社交网络 最短路径 社区划分 核心节点

中图分类号：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.