Graph Evolution Rules Meet Communities: Assessing Global and Local Patterns in the Evolution of Dynamic Networks

Abstract

The study of dynamic networks in computer science has become crucial, given their ever-evolving nature within digital ecosystems. These networks serve as fundamental models for various networked systems, usually characterized by modular structures. Understanding these structures, also known as communities, and the mechanisms driving their evolution is vital, as changes in one module can impact the entire network. Traditional static network analysis falls short of capturing the full complexity of dynamic networks, prompting a shift toward understanding the underlying mechanisms driving their evolution. Graph Evolution Rules (GERs) have emerged as a promising approach, explaining how subgraphs transform into new configurations. In this paper, we comprehensively explore GERs in dynamic networks from diverse systems with a focus on the rules characterizing the formation and evolution of their modular structures, using EvoMine for GER extraction and the Leiden algorithm for community detection. We characterize network and module evolution through GER profiles, enabling cross-system comparisons. By combining GERs and network communities, we decompose network evolution into regions to uncover insights into global and mesoscopic network evolution patterns. From a mesoscopic standpoint, the evolution patterns characterizing communities emphasize a non-homogeneous nature, with each community, or groups of them, displaying specific evolution patterns, while other networks’ communities follow more uniform evolution patterns. Additionally, closely interconnected sets of communities tend to evolve similarly. Our findings offer valuable insights into the intricate mechanisms governing the growth and development of dynamic networks and their communities, shedding light on the interplay between modular structures and evolving network dynamics.

Keywords

• graph evolution mining
• subgraph mining
• social networks
• evolution profile
• graph evolution rule (ger)
• financial networks