Location-Based Seeds Selection for Influence Blocking Maximization in Social Networks

Wenlong Zhu, Wu Yang, Shichang Xuan, Dapeng Man, Wei Wang, Xiaojiang Du, Mohsen GuizaniIEEE Access 2019 · DOI

Introduction

Influence Maximization (IM) is a cornerstone of social network analysis, focusing on identifying a set of "seed" nodes to trigger a large-scale information cascade. Its competitive counterpart, Influence Blocking Maximization (IBM), addresses the challenge of containing undesirable information—such as rumors or misinformation—by strategically spreading "truth" or competing messages. While traditional IBM models assume a location-agnostic network, real-world influence often has a strong geographical component. This paper introduces the Location-Based Seeds Selection for Influence Blocking Maximization (LSSIBM) problem, which integrates spatial constraints into the rumor-blocking framework.

The LSSIBM Problem

Most existing IBM research overlooks the physical location of users. However, in scenarios like local government interventions or regional marketing, the "block region" (where the rumor must be stopped) and the "query region" (where influencers can be recruited) are often distinct and geographically bounded.

Illustration of the LSSIBM problem showing query regions ($R^Q$) for seed selection and block regions ($R^B$) for rumor containment.

The authors identify two primary challenges in solving LSSIBM:

  1. The Location Gap: Integrating spatial restrictions into the seed selection process and the evaluation of blocking effectiveness.
  2. The Efficiency Gap: The standard "Greedy" approach for IBM relies on computationally expensive Monte Carlo simulations, making it impractical for large-scale social networks.

Methodology

The authors prove that LSSIBM is NP-hard and demonstrate that the influence function is monotone and submodular. To overcome the efficiency gap, they propose two heuristic algorithms, IS-LSS and IS-LSS+, which move away from simulations toward structure-based estimation.

Spatial Indexing and Influence Estimation

  • Quadtree Indexing: To manage geographical constraints, the authors employ a Quadtree to index users. This structure enables rapid identification of candidate seeds within a query region and target nodes within a block region.
  • Maximum Influence Arborescence (MIA): Instead of simulating thousands of propagation scenarios, the algorithms use MIA to approximate influence. MIA focuses on the most probable propagation paths (arborescences) between nodes, drastically reducing the computational overhead.

Proposed Algorithms

  • IS-LSS: This heuristic integrates Quadtree indexing with MIA to calculate the "Blocked Negative Influence" (BNI) for potential seeds.
  • IS-LSS+: An optimized variant that introduces Cell Lists and an Upper Bound method. By precomputing the potential influence of entire Quadtree cells, the algorithm can prune large numbers of sub-optimal candidates without evaluating them individually, further accelerating the selection process.

Experimental Evaluation

The study evaluates the proposed methods using three real-world datasets: Ego-Facebook (4,039 nodes), Brightkite (58K nodes), and Gowalla (197K nodes).

Key Results

  • Massive Efficiency Gains: The proposed algorithms achieve a staggering four-order-of-magnitude speedup over the traditional Greedy method. On the Ego-Facebook dataset, while the Greedy algorithm required over 49 hours to select 400 seeds, IS-LSS+ completed the task in just 5.36 seconds.
  • High Effectiveness: Despite the speedup, IS-LSS and IS-LSS+ maintain blocking performance nearly identical to the Greedy algorithm.
  • Scalability: The heuristics demonstrate excellent scalability, remaining efficient on the Gowalla dataset where the Greedy approach would be computationally unfeasible.
  • Superiority over Baselines: The proposed methods consistently outperform simpler strategies, such as selecting seeds based on network degree or proximity to the rumor source.

Insights and Future Directions

The research highlights that spatial pruning is a powerful tool for large-scale network analysis. By using Quadtree cells to establish upper bounds on influence, the algorithms can bypass thousands of insignificant nodes. Furthermore, the study suggests that local influence is often more critical than global reach; a mid-tier influencer within a specific target zone can be more effective at blocking a local rumor than a global celebrity.

Future work could extend this model by incorporating user mobility (how movement between regions affects propagation), temporal dynamics (evolving social ties), and heterogeneous propagation probabilities (accounting for the fact that misinformation often spreads differently than factual information).

Summary updated

BibTeX
@article{zhu2019location,
  author = {Wenlong Zhu and Wu Yang and Shichang Xuan and Dapeng Man and Wei Wang and Xiaojiang Du and Mohsen Guizani},
  title = {{Location-Based Seeds Selection for Influence Blocking Maximization in Social Networks}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2900708},
}
Figure