PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Influence Maximization (Extended Version)

Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, Pierre Senellart

arXiv:1506.01188v1cs.SIcs.DBphysics.soc-ph

TL;DR

Influence maximization normally relies on known influence probabilities, but those probabilities may be unavailable or incomplete. The paper proposes multi-trial campaigns that select seeds, collect feedback, and update influence information using Explore–Exploit strategies. Experiments report that the approach is more effective than traditional influence-maximization methods under partial information.

  • Problem

    The paper asks how to perform influence maximization when influence probabilities are absent or incomplete.

  • Method

    The approach runs multiple campaigns, uses Explore–Exploit seed selection, updates an uncertain influence graph from feedback, and applies an incremental algorithm to improve efficiency.

  • Results

    The experiments show that the proposed methods effectively and efficiently maximize influence spread, outperforming traditional methods on partial information.

  • Takeaways & Limitations

    Influence maximization can be conducted while influence probabilities are learned during successive campaigns.

  • Takeaways & Limitations

    One estimator relies on spread estimation and is intended for settings where full activation feedback is unavailable but successful activated nodes are accessible.

Abstract

from arXiv · show

Social networks are commonly used for marketing purposes. For example, free samples of a product can be given to a few influential social network users (or "seed nodes"), with the hope that they will convince their friends to buy it. One way to formalize marketers' objective is through influence maximization (or IM), whose goal is to find the best seed nodes to activate under a fixed budget, so that the number of people who get influenced in the end is maximized. Recent solutions to IM rely on the influence probability that a user influences another one. However, this probability information may be unavailable or incomplete. In this paper, we study IM in the absence of complete information on influence probability. We call this problem Online Influence Maximization (OIM) since we learn influence probabilities at the same time we run influence campaigns. To solve OIM, we propose a multiple-trial approach, where (1) some seed nodes are selected based on existing influence information; (2) an influence campaign is started with these seed nodes; and (3) users' feedback is used to update influence information. We adopt the Explore-Exploit strategy, which can select seed nodes using either the current influence probability estimation (exploit), or the confidence bound on the estimation (explore). Any existing IM algorithm can be used in this framework. We also develop an incremental algorithm that can significantly reduce the overhead of handling users' feedback information. Our experiments show that our solution is more effective than traditional IM methods on the partial information.

1. INTRODUCTION

The paper formulates Online Influence Maximization for settings where influence probabilities are absent or incomplete, learning them while campaigns run. It proposes repeated trials combining influence-based seed selection, feedback updates, and explore–exploit strategies, with an incremental algorithm for efficiency.

  • Influence maximization selects seed nodes under a promotion budget to maximize expected influence spread.
  • OIM asks whether influence maximization can proceed while influence probabilities are discovered through ongoing campaigns.
  • The framework runs multiple trials that select seeds, launch campaigns, and use users’ feedback to update influence information.
  • Explore–Exploit selects seeds either to maximize expected spread from current estimates or to improve knowledge using confidence bounds.
  • With suitable strategies, Explore–Exploit performs better than applying an existing influence-maximization algorithm to the uncertain graph alone.
  • The incremental algorithm reduces the overhead of repeatedly processing feedback and can support sample-based influence-maximization algorithms.

2. RELATED WORK

Prior work includes classical influence maximization, methods for learning influence probabilities, and multi-armed-bandit strategies. The paper distinguishes its framework from these approaches by learning through repeated campaigns without requiring all action logs in advance.

  • Classical influence-maximization work established hardness results, approximation guarantees, and faster heuristics such as Degree Discount, PMIA, IPA, and IRIE.
  • Influence-probability learning methods use likelihood maximization or action-log models, but some require information about all involved users in advance.
  • The OIM framework instead selects seeds across multiple advertising campaigns and uses users’ feedback to learn influence probabilities.
  • Explore–Exploit is inspired by ε-greedy multi-armed bandits, which balance exploitation of current knowledge against exploration of alternatives.
  • The cited combinatorial-bandit approach is described as inapplicable because activated nodes can be counted repeatedly and its approximation bound depends on an unavailable quantity.

3. INFLUENCE MAXIMIZATION: REVIEW

Influence maximization chooses k seed nodes whose expected spread is largest, typically under propagation models such as independent cascade. Offline algorithms assume edge probabilities are known, whereas the paper motivates online methods for unknown probabilities.

  • In the independent cascade model, active nodes make one probabilistic activation attempt toward each currently inactive neighbor at the next time step.
  • Influence spread is the expected number of nodes eventually activated from a seed set.
  • Influence maximization seeks a size-k seed set S maximizing influence spread σ(S) on a weighted influence graph.
  • Greedy and heuristic algorithms select nodes using estimated spread, marginal spread, degree, or reverse-reachable-set frequencies.
  • Offline algorithms require influence probabilities for every node pair, so they cannot run when those values are unknown.

4. MAXIMIZING INFLUENCE ONLINE

OIM performs influence maximization across repeated trials with unknown edge probabilities, representing uncertainty probabilistically and updating it from campaign feedback. Each trial chooses seeds, observes activations, and refreshes the uncertain graph.

  • OIM selects up to k seed nodes in each of N campaigns and uses feedback from earlier campaigns to choose later seeds.
  • The framework separates each trial into seed selection, real-world activation with feedback collection, and graph updating.
  • An uncertain influence graph represents each unknown edge probability with a probability density function that can be refined after trials.
  • Because activations are binary, the framework models uncertain influence probabilities with Beta distributions and updates their parameters as evidence arrives.
  • The initial model can use global α and β parameters shared across edges, with α = β = 1 representing a uniform prior.
  • The framework supports existing offline IM algorithms for seed selection and refreshes the graph using activated nodes and edge-attempt feedback.

5. CHOOSING SEEDS

The paper compares heuristic and Explore–Exploit seed-selection strategies for uncertain influence graphs. Explore–Exploit combines current estimates with deliberate exploration, while Confidence-Bound generalizes this trade-off through a tunable parameter θ.

  • Heuristic-Based Strategies: Random selects k seed nodes arbitrarily, whereas MaxDegree selects the k nodes with highest out-degree.MaxDegree uses the number of outgoing edges with non-zero influence probabilities as its selection criterion.
  • Heuristic-Based Strategies: These heuristics are easy to implement but ignore influence-probability information and feedback from activated users.The paper motivates a more adaptive seed-selection method because users can differ in influence and feedback can reveal unknown probabilities.
  • Explore-Exploit Strategies: Explore–Exploit alternates between offline IM using current influence information and exploration intended to improve knowledge about influence probabilities.Exploit uses an existing IM algorithm, while explore operations target information improvement.
  • Explore-Exploit Strategies: ε-greedy has difficulty setting an effective ε, and increasing probabilities by σ_ij may not always improve selection.These limitations motivate the improved Confidence-Bound strategy.
  • Explore-Exploit Strategies: θ = 0 yields exploit, θ = 1 yields explore, and allowing intermediate values makes Confidence-Bound more flexible than ε-greedy.The paper also notes that ε-greedy is a special case of Confidence-Bound.
  • Explore-Exploit Strategies: Confidence-Bound sets p_ij = μ_ij + θσ_ij before running offline IM on the resulting graph.The algorithm computes each edge’s mean and variance, adjusts the probability using θ, and then returns the selected seed set.

6. MANAGING USER FEEDBACK

The framework updates uncertain influence information from campaign feedback through local, global, and θ-specific mechanisms. It also develops estimation and incremental techniques to make repeated feedback processing practical, while noting that one estimator relies on spread estimates.

  • Feedback Representation: Feedback records attempted activations as tuples (i, j, a_ij), where a_ij indicates whether influence from i to j succeeded.The feedback may omit edges that an activation did not reach.
  • Update Types: The framework supports local edge updates, global prior updates, and updates to θ used by Confidence-Bound.These update types are based on activated nodes and activation results collected during a trial.
  • Local Updates: Under the Beta–Bernoulli model, a successful activation increments α_ij, while a failed activation increments β_ij.The edge distribution is updated from B(α_ij, β_ij) using each observed Bernoulli feedback outcome.
  • Local Updates: After repeated feedback, each edge distribution counts successful and failed activations, smoothed by the global prior B(α, β).The resulting local update is B(α + h_ij, β + m_ij).
  • Global Updates: Global prior updates can improve the influence graph when sparse local evidence would otherwise produce suboptimal or overfit estimates.The paper contrasts this with estimating only edges for which direct evidence exists.
  • Global Updates: Least-squares estimation fits global priors to observed campaign spread, using an estimated average spread when deriving the regression quantities.The method estimates σ̂_n from the average spread of activation campaigns.
  • Global Updates: The spread estimator relies on σ̂_n and is useful when only successful activated-node sets are available instead of complete feedback F_n.This reliance is identified as a limitation of the estimator.
  • Updating θ: Exponentiated Gradient updates the probabilities of candidate θ values according to the gain observed in each trial.The gain is defined as G_n = |A_n|/|V|, and the experiments identify Exponentiated Gradient as the best-performing strategy.

7. INCREMENTAL SOLUTION FOR OIM

The incremental OIM solution reuses sample-based influence-maximization computations across trials, replacing only samples invalidated by feedback or graph updates. Its checks preserve valid samples and can make TIM+ execution substantially faster than regenerating samples.

  • TIM+ spends more than 99% of its computation time sampling random reverse reachable sets, motivating computation reuse across OIM trials.
  • The sample manager stores prior samples, checks whether each remains valid after updates, and resamples only when reuse is unsafe.Reusable samples are selected from a pool and replaced when they fail local or global checks.
  • The approach applies to sample-based IM algorithms under independent cascade models and is demonstrated with TIM+.
  • An RR set remains valid when influence probabilities on all incoming edges to its nodes remain unchanged.This condition is formalized as the foundation of the incremental TIM+ approach.
  • Local validity can be checked in O(|Rv|) time using stored sample and node ages, rather than regenerating the sample.The check identifies whether feedback affected edges in the RR set.
  • Checks for an RR set are about d times faster than generating it, where d is the average node in-degree.The comparison follows from check cost O(|Rv|) versus generation cost O(|E(Rv)|).

8. EXPERIMENTAL EVALUATION

The evaluation uses a real-world simulator, repeated influence-spread measurements, and several collaboration-network datasets. It examines alternative seed-selection and graph-update components for OIM.

  • Setup: The experiments use a real-world simulator that assigns each edge influence probability pij = 1/dj and generates feedback through an independent cascade simulation.
  • Setup: OIM effectiveness is measured by the total number of successfully activated nodes across N trials, averaged over 10 repetitions.
  • Datasets: The study evaluates NetHept, NetPhy, and DBLP, collaboration networks whose nodes represent authors and edges represent co-authorship.
  • Algorithms: The evaluation compares alternative seed-selection and graph-update components, including heuristic-based and Explore–Exploit approaches.

[Choosing seeds]

The experiments compare seed-selection, graph-updating, and incremental strategies for Online Influence Maximization. Confidence-Bound exploration and incremental updating generally improve influence spread or efficiency, with trade-offs depending on trial size and update settings.

  • Explore–Exploit Strategies: CB outperforms other explore–exploit strategies, improving over ε-greedy by 20% and Exploit by 32% when k = 5 and N = 50.Exploit can suffer from incorrect influence-probability predictions, while exploration is especially valuable when fewer feedback tuples are returned per trial.
  • Updating the uncertain influence graph: MLE is about 25% better than LSE and 40% better than LOC for updating the uncertain influence graph.MLE uses full feedback, whereas LSE uses only successfully activated nodes; global updating also remains stable across different priors.
  • Efficiency: CB-INC achieves about 10 times the speedup of CB when N ≥ 10 and reduces running time by 88% at N = 50.This efficiency gain comes from reusing stable samples; the reuse ratio is about 80% to 99% when N ≥ 10.
  • Efficiency: A smaller k improves influence spread but reduces efficiency because more trials require more frequent TIM+ executions.The recommended k depends on how much total time the user can afford.
  • Effectiveness on other datasets: CB and CB-INC remain close to the oracle on NetHEPT and DBLP, while CB-INC saves 16 hours on DBLP at k = 1 and N = 50.CB costs 19 hours in total for that DBLP result.

9. CONCLUSIONS

The paper concludes that its multi-trial explore–exploit approach performs effectively when influence probabilities are unknown, with influence spread approaching that of the real influence graph as trials increase. It also identifies scalability as a boundary requiring distributed methods.

  • Influence spread is close to that of the real influence graph, especially as the number of trials increases.
  • Explore–exploit strategies based on graph uncertainty perform well experimentally.
  • The paper reports effective graph-knowledge updates over longer campaigns.
  • Figure 9 evaluates efficiency on other datasets.
  • Scaling the methods may require distributed algorithms such as distributed sampling.
Loading 1506.01188v1…