Estimating Reachability Set Sizes in Dynamic Graphs

Back

Student
Aji, Sudarshan Mandayam
Degree
MS
Defense date
2014-07-01
Department
Computer Science and Applications
Commitee
Vullikanti, Anil Kumar S., Chair
Marathe, Madhav V., Member
Bisset, Keith R, Member
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.
ETD Page
http://hdl.handle.net/10919/49262

Back