Clustering consensual para a detecção eficiente de comunidades em redes pela modularidade ajustada
Resumo
A maximização da modularidade é a abordagem mais utilizada para detectar comunidades em redes. Contudo, ela pode falhar em encontrar comunidades pequenas, devido a um problema de escala. Para superar esse problema, uma versão ajustada da modularidade foi proposta na literatura. Apesar de seu potencial, não foram encontrados estudos que utilizassem essa medida para encontrar agrupamentos de maneira automática. Neste artigo, é proposto um método para determinar automaticamente comunidades por meio da modularidade ajustada, usando o conceito de clustering consensual. Experimentos com diversos grafos atestaram um melhor desempenho da estratégia proposta sobre diversos algoritmos de agrupamento em grafos da literatura.Referências
Aloise, D., Caporossi, G., Hansen, P., Peron, S.and Liberti, L., and Ruiz, M. (2012). Modularity maximization in networks by variable neighborhood search. Proceeding of 10h DIMACS Implementation Challenge.
Arenas, A., Fernández, A., and Gómez, S. (2008). Analysis of the structure of complex networks at different resolution levels. New J. Phys., 10(0530039).
Blondel, V. D., loup Guillaume, J., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics, (10).
Blum, C., Puchinger, J., Raidl, G. R., and Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11:4135–4151.
Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikolosk, Z., and Wagner, IEEE Transactions on Knowledge and Data D. (2008). On modularity clustering. Engineering, 20:172–188.
Danon, L., Díaz-Guilera, A., Duch, J., and Arenas, A. (2005). Comparing community structure identication. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008–[11 pages].
Dhillon, I., Guan, Y., and Kulis, B. (2005). A fast kernel-based multilevel algorithm for graph clustering. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 629–634.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36.
Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99:7821–7826.
Lancichinetti, A. and Fortunato, S. (2009). Community detection algorithms: A comparative analysis. Phys. Rev. E, 80:056117.
Lancichinetti, A. and Fortunato, S. (2012). Consensus clustering in complex networks.Scientic Reports, 2.
Lancichinetti, A., Fortunato, S., and F, R. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78:046110–[5 pages].
Nascimento, M. (2013). Community detection in networks via a spectral heuristic based on the clustering coefcient. Submetido ao Discrete and Applied Mathematics.
Newman, M. (2012). Communities, modules and large-scale structure in networks. Nature Physics, 8:25–31.
Newman, M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical Review, 74:036–104.
Newman, M. E. J. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review, E 69(026113).
Noack, A. and Rotta, R. (2009). Multi-level algorithms for modularity clustering. SEA’09 Proceedings of the 8th International Symposium on Experimental Algorithms, 1.
Raghavan, U. N., Albert, R., and Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3 Pt 2):036106.
Reichardt, J. and Bornholdt, S. (2004). Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett., 93(21):218701.
Reichardt, J. and Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74:016110.
Rosvall, M. and Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4):1118–1123.
Schaeffer, S. E. (2007). Graph clustering. Computer Science Review, 1:27–64.
Topchy, A., Jain, A., and Punch, W. (2005). Clustering ensembles: models of consensus and weak partitions. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(12):1866–1881.
Traud, A. L., Kelsic, E. D., Mucha, P. J., and Porter, M. A. (2008). Community structure in online collegiate social networks. arXiv:0809.0960.
Arenas, A., Fernández, A., and Gómez, S. (2008). Analysis of the structure of complex networks at different resolution levels. New J. Phys., 10(0530039).
Blondel, V. D., loup Guillaume, J., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics, (10).
Blum, C., Puchinger, J., Raidl, G. R., and Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11:4135–4151.
Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikolosk, Z., and Wagner, IEEE Transactions on Knowledge and Data D. (2008). On modularity clustering. Engineering, 20:172–188.
Danon, L., Díaz-Guilera, A., Duch, J., and Arenas, A. (2005). Comparing community structure identication. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008–[11 pages].
Dhillon, I., Guan, Y., and Kulis, B. (2005). A fast kernel-based multilevel algorithm for graph clustering. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 629–634.
Feo, T. A. and Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36.
Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99:7821–7826.
Lancichinetti, A. and Fortunato, S. (2009). Community detection algorithms: A comparative analysis. Phys. Rev. E, 80:056117.
Lancichinetti, A. and Fortunato, S. (2012). Consensus clustering in complex networks.Scientic Reports, 2.
Lancichinetti, A., Fortunato, S., and F, R. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78:046110–[5 pages].
Nascimento, M. (2013). Community detection in networks via a spectral heuristic based on the clustering coefcient. Submetido ao Discrete and Applied Mathematics.
Newman, M. (2012). Communities, modules and large-scale structure in networks. Nature Physics, 8:25–31.
Newman, M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical Review, 74:036–104.
Newman, M. E. J. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review, E 69(026113).
Noack, A. and Rotta, R. (2009). Multi-level algorithms for modularity clustering. SEA’09 Proceedings of the 8th International Symposium on Experimental Algorithms, 1.
Raghavan, U. N., Albert, R., and Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3 Pt 2):036106.
Reichardt, J. and Bornholdt, S. (2004). Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett., 93(21):218701.
Reichardt, J. and Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74:016110.
Rosvall, M. and Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4):1118–1123.
Schaeffer, S. E. (2007). Graph clustering. Computer Science Review, 1:27–64.
Topchy, A., Jain, A., and Punch, W. (2005). Clustering ensembles: models of consensus and weak partitions. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(12):1866–1881.
Traud, A. L., Kelsic, E. D., Mucha, P. J., and Porter, M. A. (2008). Community structure in online collegiate social networks. arXiv:0809.0960.
Publicado
23/07/2013
Como Citar
SANTOS, Camila Pereira dos; NASCIMENTO, Mariá Cristina Vasconcelos.
Clustering consensual para a detecção eficiente de comunidades em redes pela modularidade ajustada. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 32. , 2013, Maceió.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 132-141.
