EUVIMEDEUVIMED entdecken
Crossref

Influence Maximization Revisited: Efficient Sampling with Bound Tightened

Qintian Guo, Sibo Wang, Zhewei Wei, Wenqing Lin, Jing Tang

ACM Transactions on Database Systems · 30.09.2022 · 47 (3) · 1-45

DOI: 10.1145/3533817 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 18.08.2022. Verfasst von Qintian Guo und 4 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: Hong Kong RGC ECS, Hong Kong RGC CRF, Hong Kong ITC ITF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a social network G with n nodes and m edges, a positive integer k , and a cascade model C , the influence maximization (IM) problem asks for k nodes in G such that the expected number of nodes influenced by the k nodes under cascade model C is maximized. The state-of-the-art approximate solutions run in O(k(n+m) log n/ ε 2 ) expected time while returning a (1 - 1/ e - ε) approximate solution with at least 1 - 1/ n probability. A key phase of these IM algorithms is the random reverse reachable (RR) set generation, and this phase significantly affects the efficiency and scalability of the state-of-the-art IM algorithms. In this article, we present a study on this key phase and propose an efficient random RR set generation algorithm under IC model. With the new algorithm, we show that the expected running time of existing IM algorithms under IC model can be improved to O(k ċ n log n ċ 2 ), when for any node v , the total weight of its incoming edges is no larger than a constant. For the general IC model where the weights are skewed, we present a sampling algorithm SKIP. To the best of our knowledge, it is the first index-free algorithm that achieves the optimal time complexity of the sorted subset sampling problem. Moreover, existing approximate IM algorithms suffer from scalability issues in high influence networks where the size of random RR sets is usually quite large. We tackle this challenging issue by reducing the average size of random RR sets without sacrificing the approximation guarantee. The proposed solution is orders of magnitude faster than states of the art as shown in our experiment. Besides, we investigate the issues of forward propagation and derive its time complexity with our proposed subset sampling techniques. We also present a heuristic condition to indicate when the forward propagation approach should be utilized to estimate the expected influence of a given seed set.

Förderung

  • Hong Kong RGC ECS
  • Hong Kong RGC CRF
  • Hong Kong ITC ITF
  • CUHK Direct Grant
  • NSFC of China
  • National Natural Science Foundation of China
  • Beijing Natural Science Foundation
  • PCL

Zitieren

APA

Guo, Q., Wang, S., Wei, Z., Lin, W., & Tang, J. (2022). Influence Maximization Revisited: Efficient Sampling with Bound Tightened. ACM Transactions on Database Systems, 47(3), 1-45. https://doi.org/10.1145/3533817

Vancouver

Guo Q, Wang S, Wei Z, Lin W, Tang J. Influence Maximization Revisited: Efficient Sampling with Bound Tightened. ACM Transactions on Database Systems. 2022;47(3):1-45. doi:10.1145/3533817

BibTeX
@article{Guo2022,
  author = {Guo, Qintian and Wang, Sibo and Wei, Zhewei and Lin, Wenqing and Tang, Jing},
  title = {Influence Maximization Revisited: Efficient Sampling with Bound Tightened},
  journal = {ACM Transactions on Database Systems},
  year = {2022},
  volume = {47},
  number = {3},
  pages = {1--45},
  doi = {10.1145/3533817}
}
Kostenlos starten →