Abstract
Closeness centrality is an important concept in social network analysis. In a graph representing a social network, closeness centrality measures how close a vertex is to all other vertices in the graph. In this paper, we combine existing methods on calculating exact values and approximate values of closeness centrality and present new algorithms to rank the top-k vertices with the highest closeness centrality. We show that under certain conditions, our algorithm is more efficient than the algorithm that calculates the closeness-centralities of all vertices.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Approximation Algorithm
- Betweenness Centrality
- Exact Algorithm
- Closeness Centrality
- Eigenvector Centrality
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bader, D.A., Kintali, S., Madduri, K., Mihail, M.: Approximating Betweenness Centrality. In: The 5th Workshop on Algorithms and Models for the Web-Graph, pp. 124–137 (2007)
Bavelas, A.: Communication patterns in task-oriented groups. The Journal of the Acoustical Society of America 22(6), 725–730 (1950)
Beauchamp, M.A.: An improved index of centrality. Behavioral Science 10(2), 161–163 (1965)
Brandes, U.: Faster Evaluation of Shortest-Path Based Centrality Indices. Konstanzer Schriften in Mathematik und Informatik 120 (2000)
Brandes, U., Pich, C.: Centrality Estimation in Large Networks. Intl. Journal of Bifurcation and Chaos in Applied Sciences and Engineering 17(7), 2303–2318
Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30, 107–117 (1998)
Costenbader, E., Valente, T.W.: The stability of centrality measures when networks are sampled. Social Networks 25, 283–307 (2003)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Elmacioglu, E., Lee, D.: On six degrees of separation in DBLP-DB and more. ACM SIGMOD Record 34(2), 33–40 (2005)
Eppstein, D., Wang, J.: Fast Approximation of Centrality. Journal of Graph Algorithms and Applications 8, 39–45 (2004)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596–615 (1987)
Freeman, L.C.: Centrality in social networks conceptual clarification. Social Networks 1(3), 215–239 (1978/79)
Geisberger, R., Sanders, P., Schultes, D.: Better Approximation of Betweenness Centrality. In: Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX 2008), pp. 90–100. SIAM, Philadelphia (2008)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the ACM 58(1), 13–30 (1963)
Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24(1), 1–13 (1977)
Koschutzki, D., Lehmann, K.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. Network Analysis, 16–61 (2005)
Newman, M.E.J.: Coauthorship networks and patterns of scientific collaboration. Proceedings of the National Academy of Sciences 101, 5200–5205 (2004)
Newman, M.E.J.: Who is the best connected scientist? A study of scientific coauthorship networks. Complex Networks, 337–370 (2004)
Newman, M.E.J., Park, J.: Why social networks are different from other types of networks. Physical Review E 68, 036122 (2003)
Potterat, J.J., Phillips-Plummer, L., Muth, S.Q., Rothenberg, R.B., Woodhouse, D.E., Maldonado-Long, T.S., Zimmerman, H.P., Muth, J.B.: Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. Sexually Transmitted Infections 78, i159–i163 (2002)
Sabidussi, G.: The centrality index of a graph. Psychometrika 31(4), 581–603 (1966)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okamoto, K., Chen, W., Li, XY. (2008). Ranking of Closeness Centrality for Large-Scale Social Networks. In: Preparata, F.P., Wu, X., Yin, J. (eds) Frontiers in Algorithmics. FAW 2008. Lecture Notes in Computer Science, vol 5059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69311-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-69311-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69310-9
Online ISBN: 978-3-540-69311-6
eBook Packages: Computer ScienceComputer Science (R0)