Back to search

Georgia Institute of Technology

Numerical and streaming analyses of centrality measures on graphs

Abstract

dc:description.abstract

Graph data represent information about entities (vertices) and the relationships or connections between them (edges). In real-world networks today, new data are constantly being produced, leading to the notion of dynamic graphs. When analyzing large graphs, a common problem of interest is to identify the most important vertices in a graph, which can be done using centrality metrics. This dissertation presents novel advances in the field of graph analysis by providing numerical and streaming techniques that help us better understand how to compute centrality measures. Several centrality measures are calculated by solving a linear system but since these linear systems are large, iterative solvers are often used as an alternate method to approximate the solution. We relate the two research areas of numerical accuracy and data mining by understanding how the error in a solver affects the relative ranking of vertices in a graph. To calculate the centrality values of vertices in a dynamic graph, the most naive method is to recompute the scores from scratch every time the graph is changed, but as the graph size grows larger this recomputation is computationally infeasible. We present four dynamic algorithms for updating different centrality metrics in evolving networks. All dynamic algorithms are faster than their static counterparts while maintaining good quality of the centrality scores. This dissertation concludes by applying methods discussed for the computation of centrality metrics to community detection, and we present a new algorithm for identifying local communities in a dynamic graph using personalized centrality.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computational Science and Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nathan, Eisha
Advisor dc:contributor.advisor
  • Bader, David A.
Committee members dc:contributor.committeemember
  • Aluru, Srinivas
  • Catalyurek, Umit
  • Dilkina, Bistra
  • Riedy, Jason
  • Sanders, Geoffrey

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/59871

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nathan, Eisha. Numerical and streaming analyses of centrality measures on graphs. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/59871