A weak clique based multi objective genetic algorithm for overlapping community detection in complex networks
- PDF / 2,334,142 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 84 Downloads / 191 Views
ORIGINAL RESEARCH
A weak clique based multi objective genetic algorithm for overlapping community detection in complex networks M. Sathyakala1 · M. Sangeetha2 Received: 23 March 2020 / Accepted: 2 July 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Community detection is an important technique to find hidden information, pattern, and relation in a complex network. All the traditional community detection algorithms focus on the separated community but in real-world networks, most of the community is overlapping. Detecting overlapping community thus becomes essential. Although overlapping community detection techniques based on clique, has exposed hopeful performance but suffers from the serious curse of dimensionality due to its high computational complexity, when comes to large-scale networks. To deal with this drawback this paper proposes a weak clique based multi objective evolutionary algorithm for overlapping community detection. In this algorithm, a novel gene pattern is designed using a weak_clique graph. The weak cliques in the original graph are the nodes in the weak clique graph. The weak clique is formulated by selecting two neighbours which are very similar. Any two nodes in the weak clique are differed at most two node distances. The weak cliques comprise of more than one actual node thus weak cliques share actual nodes. This property of weak clique graph allows finding overlapping communities with high accuracy and low computational cost. Experiments on a variety of real-world and artificial networks validate the performance of the proposed algorithm. Keywords Complex networks · Genetic algorithm · Community detection · Overlapping community detection
1 Introduction The recent research focus in the field of complex network analysis is Community Detection. Because of absence of generally approved definition for Communities there is lot of definitions and algorithms for community detection. But the widely accepted definition is that the nodes in the same community have dense connections and have sparse connections between communities (Girvan and Newman 2002; Newman 2003). The huge number of possible way of splitting the n nodes in to C communities formulates the problem as costly optimization problem which results in large differences between solutions. * M. Sathyakala [email protected] M. Sangeetha [email protected] 1
Department of Information Technology, Institute of Road and Transport Technology, Erode, Tamilnadu, India
Department of Information Technology, Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India
2
Community detection has its application in the field of the biological network such as protein–protein interaction network, (Maslov and Sneppen 2002; Han et al. 2004) residue interaction (Hu et al. 2014), and gene–gene interactions networks (Özgür et al. 2008). Complex network models are everywhere in the field of Computer Science. Several Complex systems are modelled as graph structure which helps the study of the complex syste
Data Loading...
