PaperlayerView exact revision on arXiv

Source-linked AI summary

From Competition to Complementarity: Comparative Influence Diffusion and Maximization

Wei Lu, Wei Chen, Laks V. S. Lakshmanan

arXiv:1507.00317v3cs.SIphysics.soc-ph

TL;DR

Influence maximization has largely modeled single entities or pure competition, leaving complementary adoption insufficiently represented. The paper introduces Com-IC and two complementary-item optimization problems, then develops RR-set and Sandwich Approximation methods. The resulting algorithms outperform intuitive baselines across four real-world social networks, while GAP parameters are learned from user action logs.

  • Problem

    Prior influence-diffusion models largely focus on single entities or pure competition, which cannot represent users adopting complementary products together.

  • Method

    Com-IC combines edge-level information propagation with a GAP-governed Node-Level Automaton, and uses extended RR-set techniques plus Sandwich Approximation for SelfInfMax and CompInfMax.

  • Results

    The proposed approximation algorithms consistently outperform intuitive baselines on four real-world social networks, and GAPs are learned from user action logs.

  • Takeaways & Limitations

    Com-IC provides a diffusion framework spanning competition and complementarity, with approximation techniques intended to extend beyond the studied model and problems.

  • Takeaways & Limitations

    Extending Com-IC to multiple items may require k · 2^k−1 GAP parameters, and simplifying that model remains an open direction.

Abstract

from arXiv · show

Influence maximization is a well-studied problem that asks for a small set of influential users from a social network, such that by targeting them as early adopters, the expected total adoption through influence cascades over the network is maximized. However, almost all prior work focuses on cascades of a single propagating entity or purely-competitive entities. In this work, we propose the Comparative Independent Cascade (Com-IC) model that covers the full spectrum of entity interactions from competition to complementarity. In Com-IC, users' adoption decisions depend not only on edge-level information propagation, but also on a node-level automaton whose behavior is governed by a set of model parameters, enabling our model to capture not only competition, but also complementarity, to any possible degree. We study two natural optimization problems, Self Influence Maximization and Complementary Influence Maximization, in a novel setting with complementary entities. Both problems are NP-hard, and we devise efficient and effective approximation algorithms via non-trivial techniques based on reverse-reachable sets and a novel "sandwich approximation". The applicability of both techniques extends beyond our model and problems. Our experiments show that the proposed algorithms consistently outperform intuitive baselines in four real-world social networks, often by a significant margin. In addition, we learn model parameters from real user action logs.

1 Introduction

The paper addresses the limits of single-entity and pure-competition diffusion models by introducing Com-IC, which represents competition and complementarity through edge propagation and node-level adoption decisions. It formulates two complementary-item maximization problems and develops approximation methods evaluated on real networks.

  • Motivation: Existing influence-diffusion research largely studies single entities or pure competition, excluding users’ adoption of multiple complementary products.The paper uses the iPhone–Apple Watch example to illustrate why pure-competition models cannot represent complementary adoption.
  • Com-IC model: Com-IC combines edge-level information propagation with a Node-Level Automaton governed by Global Adoption Probabilities.The automaton makes adoption decisions after users become aware of multiple products and can represent arbitrary interaction degrees.
  • Optimization problems: SelfInfMax selects A-seeds to maximize A adoption given fixed B-seeds, while CompInfMax selects B-seeds to increase A adoption given fixed A-seeds.These problems target complementary products, with the second measuring the benefit that B provides to A.
  • Theory: Both problems are NP-hard, and unrestricted Com-IC lacks the submodularity and monotonicity properties that support standard greedy approximation.Submodularity can still fail under mutual complementarity.
  • Algorithms: Extensions of Reverse-Reachable Set techniques and the novel Sandwich Approximation provide efficient approximation solutions for the two problems.The techniques are presented as applicable beyond the specific model and optimization problems studied here.
  • Evaluation: Experiments on four real-world social networks show that the proposed algorithms consistently outperform intuitive baselines, while GAPs can be learned from user action logs.The paper learns parameters using logs from Flixster.com and Douban.com.

2 Background & Related Work

Classical influence maximization is NP-hard but benefits from monotone submodular spread, whereas related multi-entity work has largely focused on pure competition or restricted complementarity. These limitations motivate more expressive diffusion modeling.

  • Classical influence maximization: In IC and LT, influence maximization seeks k seeds maximizing expected active nodes, and exact spread computation is #P-hard.The spread function is nevertheless monotone and submodular under both models.
  • Approximation methods: Monotone submodularity enables greedy influence maximization with a 1−1/e−ϵ approximation, while randomized RR-set methods improve computational efficiency.The cited randomized methods are described as orders of magnitude faster than original greedy algorithms.
  • Competitive diffusion: Competitive influence maximization commonly assumes pure competition, allowing each user to adopt at most one product or opinion.Many formulations optimize one party’s spread given competitor seeds or seek to minimize a competitor’s spread.
  • Complementary diffusion: Prior non-competing models include independent item propagation and a model requiring one product before adoption of a corresponding product in another set.The latter covers only perfect complementarity, unlike the broader interaction range targeted by Com-IC.

3 Comparative Independent Cascade Model

Com-IC separates information diffusion from adoption decisions: edges transmit product awareness, while a node-level automaton uses state and GAP parameters to determine transitions. Its GAPs represent competition or complementarity between products.

  • Model structure: Unlike IC, Com-IC models at least two products, with each node independently occupying idle, suspended, adopted, or rejected states for each product.All nodes begin in the joint state (A-idle, B-idle).
  • Model structure: Edges control information flow, while each node’s NLA determines state transitions using its current two-product state and transition probabilities.This separates awareness from the actual adoption decision.
  • Global Adoption Probabilities: The NLA uses four GAP parameters: qA|∅, qA|B, qB|∅, and qB|A.Each parameter specifies adoption likelihood for one product depending on whether the user has adopted the other.
  • Global Adoption Probabilities: GAPs are aggregate, non-user-specific estimates intended to reflect product popularity and market perception, and they can be learned from action logs.The paper describes GAPs as parameters of the NLA rather than individual user attributes.
  • Interaction relationships: A product competes with another when adoption probability decreases after adopting the other, and complements it when that probability increases.For example, A competes with B when qB|A ≤ qB|∅ and complements B when qB|A ≥ qB|∅.
  • Diffusion dynamics: Diffusion starts with A- and B-seeds adopted, then repeatedly tests live outgoing edges and affected nodes for information-driven state transitions.Tie-breaking handles simultaneous attempts by different products, while reconsideration can enable later adoption when products are complementary.
  • Relationship to prior models: Com-IC contains classic IC and purely competitive IC as special cases under particular GAP assignments.With qA|∅=qB|∅=1 and qA|B=qB|A=0, it reduces to competitive IC; setting qB|∅=0 further yields classic IC.

4 Formal Problem Statements

The paper formulates SelfInfMax and CompInfMax for complementary propagating entities under Com-IC, and establishes their computational difficulty and a special-case optimal solution.

  • SelfInfMax: SelfInfMax selects k A-seeds to maximize expected A-adoptions given fixed B-seeds.
  • Complexity: SelfInfMax is NP-hard because it subsumes classical IC influence maximization when B is absent and A-adoption probabilities equal one.
  • CompInfMax: CompInfMax selects k B-seeds to maximize the boost in expected A-adoptions given fixed A-seeds.
  • Complexity: CompInfMax is NP-hard through a reduction from IC influence maximization using dummy copies of graph nodes and fixed A-seeds.
  • Special case: When qB|∅ = 1 and k ≥ |SA|, CompInfMax is solved optimally by including all A-seeds among the B-seeds.

5 Properties of Com-IC

Com-IC combines stochastic edge propagation with node-level adoption rules, representing competition and complementarity through GAPs. Its monotonicity and submodularity properties hold only under specific parameter regimes.

  • Possible-world model: Com-IC represents each possible world with sampled live edges and node-level variables, making the cascade deterministic within that world.
  • Possible-world model: The possible-world formulation is distributionally equivalent to Com-IC for the sets of A- and B-adopted nodes.
  • Monotonicity: Under mutual competition or mutual complementarity, A-spread is monotone in A-seeds; B-seeds decrease it under competition and increase it under complementarity.
  • Submodularity: Self-submodularity holds under one-way complementarity, while cross-submodularity holds under mutual complementarity when qB|A = 1; these properties fail generally.

6 Approximation Algorithms

The approximation framework generalizes reverse-reachable sets through possible-world models and applies when activation is monotone and submodular. Specialized RR procedures support SelfInfMax under one-way complementarity.

  • General framework: General RR-sets contain nodes whose singleton activation reaches a sampled root in a possible world.
  • General framework: The Activation Equivalence Property equates cascade activation probability with the probability that the seed set overlaps a random RR-set.
  • General framework: When every possible-world activation indicator is monotone and submodular, GeneralTIM returns a (1−1/e−ϵ)-approximate solution with probability at least 1−|V|^-ℓ.
  • SelfInfMax algorithms: RR-SIM constructs SelfInfMax RR-sets by exploiting independence of B-diffusion from A-seeds under one-way complementarity.
  • SelfInfMax algorithms: GeneralTIM with RR-SIM has expected running time O((k + ℓ)(|V| + |E|) log |V| (1 + EPT_F/EPT_B)).

2 Q.enqueue(v); // first backward BFS

RR-SIM+ uses two backward BFS rounds to restrict forward labeling and then generate the RR-set, while preserving the B-adoption determinations of RR-SIM.

  • First backward BFS: The first backward BFS from a random root identifies the explored scope used to restrict subsequent processing.
  • Residual forward labeling: RR-SIM+ skips forward labeling when the first explored region contains no B-seeds; otherwise it performs residual labeling from the intersecting B-seeds.
  • Efficiency: RR-SIM+ is at least twice faster than RR-SIM on three of four datasets, although its worst case can waste the first round.
  • Second backward BFS: The second backward BFS generates the RR-set and tests incoming edges not resolved during the first round.
  • Correctness: For nodes backward-reachable from the root through live edges, RR-SIM and RR-SIM+ determine B-adoption identically.

4 Q.enqueue(v) // Q initialized as an empty FIFO queue

The CompInfMax RR-CIM procedure combines forward labeling with primary and secondary backward searches to identify B-seeds that can induce A-adoption. It is paired with Sandwich Approximation for cases where submodularity may fail.

  • RR-set construction: CompInfMax RR-sets contain nodes whose single B-seed can change a root from not A-adopted to A-adopted.This definition drives the more complex RR-set construction from fixed A-seeds.
  • Forward labeling: Forward labeling distinguishes A-adopted, A-suspended, A-rejected, and A-potential statuses before RR-set generation.A-potential is bookkeeping rather than a node state, and nodes may be promoted from A-potential to A-suspended.
  • Backward searches: The primary backward search traces paths through AB-diffusible and A-potential nodes, while secondary searches recover nodes that can propagate B to qualifying A-suspended nodes.Secondary searches proceed through B-diffusible nodes and stop expanding at non-B-diffusible nodes.
  • Backward searches: Case 4 stops the primary search at an A-potential, non-AB-diffusible node except when a B-diffusible path and return path justify adding it to the RR-set.This special treatment captures a cycle in which the node can activate an A-suspended, AB-diffusible node that reaches back to it.
  • Guarantee: The RR-CIM construction is correct under qA|∅≤qA|B and qB|∅≤qB|A = 1, so the GeneralTIM guarantee applies in that setting.The theorem establishes that the generated RR-sets satisfy the CompInfMax definition under these parameter restrictions.
  • Sandwich Approximation: Sandwich Approximation supplies submodular upper and lower bounds for non-submodular objectives and is incorporated into the final SelfInfMax and CompInfMax algorithms.Its effectiveness depends on how close the bounds are to the original objective; a trivial upper bound can yield trivial factors.

7 Experiments

Experiments evaluate the proposed algorithms on real-world networks using synthetic and learned GAPs, comparing them with intuitive baselines across seed-selection settings. GeneralTIM generally achieves stronger influence spread, substantial speedups, and scalable performance, while sandwich approximation remains effective in non-submodular cases.

  • Experimental Setup: Experiments use three real-world social networks, synthetic GAPs, and GAPs learned from timestamped action logs.The evaluation includes Flixster, Douban, and Last.fm data, with Douban-Book and Douban-Movie derived separately.
  • Seed Quality: GeneralTIM consistently outperforms VanillaIC and Copying across most test cases and opposite-seed selection methods, often by a large margin.The tested opposite seed sets are random nodes, top VanillaIC nodes, or moderately influential VanillaIC-ranked nodes.
  • Quality of Seeds: 13%, 2.7%, 100%, and 13% are SelfInfMax improvements over the next-best algorithm on Douban-Book, Douban-Movie, Flixster, and Last.fm; CompInfMax improvements are 31%, 31%, 122%, and 51%.These results use GeneralTIM with RR-SIM+ for SelfInfMax and RR-CIM for CompInfMax.
  • Running Time and Scalability: GeneralTIM with RR-SIM or RR-SIM+ is about two to three orders of magnitude faster than Greedy for SelfInfMax, while RR-CIM is about two orders faster for CompInfMax.RR-SIM+ is also 12, 8, 7, and 2 times as fast as RR-SIM on Douban-Book, Douban-Movie, Flixster, and Last.fm.
  • Running Time and Scalability: RR-SIM+ completes within 6.2 hours on a 1-million-node graph and grows linearly with graph size; RR-CIM also scales linearly.Greedy takes about 48 hours on Flixster, whereas RR-CIM is four hours faster on a graph ten times as large.
  • Sandwich Approximation: Sandwich approximation is effective and robust for non-submodular SelfInfMax and CompInfMax, with the largest observed error of 0.4% in an adversarial Flixster setting.Results on other datasets are reported as very similar.

8 Conclusions & Future Work

The paper presents Com-IC and two complementary-item influence-maximization problems, supported by approximation methods and empirical evaluation. It also identifies open challenges involving algorithm efficiency, model tractability, multiple items, and parameter learning.

  • Contributions: Com-IC models arbitrary degrees of competition or complementarity between two propagating items, while SelfInfMax and CompInfMax optimize complementary-product diffusion.The framework combines extensions of reverse-reachable-set techniques with a sandwich approximation for non-submodular settings.
  • Contributions: Reverse-reachable-set extensions and Sandwich Approximation provide approximation algorithms for the proposed optimization problems.The paper reports that the experiments demonstrate the effectiveness and efficiency of the proposed solutions.
  • Future Work: Near-linear-time algorithms for SelfInfMax and especially CompInfMax remain open future-work questions.The conclusion specifically calls for more efficient algorithms or heuristics.
  • Future Work: Extending Com-IC to multiple items would require k · 2^k−1 GAP parameters, while tractability and multi-way interaction analysis remain challenges.The paper also leaves learning GAP parameters from real-world data as an open direction in the multiple-item setting.

A.2 Counter-Examples for Submodularity and Monotonicity

The counter-examples show that unrestricted Com-IC lacks general monotonicity and submodularity guarantees, including under mutual complementarity. Carefully constructed propagation and adoption interactions can reverse expected marginal behavior.

  • Monotonicity: Unrestricted Com-IC does not generally satisfy self-monotonicity or cross-monotonicity.The counter-examples establish that adding seeds can change adoption interactions in ways that violate these properties.
  • Monotonicity: In a mixed interaction example, adding an A-seed can reduce A-spread because it blocks B-propagation even though B complements A.The reported construction uses qB|A < qB|∅ and qA|B > qA|∅.
  • Monotonicity: Growing the B-seed set can increase A-spread in a possible world, so cross-monotonicity need not hold when A complements B but B competes with A.The gadget exploits reduced B adoption at an intermediate node, removing competition that previously prevented downstream A adoption.
  • Submodularity: Even mutually complementary items can violate self-submodularity: an additional A-seed helps more after another A-seed is already present.The construction states that only T ∪ {u}, not S ∪ {u}, causes v to become A-adopted.
  • Submodularity: Mutual complementarity can also violate cross-submodularity, with an additional B-seed becoming effective only after another B-seed is present.The counter-example states that v becomes A-adopted only for SB = T ∪ {u}.

B.1 Proofs for Results in Section 4

For CompInfMax, when qB|∅ = 1 and k ≥ |SA|, assigning B-seed status to the fixed A-seeds already converts every node that can possibly become A-adopted. Therefore, remaining B-seeds cannot improve the objective.

  • Optimality Result: When qB|∅ = 1 and k ≥ |SA|, CompInfMax is solved optimally by choosing S*B = SA ∪ X, with |X| = k − |SA|.X may be any set of additional nodes outside SA.
  • Proof Strategy: Under A-seeds alone, only A-suspended and A-potential nodes can later adopt A with help from B.A-adopted and A-rejected nodes are irrelevant to CompInfMax in the proof.
  • Proof Strategy: Making every A-seed also a B-seed converts all A-suspended and A-potential nodes reachable through live-edge paths.A-suspended nodes adopt A after B-triggered reconsideration, while A-potential nodes adopt both items when reached.
  • Optimality Result: Because every node that can possibly be converted is already converted, any additional B-seed cannot further increase A-spread.The argument holds in each possible world and therefore establishes the optimization result.

B.2 Proofs for Results in Section 5

The proofs establish that Com-IC can be analyzed through an equivalent possible-world cascade model. This equivalence supports monotonicity results: A-spread increases with A-seeds, and its response to B-seeds follows the interaction regime.

  • Possible-World Equivalence: Com-IC and the possible-world model produce the same joint distribution of A-adopted and B-adopted nodes for fixed seed sets.The proof uses deferred decisions to match edge transitions, node adoption decisions, reconsideration, tie-breaking, and seeding.
  • Possible-World Equivalence: Reconsideration probabilities in the possible-world model match Com-IC through ρA = max{qA|B − qA|∅, 0}/(1 − qA|∅).When qA|B < qA|∅, reconsideration is meaningless and corresponds to ρA = 0.
  • Monotonicity: For fixed B-seeds, A-spread is monotonically increasing in A-seeds for both mutual complementarity and mutual competition.The theorem also characterizes how B-seeds affect A-spread under those two regimes.
  • Monotonicity: Under mutual complementarity, A-spread increases with B-seeds; under mutual competition, it decreases with B-seeds.The result is stated for any GAPs in the corresponding Q+ and Q− classes.
  • Monotonicity: The symmetric result makes B-spread increasing in B-seeds, increasing in A-seeds under complementarity, and decreasing in A-seeds under competition.This follows the corresponding symmetric formulation of the monotonicity theorem.

B.3 Proofs for Results in Section 6

These proofs establish when possible-world activation admits reverse-reachable-set characterizations, enabling the proposed influence algorithms and their approximation analyses. They also provide applicability conditions and expected running-time bounds for RR-based implementations.

  • Activation properties: Monotonicity and submodularity of each possible-world activation indicator hold exactly when Properties (P1) and (P2) are satisfied.This characterization underpins the reverse-reachable-set analysis.
  • Activation properties: If Properties (P1) and (P2) hold, reverse-reachable sets have the activation equivalence property needed by the analysis.A seed set activates a node exactly when it intersects the node’s reverse-reachable set.
  • SelfInfMax: Under one-way complementarity, RR-SIM satisfies the required reverse-reachable-set definition for SelfInfMax, so Theorem 6 applies.The condition is qA|∅≤qA|B and qB|∅=qB|A.
  • Running time: In expectation, GeneralTIM with RR-SIM runs in O((k + ℓ)(|V| + |E|) log |V| (1 + EPT_F/EPT_B)) time.The stated bound accounts for the forward and backward expected propagation quantities.
  • CompInfMax: When qA|∅≤qA|B and qB|∅≤qB|A=1, RR-CIM satisfies the required definition for CompInfMax, so Theorem 6 applies.The proof characterizes activation through live-edge paths containing A-adopted, A-suspended, or B-diffusible nodes.

B.4 Submodularity Analysis for Competitive Cases of Com-IC

For competitive Com-IC cases, cross-submodularity can hold even while ordinary submodularity fails. The analysis gives a counterexample outside the fully certain-adoption regime and a positive submodularity result when both unconditional adoption probabilities equal one.

  • Cross-submodularity: Cross-submodularity means an additional B-seed causes a larger decrease in A’s spread when added to a smaller B-seed set.This property is relevant to influence blocking maximization.
  • Counterexample: When qA|∅=qB|∅=1 and qA|B=qB|A=0, Com-IC reduces to homogeneous CIC, where monotonicity and submodularity hold; outside this setting, submodularity can fail.The paper gives a counterexample in the general Q− setting.
  • Counterexample: In Example 5, A-seeds s2 and s3 together can block B completely, allowing s1 to activate v with an additional probability of (1−q)·q6.Either s2 or s3 alone cannot block B, so s1’s influence does not reach v in those cases.
  • Counterexample: Replicating v sufficiently many times makes the non-submodularity occur for the entire graph.The counterexample therefore extends from the local construction to graph-level influence spread.
  • Positive result: When qA|∅=qB|∅=1, σA(SA,SB) is submodular with respect to SA for any fixed SB.This is the stated positive result for competitive cases of Com-IC.
Loading 1507.00317v3…