Detecção de Comunidades em Redes Sociais: Relacionando o Método Louvain a Medidas de Centralidade
Resumo
Neste projeto de iniciação científica, o foco está em algoritmos para o problema de detecção de comunidades em redes sociais, em especial, no método Louvain. O objetivo é relacionar o método aos conceitos de medidas de centralidade em redes complexas, propondo a utilização das mesmas para modificar o critério guloso do método e verificando se esta mudança aumenta a qualidade das comunidades encontradas. Mostramos que a construção de comunidades a partir dos vértices menos centrais melhorou a qualidade das comunidades obtidas pelo método em redes grandes e esparsas, porém, não trouxe ganhos significativos em redes pequenas e densas.
Referências
Bedi, P. and Sharma, C. (2016). Community detection in social networks. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 6(3):115–135.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.
Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. (2007). On finding graph clusterings with maximum modularity. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 121–132. Springer.
Clauset, A., Newman, M. E., and Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6):066111.
Dehmer, M. and Emmert-Streib, F. (2009). Analysis of complex networks: from biology to linguistics. John Wiley & Sons.
Gehrke, J., Ginsparg, P., and Kleinberg, J. (2003). Overview of the 2003 kdd cup. ACM SIGKDD Explorations Newsletter, 5(2):149–151.
Girvan, M. and Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821–7826.
Hofstad, R. V. D. (2016). Random graphs and complex networks, volume 1. Cambridge University Press.
Knuth, D. E. (1993). The Stanford GraphBase: a platform for combinatorial computing, volume 37. Addison-Wesley Reading.
Leskovec, J. and Mcauley, J. J. (2012). Learning to discover social circles in ego networks. In Advances in neural information processing systems, pages 539–547.
Motta, R., de Alneu Andrade Lopes, and de Oliveira, M. C. F. (2009). Centrality measures from complex networks in active learning. In International Conference on Discovery Science, pages 184–196. Springer.
Odent, J. and Saint-Guillain, M. (2012). Automatic detection of community structure in networks. Technical report, Université catholique de Louvain.
Özturk, K. (2014). Community detection in social networks. PhD thesis, Middle East Technical University.
Perra, N. and Fortunato, S. (2008). Spectral centrality measures in complex networks. Physical Review E, 78(3):036107.
Scholz, M. (2009). Node degree distribution. Disponível em: [link]. Acessado em: 01/2017.
Scott, J. and Carrington, P. J. (2011). The SAGE handbook of social network analysis. SAGE publications.
Shen, H.-W. (2013). Community structure of complex networks. Springer Science & Business Media.
Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452–473.
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008.
Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. (2007). On finding graph clusterings with maximum modularity. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 121–132. Springer.
Clauset, A., Newman, M. E., and Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6):066111.
Dehmer, M. and Emmert-Streib, F. (2009). Analysis of complex networks: from biology to linguistics. John Wiley & Sons.
Gehrke, J., Ginsparg, P., and Kleinberg, J. (2003). Overview of the 2003 kdd cup. ACM SIGKDD Explorations Newsletter, 5(2):149–151.
Girvan, M. and Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821–7826.
Hofstad, R. V. D. (2016). Random graphs and complex networks, volume 1. Cambridge University Press.
Knuth, D. E. (1993). The Stanford GraphBase: a platform for combinatorial computing, volume 37. Addison-Wesley Reading.
Leskovec, J. and Mcauley, J. J. (2012). Learning to discover social circles in ego networks. In Advances in neural information processing systems, pages 539–547.
Motta, R., de Alneu Andrade Lopes, and de Oliveira, M. C. F. (2009). Centrality measures from complex networks in active learning. In International Conference on Discovery Science, pages 184–196. Springer.
Odent, J. and Saint-Guillain, M. (2012). Automatic detection of community structure in networks. Technical report, Université catholique de Louvain.
Özturk, K. (2014). Community detection in social networks. PhD thesis, Middle East Technical University.
Perra, N. and Fortunato, S. (2008). Spectral centrality measures in complex networks. Physical Review E, 78(3):036107.
Scholz, M. (2009). Node degree distribution. Disponível em: [link]. Acessado em: 01/2017.
Scott, J. and Carrington, P. J. (2011). The SAGE handbook of social network analysis. SAGE publications.
Shen, H.-W. (2013). Community structure of complex networks. Springer Science & Business Media.
Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 33(4):452–473.
Publicado
02/07/2017
Como Citar
AIRES, Victoria P. S.; NAKAMURA, Fabiola G..
Detecção de Comunidades em Redes Sociais: Relacionando o Método Louvain a Medidas de Centralidade. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 36. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 2442-2451.
