一种基于APR算法和MAP算法的社区发现算法

摘要

本发明公开了一种基于APR算法和MAP算法的社区发现算法。该算法包含相似性计算和聚类两个阶段：相似性计算阶段采用本发明提供的基于APR(Approximate PageRank)算法的相似性算法对网络中节点之间的相似性进行计算；聚类阶段采用本发明提供的MAP(Modified Affinity Propagation)算法进行聚类并完成网络中社区的发现，并采用相似性计算阶段的输出作为聚类阶段的输入。提供了一种高效率的基于APR算法的相似性算法。提供了一种改进AP(Affinity Propagation)算法——即MAP算法，该算法缩小了对责任度(Responsibility)和可信度(Availability)的更新范围。与现有技术相比，本发明提供的社区发现算法具有计算效率高、综合网络拓扑结构、可适用于节点之间相似性非対称等优点。

主权项

一种基于APR算法和MAP算法相结合的社区发现算法，其特征在于：算法包含两个阶段(如图1所示)：第一阶段：相似性计算阶段，采用本发明提供的一种基于APR算法的节点之间的相似性算法来计算相似性；第二阶段：聚类阶段，采用上一阶段的输出作为初始输入，并采用一种本发明提供的MAP算法来进行聚类。