Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Thesis.pdf (1.42 MB)

ETD Abstract Container

Abstract Header

COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED

Al-Baghdadi, Ahmed
http://rave.ohiolink.edu/etdc/view?acc_num=kent1492421540217573

Abstract Details

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.
Computer Science

Recommended Citations

Citations

  • Al-Baghdadi, A. (2017). COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED [Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1492421540217573

    APA Style (7th edition)

  • Al-Baghdadi, Ahmed. COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED. 2017. Kent State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1492421540217573.

    MLA Style (8th edition)

  • Al-Baghdadi, Ahmed. "COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTED UNDIRECTED GRAPHS REVISITED." Master's thesis, Kent State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1492421540217573

    Chicago Manual of Style (17th edition)

kent1492421540217573
412
© 2017, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.