Are We Connected? Optimal Determination of Source–Destination Connectivity in Random Networks
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2016 IEEE. This paper investigates the problem of optimally determining sourcedestination connectivity in random networks. Viewing the network as a random graph, we start by investigating the ErdosRenyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source S, and a destination D are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of S and D, a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest SD path as well as in a minimum SD cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with n nodes, where there is an edge between two nodes with probability p, the optimal strategy does not depend on p or n, even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around p = ln n/n. The policy is efficiently implementable, requiring no more than 30log2 n operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.
author list (cited authors)

Fu, L., Wang, X., & Kumar, P. R.
citation count
publication date
publisher
published in
Research
keywords

Connectivity

Optimal

Random Graphs
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue