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 chara...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.展开更多
The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few inde...The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.展开更多
基金supported by the Italian Ministry of University and Research(MUR)and the European Union–NextGenerationEU in the framework of the PRIN 2022 project“AWESOME:Analysis framework for WEb3 SOcial MEdia”–CUP:I53D23003680006.
文摘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.
基金This work was supported by the National Key Research and Development Program of China(No.2019YFB2102600)the National Natural Science Foundation of China(Nos.62122042 and 61971269)the Blockchain Core Technology Strategic Research Program of Ministry of Education of China(No.2020KJ010301)fund。
文摘The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.
