Hopping in the crowd to unveil network topology

Abstract

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 that can be chosen randomly. The technique is successfully tested against both synthetic and real data, and shown to estimate with great accuracy also the total number of nodes.

References in corpus (8)

• Cooperative Game Theory Approaches for Network Partitioning
• Random walks and diffusion on networks
• Congestion phenomena on complex networks
• Maximal-entropy random walks in complex networks with limited information
• Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity
• Impact of network structure on a model of diffusion and competitive interaction
• Diffusion of tagged particles in a crowded medium
• Random Walks on Complex Networks

Cited by in corpus (16)

• Random walks on hypergraphs
• Turing patterns in systems with high-order interactions
• Graph-based data clustering via multiscale community detection
• Reactive random walkers on complex networks
• From random walks on networks to nonlinear diffusion
• Pattern invariance for reaction-diffusion systems on complex networks
• Classes of random walks on temporal networks with competing timescales
• Unifying information propagation models on networks and influence maximization
• Nonlinear random walks optimize the trade-off between cost and prevention in epidemics lockdown measures : the ESIR model
• Impact of network characteristics on network reconstruction
• Reactive explorers to unravel network topology
• Quasi-periodic dynamics and a Neimark-Sacker bifurcation in nonlinear random walks on complex networks
• Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
• Self-segregation in heterogeneous metapopulation landscapes
• Emergence of power-law distributions in self-segregation reaction-diffusion processes
• Iterative procedure for network inference