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

社区结构的发现是社交网络分析研究的重要内容,与传统的重叠社区不同,最近的研究表明某些真实网络中在社区重叠部分要比社区内部节点间的连接更加密集,而现有的算法没有考虑此类社区结构。基于遗传算法,提出了一个新颖的方法来发现此类社区划分。为了刻画节点属于多个社区的重叠现象,首次将多维染色体和均匀块交叉算子引入到社区发现算法中。通过实验证明,提出的算法可以很好地发现社交网络中重叠和非重叠的社区结构。

Multidimensional genetic algorithm for overlapping community detection

Community structure identification is an important content of social network analysis. In contrast to traditional definitions of overlapping network community, recent studies have found that overlaps between communities are more densely connected than the non-overlapping parts which are common in real social structures, and existing methods do not consider this kind of community structure. In this paper, we develop an innovative algorithm for detecting dense overlapping communities based on genetic algorithm. In order to characterize of the real situation of the nodes belonging to multiple communities, we first introduce a new multidimensional chromosome and block-uniform crossover in community discovery algorithms. We perform several experimental studies to demonstrate that our method successfully captures overlapping as well a non-overlapping communities.