Computer Science Department, Escuela Politecnica Superior, Universidad Autónoma de Madrid, 28049, Madrid, Spain.
Int J Neural Syst. 2012 Oct;22(5):1250018. doi: 10.1142/S0129065712500189. Epub 2012 Aug 23.
The graph clustering problem has become highly relevant due to the growing interest of several research communities in social networks and their possible applications. Overlapped graph clustering algorithms try to find subsets of nodes that can belong to different clusters. In social network-based applications it is quite usual for a node of the network to belong to different groups, or communities, in the graph. Therefore, algorithms trying to discover, or analyze, the behavior of these networks needed to handle this feature, detecting and identifying the overlapped nodes. This paper shows a soft clustering approach based on a genetic algorithm where a new encoding is designed to achieve two main goals: first, the automatic adaptation of the number of communities that can be detected and second, the definition of several fitness functions that guide the searching process using some measures extracted from graph theory. Finally, our approach has been experimentally tested using the Eurovision contest dataset, a well-known social-based data network, to show how overlapped communities can be found using our method.
由于几个研究社区对社交网络及其可能的应用越来越感兴趣，图聚类问题变得非常重要。重叠图聚类算法试图找到可以属于不同簇的节点子集。在基于社交网络的应用中，网络中的一个节点通常属于图中的不同组或社区。因此，试图发现或分析这些网络行为的算法需要处理这个特征，检测和识别重叠节点。本文提出了一种基于遗传算法的软聚类方法，其中设计了一种新的编码来实现两个主要目标：首先，自动适应可以检测到的社区数量，其次，定义几个适应度函数，使用从图论中提取的一些度量来指导搜索过程。最后，我们的方法使用 Eurovision 竞赛数据集进行了实验测试，这是一个著名的基于社交的数据网络，以展示如何使用我们的方法找到重叠社区。
