Influence Maximization

Jianxiong Guo; Weili Wu

doi:10.1145/3399661

journal article Sep 28, 2020

Influence Maximization

Jianxiong Guo

Weili Wu

ACM Transactions on Knowledge Discovery from Data Vol. 14 No. 6 pp. 1-22 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3399661

Abstract

Influence maximization problem attempts to find a small subset of nodes in a social network that makes the expected influence maximized, which has been researched intensively before. Most of the existing literature focus only on maximizing total influence, but it ignores whether the influential distribution is balanced through the network. Even though the total influence is maximized, but gathered in a certain area of social network. Sometimes, this is not advisable. In this article, we propose a novel seeding strategy based on community structure, and formulate the Influence Maximization with Community Budget (IMCB) problem. In this problem, the number of seed nodes in each community is under the cardinality constraint, which can be classified as the problem of monotone submodular maximization under the matroid constraint. To give a satisfactory solution for IMCB problem under the triggering model, we propose the IMCB-Framework, which is inspired by the idea of continuous greedy process and pipage rounding, and derive the best approximation ratio for this problem. In IMCB-Framework, we adopt sampling techniques to overcome the high complexity of continuous greedy. Then, we propose a simplified pipage rounding algorithm, which reduces the complexity of IMCB-Framework further. Finally, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms, as well as the advantage of IMCB-Framework against classical greedy method.

Topics

No keywords indexed for this article. Browse by subject →

References

32

[1]

10.1023/b:joco.0000038913.96607.c2

[2]

10.1145/3035918.3035924

[3]

10.1137/1.9781611973402.70

[4]

10.1016/j.knosys.2017.07.029

[5]

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

Gruia Calinescu, Chandra Chekuri, Martin Pál et al.

SIAM Journal on Computing 10.1137/080733991

[6]

10.1145/1835804.1835934

[7]

10.1109/icdm.2010.118

[8]

Finding community structure in very large networks

Aaron Clauset, M. E. J. Newman, Cristopher Moore

Physical Review E 10.1103/physreve.70.066111

[9]

10.1145/502512.502525

[10]

Fisher Marshall L. (1978)

[11]

Goyal Amit

[12]

Grötschel Martin

[13]

Guo Jianxiong "Budgeted coupon advertisement problem: Algorithm and robust analysis" DOI:https://doi.org/10.1109/TNSE. (2020)

[14]

Guo Jianxiong "Targeted protection maximization in social networks" DOI:https://doi.org/10.1109/TNSE. (2019)

[15]

10.1109/tcss.2019.2926112

[16]

10.1145/502090.502096

[17]

Jung Kyomin (2011)

[18]

10.1145/956750.956769

[19]

Lagrée Paul (2018)

[20]

10.1145/1281192.1281239

[21]

An analysis of approximations for maximizing submodular set functions—I

G. L. Nemhauser, L. A. Wolsey, M. L. Fisher

Mathematical Programming 10.1007/bf01588971

[22]

Nguyen Hung T.

[23]

Ramezani Maryam (2018)

[24]

10.1145/775047.775057

[25]

Ryan

[26]

10.1006/jctb.2000.1989

[27]

Schrijver Alexander (2003)

[28]

10.1145/2723372.2723734

[29]

10.1145/2588555.2593670

[30]

10.1145/1374376.1374389

[31]

10.1145/1835804.1835935

[32]

Yan Ruidong (2019)

Metrics

26

Citations

32

References

Details

Published: Sep 28, 2020
Vol/Issue: 14(6)
Pages: 1-22
License: View

Authors

J

Jianxiong Guo

The University of Texas at Dallas, Richardson, Texas

W

Weili Wu

The University of Texas at Dallas, Richardson, Texas

Funding

National Science Foundation Award: 1747818, 1907472

Cite This Article

Jianxiong Guo, Weili Wu (2020). Influence Maximization. ACM Transactions on Knowledge Discovery from Data, 14(6), 1-22. https://doi.org/10.1145/3399661

Influence Maximization

You May Also Like