Influence Maximization Based on Backward Reasoning in Online Social Networks
Abstract
:1. Introduction
2. Related Work
3. Methodology
3.1. Preliminaries
3.2. Proposed Method
3.2.1. Evaluate the Influence of Node Based on Maximum Likelihood Estimation
Algorithm 1 Calculate the influence cardinality based on message-passing |
Input: An online social network |
Output: Influence Cardinality of nodes in |
1: //Find out the largest connectivity subgraph . |
2: //Choose a node as the seed node and change to BFS tree graph with as root. |
3: for in do |
4: if is a leaf then |
5: |
6: |
7: else |
8: if is root then |
9: |
10: else |
11: |
12: |
13: |
14: end if |
15: end if |
16: end for |
3.2.2. Select Seed Nodes Based on Strategy
Algorithm 2 Construction of seed set based on greedy strategy |
Input: The BFS tree subgraph of an online social network , the size of seed nodes set |
Output: the set of seed nodes |
1: while do |
2: |
3: |
4: end while |
4. Experiments and Discussion
4.1. Experiment Setup
4.1.1. Dataset Description
4.1.2. Baseline Algorithms
4.1.3. Evaluation Measure
4.2. Result and Discussion
5. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
References
- Wang, F.; Wang, H.; Xu, K. Diffusive logistic model towards predicting information diffusion in online social networks. In Proceedings of the 32nd International Conference on Distributed Computing Systems Workshops, Macau, China, 18–21 June 2012; pp. 133–139. [Google Scholar]
- Li, K.; Zhang, L.; Huang, H. Social Influence Analysis: Models, Methods, and Evaluation. Engineering 2018, 4, 40–46. [Google Scholar] [CrossRef]
- Kempe, D.; Kleinberg, J.; Tardos, E. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 24–27 August 2003; pp. 137–146. [Google Scholar]
- Domingos, P.; Richardson, M. Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 26–29 August 2001; ACM: New York, NY, USA, 2001; pp. 57–66. [Google Scholar]
- Kempe, D.; Kleinberg, J.; Tardos, E. Influential nodes in a diffusion model for social networks. In Proceedings of the 32nd International Conference on Automata, Languages and Programming, Lisbon, Portugal, 11–15 July 2005; pp. 1127–1138. [Google Scholar]
- Sviridenko, M. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 2004, 32, 41–43. [Google Scholar] [CrossRef]
- Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; VanBriesen, J.; Glance, N. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD2007, San Jose, CA, USA, 12–15 August 2007; Association for Computing Machinery: New York, NY, USA, 2007; pp. 420–429. [Google Scholar]
- Goyal, A.; Lu, W.; Lakshmanan, L.V.S. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web 2011, Hyderabad, India, 28 March–1 April 2011; ACM: New York, NY, USA, 2011; pp. 47–48. [Google Scholar]
- Estevez, P.; Vera, P.; Saito, K. Selecting the Most Influential Nodes in Social Networks. In Proceedings of the International Joint Conference on Neural Networks, Orlando, FL, USA, 12–17 August 2007; IEEE: Piscataway, NJ, USA, 2007; pp. 2397–2402. [Google Scholar]
- Chen, W.; Wang, Y.; Yang, S. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 28 June–1 July 2009; ACM: New York, NY, USA, 2009; pp. 199–208. [Google Scholar]
- Zhou, C.; Zhang, P.; Zang, W.; Guo, L. On the upper bounds of spread for greedy algorithms in social network influence maximization. IEEE Trans. Knowl. Data Eng. 2015, 27, 2770–2783. [Google Scholar] [CrossRef]
- Lu, F.; Zhang, W.; Shao, L.; Jiang, X.; Xu, P.; Jin, H. Scalable influence maximization under independent Cascade model. J. Netw. Comput. Appl. 2017, 86, 15–23. [Google Scholar] [CrossRef]
- Ge, H.; Huang, J.; Di, C.; Li, J.; Li, S. Learning automata based approach for influence maximization problem on social networks. In Proceedings of the 2017 IEEE Second International Conference on Data Science in Cyberspace (DSC), Shenzhen, China, 26–29 June 2017; pp. 108–117. [Google Scholar]
- Tian, J.; Wang, Y.; Feng, X. A new hybrid algorithm for influence maximization in social networks. Chin. J. Comp. 2011, 34, 1956–1965. [Google Scholar] [CrossRef]
- Wang, Y.; Feng, X. A potential-based node selection strategy for influence maximization in a social network. In Proceedings of the Advanced Data Mining and Applications, 5th International Conference, ADMA 2009, Beijing, China, 17–19 August 2009; pp. 350–361. [Google Scholar]
- Ohsaka, N.; Akiba, T.; Yoshida, Y.; Kawarabayashi, K. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2014, Québec City, QC, Canada, 27–31 July 2014; AAAI Press: Menlo Park, CA, USA; pp. 138–144. [Google Scholar]
- Wang, Y.; Cong, G.; Song, G.; Xie, K. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, 25–28 July 2010; ACM: New York, NY, USA, 2010; pp. 1039–1048. [Google Scholar]
- Khomami, M.M.D.; Rezvanian, A.; Meybodi, M.R.; Bagheri, A. CFIN: A community-based algorithm for finding influential nodes in complex social networks. J. Supercomput. 2020, 77, 2207–2236. [Google Scholar] [CrossRef]
- Kundu, S.; Murthy, C.; Pal, S. A New Centrality Measure for Influence Maximization in Social Networks. In Proceedings of the Pattern Recognition & Machine Intelligence-International Conference, Moscow, Russia, 27 June–1 July 2011; pp. 242–247. [Google Scholar]
- Kim, J.; Kim, S.; Yu, H. Scalable and Parallelizable Processing of Influence Maximization for Large-Scale Social Networks. In Proceedings of the Twenty-Ninth International Conference on Data Engineering, Brisbane, Australia, 8–12 April 2013; IEEE: Piscataway, NJ, USA, 2013; pp. 266–277. [Google Scholar]
- Kimura, M.; Saito, K. Tractable Models for Information Diffusion in Social Networks; PKDD 2006; Springer: Berlin/Heidelberg, Germany, 2006; pp. 259–271. [Google Scholar]
- Goyal, A.; Lu, W.; Lakshmanan, L. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Proceedings of the 2011 IEEE 11th International Conference on Data Mining, ICDM, Vancouver, BC, Canada, 11–14 December 2011; pp. 211–220. [Google Scholar]
- Chen, W.; Yuan, Y.; Zhang, L. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 2010 IEEE 10th International Conference on Data Mining, ICDM, Sydney, Australia, 13–17 December 2010; pp. 88–97. [Google Scholar]
- Singh, S.; Singh, K.; Kumar, A.; Biswas, B. ACO-IM: Maximizing influence in social networks using ant Colony optimization. Soft Comput. 2020, 24, 10181–10203. [Google Scholar] [CrossRef]
- Jung, K.; Heo, W.; Chen, W. IRIE: Scalable and robust influence maximization in social networks. In Proceedings of the 2012 IEEE 12th International Conference on Data Mining, ICDM, Brussels, Belgium, 10–13 December 2012; pp. 918–923. [Google Scholar]
- Tang, Y.; Xiao, X.; Shi, Y. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Snowbird, UT, USA, 22–27 June 2014; pp. 75–86. [Google Scholar]
- Cohen, E.; Delling, D.; Pajor, T.; Werneck, R.F. Sketch-based Influence Maximization and Computation: Scaling up with Guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management (CIKM 2014), New York, NY, USA, 3–7 November 2014; pp. 629–638. [Google Scholar]
- Nguyen, H.T.; Thai, M.T.; Dinh, T.N. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD 2016), New York, NY, USA, 26 June–1 July 2016; pp. 695–710. [Google Scholar]
- Chen, W.; Wang, C.; Wang, Y. 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, San Francisco, CA, USA, 13–17 August 2016; pp. 1029–1038. [Google Scholar]
- Chen, Y.; Zhu, W.; Peng, W.; Lee, W.; Lee, S. Cim: Community-based influence maximization in social networks. ACM Trans. Intell. Syst. Technol. 2014, 5, 45–75. [Google Scholar] [CrossRef]
- Singh, S.; Singh, K.; Kumar, A.; Biswas, B. Coim: Community-Based Influence Maximization in Social Networks. In Proceedings of the ICAICR: International Conference on Advanced Informatics for Computing Research, Shimla, India, 14–15 July 2018; Springer: Singapore, 2018; pp. 440–453. [Google Scholar]
- Narayanam, R.; Narahari, Y. A shapley valuebased approach to discover influential nodes in social networks. IEEE Trans. Autom. Sci. Eng. 2011, 8, 130–147. [Google Scholar] [CrossRef]
- Borgs, C.; Brautbar, M.; Chayes, J.; Lucier, B. Maximizing social influence in nearly optimal time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, OR, USA, 5–7 January 2014; pp. 946–957. [Google Scholar]
- Gong, Y.; Liu, S.; Bai, Y. Efficient parallel computing on the game theory-aware robust influence maximization problem. Knowl.-Based Syst. 2021, 220, 106942. [Google Scholar] [CrossRef]
- Seo, J.H.; Kim, M.H. Finding influential communities in networks with multiple influence types. Inf. Sci. 2021, 548, 254–274. [Google Scholar] [CrossRef]
- Singh, A.K.; Kailasam, L. Link Prediction-Based Influence Maximization in Online Social Networks. Neurocomputing 2021, 453, 151–163. [Google Scholar] [CrossRef]
- Li, D.; Wang, Y.J.; Li, M.H.; Sun, X.; Pan, J.C.; Ma, J. Net Positive Influence Maximization in Signed Social Networks. Intell. Fuzzy Syst. 2021, 41, 3821–3832. [Google Scholar] [CrossRef]
- Wu, G.; Gao, X.; Yan, G.; Chen, G. Parallel Greedy Algorithmto Multiple Influence Maximization in Social Network. ACM Trans. Knowl. Discov. Data 2021, 15, 1–21. [Google Scholar]
- Xie, X.; Li, J.; Sheng, Y.; Wang, W.; Yang, W. Competitive influence maximization considering inactive nodes and community homophily. Knowl.-Based Syst. 2021, 233, 107497. [Google Scholar] [CrossRef]
- Singh, S.; Kumar, A.; Singh, K.; Biswas, B. C2IM: Community based context-aware influence maximization in social networks. Phys. A Stat. Mech. Its Appl. 2019, 514, 796–818. [Google Scholar] [CrossRef]
- Min, H.Y.; Cao, J.X.; Yuan, T.F.; Liu, B. Topic based time-sensitive influence maximization in online social networks. World Wide Web 2020, 23, 1831–1859. [Google Scholar] [CrossRef]
- Guo, J.X.; Wu, W.L. Adaptive Influence Maximization: If Influential Node Unwilling to Be the Seed. ACM Trans. Knowl. Discov. Data 2021, 15, 1–23. [Google Scholar] [CrossRef]
- Daley, D.J.; Kendall, D.G. Epidemics and Rumours. Nat. Cell Biol. 1964, 204, 1118. [Google Scholar] [CrossRef] [PubMed]
No. | Name | Edges | Nodes | Average Degree | Average Clustering Coefficient | Diameter |
---|---|---|---|---|---|---|
1 | 88,234 | 4039 | 43.7 | 0.61 | 8 | |
2 | ca-HepTH | 25,998 | 9877 | 5.3 | 0.47 | 17 |
3 | Epinions | 508,837 | 75,879 | 6.7 | 0.14 | 14 |
4 | 1,768,149 | 81,306 | 43.5 | 0.57 | 7 |
5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 | Average | |
---|---|---|---|---|---|---|---|---|---|---|---|
0.94 | 0.92 | 0.95 | 0.96 | 0.99 | 0.98 | 0.96 | 0.97 | 0.98 | 0.98 | 0.96 | |
ca-HepTH | 0.67 | 0.54 | 0.82 | 0.8 | 0.8 | 0.87 | 0.85 | 0.89 | 0.9 | 0.93 | 0.81 |
Epinions | 0.88 | 0.9 | 0.87 | 0.88 | 0.89 | 0.88 | 0.87 | 0.91 | 0.95 | 0.94 | 0.9 |
0.93 | 0.96 | 0.97 | 0.97 | 0.98 | 0.98 | 0.97 | 0.96 | 0.97 | 0.97 | 0.97 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Zhang, L.; Li, K. Influence Maximization Based on Backward Reasoning in Online Social Networks. Mathematics 2021, 9, 3189. https://doi.org/10.3390/math9243189
Zhang L, Li K. Influence Maximization Based on Backward Reasoning in Online Social Networks. Mathematics. 2021; 9(24):3189. https://doi.org/10.3390/math9243189
Chicago/Turabian StyleZhang, Lin, and Kan Li. 2021. "Influence Maximization Based on Backward Reasoning in Online Social Networks" Mathematics 9, no. 24: 3189. https://doi.org/10.3390/math9243189
APA StyleZhang, L., & Li, K. (2021). Influence Maximization Based on Backward Reasoning in Online Social Networks. Mathematics, 9(24), 3189. https://doi.org/10.3390/math9243189