Evaluating topology quality through random walks

A distributed system or network can be modeled as a graph representing the "who knows who" relationship. The conductance of a graph expresses the quality of the connectivity. In a network composed of large dense clusters, connected through only a few links, the risk of partitioning is high; this is typically reflected by a low conductance of the graph. Computing the conductance of a graph is a complex and cumbersome task. Basically, it requires the full knowledge of the graph and is prohibitively expensive computation-wise. Beyond the information carried by the conductance of a graph, what really matters is to identify critical nodes from the topology point of view. In this paper we propose a fully decentralized algorithm to provide each node with a value reflecting its connectivity quality. Comparing these values between nodes, enables to have a local approximation of a global characteristic of the graph. Our algorithm relies on an anonymous probe visiting the network in a unbiased random fashion. Each node records the time elapsed between visits of the probe (called return time in the sequel). Computing the standard deviation of such return times enables to give an information to all system nodes, information that may be used by those nodes to assess their relative position, and therefore the fact that they are critical, in a graph exhibiting low conductance. Based on this information, graph improvement algorithms may be triggered. Moments of order 1 and 2 of the return times are evaluated analytically using a Markov chain model, showing that standard deviation of return time is related to the position of nodes in the graph. We evaluated our algorithm through simulations. Results show that our algorithm is able give informations that are correlated to the conductance of the graph. For example we were able to precisely detect bridges in a network composed of two dense clusters connected through a single link