Abstract
dc:description.abstractGraphs 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- masters
- Discipline thesis:degree_discipline
- Computer Science and Applications
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Virginia Tech
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Aji, Sudarshan Mandayam
- Chair dc:contributor.committeechair
-
- Vullikanti, Anil Kumar S.
- Committee members dc:contributor.committeemember
-
- Marathe, Madhav Vishnu
- Bisset, Keith R.
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Licence dc:rights.uri
Identifiers
dc:identifier.*- Dc Identifier Other
- vt_gsexam:3077
- OAI identifier oai:identifier
- oai:vtechworks.lib.vt.edu:10919/49262