2019 · 17 citations · 21 references
ComputingAutonomous SystemsDecision TheoryOptimizationUncertainty QuantificationApproximation AlgorithmsInformation SpreadNetwork OptimizationNetwork PropagationSocial Network AnalysisStochastic NetworksInfluence PropagationInformation Diffusion ModelsInformation SpreadingNode InfluenceSocial Influence ModelingSocial Network InfluenceStochastic Network OptimizationUncertainty Propagation In Networks
We consider the influence maximization (IM) problem in a partially visible social network. The goal is to design a decision-making framework for an autonomous agent to select a limited set of influential seed nodes to spread a message as widely as possible across the network. We consider the realistic case where only a partial section of the network is visible to the agent, while the rest is one of a finite set of known structures, each with a given realization probability. We show that solving the IM problem in this setting is NP-hard, and we provide analytical guarantees for the performance of a novel computationally-efficient seed-selection approximation algorithm for the agent. In empirical experiments on real-world social networks, we demonstrate the efficiency of our scheme and show that it outperforms state-of-the-art approaches that do not model the uncertainty.
21
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Influence Maximization in Near-Linear Time
Youze Tang, Yanchen Shi, Xiaokui Xiao · 2015 · 754 citations
Youze Tang, Xiaokui Xiao, Yanchen Shi · 2014 · 739 citations