Browse by volume Browse by section Browse by topic Browse by conference

Section: Network Science
Topic: Applied mathematics

Structify-Net: Random Graph generation with controlled size and customized structure

Cazabet, Remy1 ; Citraro, Salvatore2 ; Rossetti, Giulio2
1 Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, F-69622 Villeurbanne, France
2 Institute of Information Science and Technologies “A. Faedo” (ISTI), National Research Council (CNR), Italy

10.24072/pcjournal.335 - Peer Community Journal, Volume 3 (2023), article no. e103.

Get full text PDF Peer reviewed and recommended by PCI

Network structure is often considered one of the most important features of a network, and various models exist to generate graphs having one of the most studied types of structures, such as blocks/communities or spatial structures. In this article, we introduce a framework for the generation of random graphs with a controlled size —number of nodes, edges— and a customizable structure, beyond blocks and spatial ones, based on node-pair rank and a tunable probability function allowing to control the amount of randomness. We introduce a structure zoo —a collection of original network structures— and conduct experiments on the small-world properties of networks generated by those structures. Finally, we introduce an implementation as a Python library named Structify-net.

Published online:
DOI: 10.24072/pcjournal.335
Type: Software tool
Keywords: Network Generation, Random Graphs, Network Structure, Python Library
Cazabet, Remy 1; Citraro, Salvatore 2; Rossetti, Giulio 2

1 Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, F-69622 Villeurbanne, France
2 Institute of Information Science and Technologies “A. Faedo” (ISTI), National Research Council (CNR), Italy
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{10_24072_pcjournal_335,
     author = {Cazabet, Remy and Citraro, Salvatore and Rossetti, Giulio},
     title = {Structify-Net: {Random} {Graph} generation with controlled size and customized structure},
     journal = {Peer Community Journal},
     eid = {e103},
     publisher = {Peer Community In},
     volume = {3},
     year = {2023},
     doi = {10.24072/pcjournal.335},
     language = {en},
     url = {https://peercommunityjournal.org/articles/10.24072/pcjournal.335/}
}
TY  - JOUR
AU  - Cazabet, Remy
AU  - Citraro, Salvatore
AU  - Rossetti, Giulio
TI  - Structify-Net: Random Graph generation with controlled size and customized structure
JO  - Peer Community Journal
PY  - 2023
VL  - 3
PB  - Peer Community In
UR  - https://peercommunityjournal.org/articles/10.24072/pcjournal.335/
DO  - 10.24072/pcjournal.335
LA  - en
ID  - 10_24072_pcjournal_335
ER  - 
%0 Journal Article
%A Cazabet, Remy
%A Citraro, Salvatore
%A Rossetti, Giulio
%T Structify-Net: Random Graph generation with controlled size and customized structure
%J Peer Community Journal
%D 2023
%V 3
%I Peer Community In
%U https://peercommunityjournal.org/articles/10.24072/pcjournal.335/
%R 10.24072/pcjournal.335
%G en
%F 10_24072_pcjournal_335
Cazabet, Remy; Citraro, Salvatore; Rossetti, Giulio. Structify-Net: Random Graph generation with controlled size and customized structure. Peer Community Journal, Volume 3 (2023), article  no. e103. doi : 10.24072/pcjournal.335. https://peercommunityjournal.org/articles/10.24072/pcjournal.335/

PCI peer reviews and recommendation, and links to data, scripts, code and supplementary information: 10.24072/pci.networksci.100114

Conflict of interest of the recommender and peer reviewers:
The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article.

[1] Abbe, E. Community Detection and Stochastic Block Models: Recent Developments, The Journal of Machine Learning Research, Volume 18 (2017) no. 1, pp. 6446-6531 | DOI

[2] Aldecoa, R.; Orsini, C.; Krioukov, D. Hyperbolic Graph Generator, Computer Physics Communications, Volume 196 (2015), pp. 492-496 | DOI

[3] Alves, L. G.; Mangioni, G.; Cingolani, I.; Rodrigues, F. A.; Panzarasa, P.; Moreno, Y. The Nested Structural Organization of the Worldwide Trade Multi-Layer Network, Scientific reports, Volume 9 (2019) no. 1, pp. 1-14 | DOI

[4] Asikainen, A.; Iñiguez, G.; Ureña-Carrión, J.; Kaski, K.; Kivelä, M. Cumulative Effects of Triadic Closure and Homophily in Social Networks, Science Advances, Volume 6 (2020) no. 19, p. eaax7310 | DOI

[5] Barthélemy, M.; Barrat, A.; Pastor-Satorras, R.; Vespignani, A. Velocity and Hierarchical Spread of Epidemic Outbreaks in Scale-Free Networks, Physical review letters, Volume 92 (2004) no. 17, p. 178701 | DOI

[6] Cazabet, R. Structify-Net, 2023 (https://github.com/Yquetzal/structify_net/)

[7] Cazabet, R.; Borgnat, P.; Jensen, P. Enhancing Space-Aware Community Detection Using Degree Constrained Spatial Null Model, Complex Networks VIII: Proceedings of the 8th Conference on Complex Networks CompleNet 2017 8, Springer, 2017, pp. 47-55 | DOI

[8] Cazabet, R. Yquetzal/Structifynet: 0.9.5 (v0.9.5), 2023 | DOI

[9] Csardi, G.; Nepusz, T.; others The Igraph Software Package for Complex Network Research, InterJournal, complex systems, Volume 1695 (2006) no. 5, pp. 1-9 (https://igraph.org)

[10] Dall, J.; Christensen, M. Random Geometric Graphs, Physical review E, Volume 66 (2002) no. 1, p. 016121 | DOI

[11] Durak, N.; Kolda, T. G.; Pinar, A.; Seshadhri, C. A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, out, and Reciprocal, 2013 IEEE 2nd Network Science Workshop (NSW), IEEE, 2013, pp. 23-30 | DOI

[12] Fortunato, S.; Hric, D. Community Detection in Networks: A User Guide, Physics reports, Volume 659 (2016), pp. 1-44 | DOI

[13] Glasscock, D. What Is... a Graphon, Notices of the AMS, Volume 62 (2015) no. 1, pp. 46-48 | DOI

[14] Hagberg, A.; Swart, P.; S Chult, D. Exploring Network Structure, Dynamics, and Function Using NetworkX, Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008) (https://www.osti.gov/biblio/960616)

[15] Hoff, P. D.; Raftery, A. E.; Handcock, M. S. Latent Space Approaches to Social Network Analysis, Journal of the american Statistical association, Volume 97 (2002) no. 460, pp. 1090-1098 | DOI

[16] Hunter, D. R.; Handcock, M. S.; Butts, C. T.; Goodreau, S. M.; Morris, M. Ergm: A Package to Fit, Simulate and Diagnose Exponential-Family Models for Networks, Journal of statistical software, Volume 24 (2008) no. 3, p. nihpa54860 | DOI

[17] Kamiński, B.; Prałat, P.; Théberge, F. Artificial Benchmark for Community Detection (Abcd)—Fast Random Graph Model with Community Structure, Network Science, Volume 9 (2021) no. 2, pp. 153-178 | DOI

[18] Lancichinetti, A.; Fortunato, S.; Radicchi, F. Benchmark Graphs for Testing Community Detection Algorithms, Physical review E, Volume 78 (2008) no. 4, p. 046110 | DOI

[19] Latouche, P.; Birmelé, E.; Ambroise, C. Overlapping Stochastic Block Models, arXiv preprint arXiv:0910.2098 (2009) | DOI

[20] Lovász, L. The Rank of Connection Matrices and the Dimension of Graph Algebras, European Journal of Combinatorics, Volume 27 (2006) no. 6, pp. 962-970 | DOI

[21] Lusher, D.; Koskinen, J.; Robins, G. Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications, Cambridge University Press, 2013 | DOI

[22] Mariani, M. S.; Ren, Z.-M.; Bascompte, J.; Tessone, C. J. Nestedness in Complex Networks: Observation, Emergence, and Implications, Physics Reports, Volume 813 (2019), pp. 1-90 | DOI

[23] McPherson, M.; Smith-Lovin, L.; Cook, J. M. Birds of a Feather: Homophily in Social Networks, Annual review of sociology (2001) | DOI

[24] Murase, Y.; Jo, H.-H.; Török, J.; Kertész, J.; Kaski, K. Structural Transition in Social Networks: The Role of Homophily, Scientific reports, Volume 9 (2019) no. 1, p. 4310 | DOI

[25] Ódor, G.; Czifra, D.; Komjáthy, J.; Lovász, L.; Karsai, M. Switchover Phenomenon Induced by Epidemic Seeding on Geometric Networks, Proceedings of the National Academy of Sciences, Volume 118 (2021) no. 41, p. e2112607118 | DOI

[26] Orbanz, P.; Roy, D. M. Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures, IEEE transactions on pattern analysis and machine intelligence, Volume 37 (2014) no. 2, pp. 437-461 | DOI

[27] Peel, L. A Model Petting Zoo for Interacting with Network Structure, Peer Community in Network Science (2023) | DOI

[28] Peixoto, T. P. Nonparametric Bayesian Inference of the Microcanonical Stochastic Block Model, Physical Review E, Volume 95 (2017) no. 1, p. 012317 | DOI

[29] Peixoto, T. P. The Graph-Tool Python Library, figshare (2014) | DOI

[30] Peng, H.; Nematzadeh, A.; Romero, D. M.; Ferrara, E. Network Modularity Controls the Speed of Information Diffusion, Physical Review E, Volume 102 (2020) no. 5, p. 052316 | DOI

[31] Perlin, K. Improving Noise, Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, 2002, pp. 681-682 | DOI

[32] Ravasz, E.; Barabási, A.-L. Hierarchical Organization in Complex Networks, Physical review E, Volume 67 (2003) no. 2, p. 026112 | DOI

[33] Schaub, M. T.; Li, J.; Peel, L. Hierarchical Community Structure in Networks, Physical Review E, Volume 107 (2023) no. 5, p. 054305 | DOI

[34] Sischka, B.; Kauermann, G. EM-based Smooth Graphon Estimation Using MCMC and Spline-Based Approaches, Social Networks, Volume 68 (2022), pp. 279-295 | DOI

[35] Sischka, B.; Kauermann, G. Stochastic Block Smooth Graphon Model, arXiv preprint arXiv:2203.13304 (2022) | DOI

[36] Snijders, T. A.; Nowicki, K. Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure, Journal of classification, Volume 14 (1997) no. 1, pp. 75-100 | DOI

[37] Talaga, S.; Nowak, A. Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model, Journal of Artificial Societies and Social Simulation, Volume 23 (2020) no. 2, p. 6 | DOI

[38] Wang, X. F.; Chen, G. Complex Networks: Small-World, Scale-Free and Beyond, IEEE circuits and systems magazine, Volume 3 (2003) no. 1, pp. 6-20 | DOI

[39] Watts, D. J.; Strogatz, S. H. Collective Dynamics of `Small-World'Networks, nature, Volume 393 (1998) no. 6684, pp. 440-442 | DOI

[40] Waxman, B. M. Routing of Multipoint Connections, IEEE journal on selected areas in communications, Volume 6 (1988) no. 9, pp. 1617-1622 | DOI

[41] Wojahn, O. W. Airline Network Structure and the Gravity Model, Transportation Research Part E: Logistics and Transportation Review, Volume 37 (2001) no. 4, pp. 267-279 | DOI

[42] Wolfe, P. J.; Olhede, S. C. Nonparametric Graphon Estimation, arXiv preprint arXiv:1309.5936 (2013) | DOI

[43] Yamaguchi, H.; Ogawa, Y.; Maekawa, S.; Sasaki, Y.; Onizuka, M. Controlling Internal Structure of Communities on Graph Generator, 2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE, 2020, pp. 937-940 | DOI

[44] Young, S. J.; Scheinerman, E. R. Random Dot Product Graph Models for Social Networks, International Workshop on Algorithms and Models for the Web-Graph, Springer, 2007, pp. 138-149 | DOI

[45] Zhuang, Y.; Arenas, A.; Yağan, O. Clustering Determines the Dynamics of Complex Contagions in Multiplex Networks, Physical Review E, Volume 95 (2017) no. 1, p. 012312 | DOI

Cited by Sources: