Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/229754
Title: Are We Connected? Optimal Determination of Source&x2013;Destination Connectivity in Random Networks
Authors: Luoyi Fu;Xinbing Wang;P. R. Kumar
Year: 2017
Publisher: IEEE
Abstract: This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (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 S-D path as well as in a minimum S-D 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 30log<sub>2</sub> 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.
URI: http://localhost/handle/Hannan/229754
volume: 25
issue: 2
More Information: 751,
764
Appears in Collections:2017

Files in This Item:
File SizeFormat 
7575664.pdf3.33 MBAdobe PDF
Title: Are We Connected? Optimal Determination of Source&x2013;Destination Connectivity in Random Networks
Authors: Luoyi Fu;Xinbing Wang;P. R. Kumar
Year: 2017
Publisher: IEEE
Abstract: This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (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 S-D path as well as in a minimum S-D 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 30log<sub>2</sub> 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.
URI: http://localhost/handle/Hannan/229754
volume: 25
issue: 2
More Information: 751,
764
Appears in Collections:2017

Files in This Item:
File SizeFormat 
7575664.pdf3.33 MBAdobe PDF
Title: Are We Connected? Optimal Determination of Source&x2013;Destination Connectivity in Random Networks
Authors: Luoyi Fu;Xinbing Wang;P. R. Kumar
Year: 2017
Publisher: IEEE
Abstract: This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos-Renyi (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 S-D path as well as in a minimum S-D 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 30log<sub>2</sub> 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.
URI: http://localhost/handle/Hannan/229754
volume: 25
issue: 2
More Information: 751,
764
Appears in Collections:2017

Files in This Item:
File SizeFormat 
7575664.pdf3.33 MBAdobe PDF