基于骨干网络扩展的社团检测方法

摘要

本发明公开了一种基于骨干网络扩展的社团检测方法，用于在大规模复杂网络中进行快速的社团发现。本发明主要包括：使用基于节点权重的改进型PageRank算法(WP)对输入的网络进行计算，选取WP值大于阈值的节点作为网络的骨干节点；遍历整体网络，抽取骨干节点和连接任意两个骨干节点的边从而构成骨干网络；在骨干网络中运行层次聚类算法得到骨干社团结构；采用扩展算法，将骨干社团扩展到全网，得到整体网络的社团结构。本发明将层次聚类算法的运行范围缩小到骨干网络，避免在全网进行聚类，具有较小的时间复杂度，适合于大规模复杂网络中的社团发现。另外本发明能够通过追踪骨干社团的变化快速捕获到整体社团的变化细节，适合于快速演变网络中的社团发现。

主权项

一种基于骨干网络扩展的社团检测方法，其特征在于，包括以下步骤：(1)以点对的形式输入网络数据，利用图的数据结构保存网络数据，并形成网络图G(V，E)；(2)使用基于节点权重的改进型PageRank算法(WP)计算网络G(V，E)中节点的影响力(WP值)；根据节点的WP值对网络节点进行排序；按照节点排序结果选取骨干节点；(3)创建骨干网络，将所有的骨干节点以及两个端点均为骨干节点的边加入骨干网络；(4)在骨干网络中运行层次聚类方法，得到骨干社团结构；(5)使用扩展方法，将骨干社团扩展到全网，得到整体网络的社团结构。