Experimental evaluation of reliability estimation over uncertain graphs

Abstract

In the study of networked system, we often look at networks such as social media networks, communication networks and biological networks. The data in these networks are often uncertain. In many real-world applications, uncertainty has been recognised to be intrinsic in graph data due to measurement error, prediction models, mistakes or noise. Graph data with uncertainty is often modelled by uncertain graphs whose vertices and/or edges are associated with probability of their existence. Querying uncertain graphs has become an increasingly important topic. Reliability, the probability of a node reaching another, is the basis for a variety of databases and network applications. Since 1990s, several sampling methods have been proposed to compute reliability. In this project, we will explore some of the proposed reliability computation approaches and comprehensively evaluate their performance on a range of real and synthesised uncertain networks with varying size and connectivity. Experiments carried out verify that different reliability computations are suitable for different situations. We will also present some of the limitations of this project and possible future work on this topic.