International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 11, No. 10, 8 Oct. 2019
Cover page and Table of Contents: PDF (size: 798KB)
Discovering the Maximum Clique in Social Networks Using Artificial Bee Colony Optimization Method
Full Text (PDF, 798KB), PP.1-11
Views: 0 Downloads: 0
Author(s)
Sepide Fotoohi
1
Shahram Saeidi
1,*
Index Terms
Social network analysis, the maximum clique problem, Artificial Bee Colony optimization, Ant Colony Optimization, PS-ACO, DIMACS
Abstract
Social networks are regarded as a specific type of social interactions which include activities such as making somebody’s acquaintance, making friends, cooperating, sharing photos, beliefs, and emotions among individuals or groups of people. Cliques are a certain type of groups that include complete communications among all of its members. The issue of identifying the largest clique in the network is regarded as one of the notable challenges in this domain of study. Up to now, several studies have been conducted in this area and some methods have been proposed for solving the problem. Nevertheless, due to the NP-hard nature of the problem, the solutions proposed by the majority of different methods regarding large networks are not sufficiently desirable. In this paper, using a meta-heuristic method based on Artificial Bee Colony (ABC) optimization, a novel method for finding the largest clique in a given social network is proposed and simulated in Matlab on two dataset groups. The former group consists of 17 standard samples adopted from the literature whit know global optimal solutions, and the latter group includes 6 larger instances adopted from the Facebook social network. The simulation results of the first group indicated that the proposed algorithm managed to find optimal solutions in 16 out of 17 standard test cases. Furthermore, comparison of the results of the proposed method with Ant Colony Optimization (ACO) and the hybrid PS-ACO method on the second group revealed that the proposed algorithm was able to outperform these methods as the network size increases. The evaluation of five DIMACS benchmark instances reveals the high performance in obtaining best-known solutions.
Cite This Paper
Sepide Fotoohi, Shahram Saeidi, "Discovering the Maximum Clique in Social Networks Using Artificial Bee Colony Optimization Method", International Journal of Information Technology and Computer Science(IJITCS), Vol.11, No.10, pp.1-11, 2019. DOI:10.5815/ijitcs.2019.10.01
Reference
[1]D.M. Boyd, N.B. Ellison, “Social network sites: Definition, history, and scholarship” Journal of Computer‐Mediated Communication, 13(1), 210-230, 2007.
[2]T.A. Pempek, Y.A. Yermolayeva, S.L. Calvert, “College students' social networking experiences on Facebook” Journal of Applied Developmental Psychology, 30(3), 227-238, 2009.
[3]F. Can, T. Ozyer, F. Polat, State of the Art Applications of Social Network Analysis, Springer, 2014.
[4]V. Krebs, “Mapping network of terrorist cells”, Connections, 24-45, 2002.
[5]M.T. Thai, P. Pardalos, Handbook of Optimization in Complex Networks, Springer, 2012.
[6]Q. Wu, J. Hao, “A review on algorithms for maximum clique problems”, European Journal of Operations Research, 242(3), 693-709, 2015.
[7]S. Fenet, C. Solnon, “Searching for Maximum Cliques with Ant Colony Optimization”, Applications of Evolutionary Computing, LNCS 2611, 236-245, 2003.
[8]X. Xu, J. Ma, J. Lei, “An Improved Ant Colony Optimization for the Maximum Clique Problem”, Proc. Third International Conference on Natural Computation (ICNC 2007), IEEE Press, Aug. 2007, 766-770, DOI: 10. 1109/ ICNC. 2007. 205, 2007.
[9]A. Rezvanian, M.R. Meybodi, “Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata”, International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems, 23(1), 2015.
[10]M. Soleimani-Pouri, A. Rezvanian, A, M.R. Meybodi, “Finding a Maximum Clique using Ant Colony Optimization and Particle Swarm Optimization in Social Networks”. “DOI: 10.1109/ASONAM.2012.20, 2012.”
[11]F. Carrabs, R. Cerulli, P. Dell’Olmo, “A mathematical programming approach for the maximum labeled clique problem”, Procedia - Social and Behavioral Sciences, 108, 69-78, 2014.
[12]J. Li, X. Wang, Y. Cui, “Uncovering the overlapping community structure of complex networks by maximal cliques”, Physica A, 2014.08.025, 2014.
[13]M.E.J. Newman, M. Girvan, “Finding and evaluating community structure in networks”, Phys. Rev. E, 69(B), 026113, 2004.
[14]M.E.J. Newman, “A fast algorithm for detecting community structure in networks”, Phys. Rev. E, 69(6) 066133, 2004.
[15]M.E.J. Newman, “Finding community structure in networks using the eigenvectors of matrices”, Phys. Rev. E, 74(3), 036104, 2006.
[16]X. Wang, G. Chen, H. Lu, “A very fast algorithm for detecting community structures in complex networks”, Physica A, 384(2), 667–674, 2007.
[17]D.B. Chen, Y. Fu, M. Shang, “A fast and efficient heuristic algorithm for detecting community structures in complex networks”, Physica A, 388 (13), 2741–2749, 2009.
[18]A. Jursa, “Fast algorithm for finding maximum clique in scale-free networks”, ITAT 2016 Proceedings, CEUR Workshop Proceedings, Vol. 1649, 212–217, 2012.
[19]G. Palla, I. Derényi, I. Farkas, T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society”, Nature, 435(9), 814–818, 2005.
[20]R.A. Rossi, D.F. Gleich, A.H. Gebremedhin, M.A. Patwary, “Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage”, arXiv:102.6256v2 [cs.SI] 26 Dec 2013, 2013.
[21]A. Conte, R. DeVirgilio, A. Maccioni, M. Patrignani, R. Torlone, “Finding All Maximal Cliques in Very Large Social Networks”, 10.5441/002/edbt.2016.18, 2016.
[22]C. Lu, X.J. Yu, H. Wei, Y. Zhang, “Finding the maximum clique in massive graphs”, Proceedings of the VLDB Endowment, Vol. 10, No. 11, Copyright 2017 VLDB Endowment 2150-8097/17/07, 1538-1549, 2017.
[23]M. Mitzenmacher, J. Pachocki, R. Peng, C. Tsourakakis, S.C. Xu, “Scalable large near-clique detection in large-scale networks via sampling”. In Proc. of KDD, “DOI: http://dx.doi.org/10.1145/2783258.2783385”, 2015.
[24]A. Dharwadker, The Clique Algorithm, H-501 Palam Vihar, Haryana 122017, India, 2006.
[25]M.T. Belachew, N. Gilli, “Solving the Maximum Clique Problem with Symmetric Rank-One Nonnegative Matrix Approximation”, Journal of Optimization Theory and Applications, 173(1), 279-296, 2017.
[26]A. Badica C. Badica, M. Ivanović, D. Logofatu, “A CLP approach for solving the maximum clique problem: Benefits and limits”, 21st International Conference on System Theory, Control and Computing (ICSTCC), “DOI: 10.1109/ICSTCC.2017.8107103”, 2017.
[27]M. Dorigo, Optimization, Learning, and Natural Algorithms, Ph.D. thesis, Politecnico di Milano, Italy, 1992.
[28]M. Dorigo, V. Maniezzo, A. Colorni, “The ant system: Optimization by a colony of cooperating agents”, IEEE Trans Syst Man Cybern, 26(2), 889-914, 1996.
[29]J. Kennedy, R.C. Eberhart, “Particle swarm optimization”, Proceedings of IEEE conference neural networks, 5, Piscataway, NJ, 1942-1948, 1995.
[30]Y.H. Shi, R.C. Eberhart, “A modified particle swarm optimizer”, Proceedings of 1998 IEEE international conference on evolutionary computation, Anchorage, AK, 69-73, 1998.
[31]B. Shuang, J. Chen, Z. Li, “Study on hybrid PS-ACO algorithm”, Appl Intell, 34, 64-73, 2011.
[32]P. Gutru, R. Dantu, “An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-Hard problems in graph and set theory via clique finding”. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 38(3), 645–666, 2008.
[33]W. Pullan, F. Mascia, M. Brunato, “Cooperating local search for the maximum clique problem”. Journal of Heuristics, 17(2), 181–199, 2011.
[34]S. Cai, K. Su, A. Sattar, “Local search with edge weighting and configuration checking heuristics for minimum vertex cover”. Artificial Intelligence, 175(9-10), 1672–1696, 2011.
[35]Q. Wu, J. Hao, F. Glover, “Multi-neighborhood tabu search for the maximum weight clique problem”. Annals of Operations Research, 196(1), 611–634, 2012.
[36]D.V. Andrade, M. Resende, R.F. Werneck, “Fast local search for the maximum independent set problem”. Journal of Heuristics, 18(4), 525–547, 2012.
[37]U. Benlic, J.K. Hao, “Breakout local search for maximum clique problems”. Computers & Operations Research, 40(1), 192–206, 2013.
[38]Y. Jin, J.K. Hao, “General swap-based multiple neighborhood tabu search for finding maximum independent set”. Engineering Application of Artificial Intelligence, 37, 20–33, 2015.