Estudo do impacto da seleção de sementes baseada em centralidade e em informações de comunidades sobrepostas

  • Gilma A. S. Campos IF Sudeste MG / UFSJ
  • José M. Ribeiro UFSJ
  • Vinícius F. Vieira UFSJ
  • Carolina R. Xavier UFSJ

Resumo


O problema de maximizar a influência, proposto para redes sociais, envolve identificar um conjunto de nós influentes que iniciem o processo de difusão de maneira a maximizar a propagação da influência. Este estudo tem como objetivo comparar a extensão da difusão em dois contextos diferentes. O primeiro contexto envolve a seleção de indivíduos com base em medidas de centralidade, enquanto o segundo contexto envolve a seleção de indivíduos usando três critérios relacionados a comunidades sobrepostas. Uma comparação abrangente foi realizada utilizando o Modelo de Cascata Independente como modelo de difusão. Os resultados revelaram que, em certos cenários, a utilização de comunidades sobrepostas resultou em melhorias no alcance da difusão.

Referências

Aghaee, Z., Ghasemi, M. M., Beni, H. A., Bouyer, A., and Fatemi, A. (2021). A survey on meta-heuristic algorithms for the influence maximization problem in the social networks. Computing, 103(11):2437–2477.

Bakshy, E., Rosenn, I., Marlow, C., and Adamic, L. (2012). The role of social networks in information diffusion. In Proceedings of the 21st international conference on World Wide Web, pages 519–528. ACM.

Chen, W., Wang, Y., and Yang, S. (2009). Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199–208.

Coscia, M., Rossetti, G., Giannotti, F., and Pedreschi, D. (2012). Demon: a local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 615–623.

Domingos, P. and Richardson, M. (2001). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 57–66.

Easley, D., Kleinberg, J., et al. (2010). Networks, crowds, and markets, volume 8. Cambridge university press Cambridge.

Goyal, A., Lu, W., and Lakshmanan, L. V. (2011). Celf++ optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web, pages 47–48.

Granovetter, M. (1978). Threshold models of collective behavior. American journal of sociology, 83(6):1420–1443.

Gregory, S. (2010). Finding overlapping communities in networks by label propagation. New journal of Physics, 12(10):103018.

Gulati, R. (1998). Alliances and networks. Strategic management journal, 19(4):293.

Kempe, D., Kleinberg, J., and Tardos, É. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146.

Lancichinetti, A., Fortunato, S., and Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New journal of physics, 11(3):033015.

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N. (2007). Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420–429.

Palla, G., Derényi, I., Farkas, I., and Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. nature, 435(7043):814.

Rossetti, G., Milli, L., and Cazabet, R. (2019). Cdlib: a python library to extract, compare and evaluate communities from complex networks. Applied Network Science, 4(1):52.

Rossetti, G., Milli, L., Rinzivillo, S., Sı̂rbu, A., Pedreschi, D., and Giannotti, F. (2018). Ndlib: a python library to model and analyze diffusion processes over complex networks. International Journal of Data Science and Analytics, 5(1):61–79.

Salavati, C., Abdollahpouri, A., and Manbari, Z. (2018). Bridgerank: A novel fast centrality measure based on local structure of the network. Physica A: Statistical Mechanics and its Applications, 496:635–653.

Shakarian, P., Bhatnagar, A., Aleali, A., Shaabani, E., and Guo, R. (2015). Diffusion in Social Networks.

Sumith, N., Annappa, B., and Bhattacharya, S. (2018). Influence maximization in large social networks: Heuristics, models and parameters. Future Generation Computer Systems, 89:777–790.

Vieira, V. d. F., Xavier, C. R., and Evsukoff, A. G. (2019). Comparing the community structure identified by overlapping methods. In International Conference on Complex Networks and Their Applications, pages 262–273. Springer.

Xie, J., Szymanski, B. K., and Liu, X. (2011). Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In 2011 ieee 11th international conference on data mining workshops, pages 344–349. IEEE.

Yang, P.-L., Xu, G.-Q., Yu, Q., and Guo, J.-W. (2020). An adaptive heuristic clustering algorithm for influence maximization in complex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30(9):093106.

Zhou, X., Liu, Y., Wang, J., and Li, C. (2017). A density based link clustering algorithm for overlapping community detection in networks. Physica A: Statistical Mechanics and its Applications, 486:65–78.
Publicado
06/08/2023
CAMPOS, Gilma A. S.; RIBEIRO, José M.; VIEIRA, Vinícius F.; XAVIER, Carolina R.. Estudo do impacto da seleção de sementes baseada em centralidade e em informações de comunidades sobrepostas. In: BRAZILIAN WORKSHOP ON SOCIAL NETWORK ANALYSIS AND MINING (BRASNAM), 12. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 163-174. ISSN 2595-6094. DOI: https://doi.org/10.5753/brasnam.2023.230705.