k-Centralities: local approximations of global measures based on shortest paths

ABSTRACT

A lot of centrality measures have been developed to analyze different aspects of importance. Some of the most popular centrality measures (e.g. betweenness centrality, closeness centrality) are based on the calculation of shortest paths. This characteristic limits the applicability of these measures for larger networks. In this article we elaborate on the idea of bounded-distance shortest paths calculations. We claim criteria for k-centrality measures and we introduce one algorithm for calculating both betweenness and closeness based centralities. We also present normalizations for these measures. We show that k-centrality measures are good approximations for the corresponding centrality measures by achieving a tremendous gain of calculation time and also having linear calculation complexity O(n) for networks with constant average degree. This allows researchers to approximate centrality measures based on shortest paths for networks with millions of nodes or with high frequency in dynamically changing networks.

References

1. Anthonisse, J. M. 1971. The rush in a directed graph, Technical Report BN 9/71, Stichting Mathematisch Centrum, Amsterdam, Netherlands.
2. Bader, D. A., and Madduri, K. 2006. Parallel algorithms for evaluating centrality indices in real-world networks. Proceedings of the ICPP 2006 - International Conference on Parallel Processing , 539--550.
3. Barabási, A. L., and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509 - 512.
4. Batagelji, V., Börner, K., Brandes, U., Hong, S.H., Johnson, J., Krempel, L., Mrvar, A., Pfeffer, J., and Quan, W. 2007. Visualization and analysis of Wikipedia. Viszards-Session at the Sunbelt XXVII Conference.
5. Batagelj, V., Kej ar, N., Korenjak-Cerne, S., and Zaveranik, M. 2006. Analyzing the structure of U.S. patents network. Data science and classification, eds. V. Batagelj, H.-H. Bock, A. Ferligoj, A. Iberna, Springer, Berlin.
6. Bavelas, A. 1948. A mathematical model for group structure. Human Organization 7, 16--30.
7. Beauchamp, M. A. 1965. An improved index of centrality. Behavioral Science 10, 161--163.
8. Bonacich, P. 1972. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology 2, 113--120.
9. Borgatti, S. P., Everett, M.G., and Freeman, L.C. 2002. Ucinet 6 for Windows, Analytic Technologies, Cambridge, MA, USA.
10. Borgatti, S. P. 2005. Centrality and network flow. Social Networks 27, 55--71.
11. Borgatti, S. P., and Everett, M.G. 2006. A graph-theoretic perspective on centrality. Social Networks 28, 466--484.
12. Brandes, U. 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 2, 163--177.
13. Brandes, U., and Pich, C. 2007. Centrality estimation in large networks. International Journal of Bifurcation and Chaos 17, 7, 2303--2318.
14. Brandes, U. 2008. On variants of shortest-path betweenness centrality and their generic computation. Social Networks 30, 136--145.
15. Burt, R. S. 2005. Brokerage and Closure: An introduction to social capital, Oxford University Press, New York, NY, USA.
16. Carley, K. M. 1999. On the evolution of social and organizational networks. Special issue of Research in the Sociology of Organizations, eds. S.B. Andrews, D. Knoke, JAI Press, Greenwhich, CT, USA.
17. Carpenter, T., Karakostas, G., and Shallcross, D. 2002. Practical issues and algorithms for analyzing terrorist networks. Invited Paper: Western Multi-Conference (WMC 2002)..
18. Chan, S. Y., Leung, I.X.Y., and Liò, P. 2009. Fast centrality approximation in modular networks. Proceeding of the 1st ACM international workshop on Complex networks meet information & knowledge management (CNIKM '09) , 31--38.
19. Chase, I. D. 1982. Dynamics of hierarchy formation: The sequential development of dominance relationships. Behaviour 80, 218--240.
20. Demetrescu, C., and Italiano, G. 2001. Fully dynamic all pairs shortest paths with real edge weights. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science , 260--267.
21. Denoyer, L., and Gallinari, P. 2006. The Wikipedia XML corpus, http://www-connex.lip6.fr/ denoyer/Wikipedia XML/ {6/2/2011}.
22. Eppstein, D., and Wang, J. 2004. Fast approximation of centrality. Journal of Graph Algorithms and Applications 8, 1, 39--45.
23. Ercsey-Ravasz, M., and Toroczkai, Z. 2010. Centrality scaling in large networks. Phys. Rev. Lett. 105, 038701.
24. Erdos, P., and Renyi, A. 1959. On random graphs. Publ. Math., Debrecen 6, 290--297.
25. Everett, M. G., and Borgatti, S. P. 2005. Ego network betweenness. Social Networks 27, 31--38.
26. Freeman, L. C. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 35--41.
27. Freeman, L. C. 1979. Centrality in social networks: Conceptual clarification. Social Networks 1, 215--239.
28. Hamill, L., and Gilbert, N. 2009. Social Circles: A Simple Structure for Agent-Based Social Network Models. Journal of Artificial Societies and Social Simulation 12, 2.
29. Kleinberg, J. 1999. Authoritative sources in a hyperlinked environment. ACM 46, 604--632.
30. Leavitt, H. J. 1951. Some effects of certain communication patterns on group performance. Journal of Abnormal and Social Psychology 46, 38--50.
31. Leskovec, J., Huttenlocher, D., and Kleinberg, J. 2010. Governance in social media: A case study of the Wikipedia promotion process. AAAI International Conference on Weblogs and Social Media (ICWSM '10).
32. Newcomb, T. N. 1961. The acquaintance process, Holt, Rinehart and Winston, New York, NY, USA.
33. Newman, M. E. J. 2001. The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA 98, 404--409.
34. Okamoto, K., Chen, W., and Li, X.-Y. 2008. Ranking of Closeness Centrality for Large-Scale Social Networks. Proceedings of the 2nd annual international workshop on Frontiers in Algorithmics (FAW '08), 186--195.
35. Onnela, J. P., Saramäki, J., Hyvönen, J., Szabó, G., de Menezes, M. A., Kaski, K., Barabási, A. L., and Kertész, J. 2007. Analysis of a large-scale weighted network of one-to-one human communication. New Journal of Physics 9.
36. Palinkas, L. A., Johnson, J. C., Boster, J. S., and Houseal, M. 1998. Longitudinal studies of behavior and performance during a winter at the south pole. Aviation, Space, and Environmental Medicine 179, 73--77.
37. Sabidussi, G. 1966. The centrality index of a graph. Psychometrika 69, 581--603.
38. Sade, D. S. 1989. Sociometrics of macaca mulatta III: N-path centrality in grooming networks. Social Networks 31, 273--292.
39. Sampson, S. F. 1968. A novitiate in a period of change. An experimental and case study of social relationships, PhD Thesis, Cornell University, NY, USA.
40. Sedgewick, R. 2011. Algorithms. 4th Edition, Addison-Wesley, Reading, MA, USA.
41. Shimbel, A. 1953. Structural parameters of communication networks. Bulletin of Mathematical Biophysics , 501--507.
42. Stephenson, K. A. and Zelen, M. 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1--37.
43. Wasserman, S., and Faust, K. 1995. Social Network Analysis, Methods and Applications, Cambridge University Press, Cambridge, UK.
44. Watts, D., and Strogatz, S. 1998. Collective dynamics of small world networks. Nature 393, 440--442.
45. Yang, J., and Leskovec., J. 2011. Temporal variation in online media. ACM International Conference on Web Search and Data Mining (WSDM '11) 15.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory