Estimating Reachability Set Sizes in Dynamic Graphs
Sudarshan Mandayam Aji · 2014
(Abstract) Graphs are a commonly used abstraction for diverse kinds of interactions, e.g., on Twitter and Facebook. Different kinds of topological properties of such graphs are computed for gaining insights into their structure. Computing properties of large real networks is computationally very challenging. Further, most real world networks are dynamic, i.e., they change over time. Therefore there is a need for efficient dynamic algorithms that offer good space-time trade-offs. In this thesis we study the problem of computing the reachability set size of a vertex, which is a fundamental problem, with applications in databases and social networks. We develop the first Giraph based algorithms for different dynamic versions of these problems, which scale to graphs with millions of edges. Acknowledgments This work has been made possible because of the support of many people. Firstly, I thank my advisor Dr.Anil Vullikanti for working with me and being a source of constant guidance and support in my research. I thank Dr.Madhav Marathe and Dr.Keith Bisset for supporting me by being on the committee. I have been exposed to a lot of quality research in diverse