Projects per year
Abstract
Original language  English 

Article number  158301 
Number of pages  5 
Journal  Physical review letters 
Volume  120 
Issue number  15 
DOIs  
Publication status  Published  9 Apr 2018 
Keywords
 random walk
 complex network
 crowding
 network reconstruction
 non linear diffusion
Fingerprint Dive into the research topics of 'Hopping in the Crowd to Unveil Network Topology'. Together they form a unique fingerprint.
Projects

Competitive and diffusive processes in complex networks and timedelayed systems
1/10/16 → 30/09/19
Project: Research

PAI n°P7/19  DYSCO: Dynamical systems, control and optimization (DYSCO)
WINKIN, J., Blondel, V., Vandewalle, J., Pintelon, R., Sepulchre, R., Vande Wouwer, A. & SARTENAER, A.
1/04/12 → 30/09/17
Project: Research
Activities

Hopping in the crowd to unveil network topology
Timoteo Carletti (Speaker)
24 Sep 2018Activity: Talk or presentation types › Invited talk

Conference on Complex Systems 2018
Timoteo Carletti (Contributor)
24 Sep 2018 → 28 Sep 2018Activity: Participating in or organising an event types › Participation in conference
Cite this
 APA
 Author
 BIBTEX
 Harvard
 Standard
 RIS
 Vancouver
}
Hopping in the Crowd to Unveil Network Topology. / Asllani, Malbor; Carletti, Timoteo; Di Patti, Francesca ; Fanelli, Duccio; Piazza, Francesco.
In: Physical review letters, Vol. 120, No. 15, 158301, 09.04.2018.Research output: Contribution to journal › Letter › peerreview
TY  JOUR
T1  Hopping in the Crowd to Unveil Network Topology
AU  Asllani, Malbor
AU  Carletti, Timoteo
AU  Di Patti, Francesca
AU  Fanelli, Duccio
AU  Piazza, Francesco
N1  Funding Information: Asllani Malbor 1 ,* Carletti Timoteo 1 Di Patti Francesca 2 Fanelli Duccio 2 Piazza Francesco 3 naXys, Namur Institute for Complex Systems, 1 University of Namur , rempart de la Vierge 8, B 5000 Namur, Belgium Dipartimento di Fisica e Astronomia, 2 Università di Firenze , INFN and CSDC, Via Sansone 1, 50019 Sesto Fiorentino, Firenze, Italy 3 University of Orléans and Centre de Biophysique Moléculaire (CBM), CNRS UPR 4301, Rue C. Sadron, 45071 Orléans, France * Corresponding author. malbor.asllani@unamur.be 9 April 2018 13 April 2018 120 15 158301 29 November 2017 © 2018 American Physical Society 2018 American Physical Society We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excludedvolume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes. Federaal Wetenschapsbeleid 10.13039/501100002749 Horizon 2020 Framework Programme 10.13039/100010661 H2020 Marie Sk?odowskaCurie Actions 10.13039/100010665 642563 Networks are everywhere. The brain, Internet and cyber world, food webs, social contacts, and commuting fall within the vast realm of network science [1–3] . Irrespective of the specific domain of application, individual entities (e.g., material units, bits of information) belonging to a certain population may jump from one site (node) to its adjacent neighbors, following the intricate web of distinct links, which defines the architecture of a complex network [4–9] . The ability of agents to explore the network to which they are bound is customarily modeled as a standard diffusive process [4,10] . Individuals are therefore independent from each other, while mutual interference stemming from the competition for the available space is deliberately omitted. However, in realworld applications, the carrying capacity of each node is finite, an ineluctable constraint that should be accommodated for under crowded conditions [11–20] . On the other hand, the structure of the network is often unknown. Several methods have been introduced in the literature aimed at reconstructing the topology of the network from a direct assessment of the transport dynamics [21–23] . This amounts to solving an inverse problem, from functions back to structure, a task that involves formidable challenges [23–25] . Working along these lines, the aim of this Letter is twofold. On the one side, we will introduce a nonlinear operator to describe diffusion in a crowded network. The derivation originates from a microscopic stochastic framework and it is solidly grounded on first principles. As an important byproduct of the analysis, we will discuss the idea of “functional degree centrality,” as opposed to the usual structural notion that is routinely invoked in network studies. Then, we will outline an innovative scheme that exploits the dynamical entanglement among walkers to reconstruct the unknown topology of the network. The method allows one to accurately determine the distribution of connectivities (degrees) and to quantify, with unprecedented efficiency, the size of the examined network, as we shall here demonstrate for a selection of paradigmatic examples. Notably, all necessary information is gathered from just one randomly chosen node of the collection. Let us consider a generic undirected graph composed of Ω nodes and characterized by its adjacency matrix A ( A i j = 1 , if nodes i and j are connected, zero otherwise). The degree of each node, namely, the number of connected neighbors, is k i = ∑ j A i j . Each node is endowed with a given “carrying capacity,” i.e., is assumed to be partitioned into a large number N of compartments, which can be either occupied by an agent (a physical or abstract entity) or empty. The stochastic dynamics of a collection of particles randomly hopping on a network and competing for the available space within nodes is described by the following master equation d d t P ( n , t ) = ∑ i , j A i j [ T ( n i , n j  n i + 1 , n j  1 ) P ( n i + 1 , n j  1 , t )  T ( n i  1 , n j + 1  n i , n j ) P ( n i , n j , t ) ] , (1) where P ( n , t ) denotes the probability that the system will be in the state n = ( n 1 , … , n Ω ) at time t [15] . The scalar quantity n i identifies the number of particles on node i . On the righthand side of Eq. (1) we indicate explicitly only the species that are involved in the selected transition. In this stochastic process, one of the walkers sitting on node i is selected with probability n i / N and then made to jump to one of the k i neighboring nodes with probability 1 / k i . However, this can only occur if the target node is not fully occupied, i.e., with probability ( N  n j ) / N . Overall, the hopping probability T ( ·  · ) from node i to node j reads T ( n i  1 , n j + 1  n i , n j ) = 1 k i n i N ( N  n j ) N . (2) The above nonlinear transition probabilities accommodate for excludedvolume interactions [12] ; i.e., the jump rate is modulated by the crowding at destination. Multiplying by n i both sides of Eq. (1) and summing over all n i (see Supplemental Material [26] and Ref. [27] ), one obtains the rate equations for the evolution of the average density ⟨ n i ⟩ ≡ ∑ n n i P ( n , t ) . In the thermodynamic limit ρ i = lim N → ∞ ⟨ n i ⟩ / N and a straightforward manipulation yields ∂ ∂ t ρ i = ∑ j = 1 Ω Δ i j ( ρ j ( 1  ρ i )  k j k i ρ i ( 1  ρ j ) ) , (3) where use has been made of the fact that A i j = A j i and ⟨ n i n j ⟩ = ⟨ n i ⟩ ⟨ n j ⟩ (a condition that holds exact when N → ∞ [27] ). In the above equation, Δ i j = A i j / k j  δ i j denotes the elements of the Laplacian Δ , the transport operator that describes diffusion of noninteracting agents on a heterogeneous network [10] . Working under diluted conditions amounts to neglecting nonlinear terms in Eq. (3) , which therefore reduces to the standard diffusion equation ( ∂ / ∂ t ) ρ i = ∑ j = 1 Ω Δ i j ρ j [28] . The mass (total number of individuals) is an invariant of the dynamics, which means that the quantity β = ∑ i = 1 Ω ρ i ( t ) ∈ ( 0 , Ω ] is conserved. Owing to the inherent symmetry, which implies detailed balance, the equilibrium solution ρ i ∞ of Eq. (3) can be determined analytically by setting ρ j ∞ ( 1  ρ i ∞ )  ρ i ∞ k j / k i ( 1  ρ j ∞ ) = 0 , ∀ i , j [30] . Disregarding the trivial solution ρ i ∞ = 1 , one gets ρ j ∞ = a i k j / ( 1 + a i k j ) , where a i = ρ i ∞ [ k i ( 1  ρ i ∞ ) ]  1 . By definition, ρ j ∞ should not depend on i , which in turn implies a i = a ∀ i . This gives ρ i ∞ = a k i 1 + a k i , (4) where the constant a should be determined from the normalization condition ∑ i = 1 Ω ( a k i ) / ( 1 + a k i ) = β . Under diluted conditions, Eq. (4) returns the standard equilibrium solution for the diffusion operator: the asymptotic distribution of walkers at node i is proportional to its connectivity k i . Peaks in the steadystate concentration therefore identify structural hubs of the network, while peripheral nodes are associated with modest densities. In many practical applications, including page ranking schemes, the distribution of hopping walkers is hence believed to return an immediate measure of the nodes’ centrality. Further, punctual information as delivered by a large, although finite, population of individual diffusing on a network is usually processed by assuming a distribution of the incoming signals, which scales linearly with the connectivity of the nodes [1] . Nonlinear interference among interacting walkers competing for space alters significantly the aforementioned simple scenario. For sufficiently large connectivities, the predicted distribution (4) reaches a constant value. This effect is more pronounced the larger the value of a or, equivalently, the larger β . In Fig. 1 , we report the equilibrium density obtained from Eq. (4) on a scalefree network under different crowding conditions. When β grows, hubs become progressively less distinct. Structural centrality, as revealed by the distribution of noninteracting agents (and asymptotically approached in the limit β → 0 ), differs significantly from functional centrality, which follows the equilibrium distribution when β ≠ 0 and nodes are assigned a finite carrying capacity. Elaborating on this dichotomy is particularly relevant for scalefree networks. 1 10.1103/PhysRevLett.120.158301.f1 FIG. 1. Asymptotic distribution of walkers diffusing on a scalefree network under different crowding conditions, as specified by β . Standard diffusion is recovered in the limit β → 0 and displayed in the leftmost picture. Nodes are drawn with a size proportional to the corresponding asymptotic density, ρ i ∞ . As anticipated, the nonlinear transport operator introduced above opens up the perspective of designing a novel scheme to access key global features of a network from direct measurements of the steadystate dynamics. We aim, in particular, at determining p ( k ) , the distribution of connectivities k , which conditions implicitly the equilibrium density of agents [31] . Importantly, our method also allows us to estimate the total number of nodes Ω in the network. In the following, we will outline the mathematical steps of the procedure and then move forward to discussing a selected gallery of case studies. For any fixed β , we monitor the dynamics of the system at just one node of the collection (hereafter, i ). After a sufficiently long time, one can measure the local asymptotic concentration ρ i ∞ . Assuming the local connectivity k i to be known, which is a reasonable working hypothesis given that we are sitting at node i , we can write a ( β ) = ρ i ∞ 1  ρ i ∞ 1 k i , where the dependence of a on β has been emphasized. We now rewrite the normalization condition so as to bring p ( k ) into the picture, that is, β = ∑ k p ( k ) a ( β ) k 1 + a ( β ) k . (5) Since the network is limited in size, the previous sum involves a finite number of terms. Performing s independent measurements (or experiments), carried out for different values of the constant β , yields β = F p , (6) where β = ( β 1 , … , β s ) T , p = ( p ( 1 ) , … , p ( s ) ) T , and F l r , the generic element of matrix F , is given by F l r = r a ( β l ) 1 + r a ( β l ) . Determining the components of the vector p amounts to inverting matrix F . Notice that s , the number of independent measurements performed, should be at least equal to the maximum degree of the inspected network, which is not known a priori . As it is shown in the Supplemental Material [26] , one can progressively increase s until the reconstructed p ( k ) converges to a stable profile. Monitoring the first moments of the distribution against s provides a robust stopping criterion (see Supplemental Material [26] ). The matrix F can be illconditioned when the size of the inspected network is too large. In this case, dedicated regularization schemes can be employed to carry out the matrix inversion and recover the degree distribution [32] . To further improve the accuracy of the reconstruction, one can also impose additional constraints on the inversion algorithm, such as requiring a positivedefined p ( k ) . A comment is in order before turning to test the adequacy of our methodology. Our protocol to reconstruct the unknown distribution of connectivities works if excludedvolume effects are accounted for. Under extremely diluted conditions, standard diffusion holds and ρ i ∞ = b k i , with b constant. In this case, Eq. (5) yields the trivial condition ⟨ k ⟩ = β / b , where ⟨ k ⟩ = ∑ j p ( k j ) k j . Hence, performing many experiments for different values of β simply returns independent estimates of the first moment of the distribution. It is the nonlinear nature of (4) , the macroscopic blueprint of crowding, that enables the higher order moments of p ( k ) to be selfconsistently computed from independent experiments [33] . Notice that one can readily extend the microscopic diffusion model so as to accommodate for different carrying capacities on each node. Also, in this case, it is straightforward to obtain the corresponding meanfield equation and to compute the associated stationary solution. Assuming known the capacity of the node where the measurements are performed, one can immediately adapt the reconstruction scheme to this general setting (see Supplemental Material [26] ). In the remaining part of this Letter, we will validate the procedure against a limited selection of case studies that bear both theoretical and applied interest. As a first example, we consider an ErdosRenyi random network [34] with Ω = 1000 nodes and a probability for two random nodes to be linked p = 0.5 . According to the procedure discussed above, we track the evolution of the walkers and measure the asymptotic density at a generic node i , whose connectivity k i is assumed to be known. Here, s = 600 < Ω independent experiments are performed and the information processed to infer the distribution of connectivity p ( k ) . In Fig. 2(a) , we compare the reconstructed profile with the exact distribution. The agreement is good and illustrates well the efficacy of our procedure. Integrating the meanfield deterministic dynamics, or operating under the original stochastic framework [35] , returns consistent and equally accurate results (see Supplemental Material [26] ). From the reconstructed distribution, one can readily calculate Ω = ∑ k p ( k ) , the total number of nodes of the network. In this case, with s = 600 measurements, one obtains the true value Ω = 1000.0 . 2 10.1103/PhysRevLett.120.158301.f2 FIG. 2. Examples of network reconstructions, p ( k ) vs k . (a) ErdosRenyi network with Ω = 1000 . The probability p for a link between any two pairs of nodes is set to 0.5. Exact profiles (blue circles) and profiles reconstructed with s = 600 (red squares). The estimated number of nodes is Ω = ∑ k p ( k ) = 1000 . (b) Scalefree network with Ω = 500 and γ = 2 . The degree distribution p ( k ) is plotted in loglog scale, focusing on the relevant region in k . Blue circles represent the exact distribution, while red squares identify the profile reconstructed with s = 150 independent singlenode measurements. The estimated number of nodes is Ω = ∑ k p ( k ) = 500.2 . (c) Reconstructed (red squares) vs exact (blue circles) degree distribution for the undirected Karate Club network (shown in the inset), Ω = 34 . Here, s = 20 . The estimated size of the network is Ω = ∑ k p ( k ) = 34.02 . (d) The performance of the method is assessed by using the (symmetrized) C. elegans metabolic network (displayed in the inset) with Ω = 453 . Blue circles depict the exact distribution, while red squares refer to the reconstruction performed with s = 200 experiments, which gives Ω = ∑ k p ( k ) = 453.76 . The second example is a scalefree network generated according to the preferential attachment rule [36] . In Fig. 2(b) , we compare the exact distribution of connectivities (circles) with the approximated solution (squares) inferred through our algorithm. Also in this case, the agreement is satisfying: the powerlaw scaling is correctly reproduced and the predicted number of nodes are in excellent agreement with the true value (see caption of Fig. 2 ). Finally, we turn to study two other examples that build on real networks: the wellknown Karate Club network [37,38] and the C. elegans metabolic network (which was artificially made undirected) [38,39] . Diffusion is assumed to occur subject to finitevolume constraints and the method exemplified above is applied in order to recover the degree distribution from singlenode measurements of the steady state. The results reported in Figs. 2(c) and 2(d) , respectively, quantify the predictive power of the proposed methodology. Summing up, we have introduced a novel nonlinear operator to model the process of diffusion on a complex network under crowded conditions. Agents may randomly hop from one node to another, provided free space is available at the target destination. The asymptotic density distribution in the presence of crowding differs significantly from that predicted by standard diffusion, i.e., under diluted conditions. In the latter case, the density scales linearly with the nodes’ degree, while in crowded conditions, the equilibrium concentration saturates for large enough values of the connectivity. Based on this observation, we discussed the notion of functional hubs, as opposed to that based only on topology. Further, we developed an efficient scheme that enables one to infer the unknown distribution of connectivities from singlenode measurements of the asymptotic diffusion dynamics. The method takes advantage of the interference that builds up among microscopic agents as a consequence of the competition for the available space. Tests are performed using both synthetic and real networks, which illustrate convincingly the power of our method. The reconstruction scheme that we have introduced could prove useful in a number of different applications where the competition for available spatial resources is to be taken into account. For instance, crawlers that are customarily employed for web indexing protocols are naturally exposed to mutual interferences due to the finite bandwidth. Thus, they are often treated as packets of information randomly hopping on a queueing network [40,41] . The packets’ mobility depends on the degree of congestion of the nodes. Starting from these premises, it should be possible to use our method to recover structural information on the local network community by injecting a population of labeled crawlers of different size ( β ) and monitoring their on site distribution. Other examples may include vehicle mobility and traffic flow [4] , assuming that the true displacement dynamics can be described by a random walk. More generally, our method allows one, in principle, to determine the degree distribution of networks that are a priori undefined and become defined, alongside their connectivity patterns, once the coarsegrained (CG) units are identified as the nodes. As such, we have introduced an effective (functional) coarsegraining procedure, suitable for large complex systems of interacting components. An example could be the diffusion of small molecules (e.g., enzyme inhibitors or competitive ligands for specific cell surface receptors) through complex tissues, such as the skin. Thus, from the local concentration, one should be able to characterize the functional connectome of the tissue, seen as a complex network of interlinked CG components. Other applications may include the diffusion of molecules that mediate quorum sensing in multibacterial colonies, e.g., social interactions of bacteria in biofilms [42,43] . In this case, it would be instructive to adapt our algorithm to resolve the statistics of interactions among different species. In its present formulation, our approach is suited for symmetric networks only. Future extensions are planned to reconstruct the distribution of outgoing and incoming connectivities in asymmetric crowded networks, i.e., when detailed balance may break, by examining the directed flux of particles from just one node. Finally, it would be interesting to gauge the impact of endowing nodes with a finite carrying capacity on other measures of centrality introduced in the literature. We thank Renaud Lambiotte for insightful comments. The work of M. A. is supported by a FRSFNRS Postdoctoral Fellowship. The work of T. C. presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The scientific responsibility rests with its author(s). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SklodowskaCurie Grant Agreement No 642563. [1] 1 M. E. J. Newman , Networks: An Introduction ( Oxford University Press , Oxford, 2010 ). [2] 2 S. Boccaletti , V. Latora , Y. Moreno , M. Chavez , and D. U. Hwang , Phys. Rep. 424 , 175 ( 2006 ). PRPLCM 03701573 10.1016/j.physrep.2005.10.009 [3] 3 R. Albert and A.L. Barabasi , Rev. Mod. Phys. 74 , 47 ( 2002 ). RMPHAT 00346861 10.1103/RevModPhys.74.47 [4] 4 A. Barrat , M. Barthélemy , and A. Vespignani , Dynamical Processes on Complex Networks , 1st ed. ( Cambridge University Press , Cambridge, England, 2008 ). [5] 5 J. D. Noh and H. Rieger , Phys. Rev. Lett. 92 , 118701 ( 2004 ). PRLTAO 00319007 10.1103/PhysRevLett.92.118701 [6] 6 R. Sinatra , J. GómezGardeñes , R. Lambiotte , V. Nicosia , and V. Latora , Phys. Rev. E 83 , 030103(R) ( 2011 ). PRESCM 15393755 10.1103/PhysRevE.83.030103 [7] 7 V. Nicosia , F. Bagnoli , and V. Latora , Europhys. Lett. 94 , 68009 ( 2011 ). EULEEJ 02955075 10.1209/02955075/94/68009 [8] 8 N. Masuda , M. A. Porter , and R. Lambiotte , Phys. Rep. 716–717 , 1 ( 2017 ). PRPLCM 03701573 10.1016/j.physrep.2017.07.007 [9] 9 S. Manfredi , E. Di Tucci , and V. Latora , Phys. Rev. Lett. 120 , 068301 ( 2018 ). PRLTAO 00319007 10.1103/PhysRevLett.120.068301 [10] 10 I. Simonsen , K. A. Eriksen , S. Maslov , and K. Sneppen , Physica (Amsterdam) 336A , 163 ( 2004 ). PHYADX 03784371 10.1016/j.physa.2004.01.021 [11] 11 A. P. S. de Moura , Phys. Rev. E 71 , 066114 ( 2005 ). PRESCM 15393755 10.1103/PhysRevE.71.066114 [12] 12 T. M. Ligget , Stochastic Interacting Systems: Contact, Voter and Exclusion Processes , 1st ed. ( SpringerVerlag , Berlin, 1999 ). [13] 13 E. Almaas , R. V. Kulkarni , and D. Stroud , Phys. Rev. E 68 , 056105 ( 2003 ). PRESCM 15393755 10.1103/PhysRevE.68.056105 [14] 14 S. Kwon and Y. Kim , Phys. Rev. E 84 , 041103 ( 2011 ). PRESCM 15393755 10.1103/PhysRevE.84.041103 [15] 15 D. Fanelli and A. J. McKane , Phys. Rev. E 82 , 021113 ( 2010 ). PRESCM 15393755 10.1103/PhysRevE.82.021113 [16] 16 M. Galanti , D. Fanelli , and F. Piazza , Front. Phys. 4 , 33 ( 2016 ). FRPHAY 2296424X 10.3389/fphy.2016.00033 [17] 17 A. E. Fernando , K. A. Landman , and M. J. Simpson , Phys. Rev. E 81 , 011903 ( 2010 ). PRESCM 15393755 10.1103/PhysRevE.81.011903 [18] 18 K. A. Landman and A. E. Fernando , Physica (Amsterdam) 390A , 3742 ( 2011 ). PHYADX 03784371 10.1016/j.physa.2011.06.034 [19] 19 M. Galanti , D. Fanelli , A. Maritan , and F. Piazza , Europhys. Lett. 107 , 20006 ( 2014 ). EULEEJ 02955075 10.1209/02955075/107/20006 [20] 20 M. Galanti , S. Traytak , D. Fanelli , and F. Piazza , Phys. Chem. Chem. Phys. 18 , 15950 ( 2016 ). PPCPFQ 14639076 10.1039/C6CP01147K [21] 21 E. Schneidman , M. J. Berry II , R. Segev , and W. Bialek , Nature (London) 440 , 1007 ( 2006 ). NATUAS 00280836 10.1038/nature04701 [22] 22 S. Coccoa , S. Leiblerb , and R. Monasson , Proc. Natl. Acad. Sci. U.S.A. 106 , 14058 ( 2009 ). PNASA6 00278424 10.1073/pnas.0906705106 [23] 23 R. Burioni , M. Casartelli , M. di Volo , R. Livi , and A. Vezzani , Sci. Rep. 4 , 4336 ( 2014 ). SRCEC3 20452322 10.1038/srep04336 [24] 24 S. G. Shandilya and M. Timme , New J. Phys. 13 , 013004 ( 2011 ). NJOPFM 13672630 10.1088/13672630/13/1/013004 [25] 25 I. Malvestio , T. Kreuz , and R. G. Andrzejak , Phys. Rev. E 96 , 022203 ( 2017 ). PRESCM 24700045 10.1103/PhysRevE.96.022203 [26] 26 See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevLett.120.158301 for the derivation of the main equations and the calculation of the associated fixed point, for an extension of the nonlinear operator to the setting with nodes characterized by distinct carrying capacities, for a numerical analysis on the convergence of the proposed algorithm and for its extension to the stochastic framework. [27] 27 N. G. van Kampen , Stochastic Processes in Physics and Chemistry , 3rd ed. ( Elsevier , Amsterdam, 2007 ). [28] As a side remark, we observe that Eq. (3) can be cast in the equivalent form ( ∂ / ∂ t ) ρ i = ∑ j = 1 Ω Δ i j ρ j  ρ i ∑ j = 1 Ω Δ i j ρ j + ( ρ i / k i ) ∑ j = 1 Ω Δ i j ρ j k j . When ( k i = k ∀ i ), as it happens on a regular lattice subject to periodic boundary conditions, the last two terms cancel out and one recovers the linear diffusion equation. Stated differently, the signature of the microscopic exclusion rule disappears when heterogeneity gets lost. This is the generalization of an observation made by Huber in [29] (see also [16] ). [29] 29 D. L. Huber , Phys. Rev. B 15 , 533 ( 1977 ). PLRBAQ 05562805 10.1103/PhysRevB.15.533 [30] Indeed, this is the only stationary solution of Eq. (3) . Looking for the stationary solution, (3) amounts to solving Δ f → ( i ) = 0 , where f j ( i ) = ρ j ∞ ( 1  ρ i ∞ )  ρ i ∞ k j / k i ( 1  ρ j ∞ ) . For all i , f → ( i ) = ( f 1 ( i ) , … , f Ω ( i ) ) should be proportional to ( k 1 , … , k Ω ), the eigenvector relative to the null eigenvalue of the random walk Laplacian Δ . Hence, f j ( i ) = b i k j , for some b i . By imposing i = j , the previous equation yields 0 = b i k i , and since k i > 0 (the network is connected), one finally gets b i = 0 ∀ i , thus proving the claim (see also Supplemental Material [26] ). [31] p ( k ) is normalized so as to yield ∑ k p ( k ) = Ω . [32] 32 G. H. Golub and C. F. van Loan , Matrix Computations ( Johns Hopkins University Press , Baltimore, 1996 ). [33] If the system has relaxed to the equilibrium solution, the choice of the node i where the asymptotic density ρ i ∞ is measured does not impact the quality of the reconstruction. Identical distributions are in fact recovered irrespective of the specific selection operated (be the selected node a hub or a leaf). On the other hand, sampling the dynamics out of equilibrium could yield a poor estimate of the parameter a , which could spuriously depend on the node of observation. Averaging over different measurements allows one, however, to improve on the estimate of a , yielding a smooth convergence of the reconstruction procedure, as discussed in the Supplemental Material [26] with reference to the stochastic analogue of the problem. [34] 34 E. N. Gilbert , Ann. Math. Stat. 30 , 1141 ( 1959 ). AASTAD 00034851 10.1214/aoms/1177706098 [35] 35 D. T. Gillespie , J. Phys. Chem. 81 , 2340 ( 1977 ). JPCHAX 00223654 10.1021/j100540a008 [36] 36 A.L. Barabasi and R. Albert , Science 286 , 509 ( 1999 ). SCIEAS 00368075 10.1126/science.286.5439.509 [37] 37 W. W. Zachary , Journal of anthropological research 33 , 452 ( 1977 ). JAPRCP 10.1086/jar.33.4.3629752 [38] 38 J. Kunegis , in Proceedings of the International World Wide Web Conference Companion, Rio de Janeiro, 2013 ( ACM , New York, 2013 ), p. 1343 . [39] 39 J. Duch and A. Arenas , Phys. Rev. E 72 , 027104 ( 2005 ). PRESCM 15393755 10.1103/PhysRevE.72.027104 [40] 40 R. Guimerà , A. DíazGuilera , F. VegaRedondo , A. Cabrales , and A. Arenas , Phys. Rev. Lett. 89 , 248701 ( 2002 ). PRLTAO 00319007 10.1103/PhysRevLett.89.248701 [41] 41 D. De Martino , L. Dall’Asta , G. Bianconi , and M. Marsili , Phys. Rev. E 79 , 015101(R) ( 2009 ). PRESCM 15393755 10.1103/PhysRevE.79.015101 [42] 42 H. C. Flemming , J. Wingender , U. Szewzyk , P. Steinberg , S. A. Rice , and S. Kjelleberg , Nat. Rev. Microbiol. 14 , 563 ( 2016 ). NRMACK NRMACK 10.1038/nrmicro.2016.94 [43] 43 Y. H. Li and X. L. Tian , in Stress and Environmental Regulation of Gene Expression and Adaptation in Bacteria ( John Wiley&Son, Inc. , Hoboken, 2016 ), Vol. 2 , p. 1197 . Publisher Copyright: © 2018 American Physical Society. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.
PY  2018/4/9
Y1  2018/4/9
N2  We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excludedvolume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.
AB  We introduce a nonlinear operator to model diffusion on a complex undirected network under crowded conditions. We show that the asymptotic distribution of diffusing agents is a nonlinear function of the nodes’ degree and saturates to a constant value for sufficiently large connectivities, at variance with standard diffusion in the absence of excludedvolume effects. Building on this observation, we define and solve an inverse problem, aimed at reconstructing the a priori unknown connectivity distribution. The method gathers all the necessary information by repeating a limited number of independent measurements of the asymptotic density at a single node, which can be chosen randomly. The technique is successfully tested against both synthetic and real data and is also shown to estimate with great accuracy the total number of nodes.
KW  random walk
KW  complex network
KW  crowding
KW  network reconstruction
KW  non linear diffusion
UR  http://www.scopus.com/inward/record.url?scp=85045303944&partnerID=8YFLogxK
U2  10.1103/PhysRevLett.120.158301
DO  10.1103/PhysRevLett.120.158301
M3  Letter
VL  120
JO  Physical review letters
JF  Physical review letters
SN  00319007
IS  15
M1  158301
ER 