Online Influence Maximization (Extended Version)

• In marketing, seed selection focuses limited promotional effort on influential users, but existing IM methods require influence probabilities that may be unavailable or incomplete.The paper motivates OIM with campaigns in which firms know the social network but not how influence propagates.Source: §1 · p. 1
• OIM runs successive campaigns in which selected seeds are activated and user feedback updates an uncertain influence graph until the marketing budget is exhausted.Each trial has selection and action phases, and selection can use an existing IM solution on the uncertain graph.Source: §1 · p. 2
• The paper develops an Explore–Exploit seed strategy that alternates between exploiting estimated influence probabilities and exploring confidence bounds to improve probability knowledge.Any existing IM algorithm can support exploitation; exploration can select seeds based on confidence bounds.Source: §1 · p. 2
• Suitable Explore–Exploit strategies outperform running an existing IM algorithm alone on the uncertain graph; experiments also show the proposed methods can maximize spread effectively and efficiently.Explore–Exploit selects seeds either to pursue rewarding spread or to improve probability knowledge.Source: §1 · p. 2
• An incremental algorithm reuses previous samples when feedback affects only part of the graph, reducing repeated sampling overhead for sample-based IM under independent cascade models.The paper notes sampling can account for more than 99% of TIM+ computation time.Source: §1 · p. 2
• The paper studies local and global updates to uncertain influence probabilities using classical machine-learning methods, including least-squares estimation and maximum likelihood.Local updates refresh distribution parameters between two nodes; global updates refresh parameters applying to the whole uncertain graph.Source: §1 · p. 2

Influence Maximization (IM)

• IM research established NP-hardness and greedy approximation, then developed heuristics and guaranteed algorithms, alongside variants for communities/topics, competition, and propagation models [11].Heuristics include Degree Discount, PMIA, IPA, and IRIE [15]; guaranteed approaches include CELF, CELF++ [13], NewGreedy, reverse influence sampling, and TIM/TIM+ [26].Source: §2 · p. 2

Learning influence probabilities

• Saito et al. used likelihood maximization and expectation maximization to estimate influence probabilities, while Goyal et al. proposed static and time-dependent models based on action logs.Those models require all involved users’ action logs in advance; this paper instead learns and refines probabilities from feedback across multiple advertising campaigns.Source: §2 · pp. 2–3

Multi-armed bandits (MAB)

• The paper’s seed-selection Explore-Exploit strategy draws on ε-greedy MAB, which exploits current knowledge with probability 1 − ε and explores with probability ε [21].The ε-greedy framework is adopted as a baseline.Source: §2 · p. 3
• CUCB [8], using upper confidence bounds, has a regret bound in an OIM-like scenario but is unsuitable because activations can be redundant and its initialization tests every seed.That initialization is impractical with limited activation budgets.Source: §2 · p. 3
• Thompson Sampling [1] models independent arms with Beta distributions of successes and failures, but in OIM the arms are algorithm parameters and defining success or failure is nontrivial.Source: §2 · p. 3

• Under the independent cascade model, each newly active node gets one chance to activate each inactive neighbor, and the process ends when no further activations are possible.Each attempt succeeds independently with probability p_ij.Source: §3 · p. 3
• Given a weighted graph and seed budget k, influence maximization selects k nodes to maximize expected influence spread.The spread σ(S) is the expected number of activated nodes.Source: §3 · p. 3
• Degree discount selects high-degree nodes, greedy selects the largest marginal spread and guarantees a (1 − 1/e)-approximation, while CELF, TIM, and TIM+ [26] use sampling-based methods.TIM counts node frequencies in reversed reachable sets; TIM+ extends TIM for large influence graphs.Source: §3 · pp. 3–4
• Offline IM algorithms assume every edge probability is known, but such probabilities may require unavailable action logs, so those algorithms cannot run when probabilities are unknown.Source: §3 · pp. 3–4

4. MAXIMIZING INFLUENCE ONLINE

• OIM selects up to k seed nodes in each of N trials, using feedback from each campaign to guide seed selection in later trials.The objective is to perform influence maximization without knowing influence probabilities in advance.Source: §4 · p. 4

4.1 The Uncertain Influence Graph

• Edge influence probabilities are modeled as Beta distributions whose posteriors can be updated easily when new evidence arrives.The model can incorporate global or edge-specific priors, including estimates learned from action logs [11].Source: §4.1 · p. 4

4.2 The OIM Framework

• Each trial selects seeds with an offline IM algorithm and uncertainty strategy, activates them in the real world, then updates the graph from activation outcomes and edge-attempt feedback.The paper reports that proper updates yield better influence spread than running the framework without updates.Source: §4.2 · pp. 4–5

5.1 Heuristic-Based Strategies

• Random selects k users for fairness, while MaxDegree selects the k nodes with most nonzero-probability outgoing edges; both are simple but ignore probability quality and activation feedback.Targeting users with higher outgoing influence probabilities may be more effective, and feedback could help estimate those probabilities.Source: §5.1 · p. 5

5.2 Explore-Exploit Strategies

• ε-greedy exploits with probability 1−ε and otherwise explores by raising edge estimates with their standard deviations, addressing uncertain means that can suppress genuinely influential nodes.Exploitation runs an offline IM algorithm on current mean probabilities; exploration is especially useful in early trials, when estimates may be inaccurate. Choosing ε is difficult, and raising probabilities by standard deviation may not always help.Source: §5.2 · p. 5
• Confidence-Bound assigns each edge probability μij + θσij, with θ=0 matching exploit and θ=1 matching explore, while allowing intermediate values for greater flexibility than ε-greedy.θ can be adjusted automatically from activated-user feedback, and one global value reduces optimization parameters and improves efficiency.Source: §5.2 · pp. 5–6

6. MANAGING USER FEEDBACK

• Each trial records attempted edge activations and their success or failure, supporting local, global-prior, and θ updates; Random and MaxDegree are unaffected by these updates.Feedback may omit graph edges that no activation reached.Source: §6 · p. 6

6.1 Updating Local⃗α and⃗β

• For each attempted edge, successful activations increment αij and failures increment βij, yielding B(α + hij, β + mij) with the shared prior as smoothing.This is a Beta-Bernoulli update based on the edge’s observed activation outcomes.Source: §6.1 · p. 6

6.2 Updating Global⃗α and⃗β

• Global priors α and β can be estimated by least squares against observed spread or by maximizing the likelihood of independent feedback outcomes.The least-squares estimator can use activated-node sets when full activation feedback is unavailable, but relies on estimated spread.Source: §6.2 · pp. 6–7

6.3 Updating⃗θ

• For CB, exponentiated gradient updates the probabilities of candidate θ values using gain Gn = |An|/|V|; experiments identify it as the best-performing strategy.A candidate’s selection probability increases when its trial produces high gain.Source: §6.3 · p. 7

7. INCREMENTAL SOLUTION FOR OIM

• Repeated IM runs make OIM costly because sampling dominates runtime, while feedback affects a relatively small part of the graph, motivating reuse across trials.The paper notes that TIM+ spends more than 99% of its computation sampling random reverse reachable sets and that DBLP feedback averages less than 1% of edges for k = 1.Source: §7 · p. 8

7.1 Solution Framework

• The sample manager stores previous samples and reuses them after local and global checks, replacing a sample with a newly generated one if either check fails.This can reduce running time when checks are cheaper than sampling and the ratio of reused samples is high.Source: §7.1 · p. 8

7.2 Case Study: TIM+

• An RR set’s occurrence probability remains unchanged when influence probabilities on its incoming edges do not change; age comparisons enable the local check for this condition.For the local check, the sample passes if every node in Rv is younger than the sample; storing sample and node ages makes this check O(|Rv|).Source: §7.2 · pp. 8–9
• Global-prior changes affect all edge probabilities, so TIM+ checks whether stored and current priors are sufficiently close before reusing a sample.The sample manager stores the priors from when each sample was generated, allowing the global check to run in O(1).Source: §7.2 · p. 9
• TIM+’s local and global checks cost O(|Rv|), about d times faster than generating a sample, and can significantly save computation when the reuse ratio is high.On average, generating Rv costs O(|E(Rv)|), where |E(Rv)| = d × |Rv| and d is the average in-degree.Source: §7.2 · p. 9

8.1 Setup

• The simulator assigns each edge probability p_ij = 1/d_j, runs one independent-cascade simulation per seed test, and records feedback and successfully activated nodes.The probability setting follows previous works [11] [26].Source: §8.1 · pp. 9–10
• OIM effectiveness is total activations across N trials, averaged over 10 repetitions of each solution.The measure is |∪_{n=1}^N A_n|, where A_n is the set of successfully activated nodes in trial n.Source: §8.1 · p. 10
• The evaluation uses NetHept, NetPhy, and DBLP, academic collaboration networks whose nodes are authors and edges represent co-authorship [11] [26].NetHept and NetPhy are arXiv collaboration networks in High Energy Physics Theory and Physics, respectively.Source: §8.1 · p. 10
• The experiments evaluate several options for the OIM algorithm’s seed-selection and graph-update components.Source: §8.1 · p. 10

[Choosing seeds]

• The evaluation combines heuristic or explore–exploit seed selection with graph-update methods; TIM+ is used when an IM algorithm is invoked, and CB and MLE are the defaults.Random and MaxDegree are not combined with update methods; the incremental CB variant is denoted CB-INC.Source: [Choosing seeds] · p. 10

8.2 Results on NetPHY

• At N = 50, CB is 20% better than MaxDegree at k = 5 and 45% better at k = 25, while its spread discount from Real at k = 5 falls from 30% at N = 10 to 13% at N = 50.With fixed Budget = 50, CB also improves over MaxDegree by about 35% at k = 1; CB-INC's spread is around 5% lower than CB's across k values.Source: §8.2 · pp. 10–11
• When k = 5 and N = 50, CB is about 20% better than ε-greedy and 32% better than Exploit, and ε-greedy remains worse than CB in all tested cases.Exploit performs worst; smaller k strengthens exploration, and ε-greedy's performance is sensitive to ε, with ε = 0.1 best among the tested settings.Source: §8.2 · p. 11, Figure 5 · p. 11
• MLE is about 25% better than LSE and 40% better than LOC; NO performs worse than the other update options.The authors attribute MLE's advantage to its use of full feedback, whereas LSE uses only successfully activated nodes and LOC lacks global updates.Source: §8.2 · p. 11, Figure 6 · p. 11
• With different priors, MLE and LSE remain stable while LOC and NO fluctuate, and the global β values for MLE and LSE converge to around 27.The authors conclude that global updating helps compensate for inexact prior information.Source: §8.2 · p. 11
• At N = 50, CB-INC reduces running time by 88% versus CB, reusing about 80% to 99% of samples when N ≥ 10.With fixed Budget = 50, smaller k increases trial count and reduces efficiency, while improving spread; the authors recommend a small k subject to available time.Source: §8.2 · p. 11, Figure 7 · p. 12
• With k = 1 and Budget = 50, τ = 0.01 yields a 3% spread discount versus CB, compared with 5% for τ = 0.02 and 15% for τ = 0.03.The running time for τ = 0.01 is about 28% slower than for τ = 0.02 and 38% worse than for τ = 0.03.Source: §8.2 · p. 11

8.3 Results for NetHEPT and DBLP

• Across NetPHY, NetHEPT, and DBLP, CB and CB-INC outperform heuristic methods and remain close to the oracle; on DBLP, CB-INC saves 16 hours versus CB at k = 1, N = 50.CB takes 19 hours in that DBLP setting; on NetPHY, the authors also report that CB-INC significantly improves CB's efficiency with only a small influence-spread discount.Source: §8.3 · p. 12, Figure 8 · p. 12, §8.2 · p. 12

9. CONCLUSIONS

• The approach’s influence spread is close to using the real influence graph, especially as trials increase; uncertainty-based explore–exploit performs well, and feedback updates are effective in longer campaigns.The method performs influence maximization over multiple trials, updating graph knowledge from real-world feedback.Source: §9 · p. 12
• Future work includes varying budgets across trials, changing influence probabilities over time, using community- and topic-aware IM methods,, exploring linear-threshold or credit-distribution models [11], and improving scalability through distributed algorithms such as distributed sampling.Source: §9 · p. 12