Abstract
In a social network, the propagation of information has sparked intense research. Influence Maximization (IM) is a well-studied problem that asks for k nodes to influence the largest users in the social network. However IM is submodular at the most time. In recent years, many non-submodular problems have been proposed and researchers give a lot of algorithms to solve them. In this paper, we propose Activity Probability Maximization Problem without submodular property. For a given social network G, a candidate edge set \({\overline{E}}\) and a constant k, the Activity Probability Maximization Problem asks for k edges in the candidate edge set that make the all nodes of G with highest probability of being activated under a pre-determined seed set S. Using the marginal increment, we give a general way to construct submodular lower bound and submodular upper bound functions of the non-submodular objective function at the same time. Interestingly, the optimal solution of upper bound is the same as that of lower bound. Therefore, we develop the Sandwich framework called Semi-Sandwich framework. Based on the same optimal solution of lower and upper bounds, we propose a Difference Minimizing Greedy (DMG) algorithm to get an approximation solution of the original problem. Through massive experiments, we show that the method and algorithm are effective.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anshelevich E, Hate A, Magdon-Ismail M (2013) Seeding influential nodes in non-submodular models of information diffusion. Autonom Agents Multi Agent Syst 29(1):131–159
Bharathi S, Kempe D, Salek M (2007) Competitive influence maximization in social networks. Internet and network economics. Springer, Berlin
Borgs C, Brautbar M, Chayes JT, Lucier B (2014) Maximizing social influence in nearly optimal time. SODA 946–957
Chaoji V, Ranu S, Rastogi R et al (2012) Recommendations to boost content spread in social networks. ACM
Chen W, Wang C, Wang Y (2010) 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, Washington, DC, USA, July 25-28, 2010. ACM
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: kdd. Proc of Acm Kdd, 199-208, 199-208
Domingos P, Richardson M (2001) Mining the Network Value of Customers. In: ACM SIGKDD international conference on knowledge discovery and data mining. ACM
Hannon J, Bennett M, Smyth B (2010) Recommending twitter users to follow using content and collaborative filtering approaches. In NIPS*17, 199-206
Kempe D, Kleinberg J (2003) Maximizing the spread of influence through a social network. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2003:137-146
Kim J, Kim S.-K, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE Computer Society
Leskovec Jure, Krevl Andrej (2014) SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. KDD 420–429
Li CT, Lin YJ, Yeh MY (2017) Forecasting participants of information diffusion on social networks with its applications. Information Sciences, S0020025516308453
Lin, Y, Chen, W, Lui, JCS (2017) Boosting Information Spread: An Algorithmic Approach. In: 2017 IEEE 33rd international conference on data engineering (ICDE). IEEE
Lin Y, Chen W, Lui JCS (2017) Boosting Information Spread: An Algorithmic Approach. In: IEEE International Conference on Data Engineering. IEEE
Lu W, Chen W, Lakshmanan LVS (2015) From competition to complementarity: comparative influence diffusion and maximization
Ma L, Cao G, Kaplan L (2017) Graphical approach for influence maximization in social networks under generic threshold-based non-submodular model. In: 2017 IEEE International conference on big data (Big Data), pp 970–975
Morone F, Makse HA (2015) Influence maximization in complex networks through optimal percolation. Nature 524(7563):65–68
Nettasinghe B, Krishnamurthy V (2018) Influence maximization over markovian graphs: a stochastic optimization approach. IEEE Trans Signal Inf Process Over Netw 5(1):1–14
Pham CV, Duong HV, Bui BQ, et al (2013) Maximizing Acceptance Probability for Active Friending in Online Social Networks. ACM
Premm Raj H, Narahari Y (2012) Influence limitation in multi-campaign social networks: A Shapley value based approach. In: IEEE international conference on automation science & engineering. IEEE
Qiang He, Xingwei Wang, Zhencheng Lei, Min Huang, Yuliang Cai, Lianbo Ma (2019) TIFIM: a two-stage iterative framework for influence maximization in social networks. Appl Math Comput 354(C):338–352
Richardson M, Domingos P (2002) Mining Knowledge-Sharing Sites for Viral Marketing. Proc Sigkdd
Shi QH, Wang C, Chen J et al (2019) Post and repost: a holistic view of budgeted influence maximization. Neurocomputing 338:92–100
Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: ACM SIGMOD international conference on management of data. ACM
Tong H, Prakash BA, Eliassi-Rad T, Faloutsos M, Faloutsos C (2012) Gelling, and melting, large graphs by edge manipulation. In: Proceedings of the 21st ACM international conference on Information and knowledge management. ACM
Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Discov 25(3):545–576
Wang Z, Yang Y, Pei J et al (2016) Activity maximization by effective information diffusion in social networks. IEEE Trans Knowl Data Eng PP(99):1–1
Wang Y, Cong G, Song G, Xie K (2010) Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. ACM
Yang D-N, Hung H-J, Lee W-C, Chen W (2013) Maximizing Acceptance Probability for Active Friending in Online Social Networks. ACM
Yang W, Yuan J, Wu W et al (2019) Maximizing activity profit in social networks. IEEE Trans Comput Soc Syst 6(1):117–126
Yang W, Ma J, Li Y et al (2019) Marginal gains to maximize content spread in social networks. IEEE Trans Comput Soc Syst 6(3):479–490
Acknowledgements
This work was supported by the National Natural Science Foundation of China under Grant 11571015 and 11991022.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Yang, W., Chen, S., Gao, S. et al. Boosting node activity by recommendations in social networks. J Comb Optim 40, 825–847 (2020). https://doi.org/10.1007/s10878-020-00629-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00629-6