Research And Applications On Expected Shortest Distance In Uncertain Graphs

In the real world, data in many fields can be viewed as “graph”. Comparingwith the traditional relational data, graph data always shows more flexibility. Due todata imprecision and the limitation of data acquisition methods, uncertainy is quitecommon in graphs, such as protein-protein interaction networks, social networks, e.t.Take protein-protein interaction networks as an example, because the detection ofinteraction between proteins is not precise, the interaction is either present orabsent.This paper focuses on shortest distance problem in uncertain graphs, which wecall expected shortest distance problem, and we analyze the complexity of thisproblem and prove that there is no polynomial time algorithm for it. To solve thisproblem, we utilize random sampling methods to acquire some possible worlds ofthe uncertain graph, then compute finite shortest distance on each and estimateexpected shortest distance with the average value. To improve efficiency, wepropose several pruning techniques. Then, we propose an approximation algorithmbasing on random sampling using antithetic variables and prove that it outperformsdirect random sampling in both efficiency and accuracy. Our experiments on realuncertain graphs demonstrate the efficiency and accuracy of our algorithm.Finally, this paper applies the expected shortest distance to the problems ofcompleting the protein complex and clustering in uncertain graphs. Our experimentsshow that it is quite effective when we apply the expected shortest distance to theabove problems.