基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。

Important-node-based community detection algorithm

The internal community structure is the specific expression of structural features and attribute features in complex networks. First, the maximum k eigenvectors matrix of the modularity matrix of the network was calculated based on the modularity maximization theory. Then, the method of cluster centrality was proposed and used to calculate the important nodes of the k communities as k cluster centralities. The distance between each node and k cluster centralities was calculate by Euclidean distance and each node was assigned to the nearest cluster centrality of the community. Final, k-means iterative calculation method was applied into the network and the k communities divisions was eventually obtained. The algorithm was verified experimentally on both Karate Club Network dataset and American College Football dataset. The experimental results show that the algorithm can effectively identify potential community. The algorithm improves the purity and modularity to a certain extent compared with other community detection algorithms, and with fewer iterations and higher efficiency.