PaperlayerView exact revision on arXiv

Source-linked AI summary

Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models

Sainyam Galhotra, Akhil Arora, Shourya Roy

arXiv:1602.03110v1cs.SIcs.DB

TL;DR

Conventional influence maximization counts activated users without accounting for their opinions or how interaction affects information perception. The paper introduces the OI model, MEO, and OSIM and EaSyIM; its experiments report a running-time and memory trade-off while retaining spread quality on large real graphs.

  • Problem

    Classical influence maximization counts activated nodes, overlooking users’ positive, neutral, or negative opinions and how prior interactions shape information perception.

    Source: §1 · p. 1

  • Method

    The paper introduces the opinion-cum-interaction model and MEO, then develops OSIM for opinion-aware maximization and EaSyIM for opinion-oblivious influence maximization.

    Source: §6 · p. 16

  • Results

    The authors report that OSIM and EaSyIM provide a trade-off between running time and memory consumption while retaining spread quality on large real graphs.

    Source: §6 · p. 16

  • Takeaways & Limitations

    The authors state that EaSyIM's score assignment captures expected spread on tree-like structures under IC, WC, and LT, and on DAGs under LT, yielding a 1 −1/e approximate solution in those settings.

    Source: §3.4.2 · p. 10

    The paper states that no correct graph-wide score assignment capturing each node’s expected spread is possible, so ScoreGREEDY cannot guarantee a 1−1/e approximate solution for general graphs.

    Source: §3.4 · p. 8

Abstract

from arXiv · show

The steady growth of graph data from social networks has resulted in wide-spread research in finding solutions to the influence maximization problem. In this paper, we propose a holistic solution to the influence maximization (IM) problem. (1) We introduce an opinion-cum-interaction (OI) model that closely mirrors the real-world scenarios. Under the OI model, we introduce a novel problem of Maximizing the Effective Opinion (MEO) of influenced users. We prove that the MEO problem is NP-hard and cannot be approximated within a constant ratio unless P=NP. (2) We propose a heuristic algorithm OSIM to efficiently solve the MEO problem. To better explain the OSIM heuristic, we first introduce EaSyIM - the opinion-oblivious version of OSIM, a scalable algorithm capable of running within practical compute times on commodity hardware. In addition to serving as a fundamental building block for OSIM, EaSyIM is capable of addressing the scalability aspect - memory consumption and running time, of the IM problem as well. Empirically, our algorithms are capable of maintaining the deviation in the spread always within 5% of the best known methods in the literature. In addition, our experiments show that both OSIM and EaSyIM are effective, efficient, scalable and significantly enhance the ability to analyze real datasets.

1. MOTIVATION

The section argues that conventional influence maximization overlooks users’ opinions and how prior interactions shape the perception of information. It introduces the OI model and MEO, alongside scalable algorithms intended to address these gaps and the memory and runtime costs of existing methods.

1. MOTIVATION

  • Conventional spread counts activated nodes, overlooking whether their opinions are positive or how past interactions shape their perception of information.The paper notes that a newly active user may disagree with the user who activated them.Source: §1 · p. 1
  • IC-N restricts negative opinions and uses a uniform quality factor, while OC models opinion changes more fully but loses submodularity.In IC-N, negatively activated nodes retain their opinion; the uniform quality factor preserves submodularity but makes the model specific.Source: §1 · p. 2
  • OI-selected seeds produce much better opinion-spread than IC-selected seeds, and the paper also reports better spread than OC-selected seeds.Figure 2 compares opinion-spread for different diffusion models.Source: Figure 2 · p. 2, §1 · p. 2
  • IC-N and OC both lack interaction modeling, and each is tied to a different first-layer diffusion model.IC-N is tuned for IC, whereas OC is designed for LT.Source: §1 · p. 2
  • OI incorporates different node opinions, edge interaction probabilities, and support for both IC and LT at the first layer.The paper presents OI as a more generic and realistic alternative to IC-N and OC.Source: §1 · p. 2
  • The paper introduces MEO under OI and proposes OSIM for opinion-aware maximization, alongside EaSyIM as an opinion-oblivious building block.The authors state that MEO is NP-hard and difficult to approximate within a constant ratio; OSIM accommodates opinion changes during propagation.Source: §1 · pp. 2–3
  • EaSyIM estimates influence using counts of simple paths and is designed to run in linear space and time, addressing scalability limits of earlier methods.The paper cites TIM+ memory use as potentially reaching 100 GB for a graph with 1M nodes and 3M edges.Source: §1 · pp. 2–3
  • The authors report that OSIM and EaSyIM provide a trade-off between running time and memory consumption while retaining spread quality on large real graphs.They characterize the algorithms as practical for large real graphs and capable of handling huge graphs on commodity hardware.Source: §1 · p. 3

2. OPINION AWARE IM

The paper extends influence maximization with an opinion-aware diffusion model and defines a new objective for selecting seeds. Its analysis establishes hardness and rules out constant-ratio approximation unless P=NP.

2.1 Preliminaries

  • Under IC and LT, influence maximization selects a fixed-budget seed set to maximize expected spread, counted as activated non-seed nodes.The OI model extends these foundations to opinion-aware diffusion.Source: §2.1 · p. 3

2.2 Opinion-cum-Interaction (OI) Model

  • The OI model adds node opinions and directed edge interaction probabilities, allowing activated nodes to contribute negatively and supporting both IC and LT.The model accounts for changes in opinion as information propagates.Source: §2.2 · pp. 3–4

2.3 Problem Formulation

  • MEO selects a seed set under the OI model to maximize expected effective opinion spread, which weights positive spread against negative spread using λ.The penalty on negative opinion spread is λ.Source: §2.3 · p. 5

2.4.1 NP-hardness

  • MEO is NP-hard, by reduction from influence maximization using uniformly positive opinions and full interaction probabilities.The reduction sets every node opinion and every edge interaction probability to 1.Source: §2.4.1 · p. 5

2.4.2 Submodularity

  • The opinion-spread function is neither monotone nor submodular; adding a seed can change effective spread from 1 to 0 and back to 1.This behavior prevents the standard greedy 1−1/e guarantee from applying to MEO.Source: §2.4.2 · p. 5
  • Approximating MEO within any constant ratio is impossible unless P=NP, as a set-cover reduction would otherwise decide set cover in polynomial time.The reduction distinguishes instances with a size-k set cover from those without one by whether the achieved spread is positive.Source: §2.4.2 · pp. 5–6

3.1 Outline of our Algorithm

The algorithm assigns node scores and iteratively selects the highest-scoring seeds. Its score assignment matches GREEDY in expectation when correct, with exact correctness on trees and small error on graphs.

3.1 Outline of our Algorithm

  • Correct score assignment yields the same expected influence spread as GREEDY; the assignment is exact for trees and introduces small error on graphs.The authors report that experiments and analysis show results do not deviate much from GREEDY.Source: §3.1 · p. 6
  • Each iteration selects the node with the maximum score and excludes previously activated nodes from later score assignments to keep seed activation sets disjoint.The process continues until k seeds have been selected.Source: §3.1 · p. 6
  • EaSyIM assigns scores for opinion-oblivious diffusion, while OSIM extends the approach to opinion-aware diffusion.The two score-assignment algorithms are fundamentally similar.Source: §3.1 · p. 6

3.2 Score Assignment

The score-assignment methods estimate node influence by aggregating contributions along paths up to length l. EaSyIM handles the opinion-oblivious case, and OSIM incorporates opinion change and interaction.

3.2 Score Assignment

  • Scores aggregate contributions from paths up to length l to rank nodes by expected spread, with l bounded by the graph diameter.The methods assume IC for their main description, with WC and LT extensions discussed separately.Source: §3.2 · p. 6, §3.2.1 · p. 6

3.2.1 EaSyIM

  • Counting simple paths is #P-complete, so Path-Union counts walks in O(n^3 log l) time and O(n^2) memory, but cyclic paths introduce score error.Path-Union weights edges by influence probabilities and removes contributions from walks that pass through the node itself.Source: §3.2.1 · pp. 6–7
  • EaSyIM computes each node’s score as a weighted sum of paths up to length l, multiplying edge influence probabilities along each path to approximate expected spread.Path contributions are accumulated from outgoing neighbors.Source: §3.2.1 · p. 7
  • EaSyIM score assignment takes O(D(m + n)) time and O(n) space; selecting k seeds takes O(kD(m + n)) time.The space bound reflects storing one score per node.Source: §3.2.1 · p. 7

3.2.2 OSIM

  • OSIM extends EaSyIM by tracking initial-opinion, interaction-probability, and opinion-change contributions, then aggregating them into each node’s score.It has the same time and space complexity as EaSyIM.Source: §3.2.2 · p. 7

3.3 Extensions

EaSyIM and OSIM extend to weighted cascade and linear threshold diffusion. The LT extension uses the live-edge model, which also removes score-assignment error from overlapping paths.

3.3 Extensions

  • For weighted cascade, the algorithms use p(u,v) = 1/|In(v)| for each edge and otherwise retain their existing form.This replaces the fixed influence probability used in IC.Source: §3.3 · p. 7
  • The LT extension uses its equivalent live-edge model, where each node has one live incoming edge, requiring no algorithm changes.The live-edge equivalence is attributed to Kempe et al..Source: §3.3 · p. 7
  • With one live incoming edge per node, each node pair has a unique path, removing score-assignment error from non-disjoint paths and enabling stronger LT analysis.The main score-assignment analysis assumes IC, with extensions to WC and LT discussed in the section’s analysis.Source: §3.3 · p. 7

3.4 Analysis of Score Assignment

The section analyzes when score-based greedy selection recovers expected spread, and where EaSyIM and OSIM scores remain faithful or incur errors. It establishes exact guarantees only under specified graph and diffusion-model settings.

3.4 Analysis of Score Assignment

  • When scores correctly capture each node’s expected spread, ScoreGREEDY matches GREEDY’s selected seeds and spread; such correct scoring is impossible for graphs generally.Source: §3.4 · p. 8

3.4.1 EaSyIM

  • EaSyIM’s score errors arise from overlapping, non-disjoint paths and cycles; the analysis separately bounds errors associated with DAG paths and cyclic paths.Source: §3.4.1 · pp. 8–9

3.4.2 Discussion

  • EaSyIM preserves GREEDY’s node ordering when its relative-error condition holds; when it does not, the authors report small errors and small overall impact on seed-set spread.Source: §3.4.2 · p. 10
  • For IC, path contributions shrink with length when ηp < 1, while higher average degree can increase error; the authors also analyze WC and report small error there.Source: §3.4.2 · p. 10
  • On tree-like structures, EaSyIM captures expected spread under IC, WC, and LT; on DAGs, it does so under LT, yielding ScoreGREEDY’s 1 −1/e guarantee in those settings.Source: §3.4.2 · p. 10

3.4.3 OSIM

  • The OSIM analysis fixes ϕ on DAGs and examines a single path; because the overall objective is neither submodular nor monotone, greedy selection cannot ensure a constant approximation.Source: §3.4.3 · pp. 10–11
  • For a path and penalty parameter λ = 1, OSIM’s node score captures that seed’s effective opinion spread along the path.Source: §3.4.3 · p. 11

4. EXPERIMENTS

Experiments use real and benchmark graphs, with opinion-aware and opinion-oblivious diffusion models and 10K Monte Carlo simulations for reported spreads. Across these settings, the authors report that OSIM and EaSyIM offer effective spread quality alongside practical time and memory use.

4.1.1 Real Data: Twitter

  • The Twitter analysis constructs topic-focused graphs by scanning tweets in timestamp order; one scan of the background graph suffices for construction.For unseen topics, estimated opinions have 3.43% error for seed nodes and 8.57% for other nodes.Source: §4.1.1 · pp. 12–13
  • OI yields the least error against ground-truth opinion-spread across the tested Twitter topic-graphs and varying seed counts.For Twitter and PAKDD churn analysis, OI-selected seeds also produce greater opinion-spread than OC- or IC-selected seeds.Source: Figure 5 · p. 13, §4.1.1 · p. 13

4.2 Opinion-Oblivious

  • EaSyIM is 10–15 times more efficient and uses 3-4 times less memory than CELF++, but takes 8–10 times more time while using ≈500 times less memory than TIM+.The authors summarize both algorithms as offering a strong time-memory trade-off for large graphs.Source: Figure 6 · p. 14, Table 4 · p. 15, Table 3 · p. 15

4.1.2 Real Data: Analyzing Customer Churn

  • OI-selected seeds yield greater opinion-spread than OC- or IC-selected seeds in the balanced 34K-customer churn analysis.The customer graph uses attribute-value similarity, label propagation to estimate churn opinions, and randomly generated interaction probabilities.Source: §4.1.2 · p. 14

4.1.3 Other Real Datasets

  • Under OI, λ = 1 outperforms λ = 0; OSIM’s spread improves as l grows, then dips near D as cyclic paths increase score error, making l = 3 the authors’ choice.OSIM closely matches Modified-GREEDY in opinion-spread quality.Source: §4.1.3 · pp. 14–15
  • OSIM is at least 10^3 times more efficient than Modified-GREEDY on NetHEPT, with gains reaching 10^5 in some cases.Its running time grows linearly with l; both algorithms’ memory use is independent of l, k, and the number of Monte Carlo simulations, and grows linearly with graph size.Source: §4.1.3 · p. 15

4.2 Opinion-Oblivious

  • EaSyIM closely matches state-of-the-art spread on most datasets and sometimes performs better; l = 3 is marginally worse than l = 5 but about twice as efficient.TIM+ crashed on DBLP at a plotted point, so that comparison is not available there.Source: §4.2 · p. 15
  • EaSyIM’s spread improves with l and then dips near D; l = 5 gives the best spread, while l = 3 is marginally worse and about twice as efficient.For comparison with other algorithms, the authors fix l = 3 as the quality-efficiency trade-off.Source: §4.2 · p. 15

5. RELATED WORK

Related work covers topic-aware and competitive influence maximization, signed networks, and classical influence-maximization algorithms. The authors distinguish OI by its real-valued opinions and interactions, while contrasting EaSyIM’s scalability with existing methods.

Topic-Aware and Competitive IM

  • Topic-aware and competitive IM optimize spread without node opinions; both omit negative activations and opinion changes during propagation.Competitive IM also assumes nodes strictly propagate a particular content, keeping its objective closer to classical node-count spread.Source: §5 · pp. 15–16

IM in signed networks

  • Unlike signed-network models with binary opinions, OI permits real-valued opinions and probabilistic interactions; the signed-network voter model is a special case of OI.Source: §5 · p. 16

Classical IM

  • Classical greedy IM is costly; sampling methods such as TIM+ improve efficiency but can require high memory, while EaSyIM is designed for linear time and space.The paper also characterizes CELF++ as the most efficient greedy optimization and IRIE and SIMPATH as state-of-the-art heuristics that do not scale to larger datasets in its experiments.Source: §5 · p. 16

6. CONCLUSIONS AND FUTURE WORK

The paper presents OI, OSIM, and EaSyIM for influence maximization when nodes may hold positive, neutral, or negative opinions. It reports linear-time and linear-space algorithms and empirical effectiveness on real-world datasets.

6. CONCLUSIONS AND FUTURE WORK

  • OI models positive, neutral, and negative opinions, and the paper introduces MEO alongside OSIM and EaSyIM as a holistic influence-maximization solution.Source: §6 · p. 16
  • The authors report linear-time and linear-space algorithms, strong empirical trade-offs between running time and memory, and practical use on large real graphs.A distributed version is proposed as future work to scale to even larger graphs.Source: §6 · p. 16

A. MODIFIED-GREEDY ALGORITHM

The excerpt presents Modified-GREEDY as an algorithm for selecting a seed set from a graph under a seed budget.

A. MODIFIED-GREEDY ALGORITHM

B. ADDITIONAL EXPERIMENTAL RESULTS

The additional experiments compare opinion-spread quality, running time, and memory use across datasets and diffusion models. They report advantages for effective opinion-spread and efficient, scalable algorithms.

B. ADDITIONAL EXPERIMENTAL RESULTS

C. ADDITIONAL NOTE ON CELF++

CELF++ uses a lazy-forward optimization for seed selection, together with a rule that skips nodes that cannot become seeds in later iterations.

C. ADDITIONAL NOTE ON CELF++

  • Lazy-forward selection ranks nodes by seed probability from prior-iteration marginal gains and skips nodes with no chance of later selection.The passage describes these optimizations as reducing the algorithm’s running time.Source: C. ADDITIONAL NOTE ON CELF++ · p. 18
Loading 1602.03110v1…