基于网络有效阻抗的社区发现算法
Community detection algorithm based on effective resistance of network

摘要： 社区发现在很多领域都有非常重要的应用。受经典电路网络中的阻抗原理启发,提出了一个新颖的社区发现算法。该算法通过迭代调用基于网络总阻抗的割边选择模型来实现社区发现的目标。在每一次迭代过程中,割边选择模型采用启发式策略割除恰当数量的边,使得割边后的网络有效阻抗最大化。理论分析表明该算法具有较低的算法复杂度。利用仿真数据和真实数据对算法进行测试,实验结果表明算法性能良好。
Abstract: Community detection has a number of important applications in many areas. Inspired by the principle of effective resistance in traditional electrical circuit, we propose a novel community detection algorithm which can discover communities by iteratively calling the edge-cutting selection model based on the total effective resistance of a network. In each iteration, the edge-cutting selection model cuts an appropriate number of edges in order to maximize the total effective resistance of the updated network. Theoretical analysis shows that our algorithm has relatively low algorithm complexity degree. Extensive empirical experiments have been conducted on simulated and real complex networks, the results show that the proposed algorithm has good performance