2019/07/03 by Wei Chen, Binghui Peng, Chen, Wei +1 · 1 citation
Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI) #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.1907.01707
openalex publication_date 2019/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the adaptivity gap of the influence maximization problem under independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescence is between [(e)/(e-1), (2e)/(e - 1)] and for the out-arborescence, the gap is between [(e)/(e-1), 2]. These are the first constant upper bounds in the full-adoption feedback model. We provide several novel ideas to tackle with correlated feedback appearing in the adaptive stochastic optimization, which we believe to be of independent interests.