基于共邻节点相似度的加权网络社区发现方法

Community discovery in weighted social networks based on similarities of common neighbors

摘要:

为实现加权网络的准确划分，发现真实的社区结构，提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM。首先，定义两节点间基于共邻节点的相似度。之后，基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区，并进行社区扩展。最后，以最大化网络模块度为目标进行社区合并以优化划分结果。算法通过形成初始社区、扩展社区、合并社区三步，实现了加权网络合理有效的社区划分。以加权模块度作为社区划分质量的评价标准，在多个数据集上的实验结果表明，IEM算法优于加权CN、加权AA、加权RA。同时，与CRMA算法相比，IEM算法对加权网络社区划分的有效性和正确性更高。

Abstract:

In order to divide communities accurately in weighted networks, a hierarchical clustering method IEM based on the similarity and modularity is proposed. Firstly, the similarity of the two nodes is defined based on attributes of their common neighbors. Then, the most closely related nodes are clustered fastly according to their similarity to form the initial community and expand it. Lastly, these communities are merged with the goal of maxmizing the modularity so as to optimize division re sults. The algorithm achieves more reasonable and effective community division for weighted network by three steps of initializing, expanding and merging communities. Correctness and effectiveness of the algorithm are verified through experiments on many weighted networks using weighted modularity as evaluation index. Results show that IEM is superior to weighted CN, weighted AA and weighted RA. Moreover, it can achieve the higher quality of community division in weighted networks compared with CRMA algorithm.