Paper Info
Title
A Multi-Objective Genetic Algorithm for overlapping community detection based on edge encoding.
Abstract
The Community Detection Problem (CDP) in Social Networks has been widely studied from different areas such as Data Mining, Graph Theory Physics, or Social Network Analysis, among others. This problem tries to divide a graph into different groups of nodes (communities), according to the graph topology. A partition is a division of the graph where each node belongs to only one community. However, a common feature observed in real-world networks is the existence of overlapping communities, where a given node can belong to more than one community. This paper presents a new Multi-Objective Genetic Algorithm (MOGA-OCD) designed to detect overlapping communities, by using measures related to the network connectivity. For this purpose, the proposed algorithm uses a phenotype-type encoding based on the edge information, and a new fitness function focused on optimizing two classical objectives in CDP: the first one is used to maximize the internal connectivity of the communities, whereas the second one is used to minimize the external connections to the rest of the graph. To select the most appropriate metrics for these objectives, a comparative assessment of several connectivity metrics has been carried out using real-world networks. Finally, the algorithm has been evaluated against other well-known algorithms from the state of the art in CDP. The experimental results show that the proposed approach improves overall the accuracy and quality of alternative methods in CDP, showing its effectiveness as a new powerful algorithm for detecting structured overlapping communities.
Year
DOI
Venue
2018
10.1016/j.ins.2018.06.015
Information Sciences
Keywords
Field
DocType
Multi-Objective genetic algorithms,Overlapping community detection,Graph clustering,Network metrics,Edge-based encoding
Graph theory,Social network,Social network analysis,Theoretical computer science,Fitness function,Artificial intelligence,Partition (number theory),Topological graph theory,Genetic algorithm,Machine learning,Mathematics,Encoding (memory)
Journal
Volume
ISSN
Citations 
462
0020-0255
3
PageRank 
References 
Authors
0.37
20
3
Name
Order
Citations
PageRank
Gema Bello Orgaz111610.36
Sancho Salcedo-Sanz258071.21
david camacho3315.84