Home Big Data Mining and Analytics Article
PDF (3.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

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

IT University Copenahgen, Copenahgen 2300, Denmark
Department Computer Science, University of Milan, Milan 20133, Italy
Show Author Information

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 miningsubgraph miningsocial networksevolution profileGraph Evolution Rule (GER)financial networks

References

[1]

J. M. Kumpula, J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski, Model of community emergence in weighted social networks, Comput. Phys. Commun., vol. 180, no. 4, pp. 517–522, 2009.

Crossref Google Scholar
[2]

G. Bianconi, R. K. Darst, J. Iacovacci, and S. Fortunato, Triadic closure as a basic generating mechanism of communities in complex networks, Phys. Rev. E, vol. 90, no. 4, p. 042806, 2014.

Crossref Google Scholar
[3]

F. Papadopoulos, M. Kitsak, M. Á. Serrano, M. Boguñá, and D. Krioukov, Popularity versus similarity in growing networks, Nature, vol. 489, no. 7417, pp. 537–540, 2012.

Crossref Google Scholar
[4]
M. Kim and J. Leskovec, Modeling social networks with node attributes using the multiplicative attribute graph model, in Proc. 27th Conf. Uncertain. Artif. Intell. UAI 2011, Barcelona, Spain, 2011, pp. 400–409.
[5]
C. T. Ba, M. Dileo, A. Galdeman, M. Zignani, and S. Gaito, Analyzing user migration in blockchain online social networks through network structure and discussion topics of communities on multilayer networks, Distrib. Ledger Technol., doi:10.1145/3640020.
Crossref
[6]
A. Galdeman, M. Zignani, and S. Gaito, User migration across Web3 online social networks: Behaviors and influence of hubs, in Proc. ICC 2023 - IEEE Int. Conf. Communications, Rome, Italy, 2023, pp. 5595–5601.
Crossref
[7]
A. Galdeman, M. Zignani, and S. Gaito, Disentangling the growth of blockchain-based networks by graph evolution rule mining, in Proc. IEEE 9th Int. Conf. Data Science and Advanced Analytics, Shenzhen, China, doi: 10.1109/DSAA54385.2022.10032398.
Crossref
[8]

M. Coscia and M. Szell, Multilayer graph association rules for link prediction, Proc. Int. AAAI Conf. Web Soc. Medium., vol. 15, pp. 129–139, 2021.

Crossref Google Scholar
[9]
T. A. B. Snijders, Models for longitudinal network data, in Models and Methods in Social Network Analysis. Cambridge, UK: Cambridge University Press, 2005. pp. 215–247.
Crossref
[10]
X. Zhao, A. Sala, C. Wilson, X. Wang, S. Gaito, H. Zheng, and B. Y. Zhao, Multi-scale dynamics in a massive online social network, in Proc. 2012 Internet Measurement Conference, Boston, MA, USA, 2012, pp. 171–184.
Crossref
[11]

G. Palla, A.-L. Barabási, and T. Vicsek, Quantifying social group evolution, Nature, vol. 446, no. 7136, pp. 664–667, 2007.

Crossref Google Scholar
[12]
M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis, Mining graph evolution rules, in Proc. ECML PKDD 2009, Bled, Slovenia, doi: 10.1007/978-3-642-04180-8_25.
Crossref
[13]

W.-T. Wang, Y.-L. He, J. Z. Huang, and L.-H. Ma, A new approach to solve opinion dynamics on complex networks, Expert Syst. Appl., vol. 145, p. 113132, 2020.

Crossref Google Scholar
[14]

D. Bright, J. Lerner, G. R. Putra Sadewo, and C. Whelan, Offence versatility among co-offenders: A dynamic network analysis, Soc. Netw., vol. 78, pp. 1–11, 2024.

Crossref Google Scholar
[15]

W. Fan, R. Jin, P. Lu, C. Tian, and R. Xu, Towards event prediction in temporal graphs, Proc. VLDB Endow., vol. 15, no. 9, pp. 1861–1874, 2022.

Crossref Google Scholar
[16]
C. W.-K. Leung, E.-P. Lim, D. Lo, and J. Weng, Mining interesting link formation rules in social networks, in Proc. 19th ACM Int. Conf. Information and knowledge management, Toronto, Canada, 2010, pp. 209–218.
Crossref
[17]
T. Ozaki and M. Etoh, Correlation and contrast link formation patterns in a time evolving graph, in Proc. IEEE 11th Int. Conf. Data Mining Workshops, Vancouver, Canada, 2011, pp. 1147–1154.
Crossref
[18]
B. Bringmann and S. Nijssen, What is frequent in a single graph? in Lecture Notes in Computer Science. Berlin, Germany: Springer, 2008. pp. 858–863.
Crossref
[19]
X. Yan and J. Han, gSpan: Graph-based substructure pattern mining, in Proc. IEEE Int. Conf. Data Mining, Maebashi City, Japan, 2002, pp. 721–724.
[20]
K. Vaculík, A versatile algorithm for predictive graph rule mining, in Proc. ITAT 2015 : Information Technologies - Applications and Theory, Slovensky Raj, Slovakia, 2015, pp. 51–58.
[21]
E. Scharwächter, E. Müller, J. Donges, M. Hassani, and T. Seidl, Detecting change processes in dynamic networks by frequent graph evolution rule mining, in Proc. IEEE 16th Int. Conf. Data Mining, Barcelona, Spain, 2016, pp. 1191–1196.
Crossref
[22]
P. Fournier-Viger, G. He, J. C.-W. Lin, and H. M. Gomes, Mining attribute evolution rules in dynamic attributed graphs, in Proc. 22nd Int. Conf. Big Data Analytics and Knowledge Discovery, Bratislave, Slovakia, 2020, pp. 167–182.
Crossref
[23]
K.-N. T. Nguyen, L. Cerf, M. Plantevit, and J.-F. Boulicaut, Discovering inter-dimensional rules in dynamic graphs, in Proc. the 1st Int. Conf. Dynamic Networks and Knowledge Discovery, Barcelona, Spain, 2010, pp. 1–12.
[24]
R. Kumar, J. Novak, and A. Tomkins, Structure and evolution of online social networks, in Proc. 12th ACM SIGKDD Int. Conf. Knowledge discovery and data mining, Philadelphia, PA, USA, 2006, pp. 611–617.
Crossref
[25]
D. Greene, D. Doyle, and P. Cunningham, Tracking the evolution of communities in dynamic social networks, in Proc. Int. Conf. Advances in Social Networks Analysis and Mining, Odense, Denmark, 2010, pp. 176–183.
Crossref
[26]

S. Asur, S. Parthasarathy, and D. Ucar, An event-based framework for characterizing the evolutionary behavior of interaction graphs, ACM Trans. Knowl. Discov. Data, vol. 3, no. 4, pp. 1–36, 2009.

Crossref Google Scholar
[27]

M. Takaffoli, F. Sangi, J. Fagnan, and O. R. Zäıane, Community evolution mining in dynamic social networks, Procedia Soc. Behav. Sci., vol. 22, pp. 49–58, 2011.

Crossref Google Scholar
[28]
M. Goldberg, M. Magdon-Ismail, S. Nambirajan, and J. Thompson, Tracking and predicting evolution of social communities, in Proc. IEEE Third Int. Conf. Privacy, Security, Risk and Trust and 2011 IEEE Third Int. Conf. Social Computing, Boston, MA, USA, 2011, pp. 780–783.
Crossref
[29]
S. R. Kairam, D. J. Wang, and J. Leskovec, The life and death of online groups: Predicting Group growth and longevity, in Proc. fifth ACM Int. Conf. Web Search and Data Mining, Seattle WA, USA, 2012, pp. 673–682.
Crossref
[30]
A. Patil, J. Liu, and J. Gao, Predicting group stability in online social networks, in Proc. 22nd Int. Conf. World Wide Web, Rio de Janeiro, Brazil, 2013, pp.1021–1030.
Crossref
[31]
P. Bródka, P. Kazienko, and B. Kołoszczyk, Predictinggroup evolution in the social network, in Proc. 4th International Conference Social Informatics, Lausanne, Switzerland, 2012, pp. 54–67.
Crossref
[32]
N. Dakiche, F. B.-S. Tayeb, K. Benatchba, Y. Slimani, A. Khelifati, and H. Chabane, EPredictor: An experimental platform for community evolution prediction tests, in Proc. 11th Int. Conf. Simulation and Modeling Methodologies, Technologies and Applications, Virtual Event, 2021, pp. 295–302.
Crossref
[33]

N. Ilhan and Ş. G. Öğüdücü, Feature identification for predicting community evolution in dynamic social networks, Eng. Appl. Artif. Intell., vol. 55, pp. 202–218, 2016.

Crossref Google Scholar
[34]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks, Science, vol. 298, no. 5594, pp. 824–827, 2002.

Crossref Google Scholar
[35]
X. Wang and M. Zhang, GLASS: GNN with labeling tricks for subgraph representation learning, in Proc. Int. Conf. Learning Representations, Virtual Event, https://openreview.net/forum?id=XLxhEjKNbXj, 2022.
[36]
X. Chen and Q. Qian, subGE: Enhancing the subgraph representation of molecular compounds structure-activity relationship discovery, Eng. Appl. Artif. Intell., vol. 119, p. 105727, 2023.
Crossref
[37]

E. Alsentzer, S. Finlayson, M. Li, and M. Zitnik, Subgraph neural networks, Advances in Neural Information Processing Systems, vol. 33, pp. 8017–8029, 2020.

Google Scholar
[38]
Y. Yu, Z. Lu, J. Liu, G. Zhao, and J.-R. Wen, RUM: Network representation learning using motifs, in Proc. IEEE 35th Int. Conf. Data Engineering, Macao, China, 2019, pp. 1382–1393.
Crossref
[39]
J. Xu, A. Yu, L. Cai, and D. Meng, MMNR: A network representation framework based on multi-view motif fusion, in Proc. IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom ), Xiamen, China, 2019, pp. 792–801.
Crossref
[40]
K. Tu, J. Li, D. F. Towsley, D. Braines, and L. D. Turner, Network classification in temporal networks using motifs, ArXiv preprint arXiv:1807.03733,2018.
[41]
K. Tu, J. Li, D. Towsley, D. Braines, and L. D. Turner, gl2vec: Learning feature representation using graphlets for directed networks, in Proc. 2019 IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, Vancouver, Canada, 2019, pp. 216–221.
Crossref
[42]

A. Longa, G. Cencetti, B. Lepri, and A. Passerini, An efficient procedure for mining egocentric temporal motifs, Data Min. Knowl. Discov., vol. 36, no. 1, pp. 355–378, 2022.

Crossref Google Scholar
[43]

C. E. S. Mattsson, T. Criscione, and W. O. Ruddick, Sarafu community inclusion currency 2020–2021, Sci. Data, vol. 9, no. 1, p. 426, 2022.

Crossref Google Scholar
[44]
C. T. Ba, M. Zignani, S. Gaito, and G. P. Rossi, The effect of cryptocurrency price on a blockchain-based social network, in Studies in Computational Intelligence. Cham, Switzerland: Springer International Publishing, 2020, pp. 581–592.
Crossref
[45]
M. Loporchio, D. Di Francesco Maesa, A. Bernasconi, and L. Ricci, Analysis and characterization of ERC-20 token network topologies, in Studies in Computational Intelligence. Cham, Switzerland: Springer Nature Switzerland, 2024. pp. 344–355
Crossref
[46]

D. Costa, L. La Cava, and A. Tagarelli, Unraveling the NFT economy: A comprehensive collection of non-fungible token transactions and metadata, Data Brief, vol. 51, p. 109749, 2023.

Crossref Google Scholar
[47]

L. Ussher, L. Ebert, G. M. Gómez, and W. O. Ruddick, Complementary currencies for humanitarian aid, J. Risk Financ. Manag., vol. 14, no. 11, p. 557, 2021.

Crossref Google Scholar
[48]

R. Mqamelo, Community currencies as crisis response: Results from a randomized control trial in Kenya, Front. Blockchain, vol. 4, p. 739751, 2022.

Crossref Google Scholar
[49]
C. T. Ba, A. Galdeman, M. Zignani, and S. Gaito, Temporal analysis of cooperative behaviour in a blockchain for humanitarian aid during the COVID-19 pandemic, in Proc. 2022 ACM Conf. Information Technology for Social Good, Limassol. Cyprus, 2022, pp. 292–299.
Crossref
[50]
M. Ley, The DBLP computer science bibliography: Evolution, research issues, perspectives, in Proc. 9th Int. Symp. On String Processing and Information Retrieval, http:doi/10.1007/3-540-45735:6_1, 2022.
[51]
J. Kunegis, KONECT–The Koblenz Network Collection, in Proc. Int. Conf. on World Wide Web Companion, doi: 10.1145/2487788.2488173.
Crossref
[52]
M. Yuuki, T. Ozaki, and O. Takenao, Mining interesting patterns and rules in a time-evolving graph, in Proc. MultiConf. of Engineers and Computer Scientists, Hong Kong, China, https://api.semanticscholar.org/CorpusID:11014989, 2011.
[53]
S. Nijssen and J. Kok, Frequent subgraph miners: Runtimes don’t say everything, in Proc. of the Workshop on Mining and Learning with Graphs, https://api.semanticscholar.org/CorpusID:63785708, 2006.
[54]

M. Chen, K. Kuzmin, and B. K. Szymanski, Community detection via maximization of modularity and its variants, IEEE Trans. Comput. Soc. Syst., vol. 1, no. 1, pp. 46–65, 2014.

Crossref Google Scholar
[55]

V. A. Traag, L. Waltman, and N. J. van Eck, From Louvain to Leiden: Guaranteeing well-connected communities, Sci. Rep., vol. 9, no. 1, p. 5233, 2019.

Crossref Google Scholar
[56]
M. Coscia and M. Szell, Multiplex graph association rules for link prediction, arXiv preprint arXiv:2008.08351, 2020.
Crossref
[57]
A. Galdeman, M. Zignani, and S. Gaito, Unfolding temporal networks through statistically significant graph evolution rules, in Proc. IEEE 10th Int. Conf. Data Science and Advanced Analytics, Thessaloniki, Greece, 2023, pp. 1–10.
Crossref
Big Data Mining and Analytics
Volume 8 Issue 1,
February 2025
Pages 78-102
DOI: 10.26599/BDMA.2024.9020050
Cite this article:
Galdeman A, Zignani M, Gaito S. Graph Evolution Rules Meet Communities: Assessing Global and Local Patterns in the Evolution of Dynamic Networks. Big Data Mining and Analytics, 2025, 8(1): 78-102. https://doi.org/10.26599/BDMA.2024.9020050
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return