Distance distribution in random graphs and application to networks exploration

Abstract

We consider the problem of determining the proportion of edges that are discovered in an Erdos-Renyi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a new way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.

12 pages, 8 figures (18 .eps files)

References in corpus (5)

• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Metric structure of random networks
• Ring structures and mean first passage time in networks
• Log-periodic oscillations due to discrete effects in complex networks

Cited by in corpus (20)

• A Spectral Graph Uncertainty Principle
• Linking the Network Centrality Measures Closeness and Degree
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Effect of shortest path multiplicity on congestion of multiplex networks
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Distribution of shortest cycle lengths in random networks
• Evolutionary Events in a Mathematical Sciences Research Collaboration Network
• Statistical analysis of articulation points in configuration model networks
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Node-node distance distribution for growing networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Statistical analysis of edges and bredges in configuration model networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Stochastic graph Voronoi tessellation reveals community structure
• Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks
• Distinguishing Infections on Different Graph Topologies