Identification of influential users in social media network using golden ratio optimization method
Abstract
A significant challenge in viral marketing is the efficient identification of a group of influential users within a given network, maximizing the spread of influence, known as influence maximization (IM). Numerous strategies have been put forth to gauge users’ influence and pinpoint influential user sets within social networks. These include greedy, heuristic, etc. However, using greedy algorithms to solve the IM problem is not ideal, as they are time-consuming and lack of scalability when dealing with large-scale networks. While heuristic-based approaches offer practical efficiency, they lack theoretical guarantees. To address these challenges, this work uses approach called metaheuristic–Golden ratio optimization method (GROM-IM) for optimizing the IM problem. In addition, our methodology incorporates the expected diffusion value function, which provides a reliable estimate of expected influence spread under both linear threshold and independent cascade models. This method selects the most effective nodes. The outcomes from experiments conducted on five actual social networks demonstrate that the proposed algorithm outperforms the base algorithm in terms of both efficiency and the extent of influence spread.
References
[1]
Aghaee Z and Kianian S Efficient influence spread estimation for influence maximization Soc Netw Anal Min 2020 10 1 81
[2]
Biswas TK, Abbasi A, and Chakrabortty RK A two-stage VIKOR assisted multi-operator differential evolution approach for Influence Maximization in social networks Expert Syst Appl 2022 192 116342
[3]
Bouyer A, Ahmadi Beni H, Arasteh B, Aghaee Z, and Ghanbarzadeh R FIP: a fast overlapping community-based influence maximization algorithm using probability coefficient of global diffusion in social networks Expert Syst Appl 2023 213 118869
[4]
Chatterjee B, Bhattacharyya T, Ghosh KK, Chatterjee A, and Sarkar R A novel meta-heuristic approach for influence maximization in social networks Expert Syst 2023 40 4
[5]
Chen W, Wang Y, Yang S (2009a) Efficient influence maximization in social networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 199–207.
[6]
Chen W, Wang Y, Yang S (2009b) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, in KDD ’09. New York, NY, USA: Association for Computing Machinery, pp. 199–208.
[7]
Chen W, Wang C, Wang Y (2010a) Scalable influence maximization for prevalent viral marketing in large-scale social networks,” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, in KDD ’10. New York, NY, USA: Association for Computing Machinery, pp. 1029–1038.
[8]
Chen W, Yuan Y, Zhang L (2010b) Scalable influence maximization in social networks under the linear threshold model. In: Proc. - IEEE Int. Conf. Data Mining, ICDM, pp. 88–97.
[9]
Cheng S, Shen H, Huang J, Zhang G, Cheng X (2013) StaticGreedy: solving the scalability-accuracy dilemma in influence maximization. Int. Conf. Inf. Knowl. Manag. Proc., no. March 2014, pp. 509–518.
[10]
Cheng S et al. Identification of influential users in social network using gray wolf optimization algorithm Phys A Stat Mech Appl 2020 142 1 112971
[11]
Cui L et al. DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks J Netw Comput Appl 2018 103 119-130
[12]
Derrac J, García S, Molina D, and Herrera F A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms Swarm Evol Comput 2011 1 1 3-18
[13]
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proc. Seventh ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 57–66.
[14]
Friedman M The use of ranks to avoid the assumption of normality implicit in the analysis of variance J Am Stat Assoc 1937 32 200 675-701
[15]
Gong H and Guo C Influence maximization considering fairness: a multi-objective optimization approach with prior knowledge Expert Syst Appl 2023 214 119138
[16]
Gong M, Song C, Duan C, Ma L, and Shen B An efficient memetic algorithm for influence maximization in social networks IEEE Comput Intell Mag 2016 11 3 22-33
[17]
Gong M, Yan J, Shen B, Ma L, and Cai Q Influence maximization in social networks based on discrete particle swarm optimization Inf Sci (NY) 2016 367–368 600-614
[18]
Goyal A, Lu W, Lakshmanan LVS (2011a) SIMPATH: An efficient algorithm for influence maximization under the Linear Threshold model. In: Proc. - IEEE Int. Conf. Data Mining, ICDM, pp. 211–220.
[19]
Goyal A, Lu W, Lakshmanan LVS (2011b) CELF++: optimizing the greedy algorithm for influence maximization in social networks. In: Proc. 20th Int. Conf. Companion World Wide Web, WWW 2011b, pp. 47–48.
[20]
Goyal A, Bonchi F, and Lakshmanan LVS A data-based approach to social influence maximization Proc VLDB Endow 2011 5 1 73-84
[21]
Guimerà R, Danon L, Díaz-Guilera A, Giralt F, and Arenas A Self-similar community structure in a network of human interactions Phys Rev E 2003 68 6 1-4
[22]
Jiang Q, Song G, Cong G, Wang Y, Si W, and Xie K Simulated annealing based influence maximization in social networks Proc Natl Conf Artif Intell 2011 1 127-132
[23]
Jung K, Heo W, Chen W (2012) IRIE: Scalable and robust influence maximization in social networks. In: Proc. - IEEE Int. Conf. Data Mining, ICDM, pp. 918–923,
[24]
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146.
[25]
Kim J, Kim SK, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks?. In: Proc. - Int. Conf. Data Eng., pp. 266–277.
[26]
Kimura M, Saito K (2006) Tractable models for information diffusion in social networks,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 4213 LNAI, pp. 259–271.
[27]
Kumar A, Singh SS, Singh K, and Biswas B Link prediction techniques, applications, and performance: a survey Phys A Stat Mech Appl 2020 553 124289
[28]
Kumar A, Mishra S, Singh SS, Singh K, and Biswas B Link prediction in complex networks based on significance of higher-order path index (SHOPI)” Phys A Stat Mech Appl 2020 545 123790
[29]
Lahiri M and Cebrian M The genetic algorithm as a general diffusion model for social networks Proc Natl Conf Artif Intell 2010 1 494-499
[30]
Lee J-R and Chung C-W A query approach for influence maximization on specific users in social networks IEEE Trans Knowl Data Eng 2015 27 2 340-353
[31]
Leskovec J, Krause A, Guestrin C, Faloutsos C, Vanbriesen J, Glance N (2007a) Cost-effective outbreak detection in networks. Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 420–429.
[32]
Leskovec J, Kleinberg J, and Faloutsos C Graph evolution: densification and shrinking diameters ACM Trans Knowl Discov Data 2007
[33]
Li D, Wang C, Zhang S, Zhou G, Chu D, and Wu C Positive influence maximization in signed social networks based on simulated annealing Neurocomputing 2017 260 69-78
[34]
Li WM, Li Z, Onjeniko AML, and Yang C Influence maximization algorithm based on Gaussian propagation model Inf Sci (NY) 2021 568 386-402
[35]
Nematollahi AF, Rahiminejad A, Vahidi B (2020) A novel meta-heuristic optimization method based on golden ratio in nature, vol. 24, no. 2. Springer Berlin, Heidelberg.
[36]
Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proc. ACM SIGMOD Int. Conf. Manag. Data, vol. 26-June-20, pp. 695–710.
[37]
Peng S, Zhou Y, Cao L, Yu S, Niu J, and Jia W Influence analysis in social networks: a survey J Netw Comput Appl 2018 106 17-32
[38]
Petard H A contribution to the mathematical theory of big game hunting Am Math Mon 1938 45 7 446
[39]
Rameshkumar K, Suresh RK, Mohanasundaram KM (2005) Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan. Lect. Notes Comput. Sci., vol. 3612, no. PART III, pp. 572–581.
[40]
Ripeanu M, Foster I, Iamnitchi A (2002) Mapping the Gnutella Network: Properties of Large- Scale Peer-to-Peer Systems and Implications for System Design. pp. 1–12. http://people.cs.uschicago.edu/~matei/PAPER/ic.pdf
[41]
Singh SS, Kumar A, Singh K, and Biswas B LAPSO-IM: a learning-based influence maximization approach for social networks Appl Soft Comput J 2019 82 105554
[42]
Singh SS, Kumar A, Singh K, and Biswas B C2IM: community based context-aware influence maximization in social networks Phys A Stat Mech Appl 2019 514 796-818
[43]
Singh SS, Singh K, Kumar A, and Biswas B ACO-IM: maximizing influence in social networks using ant colony optimization Soft Comput 2020 24 13 10181-10203
[44]
Singh SS, Srivastva D, Verma M, and Singh J Influence maximization frameworks, performance, challenges and directions on social network: a theoretical study J King Saud Univ Comput Inf Sci 2022 34 9 7570-7603
[45]
Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, in SIGMOD ’14. New York, NY, USA: Association for Computing Machinery, pp. 75–86.
[46]
Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach.
[47]
Tang J et al. Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization Phys A Stat Mech Appl 2019 513 477-496
[48]
Tang J, Zhang R, Wang P, Zhao Z, Fan L, and Liu X A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks Knowledge-Based Syst 2020 187 104833
[49]
Tang J, Zhang R, Wang P, Zhao Z, Fan L, and Liu X A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks Knowledge-Based Syst 2020
[50]
Venunath M, Sujatha P, and Koti P Buyya R, Hernandez SM, Kovvur RMR, and Sarma TH Identifying Top-N Influential Nodes in Large Complex Networks Using Network Structure Computational Intelligence and Data Analytics 2023 Springer Nature Singapore Singapore 597-607
[51]
Venunath M, Sujatha P, Koti P, Dharavath S (2023b) Influence maximization and online social capital for entrepreneurs: leveraging social networks to achieve business goals. In: Social capital in the age of online networking: genesis, manifestations, and implications, IGI Global, pp. 128–145.
[52]
Venunath M, Sujatha P, Dharavath S, Natarajasivan D, and Koti P Efficient method for identifying prominent supplier in large-scale healthcare information networks in Medicare Soft Comput 2023
[53]
Wang Y, Feng X (2009) A potential-based node selection strategy for influence maximization in a social network. Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5678 LNAI, pp. 350–361.
[54]
Wang C, Chen W, and Wang Y Scalable influence maximization for independent cascade model in large-scale social networks Data Min Knowl Discov 2012 25 3 545-576
[55]
Wang X, Zhang Y, Zhang W, and Lin X Efficient distance-aware influence maximization in geo-social networks IEEE Trans Knowl Data Eng 2017 29 3 599-612
[56]
Wu L et al. Modeling the evolution of users’ preferences and social links in social networking services IEEE Trans Knowl Data Eng 2017 29 6 1240-1253
[57]
Xie M, Zhan XX, Liu C, and Zhang ZK An efficient adaptive degree-based heuristic algorithm for influence maximization in hypergraphs Inf Process Manag 2023
[58]
Yang W, Brenner L, Giua A (2018) Influence maximization by link activation in social networks. In: 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA), pp. 1248–1251.
[59]
Yu Wang KX, Cong G, Song G (2010) Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks Categories and Subject Descriptors. In: Proc. 16th ACM SIGKDD Int. Conf. Knowl. Discov. data Min., pp. 1039–1048
[60]
Zhan Q, Zhang J, Wang S, Yu PS, and Xie J Cao T, Lim E-P, Zhou Z-H, Ho T-B, Cheung D, and Motoda H Influence Maximization Across Partially Aligned Heterogenous Social Networks Advances in Knowledge Discovery and Data Mining 2015 Cham Springer International Publishing 58-69
[61]
Zhang JX, Chen DB, Dong Q, and Zhao ZD Identifying a set of influential spreaders in complex networks Sci Rep 2016 6 1-10
[62]
Zhang K, Du H, and Feldman MW Maximizing influence in a social network: improved results using a genetic algorithm Phys A Stat Mech Appl 2017 478 20-30
[63]
Zhu T, Wang B, Wu B, and Zhu C Maximizing the spread of influence ranking in social networks Inf Sci (NY) 2014 278 3 535-544
Index Terms
- Identification of influential users in social media network using golden ratio optimization method
Index terms have been assigned to the content through auto-classification.
Recommendations
Identification of influential users in social networks based on users’ interest
AbstractEver increasing popularity social networks has attracted many companies to use them for viral marketing. Identification of influential users for spreading news and marketing is a major challenge in viral marketing. In most of the ...
Scalable influence maximization for prevalent viral marketing in large-scale social networks
KDD '10: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningInfluence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence ...
Social media analytics: tracking, modeling and predicting the flow of information through networks
WWW '11: Proceedings of the 20th international conference companion on World wide webOnline social media represent a fundamental shift of how information is being produced, transferred and consumed. User generated content in the form of blog posts, comments, and tweets establishes a connection between the producers and the consumers of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 28 September 2023
Accepted: 06 September 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024