Classificação de Relações Sociais para Melhorar a Detecção de Comunidades

• Jeancarlo C. Leão UFMG
• Michele A. Brandão UFMG
• Pedro O. S. Vaz de Melo UFMG
• Alberto H. F. Laender UFMG

DOI: https://doi.org/10.5753/brasnam.2017.3254

Resumo

Relacionamentos sociais podem ser separados em diferentes classes pela regularidade com que ocorrem e pela similaridade entre eles. Neste contexto, propomos um processo para tratamento de dados de redes sociais que explora as características temporais para melhorar a detecção de comunidades por algoritmos existentes. Por meio de um processo de remoção de interações aleatórias, observamos que as redes sociais convergem para uma topologia com interações mais puramente sociais e comunidades com maior modularidade.

Referências

Abrahao, B., Soundarajan, S., Hopcroft, J., and Kleinberg, R. (2012). On the separability of structural classes of communities. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD12, pages 624–632, New York, NY, USA. ACM.

Alves, B. L., Benevenuto, F., and Laender, A. H. (2013). The role of research leaders on the evolution of scientific communities. In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13 Companion, pages 649–656, New York, NY, USA. ACM.

Baeza-Yates, R., Ribeiro-Neto, B., et al. (1999). Modern information retrieval, volume 463.

Barabâsi, A.-L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., and Vicsek, T. (2002). Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 311(3):590–614.

Barber, M. J. and Clark, J. W. (2009). Detecting network communities by propagating labels under constraints. Phys. Rev. E, 80:026129.

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.

Brandão, M. A. and Moro, M. M. (2017a). Social professional networks: A survey and taxonomy. Computer Communications, 100:20 – 31.

Brandão, M. A. and Moro, M. M. (2017b). The strength of co-authorship ties through different topological properties. Journal of the Brazilian Computer Society, 23(1):5.

Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. (2008). On modularity clustering. IEEE Trans. on Knowl. and Data Eng., 20(2):172–188.

Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Phys. Rev. E, 70:066111.

Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3–5):75–174.

Holme, P. and Saramäki, J. (2012). Temporal networks. Physics reports, 519(3):97–125.

Lambiotte, R., Delvenne, J.-C., and Barahona, M. (2008). Laplacian dynamics and multiscale modular structure in networks. arXiv preprint arXiv:0812.1770.

Liu, X. and Murata, T. (2010). Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications, 389(7):1493–1500.

Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577–8582.

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

Newman, M. E. J. and Girvan, M. (2004). Finding and evaluating community structure in networks. Phys. Rev. E, 69(2):26113.

Orke, R. G., Maillard, P., Schumm, A., Staudt, C., Wagner, D., Görke, R., Maillard, P., Schumm, A., Staudt, C., and Wagner, D. (2013). Dynamic graph clustering combining modularity and smoothness. Journal of Experimental Algorithmics (JEA), 18(1):1–5.

Palla, G., Derenyi, I., Farkas, I., and Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814–818.

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D., and Fisica, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 101(9):2658–2663.

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):1–12.

Sah, P., Singh, L. O., Clauset, A., and Bansal, S. (2014). Exploring community structure in biological networks with random graphs. BMC Bioinformatics, 15(1):220.

Schuetz, P. and Caflisch, A. (2008). Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Physical Review E, 77(4):046112.

Šubelj, L. and Bajec, M. (2011). Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction. Physical Review E, 83(3):036103.

Vaz de Melo, P. O. S., Viana, A. C., Fiore, M., Jaffrès-Runser, K., Mouël, F. L., Loureiro, A. A. F., Addepalli, L., and Guangshuo, C. (2015). RECAST: Telling Apart Social and Random Relationships in Dynamic Networks. Performance Evaluation, 87:19–36. ”Special Issue: Recent Advances in Modeling and Performance Evaluation in Wireless and Mobile Systems ”.

Wang, L. and Hopcroft, J. (2010). Community structure in large complex networks. In International Conference on Theory and Applications of Models of Computation, pages 455–466. Springer.

Wang, M., Wang, C., Yu, J. X., and Zhang, J. (2015). Community detection in social networks: an in-depth benchmarking study with a procedure-oriented framework. Proceedings of the VLDB Endowment, 8(10):998–1009.

Xie, J., Kelley, S., and Szymanski, B. K. (2013). Overlapping Community Detection in Networks : The State-of-the-Art and Comparative Study. ACM Computing Surveys (csur), 45(4):43.

Yang, Z., Algesheimer, R., and Tessone, C. J. (2016). A Comparative Analysis of Community Detection Algorithms on Artificial Networks. Nature Publishing Group, (August):1–16.