1 Determining Source-Destination Connectivity in Uncertain Networks:Modeling and Solutions Luoyi Fu,Xinzhe Fu,Zhiying Xu2,Qianyang Pengl,Xinbing Wang2,and Songwu Lu3 Dept.of Computer Science,Shanghai Jiao Tong University,China. Email:{yiluofu,fxz0114,az950512,xwang8 @sjtu.edu.cn. 2Dept.of Electrical Engineering,Shanghai Jiao Tong University,China.Email:{xuzhiying}@sjtu.edu.cn 3Dept.of Computer Science,University of California,Los Angeles,USA.Email:{slu}@cs.ucla.edu Abstract-Determination of source-destination connectivity in the networks investigated are modeled as deterministic graphs networks has long been a fundamental problem,where most 4],[5]with the source-destination connectivity problems existing works are based on deterministic graphs that overlook transformed to the corresponding graph reachability problems. the inherent uncertainty in network links.To overcome such limitation,this paper models the network as an uncertain graph However,as indeterminacy plagues in our life,deterministic where each edge e exists independently with some probability graph often fails to serve as a suitable model for networks p(e).The problem examined is that of determining whether nowadays.Usually,we do not have certain knowledge of a given pair of nodes,a source s and a destination t,are existence of network links.For instance,in social networks. connected by a path or separated by a cut.Assuming that during due to the variability of social ties [6],the relations between each determining process we are associated with an underlying graph,the existence of each edge can be unraveled through edge network nodes may not be known in advance:in communi- testing at a cost of c(e).Our goal is to find an optimal strategy cation systems,established connections between nodes may incurring the minimum expected testing cost with the expectation frequently fail because of the unreliability of data links [7]. taken over all possible underlying graphs that form a product [8].It has also been pointed out that more than 90%of distribution. network links are observed to be unreliable [10].Consequent- Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally ly,we may not obtain deterministic network configuration determining source-destination connectivity in uncertain graphs. from the predesigned topology;sometimes we even have to Specifically,through proving the NP-hardness of two closely intentionally blur the links for privacy reasons [11].All those related problems,we show that,contrary to its counterpart in factors impose a need to incorporate uncertainty into the deterministic graphs,this problem cannot be solved in polynomial network,which can essentially be modeled as an uncertain time unless P=NP.Driven by the necessity of designing an exact algorithm,we then apply the Markov Decision Process graph [11],where,instead of appearing deterministically,each framework to give a dynamic programming algorithm that edge is associated with some prior existence probability.The derives the optimal strategies.As the exact algorithm may have existence probabilities not only are symbols of uncertainty,but prohibitive time complexity in practical situations,we further also bear important attributes of network links.Take social propose two more efficient approximation schemes compromising the optimality.The first one is a simple greedy approach with network again for example.These probabilities may represent linear approximation ratio.Interestingly,we show that naive as the confidence of link prediction [12],or the strength of the it is,it enjoys significantly better performance guarantee than influence that a node has on the other [2].In communication some other seemingly more sophisticated algorithms.Second,by networks such as data center networks,these probabilities harnessing the submodularity of the problem,we further design a reflect the failure frequency of communication links [7]. more elaborate algorithm with better approximation ratio.The When the graph is uncertain,traditional methods such as effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets,from which depth-first-traversal,breadth-first-traversal and graph labeling we demonstrate that the proposed algorithms yield strategies with are no longer suitable for determining the source-destination smaller expected cost than conventional heuristics. connectivity of networks due to the lack of deterministic information on edges'existence.To hedge the uncertainty,we I.INTRODUCTION need to test the edges to determine whether they truly exist or not.However,such edge testing involves far more complicated Source and destination connectivity of networks has sig- procedures than simply identifying uncertain links and thus nificant applications in real life.It concerns crucial issues may turn out to be more costly.For example,in citation such as reliability,routing,information diffusion [1],[2],etc. networks,we can establish probabilistic relationships between Hence,in the past few decades,a lot of research has been papers just by reference information.In contrast,to unravel the dedicated to this problem [3],4,5]and there have been genuine relation between papers,we have to apply advanced many efficient algorithms proposed under various types of data mining approaches which involves considerably more networks.A common feature shared by all those works is that intensive computation.Consequently,it is extremely desirable The early version of this paper is to appear in the Proceedings of IEEE to test the most cost-effective edges,i.e.,to design a testing INFOCOM 2017 [41]. strategy that determines the source-destination connectivity of1 Determining Source-Destination Connectivity in Uncertain Networks: Modeling and Solutions Luoyi Fu1 , Xinzhe Fu1 , Zhiying Xu2 , Qianyang Peng1 , Xinbing Wang1,2, and Songwu Lu3 1Dept. of Computer Science, Shanghai Jiao Tong University, China. Email:{yiluofu,fxz0114,az950512,xwang8}@sjtu.edu.cn. 2Dept. of Electrical Engineering, Shanghai Jiao Tong University, China. Email:{xuzhiying}@sjtu.edu.cn 3Dept. of Computer Science, University of California, Los Angeles, USA. Email:{slu}@cs.ucla.edu Abstract—Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it enjoys significantly better performance guarantee than some other seemingly more sophisticated algorithms. Second, by harnessing the submodularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics. I. INTRODUCTION Source and destination connectivity of networks has sig￾nificant applications in real life. It concerns crucial issues such as reliability, routing, information diffusion [1], [2], etc. Hence, in the past few decades, a lot of research has been dedicated to this problem [3], [4], [5] and there have been many efficient algorithms proposed under various types of networks. A common feature shared by all those works is that The early version of this paper is to appear in the Proceedings of IEEE INFOCOM 2017 [41]. the networks investigated are modeled as deterministic graphs [4], [5] with the source-destination connectivity problems transformed to the corresponding graph reachability problems. However, as indeterminacy plagues in our life, deterministic graph often fails to serve as a suitable model for networks nowadays. Usually, we do not have certain knowledge of existence of network links. For instance, in social networks, due to the variability of social ties [6], the relations between network nodes may not be known in advance; in communi￾cation systems, established connections between nodes may frequently fail because of the unreliability of data links [7], [8]. It has also been pointed out that more than 90% of network links are observed to be unreliable [10]. Consequent￾ly, we may not obtain deterministic network configuration from the predesigned topology; sometimes we even have to intentionally blur the links for privacy reasons [11]. All those factors impose a need to incorporate uncertainty into the network, which can essentially be modeled as an uncertain graph [11], where, instead of appearing deterministically, each edge is associated with some prior existence probability. The existence probabilities not only are symbols of uncertainty, but also bear important attributes of network links. Take social network again for example. These probabilities may represent the confidence of link prediction [12], or the strength of the influence that a node has on the other [2]. In communication networks such as data center networks, these probabilities reflect the failure frequency of communication links [7]. When the graph is uncertain, traditional methods such as depth-first-traversal, breadth-first-traversal and graph labeling are no longer suitable for determining the source-destination connectivity of networks due to the lack of deterministic information on edges’ existence. To hedge the uncertainty, we need to test the edges to determine whether they truly exist or not. However, such edge testing involves far more complicated procedures than simply identifying uncertain links and thus may turn out to be more costly. For example, in citation networks, we can establish probabilistic relationships between papers just by reference information. In contrast, to unravel the genuine relation between papers, we have to apply advanced data mining approaches which involves considerably more intensive computation. Consequently, it is extremely desirable to test the most cost-effective edges, i.e., to design a testing strategy that determines the source-destination connectivity of