Abstract
Influence maximization aims at finding a set of seed nodes in a social network that could influence the largest number of nodes. Existing work often focuses on the influence of individual nodes, ignoring that infecting different seeds may require different costs. Nonetheless, in many real-world applications such as advertising, advertisers care more about the influence of groups (e.g., crowds in the same areas or communities) rather than specific individuals, and are very concerned about how to maximize the influence with a limited budget. In this paper, we investigate the problem of group-level influence maximization with budget constraint. Towards this, we introduce a statistical method to reveal the influence relationship between the groups, based on which we propose a propagation model that can dynamically calculate the influence spread scope of seed groups, following by presenting a greedy algorithm called GLIMB to maximize the influence spread scope with a limited cost budget via the optimization of the seed-group portfolio. Theoretical analysis shows that GLIMB can guarantee an approximation ratio of at least \((1-1/\sqrt{e})\). Experimental results on both synthetic and real-world data sets verify the effectiveness and efficiency of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: SODA, pp. 946–957 (2014)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: KDD, pp. 1029–1038 (2010)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: KDD, pp. 199–208 (2009)
Gomez-Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. ACM Trans. Knowl. Disc. Data 5(4), 1019–1028 (2012)
Hu, Z., Yao, J., Cui, B., Xing, E.: Community level diffusion extraction. In: SIGMOD, pp. 1555–1569 (2015)
Jung, K., Heo, W., Chen, W.: IRIE: scalable and robust influence maximization in social networks. In: ICDM, pp. 918–923 (2012)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Leskovec, J., Adamic, L., Adamic, B.: The dynamics of viral marketing. ACM Trans. Web 1(1), 5 (2007)
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: KDD, pp. 420–429 (2007)
Mehmood, Y., Barbieri, N., Bonchi, F., Ukkonen, A.: CSI: community-level social influence analysis. In: Blockeel, H., Kersting, K., Nijssen, S., Železný, F. (eds.) ECML PKDD 2013. LNCS (LNAI), vol. 8189, pp. 48–63. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40991-2_4
Myers, S., Leskovec, J.: On the convexity of latent social network inference. In: NIPS, pp. 1741–1749 (2010)
Nguyen, H., Zheng, R.: On budgeted influence maximization in social networks. IEEE J. Sel. Areas Commun. 31(6), 1084–1094 (2013)
Shang, R., Luo, S., Li, Y., Jiao, L., Stolkin, R.: Large-scale community detection based on node membership grade and sub-communities integration. Phys. A Stat. Mech. Appl. 428, 279–294 (2015)
Tang, Y., Xiao, X., Shi, Y.: Influence maximization: near-optimal time complexity meets practical efficiency. In: SIGMOD, pp. 75–86 (2014)
Wang, Y., Cong, G., Song, G., Xie, K.: Community-based greedy algorithm for mining top-\(k\) influential nodes in mobile social networks. In: KDD, pp. 1039–1048 (2010)
Acknowledgements
This work was supported in part by the NSFC Grants (61502347, 61522208, 61502504, and 61472359), and the Nature Science Foundation of Hubei Province (2016CFB384).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Yan, Q., Huang, H., Gao, Y., Lu, W., He, Q. (2017). Group-Level Influence Maximization with Budget Constraint. In: Candan, S., Chen, L., Pedersen, T., Chang, L., Hua, W. (eds) Database Systems for Advanced Applications. DASFAA 2017. Lecture Notes in Computer Science(), vol 10177. Springer, Cham. https://doi.org/10.1007/978-3-319-55753-3_39
Download citation
DOI: https://doi.org/10.1007/978-3-319-55753-3_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55752-6
Online ISBN: 978-3-319-55753-3
eBook Packages: Computer ScienceComputer Science (R0)