Shixun Huang
Skip Abstract Section
Abstract
In the last few years, many closed social networks such as WhatsAPP and WeChat have emerged to cater for people's growing demand of privacy and independence. In a closed social network, the posted content is not available to all users or senders can set limits on who can see the posted content. Under such a constraint, we study the problem of influence maximization in a closed social network. It aims to recommend users (not just the seed users) a limited number of existing friends who will help propagate the information, such that the seed users' influence spread can be maximized. We first prove that this problem is NP-hard. Then, we propose a highly effective yet efficient method to augment the diffusion network, which initially consists of seed users only. The augmentation is done by iteratively and intelligently selecting and inserting a limited number of edges from the original network. Through extensive experiments on real-world social networks including deployment into a real-world application, we demonstrate the effectiveness and efficiency of our proposed method.
- 2014. https://business.sohu.com/20140624/n401244299.shtml.Google Scholar
- 2018. https://www.postbeyond.com/blog/millennials-genz-social-media/.Google Scholar
- 2018. https://medium.com/@lorenabarquin/are-closed-social-media-platforms-the-future-of-social-3a5b0cbea025.Google Scholar
- 2018. https://www.warc.com/newsandopinion/news/the_new_facebooks_the_trend_towards_a_closed_social_media/40929.Google Scholar
- 2018. https://www.quora.com/Why-are-some-people-not-interested-in-exposing-themselves-on-social-media.Google Scholar
- 2021. https://www.tailwindapp.com/blog/private-on-pinterest.Google Scholar
- 2021. https://zhuanlan.zhihu.com/p/82896779.Google Scholar
- 2021. https://cfm.qq.com/gicp/news/186/15185249.html.Google Scholar
- 2022. https://www.facebook.com/help/233739099984085.Google Scholar
- 2022. https://help.twitter.com/en/safety-and-security/public-and-protected-tweets.Google Scholar
- 2022. https://techalignment.com/closed-versus-open-social-networks/.Google Scholar
- 2022. https://github.com/rmitbggroup/IMCSN.Google Scholar
- Roy M Anderson and Robert M May. 1992. Infectious diseases of humans: dynamics and control.Google Scholar
- Cigdem Aslay, Laks VS Lakshmanan, Wei Lu, and Xiaokui Xiao. 2018. Influence maximization in online social networks. In WSDM. 775--776.Google Scholar
- Suman Banerjee, Mamata Jenamani, and Dilip Kumar Pratihar. 2019. ComBIM: A community-based solution approach for the Budgeted Influence Maximization Problem. Expert Systems with Applications 125 (2019), 1--13.Google ScholarDigital Library
- Glenn S Bevilacqua and Laks VS Lakshmanan. 2021. A fractional memory-efficient approach for online continuous-time influence maximization. The VLDB Journal (2021), 1--27.Google Scholar
- Song Bian, Qintian Guo, Sibo Wang, and Jeffrey Xu Yu. 2020. Efficient algorithms for budgeted influence maximization on massive social networks. VLDB 13, 9 (2020), 1498--1510.Google ScholarDigital Library
- Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In SODA. 946--957.Google Scholar
- Taotao Cai, Jianxin Li, Ajmal S Mian, Timos Sellis, Jeffrey Xu Yu, et al. 2020. Target-aware holistic influence maximization in spatial social networks. TKDE (2020).Google Scholar
- Claudio Castellano and Romualdo Pastor-Satorras. 2010. Thresholds for epidemic spreading in networks. Physical review letters 105, 21 (2010), 218701.Google Scholar
- Bogdan Cautis, Silviu Maniu, and Nikolaos Tziortziotis. 2019. Adaptive influence maximization. In SIGKDD. 3185--3186.Google Scholar
- Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, and Rushi Bhatt. 2012. Recommendations to boost content spread in social networks. In WWW. 529--538.Google Scholar
- Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In SIGKDD. 1029--1038.Google Scholar
- Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In SIGKDD. 199--208.Google Scholar
- Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In ICDM. 88--97.Google Scholar
- Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, and Xueqi Cheng. 2013. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In CIKM. 509--518.Google Scholar
- Boreum Choi and Inseong Lee. 2017. Trust in open versus closed social media: The relative influence of user-and marketer-generated content in social network services on customer trust. Telematics and Informatics 34, 5 (2017), 550--559.Google ScholarDigital Library
- Reuven Cohen, Keren Erez, Shlomo Havlinl, Mark Newman, Albert-László Barabási, Duncan J Watts, et al. 2011. Resilience of the internet to random breakdowns. In The Structure and Dynamics of Networks. 507--509.Google Scholar
- The Koblenz Network Collection. 2017. http://konect.uni-koblenz.de.Google Scholar
- Federico Coró, Gianlorenzo DâĂŹangelo, and Yllka Velaj. 2021. Link Recommendation for Social Influence Maximization. TKDD 15, 6 (2021), 1--23.Google ScholarDigital Library
- Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. 2019. Recommending links through influence maximization. Theor. Comput. Sci. 764 (2019), 30--41.Google ScholarDigital Library
- Sainyam Galhotra, Akhil Arora, and Shourya Roy. 2016. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In SIGMOD. 1077--1088.Google Scholar
- Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review 9, 3 (2001), 1--18.Google Scholar
- Pranava R Goundan and Andreas S Schulz. 2007. Revisiting the greedy approach to submodular set function maximization. Optimization online (2007), 1--25.Google Scholar
- Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In WWW. 47--48.Google Scholar
- Amit Goyal, Wei Lu, and Laks VS Lakshmanan. 2011. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM. 211--220.Google Scholar
- Mark Granovetter. 1978. Threshold models of collective behavior. American journal of sociology 83, 6 (1978), 1420--1443.Google Scholar
- Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. 2018. Efficient algorithms for adaptive influence maximization. VLDB 11, 9 (2018), 1029--1040.Google ScholarDigital Library
- Qiang He, Xingwei Wang, Zhencheng Lei, Min Huang, Yuliang Cai, and Lianbo Ma. 2019. TIFIM: A two-stage iterative framework for influence maximization in social networks. Appl. Math. Comput. 354 (2019), 338--352.Google ScholarDigital Library
- Huimin Huang, Hong Shen, Zaiqiao Meng, Huajian Chang, and Huaiwen He. 2019. Community-based influence maximization for viral marketing. Applied Intelligence 49, 6 (2019), 2137--2150.Google ScholarDigital Library
- Keke Huang, Jing Tang, Kai Han, Xiaokui Xiao, Wei Chen, Aixin Sun, Xueyan Tang, and Andrew Lim. 2020. Efficient approximation algorithms for adaptive influence maximization. The VLDB Journal 29, 6 (2020), 1385--1406.Google ScholarDigital Library
- Shixun Huang. 2021. Capturing and leveraging collective behavior for large-scale social networks analysis. Ph.D. Dissertation. RMIT University.Google Scholar
- Shixun Huang, Zhifeng Bao, J Shane Culpepper, and Bang Zhang. 2019. Finding temporal influential users over evolving social networks. In 2019 IEEE 35th international conference on data engineering (ICDE). IEEE, 398--409.Google ScholarCross Ref
- Kyomin Jung, Wooram Heo, and Wei Chen. 2012. Irie: Scalable and robust influence maximization in social networks. In ICDM. 918--923.Google Scholar
- David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In SIGKDD. 137--146.Google Scholar
- Elias Boutros Khalil, Bistra Dilkina, and Le Song. 2014. Scalable diffusion-aware optimization of network topology. In SIGKDD. 1226--1235.Google Scholar
- Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne Van-Briesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In SIGKDD. 420--429.Google Scholar
- Xiang Li, J David Smith, Thang N Dinh, and My T Thai. 2019. Tiptop:(almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Transactions on Networking 27, 2 (2019), 649--661.Google ScholarDigital Library
- Wei Liu, Xin Chen, Byeungwoo Jeon, Ling Chen, and Bolun Chen. 2019. Influence maximization on signed networks under independent cascade model. Applied Intelligence 49, 3 (2019), 912--928.Google ScholarDigital Library
- Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016. The H-index of a network node and its relation to degree and coreness. Nature communications 7, 1 (2016), 1--7.Google Scholar
- Marco Minutoli, Mahantesh Halappanavar, Ananth Kalyanaraman, Arun Sathanur, Ryan Mcclure, and Jason McDermott. 2019. Fast and scalable implementations of influence maximization algorithms. In 2019 IEEE International Conference on Cluster Computing (CLUSTER). 1--12.Google ScholarCross Ref
- George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions. Mathematical programming 14, 1 (1978), 265--294.Google Scholar
- Mark EJ Newman. 2002. Spread of epidemic disease on networks. Physical review E 66, 1 (2002), 016128.Google Scholar
- Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. In AAAI. 138--144.Google Scholar
- Panpan Shu, Wei Wang, Ming Tang, and Younghae Do. 2015. Numerical identification of epidemic thresholds for susceptible-infected-recovered model on finite-size networks. Chaos: An Interdisciplinary Journal of Nonlinear Science 25, 6 (2015), 063104.Google ScholarCross Ref
- Lichao Sun, Weiran Huang, Philip S Yu, and Wei Chen. 2018. Multi-round influence maximization. In SIGKDD. 2249--2258.Google Scholar
- Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In SIGMOD. 1539--1554.Google Scholar
- Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD. 75--86.Google Scholar
- Yanhao Wang, Qi Fan, Yuchen Li, and Kian-Lee Tan. 2017. Real-time influence maximization on dynamic social streams. PVLDB 10, 7 (2017), 805--816.Google ScholarDigital Library
- Hao-Hsiang Wu and Simge Küçükyavuz. 2018. A two-stage stochastic programming approach for influence maximization in social networks. Computational Optimization and Applications 69, 3 (2018), 563--595.Google ScholarDigital Library
- Jiarong Xie, Fanhui Meng, Jiachen Sun, Xiao Ma, Gang Yan, and Yanqing Hu. 2021. Detecting and modelling real percolation and phase transitions of information on social media. Nature Human Behaviour (2021), 1--8.Google Scholar
- Wenguo Yang, Shengminjie Chen, Suixiang Gao, and Ruidong Yan. 2020. Boosting node activity by recommendations in social networks. Journal of Combinatorial Optimization 40 (2020), 825--847.Google ScholarDigital Library
- Wenguo Yang, Jianmin Ma, Yi Li, Ruidong Yan, Jing Yuan, Weili Wu, and Deying Li. 2019. Marginal gains to maximize content spread in social networks. IEEE Transactions on Computational Social Systems 6, 3 (2019), 479--490.Google ScholarCross Ref
- Kaichen Zhang, Jingbo Zhou, Donglai Tao, Panagiotis Karras, Qing Li, and Hui Xiong. 2020. Geodemographic influence maximization. In SIGKDD. 2764--2774.Google Scholar
Recommendations
Influence Maximization in Multi-Relational Social Networks
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge ManagementInfluence maximization (IM) is a classic problem, which aims to find a set of k users (called seed set) in a social network such that the expected number of users influenced by the seed users is maximized. Existing IM algorithms mainly focus on one-by-...
Influence Maximization in Online Social Networks
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data MiningStarting with the earliest studies showing that the spread of new trends, information, and innovations is closely related to the social influence exerted on people by their social networks, the research on social influence theory took off, providing ...
Influence Maximization in Messenger-Based Social Networks
2016 IEEE Global Communications Conference (GLOBECOM)Many online social networks have provided a messenger app (e.g., facebook messenger, direct message on Twitter) to facilitate communication between strong- tied friends. Meanwhile, some messenger apps (WeChat) also start to offer social-networking ...
Comments