Modeling and Analyzing Collective Behavior Captured by Many-to-Many Networks

  • Carlos Henrique G. Ferreira UFMG
  • Marco Mellia Politecnico di Torino
  • Jussara M. Almeida UFMG


Several significant studies in the existing literature have relied on network models to gain insights into various collective behavior phenomena. Nevertheless, a facet that has been critically overlooked is the presence of numerous irrelevant edges that may obscure a more meaningful underlying topology, representing the targeted phenomenon. In fact, the literature provides ample evidence that overlooking these noisy edges may result in inaccurate and misleading interpretations. Nonetheless, employing these solutions presents various challenges, prominently the absence of foundational formalization regarding the appropriate application and expected outcomes. In this context, our focus centers on extracting salient edges, exploring backbone extraction methods, for the purpose of modeling and analyzing collective behavior. To address the gaps in the current literature regarding the use of such methods for modeling collective behavior, we undertake a comprehensive series of eff orts. These include formalizing, analyzing, discussing, applying, and validating existing methods, many of which are drawn from parallel fields of study to computer science, and finally introducing novel methods to advance the state-of-the-art. We also demonstrate the effectiveness of these methods as fundamental tools for uncovering relevant patterns, applying them across diverse phenomena each with distinct requirements. Our contributions are multifaceted, including innovative methods, case studies yielding specific insights, and a comprehensive methodology for the selection, application, and validation of these methods. Moreover, our outcomes wielded a substantial impact on both the scientific community and society. They not only unveiled numerous opportunities for fellow researchers but also catalyzed the initiation of new and impactful research.

Palavras-chave: Network science, collective behaviour, network backbone extraction


M Araujo, C. Ferreira, J. Reis, A. Silva, and J. Almeida. 2023. Identificação e Caracterização de Campanhas de Propagandas Eleitorais Antecipadas Brasileiras no Twitter. In Brazilian Workshop on Social Network Analysis and Mining.

M. F. C. Barros, C. H. G Ferreira, L. A .P. Junior, M. Mellia, J.M. Almeida, and B.P. Santos. 2022. Understanding mobility in networks: A node embedding approach. ACM SIGMETRICS Performance Evaluation Review (2022).

A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences (2018).

Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008 (2008).

M. A. Brandão, P. O. S. Vaz de Melo, and M. M. Moro. 2017. Tie Strength Dynamics over Temporal Co-authorship Social Networks. In International Conference on Web Intelligence.

Michele Coscia and Frank MH Neffke. 2017. Network backboning with noisy data. In International Conference on Data Engineering.

Jose da Rosa Jr, Renan Linhares, Carlos Henrique Gomes Ferreira, Gabriel P Nobre, Fabricio Murai, and Jussara M Almeida. 2022. Uncovering Discussion Groups on Claims of Election Fraud from Twitter. In Social Informatics: 13th International Conference, SocInfo.

Liang Dai, Ben Derudder, and Xingjian Liu. 2018. Transport network backbone extraction: A comparison of techniques. Journal of Transport Geography 69 (2018), 271–281.

P.O.S.V. De Melo, A. C. Viana, M. Fiore, K. Jaffrès-R., F. Le Mouël, A. A. F. Loureiro, L. Addepalli, and C. Guangshuo. 2015. Recast: Telling apart social and random relationships in dynamic networks. Performance Evaluation 87 (2015).

N. Dianati. 2016. Unwinding the hairball graph: Pruning algorithms for weighted complex networks. Physical Review E (2016).

M. F. Feitosa, G. D. Gonçalves, C. H. G. Ferreira, and J. M. Almeida. 2022. Sentiment Analysis on Twitter Repercussion of Police Operations. In Simpósio Brasileiro de Sistemas Multimídia e Web.

Carlos Henrique Gomes Ferreira. 2022. Modeling and analyzing collective behavior captured by many-to-many networks. PhD thesis. Universidade Federal de Minas Gerais. Available at

C. H. G. Ferreira, B de Souza M., and J. M. Almeira. 2018. Analyzing Dynamic Ideological Communities in Congressional Voting Networks. In International Conference on Social Informatics.

C. H. G. Ferreira, F. Murai, A. P. C. da Silva, J. M. de Almeida, M. Trevisan, L. Vassio, I. Drago, and M. Mellia. 2020. Unveiling CommunityDynamics on Instagram Political Network. In ACM Conference on Web Science.

C. H. G. Ferreira, F. Murai, A. P.C. Silva, M. Trevisan, L. Vassio, I. Drago, M. Mellia, and J. M Almeida. 2022. On network backbone extraction for modeling online collective behavior. Plos one 17, 9 (2022), e0274218.

C. H. G. Ferreira, F. Murai, Ana P. C. Silva, J. M. Almeida, M. Trevisan, Luca V., M. Mellia, and I. Drago. 2021. On the dynamics of political discussions on Instagram: A network perspective. Online Social Networks and Media 25 (2021), 100155.

C. H. G. Ferreira, F. Murai, B Souza M., and J. M. de Almeida. 2019. Modeling Dynamic Ideological Behavior in Political Networks. The Journal of Web Science 7 (2019).

D. Grady, C. Thiemann, and D. Brockmann. 2012. Robust classification of salient links in complex networks. Nature communications (2012).

A. Grover and J. Leskovec. 2016. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining.

R. Guidotti, G. Rossetti, L. Pappalardo, F. Giannotti, and D. Pedreschi. 2019. Personalized Market Basket Prediction with Temporal Annotated Recurring Sequences. IEEE Transactions on Knowledge and Data Engineering 11 (2019).

Roger N. Kamoi, L. A. Pereira Jr, F. A. Verri, C. A. Marcondes, C. H. G. Ferreira, R. I. Meneguette, and A. M. Da Cunha. 2021. Platoon grouping network offloading mechanism for vanets. IEEE Access (2021).

R. S. Linhares, Jose da Rosa Jr, C. H. G. Ferreira, G. P. Nobre, F. Murai, and J. M. Almeida. 2022. Uncovering Coordinated Communities on Twitter During the 2020 US Election. In International Conference on Advances in Social Networks Analysis and Mining.

L. Malagoli, J. Stancioli, Carlos HG Ferreira, M. Vasconcelos, A. P. C. da Silva, and J. Almeida. 2021. Caracterizaçao do debate no twitter sobre a vacinaçao contra a covid-19 no brasil. In Brazilian Workshop on Social Network Analysis and Mining.

L. G. Malagoli, J. Stancioli, C. H. G. Ferreira, M. Vasconcelos, A. P. C. da Silva, and J. M. Almeida. 2021. A look into covid-19 vaccination debate on twitter. In ACM Web Science Conference 2021.

R. Marcaccioli and G. Liivan. 2019. A Pólya urn approach to information filtering in complex networks. Nature communications (2019).

S. Martin-Gutierrez, Juan C Losada, and R. M Benito. [n. d.]. Impact of individual actions on the collective response of social systems. Scientific reports ([n. d.]).

B. Matos, C. H. G. Ferreira, and J. M. Almeida. 2018. Analisando a governabilidade presidencial a partir de padrões de homofilia na Câmara dos Deputados: Estudos de Casos no Brasil e nos EUA. In VII Brazilian Workshop on Social Network Analysis and Mining.

Z. P. Neal, R. Domagalski, and B. Sagan. 2021. Comparing alternatives to the fixed degree sequence model for extracting the backbone of bipartite projections. Scientific reports (2021).

M.E.J. Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Physical review E (2006).

MEJ Newman. 2018. Network structure from rich but noisy data. Nature Physics 14 (2018), 542–546.

Mark EJ Newman. 2003. The structure and function of complex networks. SIAM review 45, 2 (2003), 167–256.

G. P. Nobre, J. M. Almeida, and C.H.G. Ferreira. 2019. Caracterização de bots no Twitter durante as Eleições Presidenciais no Brasil em 2018. In Brazilian Workshop on Social Network Analysis and Mining.

G. P. Nobre, C. H. G. Ferreira, and J. M. Almeida. 2020. Beyond Groups: Uncovering Dynamic Communities on the WhatsApp Network of Information Dissemination. In International Conference on Social Informatics.

G. P. Nobre, C. H. G. Ferreira, and J. M. Almeida. 2022. A hierarchical network-oriented analysis of user participation in misinformation spread on WhatsApp. Information Processing & Management (2022).

F. Radicchi, J. J Ramasco, and S. Fortunato. 2011. Information filtering in complex weighted networks. Physical Review E (2011).

G. Rossetti and R. Cazabet. 2018. Community discovery in dynamic networks: A survey. Comput. Surveys 51 (2018), 35.

M. Serrano, Marián Boguná, and A. Vespignani. 2009. Extracting the multiscale backbone of complex weighted networks. Proceedings of the National Academy of Sciences (2009).

T. H. Silva, P. O. S. V. de Melo, J. M. Almeida, J. Salles, and A. F. Loureiro. 2014. Revealing the City That We Cannot See. ACM Transactions on Internet Technology (2014).

Z. Yao, Y. Sun,W. Ding, N. Rao, and H. Xiong. 2018. DynamicWord Embeddings for Evolving Semantic Discovery. In International Conference on Web Search and Data Mining.
FERREIRA, Carlos Henrique G.; MELLIA, Marco; ALMEIDA, Jussara M.. Modeling and Analyzing Collective Behavior Captured by Many-to-Many Networks. In: CONCURSO DE TESES E DISSERTAÇÕES - SIMPÓSIO BRASILEIRO DE SISTEMAS MULTIMÍDIA E WEB (WEBMEDIA), 29. , 2023, Ribeirão Preto/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 31-34. ISSN 2596-1683. DOI: