Non-submodular model for group profit maximization problem in social networks

Springer Science and Business Media LLC - Tập 8 Số 1 - 2021
Jianming Zhu1, Smita Ghosh2, Weili Wu2, Chuangen Gao3
1School of Engineering Science, University of Chinese Academy of Sciences, 19A Yuquan Rd., Beijing, 100049, China
2Department of Computer Science, University of Texas at Dallas, Richardson, USA
3Shandong University, Jinan, China

Tóm tắt

AbstractIn social networks, there exist many kinds of groups in which people may have the same interests, hobbies, or political orientation. Sometimes, group decisions are made by simply majority, which means that most of the users in this group reach an agreement, such as US Presidential Elections. A group is calledactivatedif$$\beta$$βpercent of users are influenced in the group. Enterprise will gain income from all influenced groups. Simultaneously, to propagate influence, enterprise needs pay advertisement diffusion cost.Group profit maximization(GPM) problem aims to pickkseeds to maximize the expected profit that considers the benefit of influenced groups with the diffusion cost. GPM is proved to be NP-hard and the objective function is proved to be neither submodular nor supermodular. An upper bound and a lower bound which are difference of two submodular functions are designed. We propose a submodular–modular algorithm (SMA) to solve the difference of two submodular functions and SMA is shown to converge to a local optimal. We present an randomized algorithm based on weighted group coverage maximization for GPM and apply sandwich framework to get theoretical results. Our experiments verify the efficiency of our methods.

Từ khóa


Tài liệu tham khảo

Forsyth DR. Group dynamics. 2018. p. 1.

Meeker M. Internet trends 2018-code conference. Glokalde. 2018;1(3).

Zhu J, Ghosh S, Wu W. Group influence maximization problem in social networks. IEEE Trans Comput Soc Syst. 2019. https://doi.org/10.1109/TCSS.2019.2938575.

Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, ACM. 2003. pp. 137–46.

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, ACM. 2007. pp. 420–9.

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, ACM. 2010. pp. 1029–38.

Goyal A, Lu W, Lakshmanan LV. Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: Data Mining (ICDM), 2011 IEEE 11th international conference on, IEEE. 2011. pp. 211–20.

Cohen E, Delling D, Pajor T, Werneck RF. 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, ACM. 2014. pp. 629–38.

Ohsaka N, Akiba T, Yoshida Y, Kawarabayashi K-i. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In: AAAI. 2014. pp. 138–44.

Du N, Liang Y, Balcan M-F, Gomez-Rodriguez M, Zha H, Song L. Scalable influence maximization for multiple products in continuous-time diffusion networks. J Mach Learn Res. 2017;18(2):1–45.

Yang Y, Lu Z, Li VO, Xu K. Noncooperative information diffusion in online social networks under the independent cascade model. IEEE Trans Comput Soc Syst. 2017;4(3):150–62.

Aslay C, Lakshmanan LV, Lu W, Xiao X. Influence maximization in online social networks. In: Proceedings of the eleventh ACM international conference on web search and data mining, ACM. 2018. pp. 775–6.

Zhu J, Zhu J, Ghosh S, Wu W, Yuan J. Social influence maximization in hypergraph in social networks. IEEE Trans Netw Sci Eng. 2018. https://doi.org/10.1109/TNSE.2018.2873759.

Zhu J, Ghosh S, Zhu J, Wu W. Near-optimal convergent approach for composed influence maximization problem in social networks. IEEE Access. 2019;7:142488–97.

Zhu J, Ghosh S, Wu W, Gao C. Profit maximization under group influence model in social networks. In: International conference on computational data and social networks. Springer. 2019. pp. 108–19.

Tang J, Tang X, Yuan J. Profit maximization for viral marketing in online social networks: algorithms and analysis. IEEE Trans Knowl Data Eng. 2018;30(6):1095–108.

Lu W, Lakshmanan LV. Profit maximization over social networks. In: Data mining (ICDM), 2012 IEEE 12th international conference on, IEEE. 2012. pp. 479–88.

Zhu Y, Lu Z, Bi Y, Wu W, Jiang Y, Li D. Influence and profit: two sides of the coin. In: Data mining (ICDM), 2013 IEEE 13th international conference on, IEEE. 2013. pp. 1301–6.

Tang J, Tang X, Yuan J. Towards profit maximization for online social network providers. arXiv preprint arXiv:1712.08963. 2017.

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. SIAM. 2014. pp. 946–57.

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, ACM. 2014. pp. 75–86.

Tang Y, Shi Y, Xiao X. Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, ACM. 2015. pp. 1539–54.

Nguyen HT, Thai MT, Dinh TN. Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 international conference on management of data, ACM. 2016. pp. 695–710.

Schoenebeck G, Tao B. Beyond worst-case (in)approximability of nonsubmodular influence maximization. In: International conference on web and internet economics. 2017.

Narasimhan M, Bilmes JA. A submodular-supermodular procedure with applications to discriminative structure learning. arXiv preprint arXiv:1207.1404. 2012.

Bach F, et al. Learning with submodular functions: a convex optimization perspective. Found Trends ® Mach Learn. 2013;6(2–3):145–373.

Lu W, Chen W, Lakshmanan LV. From competition to complementarity: comparative influence diffusion and maximization. Proc VLDB Endow. 2015;9(2):60–71.

Wu WL, Zhang Z, Du DZ. Set function optimization. J Oper Res Soc China. 2018;3:1–11.

Zhu J, Ghosh S, Wu W. Robust rumor blocking problem with uncertain rumor sources in social networks. World Wide Web. 2020. https://doi.org/10.1007/s11280-020-00841-8.

Fujishige S. Submodular functions and optimization. In: Of Annals Of discrete mathematics, vol. 47. 2008.

Nemhauser GL, Wolsey LA, Fisher ML. An analysis of approximations for maximizing submodular set functions. Math Program. 1978;14(1):265–94.

Dagum P, Karp R, Luby M, Ross S. An optimal algorithm for monte carlo estimation. SIAM J Comput. 2000;29(5):1484–96.

Iyer R, Bilmes J. Algorithms for approximate minimization of the difference between submodular functions, with applications. arXiv preprint arXiv:1207.0560. 2012.

Opsahl T. Triadic closure in two-mode networks: redefining the global and local clustering coefficients. Soc Netw. 2013;35(2):159–67.

Newman ME. The structure of scientific collaboration networks. Proc Nat Acad Sci. 2001;98(2):404–9.

Tagarelli A., Tong H, editors. Computational data and social networks. CSoNet 2019. Lecture notes in computer science, vol. 11917. Berlin: Springer. pp. 108–19.

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 8 Số 1

Thông tin tác giả