.2021 Nov 25;11(1):22964.

doi: 10.1038/s41598-021-02203-4.

Deciphering the generating rules and functionalities of complex networks

Xiongye Xiao^#¹, Hanlong Chen^#¹, Paul Bogdan²

Affiliations

PMID:34824290
PMCID: PMC8616909
DOI: 10.1038/s41598-021-02203-4

Deciphering the generating rules and functionalities of complex networks

Xiongye Xiao et al. Sci Rep.2021.

.2021 Nov 25;11(1):22964.

doi: 10.1038/s41598-021-02203-4.

Authors

Xiongye Xiao^#¹, Hanlong Chen^#¹, Paul Bogdan²

Affiliations

¹ Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90007, USA.
² Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90007, USA. pbogdan@usc.edu.

^# Contributed equally.

PMID:34824290
PMCID: PMC8616909
DOI: 10.1038/s41598-021-02203-4

Abstract

Network theory helps us understand, analyze, model, and design various complex systems. Complex networks encode the complex topology and structural interactions of various systems in nature. To mine the multiscale coupling, heterogeneity, and complexity of natural and technological systems, we need expressive and rigorous mathematical tools that can help us understand the growth, topology, dynamics, multiscale structures, and functionalities of complex networks and their interrelationships. Towards this end, we construct the node-based fractal dimension (NFD) and the node-based multifractal analysis (NMFA) framework to reveal the generating rules and quantify the scale-dependent topology and multifractal features of a dynamic complex network. We propose novel indicators for measuring the degree of complexity, heterogeneity, and asymmetry of network structures, as well as the structure distance between networks. This formalism provides new insights on learning the energy and phase transitions in the networked systems and can help us understand the multiple generating mechanisms governing the network evolution.

PubMed Disclaimer

Conflict of interest statement

The authors declare no competing interests.

Figures

**Figure 1**
NFD and NMFA quantify the network structure and reveal their generating rules. (**a,b**) The power-law dependence between the number of nodes (N) in the box and the box radius (r) centered on the single node quantifies the spatial expansion of the network structure, revealing the generating rules. (a) The node in the infinite unweighted networks. (b) The origin node of the weighted Sierpinski fractal networks. (c) The box-growing method of two different nodes (marked as red square and red triangle, respectively) in the artificial network G0. (d) The logarithmic relationship between the partition function and the observation scale, and the non-linear relationship between the mass exponent $τ (q)$ andq. (**g,h**) the multifractal spectrum (g) and the generalized fractal dimension (h) of the network G0. (e) The network examples. G0 is the network mentioned above composed of blue nodes and edges, we add three edges (orange dashed line) to form G1 and continue to add three edges (green dashed line) to form G2. (f) The structure distances between G0, G1, and G2. (**i,j**) The comparisons of the multifractal spectra(i) and the generalized fractal dimensions (j) between G0, G1, and G2. (k) The mean squared error (MSE) between the mass exponent distributions calculated by MFA and NMFA and the analytical mass exponent distribution of the (u, v)-flower network (u = 2, v = 2). (**l,m**) Three distance methods (i.e., structure distance, spectral distance and correlation distance) comparison using the Ollivier–Ricci curvature and the edge betweenness centrality.

**Figure 2**
The evolution of the Watts–Strogatz network. (a) The mechanism of the Watts–Strogatz network, which starts from a regular network. As the rewiring probability increases, the randomness increases, the network gradually becomes random. (b) The logarithmic relationship between the partition function and the scale, and the linear relationship between the mass exponent $τ (q)$ andq for the initial regular network with the rewiring probability $p = 0$ . (**c–e**) The multifractal spectrum (c) and the generalized fractal dimension (d) of 1000-node Watts–Strogatz networks with $p = 0, 0.001, 0.01, 0.1, 1$ (for eachp, the analysis is repeated 100 times). (e) The structure distance between the 400 networks with $p = 0.001, 0.01, 0.1, 1$ (we generate 100 networks randomly for eachp). (**f,g**) The variations in the distribution of the specific heat (f) and the Lipschitz–Holder exponent (g) whenp increases from 0 to 1 (we take 50 sets ofp at equal intervals, repeat 100 times for eachp and use the mean value). (**h–k**) Asp increases from 0 to 1, the evolution of the structural distance from the initial regular network (h); the degree of the complexity $α_{0}$ and the heterogeneityw (i); the measure of fractal dimension $D_{\max}, D_{\min}$ (j); and the measure of specific heat $C (q)$ (k). The solid lines in figures represent the mean value while the shades being the 99% confidence interval.

**Figure 3**
NMFA of real complex social networks. (**a–c**) We use BA and ER models to generate two networks with a similar number of nodes (200) and edges (600), and a merged network of them by linking their highest connected nodes with one edge (a). The differences between their multifractal spectra (a), generalized fractal dimension (b), and specific heat distributions (c). The BA, ER, and merged networks are represented as blue, orange, and green respectively. (d) We use the BA and ER models to generate 100 networks with a similar number of nodes (200) and edges (600) and measure their multifractal spectra and asymmetry shown in (d). The solid lines in the figures represent the mean value while the shades represent the 99% confidence interval. (**e,f**) The different structural features of BA network (clump) (e) and ER network (thorn) (f). (**g–l**) We use NMFA to show the multifractal features of two typical social networks changing over time. (**g–i**) The variations of the multifractal spectra (g), the generalized fractal dimension (h), and the specific heat distributions (i) of the Ask Ubuntu networks. (**j–l**) The variations of the multi-fractal spectra (j), generalized fractal dimension (k), and specific heat distributions (l) of the Facebook-like Forum networks. (**m–o**) The variation of the degree of complexity (m), heterogeneity (n), and asymmetry (o) of the two social networks for different time stamps.

**Figure 4**
NMFA of the adult Drosophila visual system. (a) The composition of the Drosophila visual system. (b) The connections between different regions in the Drosophila visual system. The area of the circle characterizes the size of the corresponding brain regions (i.e., number of neurons) and the width of the line between two circles characterizes the connection between the brain regions (i.e., number of neural connections shared by two regions). (**c–h**) The comparisons of the multifractal behavior between the networks in the optic lobe (OL) and the ventrolateral neuropils (VLNP). (**c,d,g**) The comparisons of the multifractal spectra (c), the mass exponent (d), generalized fractal dimension (d), and specific heat distribution (g) of the networks in the OL. (**e,f,h**) The comparisons of the multifractal spectra (e), the mass exponent (f), generalized fractal dimension (f), and specific heat distribution (h) of the networks in the VLNP. (**i,j**) The structure distance between the regional networks when q < 0 (i) and q > 0 (j) respectively. (**k–m**) The comparisons of the multifractal behaviors between the OL, VLNP, and the whole hemibrain. (k) The multifractal spectrum. (l) The generalized fractal dimension and mass exponent distribution. (m) The specific heat distribution.

See this image and copyright information in PMC

Cited by

Community detection in networks by dynamical optimal transport formulation.
Leite D, Baptista D, Ibrahim AA, Facca E, De Bacco C.Leite D, et al.Sci Rep. 2022 Oct 7;12(1):16811. doi: 10.1038/s41598-022-20986-y.Sci Rep. 2022.PMID:36207412Free PMC article.
Hierarchical growth in neural networks structure: Organizing inputs by Order of Hierarchical Complexity.
Leite S, Mota B, Silva AR, Commons ML, Miller PM, Rodrigues PP.Leite S, et al.PLoS One. 2023 Aug 31;18(8):e0290743. doi: 10.1371/journal.pone.0290743. eCollection 2023.PLoS One. 2023.PMID:37651418Free PMC article.
Adding links on minimum degree and longest distance strategies for improving network robustness and efficiency.
Chujyo M, Hayashi Y.Chujyo M, et al.PLoS One. 2022 Oct 26;17(10):e0276733. doi: 10.1371/journal.pone.0276733. eCollection 2022.PLoS One. 2022.PMID:36288333Free PMC article.
From pixels to connections: exploring in vitro neuron reconstruction software for network graph generation.
Hoffmann C, Cho E, Zalesky A, Di Biase MA.Hoffmann C, et al.Commun Biol. 2024 May 15;7(1):571. doi: 10.1038/s42003-024-06264-9.Commun Biol. 2024.PMID:38750282Free PMC article.Review.
Energy Transport alongα-Helix Protein Chains: External Drives and Multifractal Analysis.
Sefidkar N, Fathizadeh S, Nemati F, Simserides C.Sefidkar N, et al.Materials (Basel). 2022 Apr 10;15(8):2779. doi: 10.3390/ma15082779.Materials (Basel). 2022.PMID:35454472Free PMC article.

See all "Cited by" articles

References

1. Turner LM, White MA, Tautz D, Payseur BA. Genomic networks of hybrid sterility. PLoS Genet. 2014;10(2):e1004162. - PMC - PubMed
1. Jain, S., Xiao, X., Bogdan, P. & Bruck, J. (2021) Generator based approach to analyze mutations in genomic datasets. Scientific Reports11(1). 10.1038/s41598-021-00609-8 - PMC - PubMed
1. Wang J, Rao S, Chu J, et al. A protein interaction network for pluripotency of embryonic stem cells. Nature. 2006;444(7117):364–368. - PubMed
1. Jeong H, Mason SP, Barabási A-L, Oltvai ZN. Lethality and centrality in protein networks. Nature. 2001;411(6833):41–42. - PubMed
1. Ideker T, Thorsson V, Ranish JA, et al. Integrated genomic and proteomic analyses of a systematically perturbed metabolic network. Science. 2001;292(5518):929–934. - PubMed

Movatterモバイル変換

Account

Save citation to file

Email citation

Add to Collections

Add to My Bibliography

Your saved search

Create a file for external citation management software

Your RSS Feed

Full text links

Actions

Share

Deciphering the generating rules and functionalities of complex networks

Affiliations

Deciphering the generating rules and functionalities of complex networks

Authors

Affiliations

Abstract

Conflict of interest statement

Figures

Similar articles

Cited by

References

Publication types

Grants and funding

LinkOut - more resources

Full Text Sources