基于边重整化方法的新社团检测算法

A new community detection algorithm based on edge renormalization method

现实网络构造过程中,存在连接数据不完整甚至自相矛盾等问题,且现有的社团检测算法易出现丢失部分连接信息等现象,为此,提出一种基于边重整化方法的新社团检测算法。根据“节点间相似性越小则属于同一社团的概率也越小”原理,引入节点间随机游走的稳态概率来衡量节点之间的相似性,不断移除相似性最小的现存连边,并补充相似性最大的丢失连边,以保持网络总连接边数不变。最后通过实例验证了新社团检测算法的有效性。

Community detecting of complex networks provides an important theoretical basis for analyzing network topology and level,predicting network evolution mechanism,and controlling network dynamics.Some incomplete even self-contradiction network data are generally available in the process of actual network construction,and existing community detection algorithms,whether they are agglomerating or splitting,will lose most of the network connection information.A new community detecting algorithm based on edge renormalization is proposed to preserve the network connection information as much as possible.The principle of the new algorithm is the intuitive rule of"the smaller the similarity between nodes,the lower the probability of belonging to the same community".The steady-state probability of random walk between nodes is innovatively introduced to measure their similarity.The existing edges with the least similarity are removed while the new edges with greatest similarity are added into the network to keep the total number of edges unchanged.Finally,the effectiveness of the new community detection algorithm is verified by four real-world networks.