Actas de congresos
Identifying Overlapping Communities In Complex Networks With Multimodal Optimization
Registro en:
9781479904549
2013 Ieee Congress On Evolutionary Computation, Cec 2013. , v. , n. , p. 269 - 276, 2013.
10.1109/CEC.2013.6557580
2-s2.0-84881608984
Autor
De Franca F.O.
Coelho G.P.
Institución
Resumen
The analysis of complex networks is an important research topic that helps us understand the underlying behavior of complex systems and the interactions of their components. One particularly relevant analysis is the detection of communities formed by such interactions. Most community detection algorithms work as optimization tools that minimize a given quality function, while assuming that each node belongs to a single community. However, most complex networks contain nodes that belong to two or more communities, which are called bridges. The identification of bridges is crucial to several problems, as they often play important roles in the system described by the network. By exploiting the multimodality of quality functions, it is possible to obtain distinct optimal communities where, in each solution, each bridge node belongs to a distinct community. This paper proposes a technique that tries to identify a set of (possibly) overlapping communities by combining diverse solutions contained in a pool, which correspond to disjoint community partitions of a given network. To obtain the pool of partitions, an adapted version of the immune-inspired algorithm named cob-aiNet[C] was adopted here. The proposed methodology was applied to four real-world social networks and the obtained results were compared to those reported in the literature. The comparisons have shown that the proposed approach is competitive and even capable of overcoming the best results reported for some of the problems. © 2013 IEEE.
269 276 Girvan, M., Newman, M.E.J., Community structure in social and biological networks (2002) Physical Review, e, 99 Simon, H.A., On a class of skew distribution functions (1955) Biometrika, pp. 425-440 Merton, R.K., The Matthew effect in science (1968) Science, 159 (3810), pp. 56-63 Newman, M.E.J., Power laws, Pareto distributions and Zipf's law (2005) Contemporary Physics, 46 (5), pp. 323-351 Xie, J., Kelley, S., Szymanski, B.K., Overlapping community detection in networks: The state of the art and comparative study (2013) ACM Computing Surveys, 45 (4) Newman, M.E.J., Girvan, M., Finding and evaluating community structure in networks (2004) Proceedings of the National Academy of Sciences of the United States of America, 99 (12), pp. 7821-7826 Yang, X.S., (2009) Firefly Algorithms for Multimodal Optimization, pp. 169-178. , Stochastic Algorithms: Foundations and Applications De França, F.O., Coelho, G.P., Von Zuben, F.J., On the diversity mechanisms of opt-aiNet: A comparative study with fitness sharing (2010) Proc. of the 2010 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp. 1-8 De França, F.O., Coelho, G.P., Castro, P.A.D., Von Zuben, F.J., Conceptual and practical aspects of the aiNet family of algorithms (2010) International Journal of Natural Computing Research, 1 (1), pp. 1-35 De Castro, L.N., Timmis, J., An artificial immune network for multimodal function optimization Proc. of the 2002 IEEE Congress on Evolutionary Computation (CEC), 1, pp. 699-704. , IEEE 2002 De França, F.O., Von Zuben, F.J., De Castro, L.N., An artificial immune network for multimodal function optimization on dynamic environments (2005) Proc. of the 2005 Conference on Genetic and Evolutionary Computation (GECCO) ACM, pp. 289-296 De França, F.O., Von Zuben, F.J., A dynamic artificial immune algorithm applied to challenging benchmarking problems (2009) Proc. of the 2009 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp. 423-430 Coelho, G.P., Von Zuben, F.J., A concentration-based artificial immune network for continuous optimization (2010) Proc. of the 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 108-115 Coelho, G.P., De França, F.O., Von Zuben, F.J., A concentrationbased artificial immune network for combinatorial optimization (2011) Proc. of the 2011 IEEE Congress on Evolutionary Computation (CEC) Adamcsek, B., Palla, G., Farkas, I., Derényi, I., Vicsek, T., CFinder: Locating cliques and overlapping modules in biological networks (2006) Bioinformatics, 22 (8), pp. 1021-1023 Lee, C., Reid, F., McDaid, A., Hurley, N., (2010) Detecting Highly Overlapping Community Structure by Greedy Clique Expansion, , arXiv preprint arXiv 10021827 Shen, H., Cheng, X., Guo, J., Quantifying and identifying the overlapping community structure in networks (2009) Journal of Statistical Mechanics: Theory and Experiment, 2009 (7), pp. P07042 Lancichinetti, A., Fortunato, S., Kertész, J., Detecting the overlapping and hierarchical community structure in complex networks (2009) New Journal of Physics, 11 (3), p. 033015 Nepusz, T., Petróczi, A., Négyessy, L., Bazsó, F., Fuzzy communities and the concept of bridgeness in complex networks (2008) Physical Review e, 77 (1), p. 016107 Gregory, S., Finding overlapping communities in networks by label propagation (2010) New Journal of Physics, 12 (10), p. 103018 Chen, W., Liu, Z., Sun, X., Wang, Y., A game-theoretic framework to identify overlapping communities in social networks (2010) Data Mining and Knowledge Discovery, 21 (2), pp. 224-240 Gregory, S., An algorithm to find overlapping community structure in networks (2007) Knowledge Discovery in Databases: PKDD, 2007, pp. 91-102 Burnet, F.M., Clonal selection and after (1978) Theoretical Immunology, pp. 63-85. , G I. Bell, A. S. Perelson, and G. H. Pimgley Jr, Eds Marcel Dekker Inc Jerne, N.K., Towards a network theory of the immune system (1974) Annales d'Immunologie, 125 (1-2), pp. 373-389 Chira, C., Gog, A., Iclanzan, D., Evolutionary detection of community structures in complex networks: A new fitness function (2012) Proc. of the 2012 IEEE Congress on Evolutionary Computation (CEC). IEEE, pp. 1719-1725 Danon, L., Dáz-Guilera, A., Duch, J., Arenas, A., Comparing community structure identification (2005) Journal of Statistical Mechanics: Theory and Experiment, 2005, pp. P09008 Aldecoa, R., Maŕn, I., Deciphering network community structure by surprise (2011) PLoS ONE, 6 (9), pp. e24195 Shen, H., Cheng, X., Guo, J., Quantifying and identifying the overlapping community structure in networks (2009) J. Stat. Mech, 7 (9) Zachary, W.W., An information flow model for conflict and fission in small groups (1977) Journal of Anthropological Research, 33, pp. 452-473 Knuth, D.E., (1993) The Stanford GraphBase: A Platform for Combinatorial Computing, , Reading MA Addison-Wesley 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 (2003) Behavioral Ecology and Sociobiology, 54 (4), pp. 396-405