UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Efficient computations on uncertain graphs by group testing, streaming and recycling Bevilacqua, Glenn Steven


Uncertain graphs, where the presence of connections between nodes is probabilistic, have received a great deal of attention in a wide range of fields. Despite the progress made by prior works, the application of existing algorithms to solve the important problems of coverage maximization, also known as Influence Maximization (IM), and reachability estimation, also known as reliability, on uncertain graphs remains constrained by their computational costs in the form of both the running time and memory needed for one to achieve high quality solutions. In Chapter 2 we address the issue that when performing sampling on large networks the majority of random draws of edges are being effectively wasted as the majority of edges will not be live. We resolve this by introducing an approach that through the application of group testing of edges scales only logarithmically with the number of failed edges in the worst case as opposed to linearly. In Chapter 3 we tackle the problem of the exorbitant memory required to store the Reverse Influence Sample (RIS) collection used by existing approaches to solve the IM problem becoming prohibitive. We avoid this by developing a new non-greedy approach that avoids storing the RIS collection by streaming it instead. In Chapter 4 we note that a key cause of Monte Carlo simulation, along with existing approaches that build upon it, becoming ineffective for estimating low probability reachability is caused by the number of samples it needs to attain a desired relative error depending on the probability that is being estimated. We remedy this by developing a technique of recycling of random draws which enables us to develop an algorithm whose relative error does not depend on the probability being estimated and as such does not suffer from this limitation. In all cases we perform experiments on real datasets to empirically validate the effectiveness of the algorithms and techniques we develop.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International