Search ETDs:
COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED

2017, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
Centrality indices are essential concepts in network analysis. Closeness centrality is the very popular and most widely used centrality in the analysis of real-world complex networks. Closeness of a vertex is the inverse of the average distance to each other vertex, it shows how important and influential the vertex is. In particular, the current best algorithm of selecting the k most central vertices in unweighted undirected graphs is based on the All-Pairs-Shortest-Path approach (in short, APSP). However, in practice finding the most k central vertices in a dataset is computationally intractable, even for sparse graphs, since it requires a quadratic running time in the worst case. Fortunately, in this problem we are not required to compute the exact closeness centrality for all vertices, to save time, we can cut computation after finding the k vertices with the most closeness value. Bergamini et al. proposed a new algorithm for computing top-k ranking in unweighted graphs. Their work is based on computing a lower bound on total distances of every vertex and stopping the search when k vertices already have lower total distances than the bounds computed for the other vertices. In Bergamini et al. algorithm, the tightness of the bounds dramatically influences the algorithm performance. In this work, first, we propose a new method of computing lower bounds on total distances of vertices to replace the method of computing lower bounds in Bergamini et al. algorithm. We achieve excellent improvements through replacing the method of computing lower bounds in Bergamini et al. algorithm by our method of computing lower bounds. In our experiments on real-world networks we show that our new method of computing bounds combined with top-k ranking algorithm of Bergamini et al. significantly improves computation of finding the k most closeness vertices over the APSP and Bergamini et al. algorithm. Second, our method of computing lower bounds can be used as an approximation algorithm for finding the median vertex in a graph; the median of a graph is a vertex with the highest closeness centrality. We validate our approximation algorithm experimentally on various datasets from different domains, such as biology, social networks, collaboration networks, etc.
Feodor Dragan, Prof (Advisor)
59 p.

Recommended Citations

Hide/Show APA Citation

Al-Baghdadi, A. (2017). COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Al-Baghdadi, Ahmed. "COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED." Electronic Thesis or Dissertation. Kent State University, 2017. OhioLINK Electronic Theses and Dissertations Center. 22 Nov 2017.

Hide/Show Chicago Citation

Al-Baghdadi, Ahmed "COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED." Electronic Thesis or Dissertation. Kent State University, 2017. https://etd.ohiolink.edu/

Files

Thesis.pdf (1.42 MB) View|Download