Research map / Learning theory and algorithms / Submodular and game algorithms
Motif-oriented influence maximization for viral marketing in large-scale social networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LBMOIM, a sandwich-bound greedy RR-set algorithm for motif-oriented influence maximization (maximizing activated motifs) under the linear threshold model, with a provable approximation ratio.
Problem
Influence maximization where targets are strongly connected motifs that must be activated (threshold r_i activated nodes), rather than individual nodes; the motif-level influence function is neither submodular nor supermodular.
Approach
Derive submodular upper and lower bounds on the motif activation objective (lower bound scaled by tau), and optimize them with an RR-set based greedy algorithm (TIM-style) with root nodes sampled proportional to motif weights, yielding a tau(1-1/e-eps) approximation.
Key results
- LBMOIM outperforms TIM+, OPIM, DeepIM, GIM and GIA in expected motif influence under the LT model across Flickr, Amazon, Catster, and Youtube for r_i=1 with motif size 2 and 3.
- Under the IC model on Douban, LBMOIM consistently achieves higher motif coverage than baselines for r_i=1,2,3.
- Theoretical guarantee: approximation ratio tau*(1-1/e-eps) with time complexity O((k+l)(m+eta) log eta / eps^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LBMOIM instead of the evaluated alternatives | Motif influence maximization · LT model, Flickr, Amazon, Catster, and Youtube | motif influence | Helped |
| Use LBMOIM instead of the evaluated alternatives | Motif influence maximization · IC model, Douban, ri = 1, 2, and 3 | motif influence | Helped |
| Optimize the simplified submodular bound with LBMOIM rather than the baseline methods | Motif influence maximization · LT model, varied motif sizes and activation thresholds | motif influence | Helped |
| Use LBMOIM rather than GIM | Motif influence maximization · LT model, Flickr, Amazon, Catster, and Youtube | runtime | Helped |
| Increase the motif size | Evaluated influence maximization methods · LT model, Figures 2 and 3 | motif influence | Hurt |
Surprising findings
- The motif-level influence function is shown to be neither submodular nor supermodular, so direct greedy has no guarantee.
- Node-level IM methods (TIM+, OPIM, DeepIM) fail to reach the best motif coverage, showing that node-level optimization does not transfer to motif targets.
Limitations
- Approximation ratio depends on tau, the minimum over motifs of the minimal spanning-tree probability, which can be small and makes the guarantee loose.
- Experiments use synthetic motif sets (2000 random strongly connected subgraphs) rather than real group-decision data.
- Experiments run on a single CPU machine; results on larger hardware are not reported.
Experimental setup
Datasets: Flickr Amazon Catster Youtube Douban
Benchmarks: Flickr Amazon Catster Youtube Douban
Metrics: expected activated motif influence running time
Baselines: TIM+ OPIM DeepIM GIM GIA
Builds on: TIM IMM sandwich approximation Kempe et al. linear threshold model
Closest papers by meaning
- Computing and maximizing influence in linear threshold and triggering models (NeurIPS 2016 · similarity 0.88)
- Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions (NeurIPS 2017 · similarity 0.88)
- When Social Advertising Meets Viral Marketing: Sequencing Social Advertisements for Influence Maximization (AAAI 2018 · similarity 0.88)
- Maximizing Influence Spread through a Dynamic Social Network (Student Abstract) (AAAI 2023 · similarity 0.87)
- Graph Bayesian Optimization for Multiplex Influence Maximization (AAAI 2024 · similarity 0.86)
- The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.