PaperlayerView exact revision on arXiv

Source-linked AI summary

Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model Technical Report

Xinran He, Guojie Song, Wei Chen, Qingye Jiang

arXiv:1110.4723v1cs.SIphysics.soc-ph

TL;DR

The paper studies how to block competing influence by selecting positive seed nodes under a competitive linear threshold model. It proves submodularity, designs CLDAG to avoid slow greedy evaluation, and reports comparable blocking with substantially faster running time.

  • Problem

    The paper asks how to select positive seeds to minimize or block a competing negative influence in social networks.

  • Method

    The paper formulates IBM under CLT, proves monotonicity and submodularity, and designs CLDAG using efficient LT computation properties.

  • Results

    CLDAG matches greedy blocking performance while achieving at least two orders of magnitude speedup in running time.

  • Takeaways & Limitations

    CLDAG is reported as a stable and robust algorithm for IBM and outperforms other tested heuristic algorithms.

  • Takeaways & Limitations

    The paper identifies faster, more space-efficient algorithms and competitive diffusion models without submodularity as future directions.

Abstract

from arXiv · show

In many real-world situations, different and often opposite opinions, innovations, or products are competing with one another for their social influence in a networked society. In this paper, we study competitive influence propagation in social networks under the competitive linear threshold (CLT) model, an extension to the classic linear threshold model. Under the CLT model, we focus on the problem that one entity tries to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate its own influence propagation. We call this problem the influence blocking maximization (IBM) problem. We prove that the objective function of IBM in the CLT model is submodular, and thus a greedy algorithm could achieve 1-1/e approximation ratio. However, the greedy algorithm requires Monte-Carlo simulations of competitive influence propagation, which makes the algorithm not efficient. We design an efficient algorithm CLDAG, which utilizes the properties of the CLT model, to address this issue. We conduct extensive simulations of CLDAG, the greedy algorithm, and other baseline algorithms on real-world and synthetic datasets. Our results show that CLDAG is able to provide best accuracy in par with the greedy algorithm and often better than other algorithms, while it is two orders of magnitude faster than the greedy algorithm.

1 Introduction

The paper addresses competitive influence diffusion by formulating influence blocking maximization under the competitive linear threshold model. It proves useful optimization structure, proposes CLDAG for efficiency, and evaluates it against greedy and heuristic methods.

  • Problem motivation: Influence blocking maximization selects positive seeds to reduce or block a competing negative influence.The setting includes competing commercial, political, rumor, and public-safety information campaigns.
  • Problem and theory: Under the CLT model, IBM is monotone and submodular, enabling a greedy algorithm with approximation ratio 1 −1/e −ϵ.The greedy method relies on Monte-Carlo simulations of competitive propagation.
  • Algorithmic response: CLDAG uses efficient computation properties of the linear threshold model on directed acyclic graphs to address greedy evaluation cost.On a 6.4k-node network, the greedy algorithm took more than 8 hours in simulation.
  • Novelty: The paper claims to be the first study of IBM under the competitive linear threshold model.Earlier work closest to it studied an extension of the independent cascade model and did not address efficiency.

2 Related Work

Prior work studied competitive diffusion through several models, dynamics, optimization problems, and game-theoretic perspectives. The paper distinguishes its CLT-based IBM formulation from IC-based approaches with restricted submodularity or limited scalability.

  • Competitive diffusion models: Competitive diffusion research has extended IC, LT, voter, epidemic, and related models, but studies differ in objectives and supported graph settings.Some works study dynamics or hardness rather than influence maximization.
  • Optimization focus: Several prior studies focus on one competing party’s influence maximization or on game-theoretic aspects of competition.The paper instead focuses on blocking an opposing influence.
  • Closest related work: An IC extension with separate positive and negative propagation parameters is not submodular in general.Its authors restrict propagation probabilities to recover submodularity, limiting model expressiveness.

3 Competitive Linear Threshold Model

The competitive linear threshold model extends LT by allowing positive and negative influence to propagate concurrently with separate weights and thresholds. Nodes become permanently positive, negative, or remain inactive, with negative activation winning ties.

  • Classic LT model: The classic LT model represents a social network as a weighted directed graph with independently sampled vertex thresholds.Seeds activate initially, and inactive vertices activate when incoming active-neighbor weight reaches their thresholds.
  • Competitive extension: CLT assigns each vertex three permanent states: inactive, +active, and -active.Positive and negative influence use separate edge weights and thresholds.
  • Tie breaking: When both influences activate a vertex in the same step, negative activation dominates.The paper notes that an alternative random tie-breaking rule would preserve the relevant submodularity and algorithmic results with adaptation.
  • Propagation: Positive and negative diffusion propagate independently from disjoint seed sets at each time step.A vertex activated by only one process takes that process’s state.

4 Influence Blocking Maximization Problem

The paper defines IBM as maximizing expected negative influence reduction under CLT, proves the problem NP-hard and its objective monotone and submodular, then derives a greedy approximation and motivates CLDAG to overcome simulation costs.

  • Problem definition: IBM chooses at most k positive seeds to maximize the expected number of nodes whose negative activation is prevented.The negative seed set is fixed, while positive seeds determine the blocking set.
  • Computational complexity: The exact IBM problem is NP-hard under the CLT model.The paper states this through a reduction from vertex cover.
  • Equivalent process: A random live-path graph produces the same distribution of positive and negative activation sets as the CLT process.This equivalence lets the proof analyze blocking through reachability and shortest-path distances.
  • Submodularity: The negative influence reduction function is monotone and submodular under CLT.The live-path blocking-set cardinality is also monotone and submodular, supporting the CLT result.
  • Approximation and efficiency: The greedy algorithm achieves a 1 −1/e approximation but requires costly Monte-Carlo evaluation of competitive propagation.This makes greedy unacceptable for large graphs and motivates CLDAG.

5 CLDAG Algorithm for the IBM Problem

CLDAG computes competitive activation locally by constructing separate positive and negative LDAGs and using dynamic programming that accounts for propagation timing and interference. It then integrates these computations into greedy positive-seed selection while exploiting local DAG structure for efficiency.

  • 5.1 Influence computation.: The LDAG threshold θ controls local-structure size: smaller θ produces larger LDAGs, and nodes are included when their influence to v reaches θ.LDAG construction uses the linear activation-probability relationship in DAGs to update influence values from in-neighbors.
  • 5.1 Influence computation.: Inf-CLDAG computes exact positive and negative activation probabilities for a central node using separate LDAG+(v) and LDAG−(v) structures.The CLT model requires separate positive- and negative-weight LDAGs because the two cascades propagate concurrently and interfere.
  • 5.1 Influence computation.: The dynamic program uses boundary conditions for positive seeds, negative seeds, and nonseed nodes, enabling exact activation probabilities for every node.Positive and negative seed states are initialized at time 0, while nonseed probabilities begin at zero.
  • 5.1 Influence computation.: With careful planning, the dynamic-programming computation is reduced from O(m_Dℓ_D) to O(m_D) time for a node’s local structures.Here m_D is the combined LDAG size and ℓ_D is the longest path length in the two LDAGs.
  • 5.1 Influence computation.: Alternating BFS traversals over LDAG−(v) and LDAG+(v) compute time-indexed activation probabilities while incorporating interference between competing cascades.The procedure alternates one layer from negative seeds with one layer from positive seeds, using earlier probabilities in subsequent updates.
  • 5.2 CLDAG algorithm.: CLDAG plugs negative-influence reduction into greedy positive-seed selection and updates only candidates affected through local DAG structures.The algorithm constructs LDAG+(v), LDAG−(v), and OutLS+(v), then updates DecInf values for nodes whose positive influence can reach affected targets.

6 Experiments

Experiments on real-world and synthetic networks evaluate CLDAG against greedy and heuristic baselines for influence blocking under the CLT model. CLDAG matches greedy blocking performance while offering substantially faster and scalable execution, with performance depending on negative-seed placement and propagation strength.

  • Experiment setting: Experiments use three real-world networks and synthetic power-law graphs to evaluate CLDAG's efficiency and effectiveness.The real-world data include a mobile call network and collaboration networks; synthetic graphs range from 0.2K to 6.4K nodes.
  • Experiment setting: The evaluation compares CLDAG with Greedy, Degree, Random, and Proximity Heuristic baselines using repeated stochastic simulations.Blocking effects are averaged over 1000 trials; negative seeds are selected either randomly or by largest degree.
  • Results with the greedy algorithm: CLDAG consistently matches greedy blocking performance on the 1000-node mobile and 5000-node NetHEPT comparisons.On the mobile graph, CLDAG completely blocks negative influence with 130 seeds, while Proximity still allows influence to reach about 30 more nodes; on NetHEPT, Proximity performs similarly.
  • Results with the greedy algorithm: More than two orders of magnitude speedup lets CLDAG select 200 seeds in one minute on 5000 nodes, whereas Greedy takes more than five hours.On synthetic power-law graphs, CLDAG's running time has a linear relationship with graph size.
  • Results on larger datasets: Across larger real-world tests, CLDAG outperforms Proximity by 78.24% for random negative seeds and 80.75% for max-degree negative seeds on average.Degree and Random show no blocking effect in these test cases, while CLDAG maintains consistently low running time.
  • Propagation-rate effects: CLDAG is especially superior when negative diffusion is strong, whereas Proximity performs close to CLDAG when negative diffusion is weak.With stronger negative diffusion, negative influence can traverse long paths, reducing the effectiveness of placing positive seeds only beside negative seeds.
  • Effectiveness at different negative seed sizes: Reducing negative influence to about 10% requires roughly 20 to 30 times as many positive seeds, and blocking becomes increasingly difficult as negative seed count grows.With 1000 negative seeds and 1000 positive seeds, the experiments reduce negative influence by only 17%.

7 Conclusion and Discussions

The paper establishes submodularity for influence blocking maximization under CLT, introduces CLDAG for efficiency, and reports comparable blocking with substantially faster runtime than greedy methods.

  • CLDAG matches the greedy algorithm's blocking effect while significantly improving running time.
  • CLDAG outperforms proximity heuristic and is described as stable and robust for IBM.
  • The CLT model allows different diffusion strengths to be modeled and evaluated through separate positive and negative weights.
  • Unlike positive-influence maximization, IBM is submodular under the CLT model, despite related work finding non-submodularity for that maximization problem.
  • The paper identifies faster, more space-efficient IBM algorithms and extensions to competitive diffusion models without submodularity as future directions.

A Proof of Theorem 4.1

The NP-hardness proof reduces vertex cover to IBM by constructing a directed graph with spindle and chain structures. The construction makes selecting appropriate bottom nodes encode vertex-cover solutions and their blocking gains.

  • Proof strategy: The proof reduces the NP-complete vertex cover problem to IBM under the CLT model.
  • Graph construction: For each original vertex, the construction adds a spindle structure and a chain sharing that vertex, producing a graph of size O(|V|^2).
  • Graph construction: The bottom nodes reproduce the original graph with bidirectional positive edges, while chains extend from the shared vertices.
  • Graph construction: Each spindle has a negative-seed top node, |V| intermediate nodes, and a bottom node connected through negative edges.
  • Seed-selection lemma: A bottom node is always a better positive seed than an intermediate or chain node when its step-1 positive activation probability is below 1.
  • Reduction consequence: A vertex cover of size k deterministically achieves σNIR(S) = |V|(ℓ + 1), and reaching at least this value requires bottom-node seeds forming a vertex cover.
Loading 1110.4723v1…