Detecção de comunidades em redes complexas: um modelo de correlação oscilatória

• Marcos G. Quiles USP
• Liang Zhao USP
• Fabricio A. Breve USP
• Roseli A. F. Romero USP

Resumo

Uma característica saliente em redes complexas é a presença de comunidades, ou grupos de vértices densamente conectados. A detecção de comunidades pode além de auxiliar na compreensão da estrutura topológica da rede também fornecer novas técnicas para aplicações reais, como por exemplo, em mineração de dados. Neste artigo, um novo modelo para detecção de comunidades baseado na teoria da correlação oscilatória é proposto. Este modelo foi aplicado em diversas redes artificiais e reais e os resultados obtidos mostram seu bom desempenho e precisão.

Referências

Boccaletti, S., Ivanchenko, M., Latora, V., Pluchino, A., & Rapisarda, A. (2007). “Detecting complex network modularity by dynamical clustering”. Physical Review E, 75:045102(1–4).

Clauset, A. (2005). “Finding local community structure in networks”. Physical Review E, 72:026132(1–6).

Cook, D. J. & Holder, L. B. (2000). “Graph-based data mining”. IEEE Intelligent Systems, 15:32–41.

Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005). “Comparing community structure identification”. Journal of Statistical Mechanics: Theory and Experiment, P09008:1–10.

Flake, G. W., Lawrence, S., Giles, C. L., & Coetzee, F. M. (2002). “Self-organization and identification of web communities”. IEEE Computer, 35(3):66–70.

Girvan, M. & Newman, M. E. J. (2002). “Community structure in social and biological networks”. Proceedings of the National Academy of Sciences of the USA, 99(2):7821–7826.

Guimerà, R. & Amaral, L. A. N. (2005). “Functional cartography of complex metabolic networks”. Nature, 433:895–900.

Guimerà, R., Mossa, S., Turtschi, A., & Amaral, L. A. N. (2003). “The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles”. Proceedings of the National Academy of Sciences of the USA, 102(22):7704–7709.

Izhikevich, E. M. (2004). “Which model to use for cortical spiking neurons?” IEEE Transactions on Neural Networks, 15(5):1063–1070.

Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000). “The large scale organization of metabolic networks”. Nature, 407:651–654.

Karypis, G., Han, E.-H., & Kumar, V. (1999). “Chameleon: hierarchical clustering using dynamic modeling”. IEEE Computer, 32:68–75.

Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). “The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. can geographic isolation explain this unique trait?” Behavioral Ecology and Sociobiology, 54:396–405.

Newman, M. E. J. (2004a). “Detecting community structure in networks”. The European Physical Journal B, 38:321–330.

Newman, M. E. J. (2004b). “Fast algorithm for detecting community structure in networks”. Physical Review E, 69:066133(1–5).

Newman, M. E. J. & Girvan, M. (2004). “Finding and evaluating community structure in networks”. Physical Review E, 69:026113(1–15).

Quiles, M. G., Zhao, L., Alonso, R. L., & Romero, R. A. F. (2008). “Particle competition for complex network community detection”. Chaos (Woodbury), 18:033107(1–10).

Ravasz, E. & Barabasi, A.-L. (2003). “Hierarchical organization in complex networks”. Physical Review E, 67:026112(1–7).

Reichardt, J. & Bornholdt, S. (2004). “Detecting fuzzy community structure in complex networks with a potts model”. Physical Review Letters, 93:218701(1–4).

Schaeffer, S. E. (2007). “Graph clustering”. Computer Science Review, 1:27–34.

von der Malsburg, C. (1981). The correlation theory of brain function. Technical report, Internal report 81-2: Max-Planck Institute for Biophysical Chemistry, Göttingen, Germany.

Wang, D. L. (2005). “The time dimension for scene analysis”. IEEE Transactions on Neural Networks, 16(6):1401–1426.

Zachary, W. W. (1977). “An information flow model for conflict and fission in small groups”. Journal of Anthropological Research, 33:452–473.