一种基于多维遗传算法的重叠社区发现方法

摘要

社区结构的发现是社交网络分析研究的重要内容。与传统的重叠社区不同，最近的研究表明某些真实网络中在社区重叠部分要比社区内部节点间的连接更加密集，而现有的算法没有考虑此类社区结构。基于遗传算法，提出了一种新颖的方法来发现此类社区划分。为了刻画节点属于多个社区的重叠现象，首次将多维染色体和均匀块交叉算子引入到社区发现算法中。通过实验证明，提出的算法可以很好地发现社交网络中重叠和非重叠的社区结构。%Community structure identification is an important content of social network analysis.In contrast to traditional defi-nitions of overlapping network community,recent studies have found that overlaps between communities are more densely con-nected than the non-overlapping parts which are common in real social structures,and existing methods do not consider this kind of community structure.This paper developed an innovative algorithm for detecting dense overlapping communities based on genetic algorithm.In order to characterize the real situation of the nodes belonging to multiple communities,it first intro-duced a new multidimensional chromosome and block-uniform crossover in community discovery algorithms.It performed several experimental studies to demonstrate that this method successfully captures overlapping as well as non-overlapping communities.