Abstract
With the increase in popularity of the social networks, it has become a perennial source of data analytics to mining the abundant information in real-world networks. As the social network is heterogeneous, some of its entities like nodes and edges may be more influential than other entities. It is observed that identification of the most influential entities in large-scale networks has many real-time applications like social network analysis, fraud detection, community detection, traffic control of the transportation network, software-defined network, and many more. Several centrality measures exist to identify the importance of a node in the network. However, betweenness centrality is found to be the most promising one, to investigate a network and the importance of nodes in the network. In the era of big data, the size of the social network is increasing exponentially. Although a number of algorithms exist for identifying betweenness centrality for large-scale networks, very few algorithms attempt to identify the influential nodes in a dynamic network. A single insertion or deletion of a node or edge may drastically change the structure of the network, which limits the performance of algorithms in terms of computational efficiency. In order to accommodate this problem, in this paper, a MapReduce-based incremental parallel algorithm for exploring the influential nodes based on betweenness centrality is proposed. The proposed algorithm is compared with a few other algorithms that are used to compute betweenness centrality in a dynamic network. The major advantage of the proposed algorithm is that it allows the network to be updated by the insertion of an edge. The effectiveness of the proposed algorithm has been critically examined in a distributed environment in terms of execution time by using both real-time and synthetic networks. The experimental results show a significant speedup over the other algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adamic LA, Huberman BA (2000) Power-law distribution of the worldwide web. Science 287(5461):2115–2115
Barabâsi A-L et al (2002) Evolution of the social network of scientific collaborations.". Phys A 311(3–4):590–614
Barthelemy M (2004) Betweenness centrality in large complex networks. Eur Phys J B 38(2):163–168
Behera RK, Rath SK (2016) An efficient modularity based algorithm for community detection in social network. IEEE, International conference on internet of things and applications (IOTA)
Behera RK, Rath SK, Jena M (2016) Spanning tree based community detection using min-max modularity. Procedia Computer Science 93:1070–1076
Borgatti SP, Everett MG (2006) A graph-theoretic perspective on centrality. Soc Netw 28(4):466–484
Brandes U (2001) A faster algorithm for betweenness centrality. J Math Soc 25(2):163–177
Cook DJ, Holder LB (eds) (2006) Mining graph data. Wiley, Hoboken
Das K, Samanta S, Pal M (2018) Study on centrality measures in social networks: a survey. Social Netw Anal Min 8(1):13
Email Network Dataset {KONECT} (2016) October 2016. https://konect.uni-koblenz.de/networks/arenas-email.
Facebook (Nips) Network Dataset {KONECT} (2016) October 2016. https://konect.uni-koblenz.de/networks/ego-facebook.
Fellman PV, Wright R (2014) Modeling terrorist networks, complex systems at the mid-range." arXiv preprint arXiv:1405.6989.
Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215–239
Green O, McColl R, Bader DA (2012) A fast algorithm for streaming betweenness centrality. In: 2012 international conference on privacy, security, risk and trust (PASSAT) and 2012 international conference on social computing (SocialCom). IEEE
Hamsterster Friendships Network Dataset {KONECT} (2016) October 2016. https://konect.uni-koblenz.de/networks/petster-friendships-hamster.
Holme P et al (2002) Attack vulnerability of complex networks. Phys Rev E 65(5):056109
Jamour F, Skiadopoulos S, Kalnis P (2018) Parallel algorithm for incremental betweenness centrality on large graphs. IEEE Trans Parallel Distrib Syst 29(3):659–672
Jazz Musicians Network Dataset {KONECT} (2016) October 2016. https://konect.uni-koblenz.de/networks/arenas-jazz.
Kas M et al (2013) 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. ACM
Khopkar SS, Nagi R, Nikolaev AG, Bhembre V (2014) Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis. Soc Netw Anal Min 4(1):220
Kourtellis N et al (2013) Identifying high betweenness centrality nodes in large social networks. Soc Netw Anal Min 3(4):899–914
Lee M-J et al (2012) Qube: a quick algorithm for updating betweenness centrality. In: Proceedings of the 21st international conference on World Wide Web. ACM
Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems
Liben-Nowell D, Balakrishnan H, Karger D (2002) Analysis of the evolution of peer-to-peer systems. In: Proceedings of the twenty-first annual symposium on principles of distributed computing. ACM
Mahyar H, Hasheminezhad R, Ghalebi E, Nazemian A, Grosu R, Movaghar A, Rabiee HR (2018) Identifying central nodes for information flow in social networks using compressive sensing. Soc Netw Anal Min 8(1):33
Nathan E, Bader DA (2018) Incrementally updating Katz centrality in dynamic graphs. Soc Netw Anal Min 8(1):26
Nasre M, Pontecorvi M, Ramachandran V (2014) Betweenness centrality–incremental and faster. In: International symposium on mathematical foundations of computer science. Springer, Berlin
Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256
Newman MEJ (2004) Analysis of weighted networks. Phys Rev E 70(5):056131
Newman MEJ (2005) A measure of betweenness centrality based on random walks. Soc Netw 27(1):39–54
Newman MEJ, Watts DJ, Strogatz SH (2002) Random graph models of social networks. Proc Natl Acad Sci 99(suppl 1):2566–2572
Newman ME, Barabási ALE, Watts DJ (2006) The structure and dynamics of networks. Princeton University Press
Ruhnau B (2000) Eigenvector-centrality—a node-centrality? Soc Netw 22(4):357–365
Sharan R, Ulitsky I, Shamir R (2007) Network-based prediction of protein function. Mol Syst Biol 3(1):88
Singh RR et al (2015) A faster algorithm to update betweenness centrality after node alteration. Internet Math 11(4–5):403–420
Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146–160
Zachary Karate Club Network Dataset {KONECT} (2016) October 2016. https://konect.uni-koblenz.de/networks/ucidata-zachary.
Acknowledgments
This work is partially supported by IIT (ISM) Dhanbad and National Institute of Technology Rourkela, Govt. of India. The authors would like to express their gratitude and heartiest thanks to the Department of Computer Science and Engineering, Indian Institute of Technology (ISM), Dhanbad, India, for providing their research support.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that there is no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Behera, R.K., Naik, D., Ramesh, D. et al. MR-IBC: MapReduce-based incremental betweenness centrality in large-scale complex networks. Soc. Netw. Anal. Min. 10, 25 (2020). https://doi.org/10.1007/s13278-020-00636-9
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13278-020-00636-9