Abstract
Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive to exactly determine betweenness; currently the fastest-known algorithm by Brandes requires O(nm) time for unweighted graphs and O(nm + n 2logn) time for weighted graphs, where n is the number of vertices and m is the number of edges in the network. These are also the worst-case time bounds for computing the betweenness score of a single vertex. In this paper, we present a novel approximation algorithm for computing betweenness centrality of a given vertex, for both weighted and unweighted graphs. Our approximation algorithm is based on an adaptive sampling technique that significantly reduces the number of single-source shortest path computations for vertices with high centrality. We conduct an extensive experimental study on real-world graph instances, and observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Sabidussi, G.: The centrality index of a graph. Psychometrika 31, 581–603 (1966)
Shimbel, A.: Structural parameters of communication networks. Bulletin of Mathematical Biophysics 15, 501–507 (1953)
Freeman, L.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)
Anthonisse, J.: The rush in a directed graph. In: Report BN9/71, Stichting Mathematisch Centrum, Amsterdam, Netherlands (1971)
Jeong, H., Mason, S., Barabási, A.L., Oltvai, Z.: Lethality and centrality in protein networks. Nature 411, 41–42 (2001)
Pinney, J., McConkey, G., Westhead, D.: Decomposition of biological networks using betweenness centrality. In: McLysaght, A., Huson, D.H. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3678, Springer, Heidelberg (2005)
del Sol, A., Fujihashi, H., O’Meara, P.: Topology of small-world networks of protein-protein complex structures. Bioinformatics 21(8), 1311–1315 (2005)
Liljeros, F., Edling, C., Amaral, L., Stanley, H., Åberg, Y.: The web of human sexual contacts. Nature 411, 907–908 (2001)
Krebs, V.: Mapping networks of terrorist cells. Connections 24(3), 43–52 (2002)
Coffman, T., Greenblatt, S., Marcus, S.: Graph-based technologies for intelligence analysis. Communications of the ACM 47(3), 45–47 (2004)
Buckley, N., van Alstyne, M.: Does email make white collar workers more productive? Technical report, University of Michigan (2004)
Cisic, D., Kesic, B., Jakomin, L.: Research of the power in the supply chain. In: International Trade, Economics Working Paper Archive EconWPA (April 2000)
Newman, M.: The structure and function of complex networks. SIAM Review 45(2), 167–256 (2003)
Girvan, M., Newman, M.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences, USA 99(12), 7821–7826 (2002)
Brandes, U.: A faster algorithm for betweenness centrality. J. Mathematical Sociology 25(2), 163–177 (2001)
Bader, D., Madduri, K.: Parallel algorithms for evaluating centrality indices in real-world networks. In: ICPP. Proc. 35th Int’l Conf. on Parallel Processing, Columbus, OH, IEEE Computer Society, Los Alamitos (2006)
Eppstein, D., Wang, J.: Fast approximation of centrality. In: SODA 2001. Proc. 12th Ann. Symp. Discrete Algorithms, Washington, DC, pp. 228–229 (2001)
Brandes, U., Pich, C.: Centrality estimation in large networks. In: To appear in Intl. Journal of Bifurcation and Chaos, Special Issue on Complex Networks’ Structure and Dynamics (2007)
Lipton, R., Naughton, J.: Estimating the size of generalized transitive closures. In: VLDB, pp. 165–171 (1989)
Madduri, K., Bader, D.: Small-world Network Analysis in Parallel: a toolkit for centrality analysis (2007), http://www.cc.gatech.edu/~kamesh
Madduri, K., Bader, D.: GTgraph: A suite of synthetic graph generators (2006), http://www.cc.gatech.edu/~kamesh/GTgraph
Barabási, A.L.: Network databases (2007), http://www.nd.edu/~networks/resources.htm
Bader, D., Madduri, K.: A graph-theoretic analysis of the human protein interaction network using multicore parallel algorithms. In: HiCOMB 2007. Proc. 6th Workshop on High Performance Computational Biology, Long Beach, CA (March 2007)
Davis, T.: University of Florida Sparse Matrix Collection (2007), http://www.cise.ufl.edu/research/sparse/matrices
Batagelj, V., Mrvar, A.: PAJEK datasets (2006), http://www.vlado.fmf.uni-lj.si/pub/networks/data/
Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS implementation challenge – Shortest Paths (2006), http://www.dis.uniroma1.it/~challenge9/
Erdős, P., Rényi, A.: On random graphs I. Publicationes Mathematicae 6, 290–297 (1959)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Peri, S., et al.: Development of human protein reference database as an initial platform for approaching systems biology in humans. Genome Research 13, 2363–2371 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bader, D.A., Kintali, S., Madduri, K., Mihail, M. (2007). Approximating Betweenness Centrality. In: Bonato, A., Chung, F.R.K. (eds) Algorithms and Models for the Web-Graph. WAW 2007. Lecture Notes in Computer Science, vol 4863. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77004-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-77004-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77003-9
Online ISBN: 978-3-540-77004-6
eBook Packages: Computer ScienceComputer Science (R0)