Abstracts Category : Other

COMPUTING TOP-K CLOSENESS CENTRALITY IN UNWEIGHTEDUNDIRECTED GRAPHS REVISITED

by Ahmed Al-Baghdadi

Centrality indices are essential concepts in networkanalysis. Closeness centrality is the very popular and most widelyused centrality in the analysis of real-world complex networks.Closeness of a vertex is the inverse of the average distance toeach other vertex, it shows how important and influential thevertex is. In particular, the current best algorithm of selectingthe k most central vertices in unweighted undirected graphs isbased on the All-Pairs-Shortest-Path approach (in short, APSP).However, in practice finding the most k central vertices in adataset 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 theexact closeness centrality for all vertices, to save time, we cancut computation after finding the k vertices with the mostcloseness value. Bergamini et al. proposed a new algorithm forcomputing top-k ranking in unweighted graphs. Their work is basedon computing a lower bound on total distances of every vertex andstopping the search when k vertices already have lower totaldistances than the bounds computed for the other vertices. InBergamini et al. algorithm, the tightness of the boundsdramatically influences the algorithm performance. In this work,first, we propose a new method of computing lower bounds on totaldistances of vertices to replace the method of computing lowerbounds in Bergamini et al. algorithm. We achieve excellentimprovements through replacing the method of computing lower boundsin Bergamini et al. algorithm by our method of computing lowerbounds. In our experiments on real-world networks we show that ournew method of computing bounds combined with top-k rankingalgorithm of Bergamini et al. significantly improves computation offinding the k most closeness vertices over the APSP and Bergaminiet al. algorithm. Second, our method of computing lower bounds canbe used as an approximation algorithm for finding the median vertexin a graph; the median of a graph is a vertex with the highestcloseness centrality. We validate our approximation algorithmexperimentally on various datasets from different domains, such asbiology, social networks, collaboration networks,etc.Advisors/Committee Members: Dragan, Feodor (Advisor).