Abstract
Betweenness Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen wide and increasing applications across several disciplines of late. In conjunction with the big data problems, there came the need to analyze large complex networks. Exact computation of a node’s betweenness is a daunting task in the networks of large size. In this paper, we propose a non-uniform sampling method to estimate the betweenness of a node. We apply our approach to estimate a node’s betweenness in several synthetic and real world graphs. We compare our method with the available techniques in the literature and show that our method fares several times better than the currently known techniques. We further show that the accuracy of our algorithm gets better with the increase in size and density of the network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anthonisse, J.M.: The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde (BN 9/71), 1–10 (1971)
Bader, D.A., Kintali, S., Madduri, K., Mihail, M.: Approximating betweenness centrality. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 124–137. Springer, Heidelberg (2007)
Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Batagelj, V., Mrvar, A.: Pajek datasets (2006), http://vlado.fmf.uni-lj.si/pub/networks/data
Brandes, U.: A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25(2), 163–177 (2001)
Brandes, U., Erlebach, T. (eds.): Network Analysis. LNCS, vol. 3418. Springer, Heidelberg (2005)
Brandes, U., Pich, C.: Centrality estimation in large networks. International Journal of Bifurcation and Chaos 17(07), 2303–2318 (2007)
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., et al.: Topological structure analysis of the protein–protein interaction network in budding yeast. Nucleic Acids Research 31(9), 2443–2450 (2003)
Chehreghani, M.H.: An efficient algorithm for approximate betweenness centrality computation. The Computer Journal, page bxu003 (2014)
Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS) 38(1), 1 (2011)
Erdos, P., Renyi, A.: On random graphs i. Publ. Math. Debrecen 6, 290–297 (1959)
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)
Geisberger, R., Sanders, P., Schultes, D.: Better Approximation of Betweenness Centrality, ch. 8, pp. 90–100 (2008)
Gkorou, D., Pouwelse, J., Epema, D., Kielmann, T., van Kreveld, M., Niessen, W.: Efficient approximate computation of betweenness centrality. In: 16th Annual Conf. of the Advanced School for Computing and Imaging, ASCI 2010 (2010)
Goel, K., Singh, R.R., Iyengar, S., Sukrit: A faster algorithm to update betweenness centrality after node alteration. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 170–184. Springer, Heidelberg (2013)
Green, O., McColl, R., Bader, D.A.: A fast algorithm for streaming betweenness centrality. In: 2012 International Conference on Privacy, Security, Risk and Trust (PASSAT) and 2012 International Confernece on Social Computing (SocialCom), pp. 11–20 (September 2012)
Kas, M., Wachs, M., Carley, K.M., Carley, L.R.: Incremental algorithm for updating betweenness centrality in dynamically growing networks. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013, pp. 33–40. ACM, New York (2013)
Kintali, S.: Betweenness centrality: Algorithms and lower bounds. arXiv preprint arXiv:0809.1906 (2008)
Knuth, D.E.: The Stanford GraphBase: a platform for combinatorial computing, vol. 37. Addison-Wesley, Reading (1993)
Lee, M.-J., Lee, J., Park, J.Y., Choi, R.H., Chung, C.-W.: Qube: A quick algorithm for updating betweenness centrality. In: Proceedings of the 21st International Conference on World Wide Web, WWW 2012, pp. 351–360. ACM, New York (2012)
Leskovec, J.: Stanford large network dataset collection (2010)
Nasre, M., Pontecorvi, M., Ramachandran, V.: Betweenness centality–incremental and faster. arXiv preprint arXiv:1311.2147 (2013)
Newman, M.: Networks: An Introduction. Oxford University Press, Inc., New York (2010)
Riondato, M., Kornaropoulos, E.M.: Fast approximation of betweenness centrality through sampling. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, pp. 413–422. ACM (2014)
Sariyüce, A.E., Saule, E., Kaya, K., Çatalyürek, Ü.V.: Shattering and compressing networks for betweenness centrality. In: SIAM Data Mining Conference (SDM). SIAM (2013)
Taylor, P.J.: World city network: a global urban analysis. Psychology Press (2004)
Ulanowicz, R.E., DeAngelis, D.L.: Network analysis of trophic dynamics in south florida ecosystems. In: FY97: The Florida Bay Ecosystem, pp. 20688–20038 (1998)
Van Der Hofstad, R.: Random graphs and complex networks (2009), http://www.win.tue.nl/rhofstad/NotesRGCN.pdf
Wang, X.: Deciding on the type of the degree distribution of a graph (network) from traceroute-like measurements (2011)
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(6684), 440–442 (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Agarwal, M., Singh, R.R., Chaudhary, S., Iyengar, S.R.S. (2015). An Efficient Estimation of a Node’s Betweenness. In: Mangioni, G., Simini, F., Uzzo, S., Wang, D. (eds) Complex Networks VI. Studies in Computational Intelligence, vol 597. Springer, Cham. https://doi.org/10.1007/978-3-319-16112-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-16112-9_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16111-2
Online ISBN: 978-3-319-16112-9
eBook Packages: EngineeringEngineering (R0)