Detecting communities in complex networks-A discrete hybrid evolutionary approach

被引：5

作者：

Banati H. ^{[1
]}

Arora N. ^{[2
]}

机构：

[1] Department of Computer Science, Dyal Singh College, University of Delhi, Delhi

[2] Department of Computer Science, Kalindi College, University of Delhi, Delhi

来源：

International Journal of Computers and Applications | 2016年 / 38卷 / 01期

关键词：

Community detection; complex networks; evolutionary algorithms; group search optimization; teachers learners based optimization; hybrid algorithms;

D O I：

10.1080/1206212X.2016.1210280

中图分类号：

学科分类号：

摘要：

Evolving densely connected communities of nodes in the real life complex networks is a computationally extensive (NP hard) problem. Nature based evolutionary heuristic algorithms provide an effective solution to such kind of problems. However, very few evolutionary approaches have been tested on this domain with most of them applying real time operators. Incorporating discrete behaviour in the evolutionary process can further lead to improvisation in the overall efficiency of the applied algorithm. This paper proposes a discrete adaption of the TL-GSO community detection (CD) algorithm for faster convergence of the optimization function in comparison to the existing variants of Group Search Optimization (GSO) and TL-GSO. The approach mixes the exploration strategies of Teachers Learners (I-TLBO) and GSO algorithms to detect communities in complex networks. It modifies the optical search of GSO to step search and real time crossover to single point crossover. The modifications result in minimizing the parameters to be externally set. Optimized search space reduces the runtime and evolve communities in an unsupervised manner. Experimental results on real and synthetic networks show that the proposed algorithm converges faster and evolves to accurate communities with high fitness as compared to varied state of the art CD algorithms. © 2016 Informa UK Limited.

引用

页码：29 / 40

页数：11

共 35 条

[1]

Zhou Y., Cheng H., Yu J.X., Graph clustering based on structural/attribute similarities, Proceedings of VLDB Endowment, 2, pp. 718-729, (2009)

[2]

Chen D., Wang D., Xia F., A modularity degree based heuristic community detection algorithm, Math. Prob. Eng., 2014, pp. 1-9, (2014)

[3]

Pothen A., Horst S.D., Liou K.P., Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11, pp. 430-452, (1990)

[4]

Kernighan B., Lin S., An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, pp. 291-307, (1970)

[5]

Ankerst M., Breunig M.M., Kriegel H.P., Et al., Optics:ordering points to identify the clustering structure, ACM SIGMOD Record., 28, pp. 49-60, (1999)

[6]

Easter M., Kriegel H.P., Sander J., Et al., A density based algorithm for discovering clusters in large spatial databases with noise, KDD., 96, pp. 226-231, (1996)

[7]

Girvan M., Newman M.E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA., 99, pp. 7821-7826, (2002)

[8]

Newman M.E.J., Fast algorithm for detecting community structure in networks, Phys. Rev., E69, pp. 1-5, (2004)

[9]

Clauset A., Newman M.E.J., Moore C., Finding community structure in very large networks, Phys. Rev. E., 70, (2004)

[10]

Hafez A.I., Zawbaa H.M., Hassanien A.E., Et al., Networks community detection using artificial bee colony swarm optimization, Fifth International Conference on Innovations in Bio-inspired Computing and Applications 2014. Proceedings, pp. 229-239, (2014)

← 1 2 3 4 →