付东炜

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

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

中图分类号：TP293 文献标识码：A 文章编号：1672-3791（2017）04（a）-0223-02

社交网络可以描述为图的应用，基于此类算法来分析社交网络的相关性质，而分析的基础为计算社交网络中的最短路径，计算过程具有复杂性和性能方面等问题。

Milgram[1]提出的“六度分离”性质，就是对社会网络最短路径长度的假设；许多聚类算法也需要节点之间的距离或最短路径信息[2]，如Girvan-Newman 算法[3]等.都是典型的最短路径查找问题。

1 社交网络关键节点定义

社交网络最理想的核心节点，即认为与网络中所有节点均有边相连接的节点为最重要的核心节点，如星形网中的中心节点显然是网络中最重要的“核心节点”，可以通过重点保护这些核心节点提高整个网络的可靠性，也可以通过攻击这些“薄弱环节”达到摧毁整个网络的目的。然而在社交网络是一个稀疏矩阵，各个社区之间的连接少，而社区内信息交流量大。

定义：如果一个节点属于整个社交网络中关键节点，那么这个节点也属于某个社区的关键节点；……