Zheng Hu
Xiang Lian
Skip Abstract Section
Abstract
In many real-world applications such as social network analysis and online advertising/marketing, one of the most important and popular problems is called influence maximization (IM), which finds a set of k seed users that maximize the expected number of influenced user nodes. In practice, however, maximizing the number of influenced nodes may be far from satisfactory for real applications such as opinion promotion and collective buying. In this paper, we explore the importance of stability and triangles in social networks, and formulate a novel problem in the influence spread scenario, named triangular stability maximization, over social networks, and generalize it to a general triangle influence maximization problem, which is proved to be NP-hard. We develop an efficient reverse influence sampling (RIS) based framework for the triangle IM with theoretical guarantees. To enable unbiased estimators, it demands probabilistic sampling of triangles, that is, sampling triangles according to their probabilities. We propose an edge-based triple sampling approach, which is exactly equivalent to probabilistic sampling and avoids costly triangle enumeration and materialization. We also design several pruning and reduction techniques, as well as a cost-model-guided heuristic algorithm. Extensive experiments and a case study over real-world graphs confirm the effectiveness of our proposed algorithms and the superiority of triangular stability maximization and triangle influence maximization.
- Nesreen K. Ahmed, Nick G. Duffield, Jennifer Neville, and Ramana Rao Kompella. 2014. Graph sample and hold: a framework for big-graph analytics. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1446--1455.Google Scholar
Digital Library
- Mohammad Al Hasan and Vachik S Dave. 2018. Triangle counting in large networks: a review. WIREs Data Mining Knowl. Discov. 8, 2 (2018), e1226.Google ScholarCross Ref
- Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2008. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In SIGKDD. 16--24.Google Scholar
- Suman K. Bera and C. Seshadhri. 2020. How to Count Triangles, without Seeing the Whole Graph. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 306--316.Google Scholar
- Shishir Bharathi, David Kempe, and Mahyar Salek. 2007. Competitive influence maximization in social networks. In WINE. 306--311.Google Scholar
- Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In SODA. 946--957.Google Scholar
- Allan Borodin, Yuval Filmus, and Joel Oren. 2010. Threshold models for competitive influence in social networks. In Internet and Network Economics: 6th International Workshop. Springer, 539--550.Google ScholarCross Ref
- Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. 2011. Limiting the spread of misinformation in social networks. In WWW. 665--674.Google Scholar
- Chenwei Cai, Ruining He, and Julian McAuley. 2017. SPMC: socially-aware personalized markov chains for sparse sequential recommendation. arXiv preprint arXiv:1708.04497 (2017).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. IEEE Transactions on Knowledge and Data Engineering (2020).Google Scholar
- Jyothimon Chandran et al. 2021. A Novel Triangle Count-Based Influence Maximization Method on Social Networks. International Journal of Knowledge and Systems Science (IJKSS) 12, 4 (2021), 1--17.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
- Yi-Cheng Chen, Wen-Yuan Zhu, Wen-Chih Peng, Wang-Chien Lee, and Suh-Yin Lee. 2014. CIM: community-based influence maximization in social networks. TIST 5, 2 (2014), 1--31.Google ScholarDigital Library
- Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008).Google Scholar
- Jean-Pierre Eckmann and Elisha Moses. 2002. Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS 99, 9 (2002), 5825--5829.Google ScholarCross Ref
- Sainyam Galhotra, Akhil Arora, and Shourya Roy. 2016. Holistic influence maximization: Combining scalability and efficiency with opinion-aware models. In Proceedings of the international conference on management of data. 743--758.Google ScholarDigital Library
- Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. 2013. Opinion maximization in social networks. In Proceedings of the 2013 SIAM International Conference on Data Mining. SIAM, 387--395.Google ScholarCross Ref
- Jacob Goldenberg and Libai Eitan Muller. 2001. Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth. Marketing Letters 12, 3 (2001), 211--223.Google ScholarCross Ref
- Granovetter and Mark. 1978. Threshold Models of Collective Behavior. Amer. J. Sociology 83, 6 (1978), 1420--1443.Google ScholarCross Ref
- Jianxiong Guo, Tiantian Chen, and Weili Wu. 2020. Continuous activity maximization in online social networks. IEEE Transactions on Network Science and Engineering 7, 4 (2020), 2775--2786.Google ScholarCross Ref
- Jing Guo, Peng Zhang, Chuan Zhou, Yanan Cao, and Li Guo. 2013. Personalized influence maximization on social networks. In CIKM. 199--208.Google Scholar
- Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. 2020. Influence maximization revisited: Efficient reverse reachable set generation with bound tightened. In SIGMOD. 2167--2181.Google Scholar
- 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, Sibo Wang, Glenn Bevilacqua, Xiaokui Xiao, and Laks VS Lakshmanan. 2017. Revisiting the stop-and-stare algorithms for influence maximization. Proceedings of the VLDB Endowment 10, 9 (2017), 913--924.Google ScholarDigital Library
- Shixun Huang, Wenqing Lin, Zhifeng Bao, and Jiachen Sun. 2022. Influence Maximization in Real-World Closed Social Networks. Proc. VLDB Endow. 16, 2 (oct 2022), 180--192. Google ScholarDigital Library
- Xin Huang and Laks VS Lakshmanan. 2017. Attribute-driven community search. Proceedings of the VLDB Endowment 10, 9 (2017), 949--960.Google ScholarDigital Library
- David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In SIGKDD. 137--146.Google Scholar
- Jinha Kim, Wonyeol Lee, and Hwanjo Yu. 2014. CT-IC: Continuously activated and time-restricted independent cascade model for viral marketing. Knowledge-Based Systems 62 (2014), 57--68.Google ScholarDigital Library
- Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.Google Scholar
- Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, and Wen-syan Li. 2014. Efficient location-aware influence maximization. In SIGMOD. 87--98.Google Scholar
- Jianxin Li, Taotao Cai, Ke Deng, Xinjue Wang, Timos Sellis, and Feng Xia. 2020. Community-diversified influence maximization in social networks. Information Systems 92 (2020), 101522.Google ScholarCross Ref
- Rong-Hua Li and Jeffrey Xu Yu. 2015. Triangle minimization in large networks. Knowl. Inf. Syst. 45, 3 (2015), 617--643.Google ScholarDigital Library
- Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018. Influence maximization on social graphs: A survey. TKDE 30, 10 (2018), 1852--1872.Google ScholarCross Ref
- Yuchen Li, Ju Fan, Dongxiang Zhang, and Kian-Lee Tan. 2017. Discovering your selling points: Personalized social influential tags exploration. In SIGMOD. 619--634.Google Scholar
- Wei Lu, Wei Chen, and Laks VS Lakshmanan. 2015. From Competition to Complementarity: Comparative Influence Diffusion and Maximization. Proc. VLDB Endow. 9, 2 (2015), 60--71.Google ScholarDigital Library
- R Duncan Luce and Albert D Perry. 1949. A method of matrix analysis of group structure. Psychometrika 14, 2 (1949), 95--116.Google ScholarCross Ref
- Yasir Mehmood, Francesco Bonchi, and David García-Soriano. 2016. Spheres of influence for more effective viral marketing. In SIGMOD. 711--726.Google Scholar
- Huiyu Min, Jiuxin Cao, Tangfei Yuan, and Bo Liu. 2020. Topic based time-sensitive influence maximization in online social networks. World Wide Web 23, 3 (2020), 1831--1859.Google ScholarDigital Library
- George L Nemhauser and Laurence A Wolsey. 1981. Maximizing submodular set functions: formulations and analysis of algorithms. In North-Holland Mathematics Studies. Vol. 59. Elsevier, 279--301.Google Scholar
- Hung T Nguyen, My T Thai, and Thang N Dinh. 2016. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In SIGMOD. 695--710.Google ScholarDigital Library
- Qiufen Ni, Jianxiong Guo, Weili Wu, and Huan Wang. 2022. Influence-based community partition with sandwich method for social networks. IEEE Transactions on Computational Social Systems (2022).Google Scholar
- Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. nature 435, 7043 (2005), 814--818.Google Scholar
- Benedek Rozemberczki and Rik Sarkar. 2021. Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings. arXiv:2101.03091 [cs.SI]Google Scholar
- Alexander J Stewart, Mohsen Mosleh, Marina Diakonova, Antonio A Arechar, David G Rand, and Joshua B Plotkin. 2019. Information gerrymandering and undemocratic decisions. Nature 573, 7772 (2019), 117--121.Google Scholar
- Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, Vol. 1. Present Day Trends of Innovations Lamza Poland.Google Scholar
- Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. 2018. Online processing algorithms for influence maximization. In SIGMOD. 991--1005.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
- Shan Tian, Songsong Mo, Liwei Wang, and Zhiyong Peng. 2020. Deep reinforcement learning-based approach to tackle topic-aware influence maximization. Data Science and Engineering 5, 1 (2020), 1--11.Google ScholarCross Ref
- Silke Trißl and Ulf Leser. 2007. Fast and practical indexing and querying of very large graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 845--856.Google Scholar
- Dimitris Tsaras, George Trimponias, Lefteris Ntaflos, and Dimitris Papadias. 2021. Collective influence maximization for multiple competing products with an awareness-to-influence model. Proc. VLDB Endow. 14, 7 (2021), 1124--1136.Google ScholarDigital Library
- Duru Türkoglu and Ata Turk. 2017. Edge-Based Wedge Sampling to Estimate Triangle Counts in Very Large Graphs. In 2017 IEEE International Conference on Data Mining. IEEE Computer Society, 455--464.Google ScholarCross Ref
- Pinghui Wang, Yiyan Qi, Yu Sun, Xiangliang Zhang, Jing Tao, and Xiaohong Guan. 2017. Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage. Proc. VLDB Endow. 11, 2 (2017), 162--175.Google ScholarDigital Library
- Xiaoyang Wang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016. Efficient distance-aware influence maximization in geo-social networks. TKDE 29, 3 (2016), 599--612.Google ScholarDigital Library
- Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. 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. ACM, 1039--1048.Google ScholarDigital Library
- Yaxuan Wang, Hongzhi Wang, Jianzhong Li, and Hong Gao. 2016. Efficient Influence Maximization in Weighted Independent Cascade Model. In Database Systems for Advanced Applications - 21st International Conference (Lecture Notes in Computer Science), Vol. 9643. Springer, 49--64.Google Scholar
- Zhefeng Wang, Yu Yang, Jian Pei, Lingyang Chu, and Enhong Chen. 2017. Activity maximization by effective information diffusion in social networks. IEEE Transactions on Knowledge and Data Engineering 29, 11 (2017), 2374--2387.Google ScholarDigital Library
- Stanley Wasserman, Katherine Faust, et al. 1994. Social network analysis: Methods and applications. (1994).Google Scholar
- Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world'networks. nature 393, 6684 (1998), 440--442.Google Scholar
- Xiaowei Ye, Rong-Hua Li, Qiangqiang Dai, Hongzhi Chen, and Guoren Wang. 2022. Lightning Fast and Space Efficient K-Clique Counting. In Proceedings of the ACM Web Conference 2022. Association for Computing Machinery, 1191--1202.Google ScholarDigital Library
- Kem ZK Zhang and Morad Benyoucef. 2016. Consumer behavior in social commerce: A literature review. Decision support systems 86 (2016), 95--108.Google Scholar
- Xinxin Zhang, Li Xu, and Zhenyu Xu. 2022. Influence Maximization Based on Network Motifs in Mobile Social Networks. IEEE Trans. Netw. Sci. Eng. 9, 4 (2022), 2353--2363. Google ScholarCross Ref
- Tong Zhao, Julian McAuley, and Irwin King. 2015. Improving latent factor models via personalized feature projection for one class recommendation. In Proceedings of the 24th ACM international on conference on information and knowledge management. 821--830.Google ScholarDigital Library
- Yuting Zhong and Longkun Guo. 2020. Group Influence Maximization in Social Networks. In CSoNet. 152--163.Google Scholar
- Jianming Zhu, Smita Ghosh, and Weili Wu. 2019. Group influence maximization problem in social networks. TCSS 6, 6 (2019), 1156--1164.Google Scholar
Recommendations
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 ...
General triangular midpoint subdivision
Smoothness of general triangular midpoint surfaces for arbitrary control meshes. C 1 analysis tools for infinite classes of triangular subdivision schemes.New spectral properties of subdivision matrices.Smoothness analysis of Loop subdivision surfaces. ...
Personalized influence maximization on social networks
CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge ManagementIn this paper, we study a new problem on social network influence maximization. The problem is defined as, given a target user $w$, finding the top-k most influential nodes for the user. Different from existing influence maximization works which aim to ...
Comments