×

zbMATH — the first resource for mathematics

An ideal point based many-objective optimization for community detection of complex networks. (English) Zbl 1453.90153
Summary: Community detection is one of the major topics in the study of complex networks, which aims to uncover their structural properties. Recently, many evolutionary methods have been successfully employed to identify communities of complex networks. Community detection has been treated so far as a single or multi-objective problem in evolutionary-based approaches. Since each objective covers a specific aspect of the network’s properties, it could result in identification of better community structures to investigate the problem with more than two objectives. In this paper, we proposed a method referred to as MaOCD that formulates community detection as a many objective task. MaOCD uses an ideal-point based strategy to guide the population towards an optimal community structure. The main purpose is to take advantage of optimizing several objectives simultaneously and using a representation that reduces the search space. This enhances the convergence of the method, and automatically determines the number of modules. We introduced a novel metric called IGDC that gives multi/many-objective community detection methods the capability of being comparable regarding multiple objectives. Several experiments were carried out on synthetic and real-world datasets to show the performance of our method. The results demonstrated that MaOCD successfully detected the communities in the network structure compared to some state-of-the-art single and multi-objective methods.
MSC:
90C29 Multi-objective and goal programming
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90C59 Approximation methods and heuristics in mathematical programming
Software:
HypE; MOCK; MOEA/D
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrawal, R., Bi-objective community detection (BOCD) in networks using genetic algorithm, (International Conference on Contemporary Computing. International Conference on Contemporary Computing, Berlin Heidelberg (2011), Springer), 5-15
[2] Altinoz, O. T.; Deb, K.; Yilmaz, A. E., Evaluation of the migrated solutions for distributing reference point-based multi-objective optimization algorithms, Information Sciences, 467, 750-765 (2018)
[3] Bader, J.; Zitzler, E., HypE: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[4] Bara’a, A. A.; Khoder, H. S., A new multi-objective evolutionary framework for community mining in dynamic social networks, Swarm Evol. Comput., 31, 90-109 (2016)
[5] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints, IEEE Trans. Evol. Comput., 18, 4, 577-601 (2014)
[6] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[7] Folino, F.; Pizzuti, C., An evolutionary multiobjective approach for community discovery in dynamic networks, IEEE Trans. Knowl. Data Eng., 26, 8, 1838-1852 (2014)
[8] Fortunato, S.; Barthelemy, M., Resolution limit in community detection, Proc. Natl. Acad. Sci., 104, 1, 36-41 (2007)
[9] Gong, M.; Cai, Q.; Chen, X.; Ma, L., Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition, IEEE Trans. Evol. Comput., 18, 1, 82-97 (2014)
[10] Guerrero, M.; Montoya, F. G.; Baños, R.; Alcayde, A.; Gil, C., Adaptive community detection in complex networks using genetic algorithms, Neurocomputing, 266, 101-113 (2017)
[11] Handl, J.; Knowles, J., An evolutionary approach to multiobjective clustering, IEEE Trans. Evol. Comput., 11, 1, 56-76 (2007)
[12] He, Z.; Yen, G. G., Many-objective evolutionary algorithm: objective space reduction and diversity improvement, IEEE Trans. Evol. Comput., 20, 1, 145-160 (2016)
[13] Kannan, R.; Vempala, S.; Vetta, A., On clusterings: good, bad and spectral, J. ACM (JACM), 51, 497-515 (2004) · Zbl 1192.05160
[14] Labatut, V., Generalized measures for the evaluation of community detection methods, Int. J. Soc. Netw. Mining, 2, 44-63 (2015)
[15] Lancichinetti, A.; Fortunato, S., Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Phys. Rev. E, 80, 1, Article 016118 pp. (2009)
[17] Li, Z.; Liu, J.; Wu, K., A multiobjective evolutionary algorithm based on structural and attribute similarities for community detection in attributed networks, IEEE Trans. Cybernet., 48, 7, 1963-1976 (2018)
[18] Lin, Y.-R.; Chi, Y.; Zhu, S.; Sundaram, H.; Tseng, B. L., Analyzing communities and their evolutions in dynamic social networks, ACM Trans. Knowl. Discovery Data (TKDD), 3, 2, 1-31 (2009)
[19] Liu, C.; Liu, J.; Jiang, Z., A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks, IEEE Trans. Cybernet., 44, 12, 2274-2287 (2014)
[20] Liu, H. L.; Gu, F.; Zhang, Q., Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems, IEEE Trans. Evol. Comput., 18, 3, 450-455 (2014)
[21] Liu, Y.; Gong, D.; Sun, J.; Jin, Y., A many-objective evolutionary algorithm using a one-by-one selection strategy, IEEE Trans. Cybernet., 47, 9, 2689-2702 (2017)
[22] Lu, X.; Kuzmin, K.; Chen, M.; Szymanski, B. K., Adaptive modularity maximization via edge weighting scheme, Info. Sci., 424, 55-68 (2018)
[23] Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., 54, 4, 396-405 (2003)
[24] Mohammadi, M.; Moradi, P.; Jalili, M., SCE: subspace-based core expansion method for community detection in complex networks, Phys. A, 527, Article 121084 pp. (2019)
[25] Moradi, M.; Parsa, S., An evolutionary method for community detection using a novel local search strategy, Phys. A, 523, 457-475 (2019)
[26] Moradi, P.; Rostami, M., Integration of graph clustering with ant colony optimization for feature selection, Knowl. Based Syst., 84, 144-161 (2015)
[27] Mu, C.; Zhang, J.; Jiao, L., An intelligent ant colony optimization for community detection in complex networks, (2014 IEEE Congress on Evolutionary Computation (CEC) (2014), IEEE), 700-706
[28] Girvan, M.; Newman, M. E.J., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, Article 026113 pp. (2004)
[29] Pizzuti, C., Ga-net: a genetic algorithm for community detection in social networks, (International Conference on Parallel Problem Solving from Nature (2008), Springer), 1081-1090
[30] Pizzuti, C., A multiobjective genetic algorithm to find communities in complex networks, IEEE Trans. Evol. Comput., 16, 3, 418-430 (2012)
[31] Pizzuti, C., Evolutionary computation for community detection in networks: a review, IEEE Trans. Evol. Comput., 22, 3, 464-483 (2018)
[32] Purshouse, R. C.; Fleming, P. J., On the evolutionary optimization of many conflicting objectives, IEEE Trans. Evol. Comput., 11, 6, 770-784 (2007)
[33] Rahimi, S.; Abdollahpouri, A.; Moradi, P., A multi-objective particle swarm optimization algorithm for community detection in complex networks, Swarm Evol. Comput., 39, 297-309 (2017)
[34] Rand, W. M., Objective criteria for the evaluation of clustering methods, J. Am. Stat. Assoc., 66, 336, 846-850 (1971)
[35] Rezaeimehr, F.; Moradi, P.; Ahmadian, S.; Qader, N. N.; Jalili, M., TCARS: time- and community-aware recommendation system, Future Gener. Comput. Syst., 78, 419-429 (2018)
[36] Schutze, O.; Esquivel, X.; Lara, A.; Coello, C. A.C., Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization, IEEE Trans. Evol. Comput., 16, 4, 504-522 (2012)
[37] Shang, J.; Liu, L.; Li, X.; Xie, F.; Wu, C., Epidemic spreading on complex networks with overlapping and non-overlapping community structure, Phys. A, 419, 171-182 (2015) · Zbl 1395.92165
[38] Shi, C.; Yan, Z.; Wang, Y.; Cai, Y.; Wu, B., A genetic algorithm for detecting communities in large-scale complex networks, Adv. Complex Syst., 13, 01, 3-17 (2010) · Zbl 1184.90026
[39] Wen, X.; Chen, W.-N.; Lin, Y.; Gu, T.; Zhang, H.; Li, Y.; Yin, Y.; Zhang, J., A maximal clique based multiobjective evolutionary algorithm for overlapping community detection, IEEE Trans. Evol. Comput., 21, 363-377 (2017)
[40] Whang, J. J.; Gleich, D. F.; Dhillon, I. S., Overlapping community detection using neighborhood-inflated seed expansion, IEEE Trans. Knowl. Data Eng., 28, 5, 1272-1284 (2016)
[41] Wu, W.; Kwong, S.; Zhou, Y.; Jia, Y.; Gao, W., Nonnegative matrix factorization with mixed hypergraph regularization for community detection, Info. Sci., 435, 263-281 (2018)
[42] Žalik, K. R.; Žalik, B., Memetic algorithm using node entropy and partition entropy for community detection in networks, Info. Sci., 445, 38-49 (2018)
[43] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 712-731 (2007)
[44] Zhou, C.; Dai, G.; Zhang, C.; Li, X.; Ma, K., Entropy based evolutionary algorithm with adaptive reference points for many-objective optimization problems, Info. Sci., 465, 232-247 (2018)
[45] Zhou, X.; Zhao, X.; Liu, Y., A multiobjective discrete bat algorithm for community detection in dynamic networks, Appl. Intell., 48, 9, 3081-3093 (2018)
[46] Zitzler, E.; Künzli, S., Indicator-based selection in multiobjective search, (International Conference on Parallel Problem Solving from Nature. International Conference on Parallel Problem Solving from Nature, Berlin Heidelberg (2004), Springer), 832-842
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.