Hopping in the Crowd to Unveil Network Topology

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 excluded-volume 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.

Figure 1

Asymptotic distribution of walkers diffusing on a scale-free network under different crowding conditions, as specified by $\beta$. Standard diffusion is recovered in the limit $\beta \to 0$ and displayed in the leftmost picture. Nodes are drawn with a size proportional to the corresponding asymptotic density, ${\rho }_i^{\infty }$.

Figure 2

Examples of network reconstructions, $p(k)$ vs $k$. (a) Erdos-Renyi network with $\mathrm{\Omega }=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 $\mathrm{\Omega }=\sum _{k}p(k)=1000$. (b) Scale-free network with $\mathrm{\Omega }=500$ and $\gamma =2$. The degree distribution $p(k)$ is plotted in log-log 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 single-node measurements. The estimated number of nodes is $\mathrm{\Omega }=\sum _{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), $\mathrm{\Omega }=34$. Here, $s=20$. The estimated size of the network is $\mathrm{\Omega }=\sum _{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 $\mathrm{\Omega }=453$. Blue circles depict the exact distribution, while red squares refer to the reconstruction performed with $s=200$ experiments, which gives $\mathrm{\Omega }=\sum _{k}p(k)=453.76$.