Influence Maximization in Online Social Networks Using Community Structures

Naima Bashir; Dr. Ashish Oberoi

doi:10.55524/ijirem.2022.9.5.16

Abstract

Online social networks (OSNs) have dominated modern life on a global scale. The immense popularity of online social networks increases day by day as they help us in modelling various types of processes like viral marketing, rumor controlling, collaborative filtering, market prediction and controlling diseases spread. In the realm of complex networks research, influence maximisation in social networks has long been a challenging task. Influence maximisation is the method of identifying k-seed nodes or influential nodes in order to increase overall influence in a network. Ranking the nodes using network node-centrality metrics is one of the conventional techniques for finding prominent nodes in a social network. However, estimating global centrality metrics like betweenness centrality is computationally exhaustive and typically not scalable for very large size networks such as a country's whole population. In this paper, we provide a novel approach for extracting communities from the underlying social network to identify prominent nodes aka "influential nodes”. Experimental results indicate that the seed nodes identified by the proposed approach have high betweenness centrality in the social network thus rendering the proposed approach significant.

Keywords

Information Diffusion, Influence maximisation, Centrality Measures, Betweenness Centrality, Community Structures.

References

A. Guille, H. Hacid, C. Favre, and D. A. Zighed, “Information diffusion in online social networks: A survey,” SIGMOD Rec, vol. 42, no. 2, 2013, doi: 10.1145/2503792.2503797.
D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” Theory of Computing, vol. 11, 2015, doi: 10.4086/toc.2015.v011a004.
B. Wilder, N. Immorlica, E. Rice, and M. Tambe, “Maximizing influence in an unknown social network,” 2018. doi: 10.1609/aaai.v32i1.11585.
Y. Zhao, S. Li, and F. Jin, “Identification of influential nodes in social networks with community structure based on label propagation,” Neurocomputing, vol. 210, 2016, doi: 10.1016/j.neucom.2015.11.125.
J. Dong, F. Ye, W. Chen, and J. Wu, “Identifying Influential Nodes in Complex Networks via Semi-Local Centrality,” in Proceedings - IEEE International Symposium on Circuits and Systems, 2018, vol. 2018-May. doi: 10.1109/ISCAS.2018.8351889.
A. Namtirtha, A. Dutta, and B. Dutta, “Weighted kshell degree neighborhood: A new method for identifying the influential spreaders from a variety of complex network connectivity structures,” Expert Syst Appl, vol. 139, 2020, doi: 10.1016/j.eswa.2019.112859.
B. Adamcsek, G. Palla, I. J. Farkas, I. Derényi, and T. Vicsek, “CFinder: Locating cliques and overlapping modules in biological networks,” Bioinformatics, vol. 22, no. 8, 2006, doi: 10.1093/bioinformatics/btl039.
J. Xie, S. Kelley, and B. K. Szymanski, “Overlapping community detection in networks: The state-of-the-art and comparative study,” ACM Comput Surv, vol. 45, no. 4, 2013, doi: 10.1145/2501654.2501657.
U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys Rev E Stat Nonlin Soft Matter Phys, vol. 76, no. 3, 2007, doi: 10.1103/PhysRevE.76.036106.
J. Xie, B. K. Szymanski, and X. Liu, “SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process,” 2011. doi: 10.1109/ICDMW.2011.154.
M. Coscia, G. Rossetti, F. Giannotti, and D. Pedreschi, “DEMON: A local-first discovery method for overlapping communities,” 2012. doi: 10.1145/2339530.2339630.
N. P. Nguyen, T. N. Dinh, S. Tokala, and M. T. Thai, “Overlapping communities in dynamic networks: Their detection and mobile applications,” 2011. doi: 10.1145/2030613.2030624.

Cites this article as

N. Bashir, D. A. Oberoi, "Influence Maximization in Online Social Networks Using Community Structures", International Journal of Innovative Research in Engineering & Management (IJIREM), Vol-9, Issue-5, Page No-113-118, 2022. Available from: https://doi.org/10.55524/ijirem.2022.9.5.16