MDER: modified degree with exclusion ratio algorithm for influence maximisation in social networks
Tóm tắt
The online social network has become an integral part of our day to life and serves as an excellent platform for sharing ideas, opinions, and products. Influence maximization (IM) is a widely studied topic in the area of social network analysis. The objective of IM is to find influential nodes that can disseminate information to a larger extent in the network. Many local and global centrality measures are proposed to rank the nodes based on their spreading capability with certain limitations. Many proposed algorithms locate the spreaders sharing overlapping regions or are closely placed, which may cause interference in spreading. In this paper, based on the notion of maximum coverage of the information and minimum interference in spreading, we propose a novel semi-local algorithm named as modified degree centrality with exclusion ratio to identify influential nodes from diverse locations in the network. We use modified degree centrality by considering neighbours upto 2-hops and introduce the novel idea of exclusion ratio to ensure minimum overlapping between regions influenced by the chosen spreader nodes. Extensive experimental validation using classical information diffusion model demonstrates that the proposed method delivers better results in comparison to many popular contemporary methods of influence maximization.
Tài liệu tham khảo
Heidemann J, Klier M, Probst F (2012) Online social networks: a survey of a global phenomenon. Comput Netw 56(18):3866–3878
Krasnova H, Spiekermann S, Koroleva K, Hildebrand T (2010) Online social networks: why we disclose. J Inf Technol 25(2):109–125
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp 137–146
Li Y, Fan J, Wang Y, Tan KL (2018) Influence maximization on social graphs: a survey. IEEE Trans Knowl Data Eng 30(10):1852–72
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66
Vega-Oliveros DA, da Fontoura CL, Rodrigues FA (2020) Influence maximization by rumor spreading on correlated networks through community identification. Commun Nonlinear Sci Numer Simul 83:105094
Kumar S, Panda BS, Aggarwal D (2020) Community detection in complex networks using network embedding and gravitational search algorithm. J Intell Inf Syst. https://doi.org/10.1007/s10844-020-00625-6
Oueslati W, Arrami S, Dhouioui Z, Massaabi M (2021) Opinion leaders’ detection in dynamic social networks. Concurr Comput Pract Exp 33(1):e5692. https://doi.org/10.1002/cpe.5692
Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215–39
Okamoto K, Chen W, Li XY (2008) Ranking of closeness centrality for large-scale social networks. In: International workshop on frontiers in algorithmics. Springer, Berlin, Heidelberg, pp 186–195
Bonacich P (2007) Some unique properties of eigenvector centrality. Soc Netw 29(4):555–64
Brin S, Page L (2012) Reprint of: The anatomy of a large-scale hypertextual web search engine. Comput Netw 56(18):3825–33
Cheng S, Shen H, Huang J, Zhang G, Cheng X (2013) Staticgreedy: solving the scalability–accuracy dilemma in influence maximization. In: Proceedings of the 22nd ACM international conference on information & knowledge management, pp 509–518
Goyal A, Lu W, Lakshmanan LV (2011) Celf++ optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on World wide web, pp 47–48
Huang H, Shen H, Meng Z (2020) Community-based influence maximization in attributed networks. Appl Intell 50(2):354–64
Kumar S, Singhla L, Jindal K, Grover K, Panda BS (2021) IM-ELPR: Influence maximization in social networks using label propagation based community structure. Appl Intell. https://doi.org/10.1007/s10489-021-02266-w
Satsuma J, Willox R, Ramani A, Grammaticos B, Carstea AS (2004) Extending the SIR epidemic model. Phys A Stat Mech Appl 336(3–4):369–75
Goldenberg J, Libai B, Muller E (2001) Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata. Acad Mark Sci Rev 9(3):1–8
Murase Y, Jo HH, Török J, Kertész J, Kaski K (2019) Structural transition in social networks: the role of homophily. Sci Rep 9(1):1–8
Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 35–41. https://doi.org/10.2307/3033543
Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys 6(11):888–93
Ma LL, Ma C, Zhang HF, Wang BH (2016) Identifying influential spreaders in complex networks based on gravity formula. Phys A Stat Mech Appl 451:205–12
Lü L, Zhou T, Zhang QM, Stanley HE (2016) The H-index of a network node and its relation to degree and coreness. Nat Commun 7:10168
Sheikhahmadi A, Nematbakhsh MA, Shokrollahi A (2015) Improving detection of influential nodes in complex networks. Phys A Stat Mech Appl 436:833–845
Berahmand K, Bouyer A, Samadi N (2019) A new local and multidimensional ranking measure to detect spreaders in social networks. Computing 101(11):1711–33
Samadi N, Bouyer A (2019) Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks. Computing 101(8):1147–75
Rui X, Yang X, Fan J, Wang Z (2020) A neighbour scale fixed approach for influence maximization in social networks. Computing. 102(2):427–449. https://doi.org/10.1007/s00607-019-00778-5
Kumar S, Saini M, Goel M, Panda BS (2021) Modeling information diffusion in online social networks using a modified forest-fire model. J Intell Inf Syst 56(2):355–377
Hethcote HW (2000) The mathematics of infectious diseases. SIAM Rev 42:599–653
Watts DJ (2002) A simple model of global cascades on random networks. Proc Natl Acad Sci 99(9):5766–71
Yamasaki K, Matia K, Buldyrev SV, Fu D, Pammolli F, Riccaboni M, Stanley HE (2006) Preferential attachment and growth dynamics in complex systems. Phys Rev E 74(3):035103
Leskovec J, Krevl A, SNAP Datasets (2014) Stanford large network dataset collection, vol 2016, p 49. http://snap.stanford.edu/data
Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD) 1(1):2-es
Rozemberczki B, Allen C, Sarkar R (2019) Multi-scale attributed node embedding. arXiv preprint arXiv:1909.13021
Boguná M, Pastor-Satorras R, Díaz-Guilera A, Arenas A (2004) Models of social networks based on social distance attachment. Phys Rev E 70(5):056122
Cho E, Myers SA, Leskovec J (2011) Friendship and mobility: friendship and mobility: user movement in location-based social networks. In: ACM SIGKDD international conference on knowledge discovery and data mining (KDD)
McAuley JJ, Leskovec J (2012) Learning to discover social circles in ego networks. In: NIPS, vol 2012, pp 548–556