Laplacian paths in complex networks: Information core emerges from entropic transitions

Open Access

Laplacian paths in complex networks: Information core emerges from entropic transitions

Pablo Villegas, Andrea Gabrielli, Francesca Santucci, Guido Caldarelli, and Tommaso Gili

Phys. Rev. Research 4, 033196 – Published 12 September 2022

Abstract

Complex networks usually exhibit a rich architecture organized over multiple intertwined scales. Information pathways are expected to pervade these scales reflecting structural insights that are not manifest from analyses of the network topology. Moreover, small-world effects correlate with the different network hierarchies complicating the identification of coexisting mesoscopic structures and functional cores. We present a communicability analysis of effective information pathways throughout complex networks based on information diffusion to shed further light on these issues. We employ a variety of brand-new theoretical techniques allowing for: (i) bring the theoretical framework to quantify the probability of information diffusion among nodes, (ii) identify critical scales and structures of complex networks regardless of their intrinsic properties, and (iii) demonstrate their dynamical relevance in synchronization phenomena. By combining these ideas, we evidence how the information flow on complex networks unravels different resolution scales. Using computational techniques, we focus on entropic transitions, uncovering a generic mesoscale object, the information core, and controlling information processing in complex networks. Altogether, this study sheds much light on allowing new theoretical techniques paving the way to introduce future renormalization group approaches based on diffusion distances.

Received 14 February 2022
Accepted 22 June 2022

DOI:https://doi.org/10.1103/PhysRevResearch.4.033196

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Physics Subject Headings (PhySH)

Community structure Critical phenomena Network diffusion Network phase transitions Network structure Phase transitions Shannon entropy Structural phase transition Synchronization Synchronization transition

Networks & random structures Scale free & inhomogeneous networks

Computational complexity Diffusion & random walks Information theory

NetworksStatistical Physics & ThermodynamicsInterdisciplinary PhysicsPhysics of Living Systems

Authors & Affiliations

Pablo Villegas ^1,2,*, Andrea Gabrielli ^3,2,4, Francesca Santucci ¹, Guido Caldarelli ^5,6,7,†, and Tommaso Gili ¹

¹Networks Unit, IMT School for Advanced Studies Lucca, Piazza San Francesco 19, 50100, Lucca, Italy
²“Enrico Fermi” Research Center (CREF), Via Panisperna 89A, 00184 Rome, Italy
³Dipartimento di Ingegneria, Università Roma Tre, Via Vito Volterra 62, 00146 Rome, Italy
⁴Istituto dei Sistemi Complessi (ISC) - CNR, Dipartimento di Fisica, Università “Sapienza”, Piazzale Aldo Moro 2, 00185 Rome, Italy
⁵Department of Molecular Sciences and Nanosystems, Ca' Foscari University of Venice, 30172 Venice, Italy
⁶European Centre for Living Technology, 30124 Venice, Italy
⁷London Institute for Mathematical Sciences, W1K2XF London, United Kingdom

^*pablo.villegas@cref.it
^†guido.caldarelli@unive.it

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand

Issue

Vol. 4, Iss. 3 — September - November 2022

Subject Areas

Reuse & Permissions

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Network average of the entropy $S [ρ (τ)]$ versus the inverse of time evolution $1 / τ$ for an Erdös-Renyi network of $〈 k 〉 = 30$ and different system sizes (see legend). A critical point ( $τ_{C}$ ) separates the segregated phase from the integrated one. The specific heat $C$ presents a peak just at this critical value. Inset: Variance of the entropy, averaged in the graph ensemble, and multiplied by $N$ ; $Σ = σ_{S}^{2} N$ . The point of maximal variability coincides with the point of maximal slope in $S [ρ (τ)]$ for all network sizes $N$ (dashed lines in the main figure). All curves have been averaged over $10^{2}$ realizations.
Reuse & Permissions
Figure 2
Network average of the entropy parameter $S$ versus the inverse of time evolution $1 / τ$ for: (a) Stochastic block model (SBM) for different network sizes (see legend) constituted by four equal interconnected modules $p = 128 / N$ and interconnectivity probability $q = 1 / N$ (i.e., with $〈 k 〉 = 32$ ). Two peaks in the derivative of the order parameter $C$ indicate diverse critical points, and a broad region separates the segregated phase from the integrated one. The peak at short times happens for similar diffusion times to the ER network, because of the similarity between both networks at a local scale. (b) Hierarchic modular network with core-periphery structure (HC-CP). We consider a set of basal nodes with $N_{b} = 25$ units and connectivity per node $k_{0} = 12$ (the mean connectivity ranges from $〈 k 〉 ≃ 37$ for $N = 256$ to $〈 k 〉 ≃ 52$ for $N = 2048$ ). (c) Human Connectome network ( $〈 k 〉 ≃ 38$ for the binarized case). All curves for the SBM and the HM-CP have been averaged over $10^{2}$ realizations.
Reuse & Permissions
Figure 3
Information integration substructures. (a) Probability distribution of processed information $P (ρ^{'})$ for different values of the time evolution in the weighted Human Connectome network (see legend). At short times no nodes can integrate and process information (red line), generating an emergent processing information structure at intermediate times that finally converges to a delta function for large enough times (dark blue line). (b) Rank index $i$ versus the normalized inverse of the corresponding nonzero eigenvalues of the $ζ$ Laplacian matrix for the weighted HC, at different evolution times (see legend). The decay time, associated with the different eigenvalues, reflects the different hierarchical organizations at different resolution scales. Inset: Fraction of nodes which are in the giant component (GC) versus $1 / τ$ for the weighted HC. The gray dashed line indicates the position of the $C$ peak at short times [see purple line in Fig. 2]. (c) Emergent structures in the weighted HC. The time evolution $τ$ increases from up to down highlighting different meaningful mesoscopic scales, namely: $τ = 2$ (segregated phase), $τ = 2 \times 10^{1}, 2 \times 10^{2}, 2 \times 10^{3}$ (intermediate phase), and $τ = 2 \times 10^{4}$ (integrated phase). Left column: The giant component of network substructures, obtained through the $ρ^{'}$ binarized version $ζ$ (as explained in the main text). Right column: Snapshots of typical $ζ$ information integration matrices; the color code represents the information integration for pair nodes as shown in the scale. The segregated phase is characterized by no information invading the system, being it confined on each node (i.e., along the diagonal, displaying the basal system scale). On the other hand, for intermediate values of $τ$ different substructures coexist, depending on the structural complexity of the underlying network. In the segregated phase, substructures are no longer observed, and a homogeneous “all to all,” information integration network is observed (i.e., the network can be considered as a unique node, see also the videos in the Supplemental Material [57]). (d)–(g) Information core for different networks: (d) Stochastic block model (SBM) with $N = 1024$ nodes. Inset: Giant component corresponding to the particular decomposition of an individual module. (e) Giant component of a hierarchic modular network with core-periphery (HM-CP) with $N = 1024$ nodes and six hierarchical levels, and the Human Connectome network, whether (f) binarized or (g) weighted.
Reuse & Permissions
Figure 4
Information core synchronizability. Kuramoto order parameter of the full network and the information core $R$ and $R_{core}$ versus coupling strength $K$ for: (a) A SBM of size $N = 1024$ , with $p = 128 / N$ and $q = 1 / N$ , (b) a HM-CP network with $N_{b} = 25, k_{0} = 12$ , and $l = 6$ , (c) a SF network of size $N = 1024$ and $m = 1$ , and (d) the weighted HC. Right $y$ axis shows the temporal variance of $R$ over network realizations (dashed lines). The point of maximal temporal fluctuations indicates the critical point for the full network and the information core. Observe that the information core generically synchronizes first for all network structures. All curves have been averaged over $10^{2}$ intrinsic frequency realizations. Parameters: $σ = 0.1, g (ω) = N (0, 0.1), d t = 5 \times 10^{- 3}$ .
Reuse & Permissions
Figure 5
Network average of the entropy parameter $S [ρ (τ)]$ versus the inverse of diffusion time $1 / τ$ , for a Barabasi-Albert network with $m = 1, 〈 k 〉 = 2$ , and different sizes (see legend). The critical point ( $τ_{C}$ ) separates the segregated phase from the integrated one. The specific heat $C$ scales depending on the system size at this critical value, even if it presents a local peak at short diffusion times. Inset: Variance of the entropy averaged over network realizations multiplied by $N$ ; $Σ = σ_{S} N$ . The point of maximal variability marks the full integration of information throughout the network for all network sizes $N$ (dashed lines in main figure). All curves have been averaged over $10^{2}$ realizations.
Reuse & Permissions
Figure 6
Network average of the entropy parameter $S [ρ (τ)]$ versus the inverse of diffusion time $1 / τ$ for: (a) HM-R network for different network sizes, $N = 2^{s}$ (see legend), where $s$ is the total number of hierarchical levels. The slow decay in the derivative of the order parameter $C$ confirms the existence of a broad region separating the segregated phase from the integrated one. (b) Comparison between a hierarchic modular network with core-periphery structure (HM-CP, $〈 k 〉 ≃ 47$ ) and a simple hierarchic modular network (HM-R, $〈 k 〉 ≃ 28$ ) with six hierarchical levels. The HM-CP network exhibits shorter integration times and a broader regime of information processing in the zooming-out process. All curves for the HM-R and the HM-CP have been averaged over $10^{2}$ realizations.
Reuse & Permissions

Physical Review Research