Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
arXiv:1408.6282 · doi:10.1145/2661829.2662077
Abstract
Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a probabilistic model, such as Independent Cascade (IC), or captured by a set of representative traces. Basic computational problems in the study of diffusion are influence queries (determining the potency of a specified seed set of nodes) and Influence Maximization (identifying the most influential seed set of a given size). Answering each influence query involves many edge traversals, and does not scale when there are many queries on very large graphs. The gold standard for Influence Maximization is the greedy algorithm, which iteratively adds to the seed set a node maximizing the marginal gain in influence. Greedy has a guaranteed approximation ratio of at least (1-1/e) and actually produces a sequence of nodes, with each prefix having approximation guarantee with respect to the same-size optimum. Since Greedy does not scale well beyond a few million edges, for larger inputs one must currently use either heuristics or alternative algorithms designed for a pre-specified small seed set size. We develop a novel sketch-based design for influence computation. Our greedy Sketch-based Influence Maximization (SKIM) algorithm scales to graphs with billions of edges, with one to two orders of magnitude speedup over the best greedy methods. It still has a guaranteed approximation ratio, and in practice its quality nearly matches that of exact greedy. We also present influence oracles, which use linear-time preprocessing to generate a small sketch for each node, allowing the influence of any seed set to be quickly answered from the sketches of its nodes.
10 pages, 5 figures. Appeared at the 23rd Conference on Information and Knowledge Management (CIKM 2014) in Shanghai, China
References in corpus (3)
Cited by in corpus (43)
- Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models
- Learning Heuristics over Large Graphs via Deep Reinforcement Learning
- A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
- Controlling Elections through Social Influence
- Tracking Influential Nodes in Dynamic Networks
- Efficient Approximation Algorithms for Adaptive Seed Minimization
- Maximizing the Diversity of Exposure in a Social Network
- gIM: GPU Accelerated RIS-based Influence Maximization Algorithm
- Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
- The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches
- Distance-Based Influence in Networks: Computation and Maximization
- Scalable Influence Estimation Without Sampling
- Seeding with Costly Network Information
- Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret
- Sample Complexity Bounds for Influence Maximization
- Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach
- Popular Topics Spread Faster: New Dimension for Influence Propagation in Online Social Networks
- Refutations on "Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study"
- Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization
- Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty - An Extended Version
- No Time to Observe: Adaptive Influence Maximization with Partial Feedback
- Semi-Supervised Learning on Graphs through Reach and Distance Diffusion
- Tracking Top-K Influential Vertices in Dynamic Networks
- Network Diffusions via Neural Mean-Field Dynamics
- Exact Computation of Influence Spread by Binary Decision Diagrams
- How to Maximize the Spread of Social Influence: A Survey
- Regularized Unconstrained Weakly Submodular Maximization
- Scalable Lattice Influence Maximization
- Cost-Effective Seed Selection in Online Social Networks
- Approximate k-Cover in Hypergraphs: Efficient Algorithms, and Applications
- TipTop: (Almost) Exact Solutions for Influence Maximization in Billion-scale Networks
- Reverse Ranking by Graph Structure: Model and Scalable Algorithms
- Revenue Maximization in Incentivized Social Advertising
- RCELF: A Residual-based Approach for Influence Maximization Problem
- Evolving Influence Maximization in Evolving Networks
- Influence Maximization for Social Good: Use of Social Networks in Low Resource Communities
- Toward Optimal Coupon Allocation in Social Networks: An Approximate Submodular Optimization Approach
- A Behavioral Analysis on the Reselection of Seed Nodes in Independent Cascade Based Influence Maximization
- Influence Estimation and Maximization via Neural Mean-Field Dynamics
- Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
- Efficient and Effective Algorithms for Revenue Maximization in Social Advertising
- Offline and Online Models of Budget Allocation for Maximizing Influence Spread
- A Co\mbox{-}Operative Game Theoretic Approach for the Budgeted Influence Maximization Problem