Estimating Reachability Set Sizes in Dynamic Graphs
| dc.contributor.author | Aji, Sudarshan Mandayam | en |
| dc.contributor.committeechair | Vullikanti, Anil Kumar S. | en |
| dc.contributor.committeemember | Marathe, Madhav Vishnu | en |
| dc.contributor.committeemember | Bisset, Keith R. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2014-07-02T08:01:01Z | en |
| dc.date.available | 2014-07-02T08:01:01Z | en |
| dc.date.issued | 2014-07-01 | en |
| dc.description.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. | en |
| dc.description.degree | Master of Science | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:3077 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/49262 | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | Algorithm | en |
| dc.subject | Dynamic graphs | en |
| dc.subject | Giraph | en |
| dc.subject | Graph framework | en |
| dc.title | Estimating Reachability Set Sizes in Dynamic Graphs | en |
| dc.type | Thesis | en |
| thesis.degree.discipline | Computer Science and Applications | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | masters | en |
| thesis.degree.name | Master of Science | en |
Files
Original bundle
1 - 1 of 1