Open Collections

Bevilacqua, Glenn Steven

University of British Columbia

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.

Text

2022-04-19

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/81252

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/