WSEAS Transactions on Systems and Control


Print ISSN: 1991-8763
E-ISSN: 2224-2856

Volume 14, 2019

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

Volume 14, 2019


Finding a Maximum Clique in Social Networks using a Modified Differential Evolution Algorithm

AUTHORS: Jutamard Wongpen, Jeerayut Wetweerapong, Pikul Puphasuk

Download as PDF

ABSTRACT: The relationships of the individuals in social networks give rise to interesting and important features in various fields, such as graph mining and communication networks. Among those useful features are clique structures which represent fully connected relations between members, and the maximum cliques which identify the highest-connected subgroups. In this work, we propose the modified differential evolution algorithm (moDE) for finding a maximum clique in social networks. The moDE solves the constrained continuous optimization problem which is transformed from the discrete maximum clique problem. It uses a new mutation strategy to generate and adjust mutant vectors, mixes two important crossover rates in crossover, and incorporates the extracting and extending clique procedure to increase the performance of clique finding. The algorithm is tested on several social network problems and compared with the previously developed method. The results show that moDE is effective for finding a maximum clique and outperforms the compared method.

KEYWORDS: Maximum clique problem, social network, differential evolution algorithm, constrained continuous optimization problem

REFERENCES:

[1] B. Balasundaram and S. Butenko, Graph domination, coloring and cliques in telecommunications, Handbook of Optimization in Telecommunications, pp. 865-890, Springer, 2006.

[2] E. Tomita, T. Akutsu and T. Matsunaga, Efficient algorithms for finding maximum and maximal cliques: Effective tools for bioinformatics, in A. N. Laskovski (Eds.), Biomedical Engineering Trends in Electronics, Communications and Software, pp. 625-640, InTech, 2011.

[3] M. Soleimani-Pouri, A. Rezvanian and M. R. Meybodi, An ant based particle swarm optimization algorithm for maximum clique problem in social network, in F. Can, T. Ozyer and F. Polat (eds.), State of the art applications of social network analysis, Lecture notes in social networks, pp. 295-304, Springer International Publishing, 2014.

[4] R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (Eds.), Complexity of Computer Computations, pp. 85-103, Plenum Press, 1972.

[5] P. M. Pardalos and G. P. Rodgers, A branch and bound algorithm for the maximum clique problem, Computers Ops Res, 19(5), 1992, pp. 363-375.

[6] M. Gendreau, P. Soriano and L. Salvail, Solving the maximum clique problem using a tabu search approach, Annals of Operations Research, 41(4), 1993, pp. 385-403.

[7] I. M. Bomze, M. Budinich, P. M. Pardalos and M. Pelillo, The Maximum Clique Problem, in D. Z. Du and P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization, pp. 1-74. Kluwer Academic Publishers, 1999.

[8] P. Hansen, N. Mladenovic and D. Urosevic, Variable neighborhood search for the maximum clique, Discrete Applied Mathematics, 145, 2004, pp. 117-125.

[9] E. Marchiori, Genetic, iterated and multistart local search for the maximum clique problem, Proceedings of the Applications of Evolutionary Computing on EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN ,2002, pp. 112- 121.

[10] C. Solnon and S. Fenet, A study of ACO capabilities for solving the maximum clique problem, J Heuristics, 12, 2006, pp. 155-180.

[11] S. Das, S. S. Mullick and P. N. Suganthan, Recent advances in differential evolution - An updated survey, Swarm and Evolutionary Computation, 27, 2016, pp. 1-30.

[12] R. Storn and K. Price, Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces, J Glob Optim, 11(4), 1997, pp. 341-359.

[13] T. S. Motzkin and E. G. Straus, Maxima for Graphs and a new proof of a theorem of Turán, Canadian Journal of Mathematics, 17, 1965, pp. 533-540.

[14] R. Storn, Differential evolution research-trends and open questions, in U. K. Chakraborty (ed.), Advances in Differential Evolution, pp. 1-31, Springer, 2008.

[15] F. Neri and V. Tirronen, Recent advances in differential evolution: a survey and experimental analysis, Artif Intell Rev, 33, 2010, pp. 61-106.

[16] S. Das and P. N. Suganthan, Differential evolution: a survey of the state-of-the-art, IEEE Trans Evol Comput, 15(1), 2011, pp. 4-31.

[17] J. Lampinen and I. Zelinka, On stagnation of the differential evolution algorithm, Proceeding of the 6th international Mendel conference on soft computing, 2002, pp. 76-83.

[18] R. Gamperle, S. D. Muller and P. Koumoutsakos, A parameter study for differential evolution, Proceeding of the conference in neural networks and applications (NNA), fuzzy sets and fuzzy systems (FSFS) and evolutionary computation (EC), WSEAS, 2002, pp. 293-298.

[19] Network repository: A scientific network data repository with interactive visualization and mining tools. http://networkrepository.com/ index.php.

[20] SocNetV: Social Network Analysis and Visualization Software. https://socnetv.org.

WSEAS Transactions on Systems and Control, ISSN / E-ISSN: 1991-8763 / 2224-2856, Volume 14, 2019, Art. #42, pp. 333-342


Copyright Β© 2019 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board

Currently:

The editorial board is accepting papers.


WSEAS Main Site