Reverse Path Activation-based Reverse Influence Maximization in Social Networks

Ashis Talukder, Anupam Kumar Bairagi, Do Hyeon Kim, Choong Seon HongJournal of KIISE 2018 · DOI

TL;DR

This paper introduces a novel "Active Reverse Path-based Reverse Influence Maximization" (ARP-RIM) model to tackle the challenge of minimizing "seeding cost" in social networks. By considering how nodes are influenced before they become influencers, ARP-RIM aims to find the most cost-effective way to activate a set of target nodes, outperforming existing methods.

What Problem Does This Paper Address?

In social network marketing, "Influence Maximization" (IM) is about finding a small set of influential users (seed nodes) to maximize the spread of information or products. However, this often assumes these seed nodes are activated from the start. "Reverse Influence Maximization" (RIM) flips this, focusing on the "seeding cost" – the minimum number of nodes that need to be activated to cause a predefined set of target nodes to become active. This is crucial for understanding the cost of initiating a viral campaign. Existing RIM approaches have limitations, particularly in handling network structures, stopping criteria, and the fundamental idea that even "seed" nodes might need to be influenced by others before they can exert their own influence. This paper addresses these limitations by proposing a new model that accounts for this reverse influence flow.

Methods

The core of this paper is the Active Reverse Path-based Reverse Influence Maximization (ARP-RIM) model. It builds upon two established concepts:

  • Independent Cascade (IC) Model: A standard model for influence propagation where an activated node has a probability of activating its neighbors.
  • Voting Model: Used here to determine the marginal seeding cost for target nodes, essentially simulating a "vote" from their in-neighbors.

The novelty lies in the "Active Reverse Path" (ARP) concept. Instead of just looking at direct influence, ARP-RIM traces "reverse paths" – the paths leading to a node. It then identifies the "active" portion of these reverse paths, meaning the sequence of nodes that would be activated by the IC model up to a certain point, but where the final node in that sequence remains inactive. This ARP represents the minimal set of upstream nodes that need to be activated to potentially influence a target node. The model then uses a greedy approach to select the most cost-effective set of these upstream nodes to minimize the overall seeding cost.

Datasets

The authors evaluated their ARP-RIM model using three real-world social network datasets:

  • ego-Facebook: A dataset of Facebook ego networks.
  • ego-Twitter: A dataset of Twitter ego networks.
  • web-Google: A dataset representing the Google web graph.

These datasets are publicly available and commonly used in social network analysis research.

Key Insights and Ideas

  • Seed nodes aren't always self-activating: The paper challenges the assumption that seed nodes are inherently active. It argues that even these initial nodes might need to be influenced by their in-neighbors, mirroring how influence spreads in the forward direction.
  • Reverse paths are key to cost optimization: By analyzing "active reverse paths," the model identifies the most critical upstream nodes that, if activated, can trigger the desired influence cascade. This is more nuanced than simply looking at direct connections.
  • ARP-RIM handles RIM challenges: The proposed model is designed to address limitations in previous RIM approaches, specifically regarding stopping criteria and handling complex network structures, leading to more robust results.
  • Greedy approach for efficiency: While the underlying problem is NP-Hard, the use of a greedy strategy for selecting nodes significantly improves computational efficiency compared to brute-force methods.

Key Results

The experimental results demonstrate that the ARP-RIM model consistently achieves a lower seeding cost compared to existing Random-RIM (R-RIM) and Randomized LT-based RIM (RLT-RIM) models across all three datasets.

  • Seeding Cost: Figures 3, 4, and 5 clearly show ARP-RIM outperforming R-RIM and RLT-RIM in terms of minimizing the cost to activate target nodes.
  • Robustness: Unlike the random-based models (R-RIM, RLT-RIM) which exhibit drastic fluctuations, ARP-RIM provides more stable and predictable results.
  • Running Time: The ARP-RIM model has a slightly higher running time (O(kd(n+m))) compared to existing models (O(kd²)). This is attributed to the computational overhead of calculating the Active Reverse Paths. However, the authors argue that this trade-off is justified by the improved seeding cost and the model's ability to address RIM challenges more effectively.

Limitations and Future Work

  • Running Time: The authors acknowledge that the ARP-RIM model has a higher running time due to the computation of Active Reverse Paths. Future work could focus on optimizing this aspect to further reduce the execution time.
  • Model Complexity: While the ARP-RIM model is more effective, its complexity might be a consideration for extremely large-scale networks. Further research could explore more computationally efficient approximations.
  • Generalizability: While tested on three diverse datasets, further validation on a wider range of social network structures and types could enhance confidence in its generalizability.

Summary updated

Abstract

영향력 극대화(Influence Maximizaion)기법은 소셜 네트워크에서 바이럴 마케팅에 대한 영향력 있는 사용자를 찾는 것을 다루지만, 역방향 영향력 극대화(Reverse Influence Maximizaion) 기법은 영향 비용 극대화 영역의 새로운 연구 방향으로 기회비용을 처리한다. 영향력 극대화 기법은 이러한 시드노드를 대상으로 네트워크에서 영향이 극대화되는 방식으로 작은 시드 집합을 추정한다. 일반적으로 시드노드는 영향력 극대화 문제에서 처음에 활성화되는 노드로 가정한다. 그러나, 우리는 활성화 된 노드가 추후 활성화 될 외부 노드에 영향을 주는 것과 유사한 방식으로 다른 노드의 영향을 받아야한다고 주장한다. 역방향 영향력 극대화 문제는 모든 시드 노드를 활성화하기 위해 활성화해야하는 최소 노드 수로 정의되는 시드 비용을 찾는 문제이다. 이에 본 논문에서는 최소 기회 비용을 찾기 위해 Active Reverse Path 기반 역방향 영향력 극대화 모델을 제안한다. 본 모델은 Voting 모델과 전통적인 Independent Cascade 모델을 기반으로 한다. 아울러 잘 알려진 세 가지 소셜 네트워크의 실제 데이터 셋을 활용하여 모델을 시뮬레이션 하였으며, 그 결과 제안하는 모델이 기존 역방향 영향력 극대화 모델보다 우수한 성능을 보였다.
BibTeX
@article{talukder2018reverse,
  author = {Ashis Talukder and Anupam Kumar Bairagi and Do Hyeon Kim and Choong Seon Hong},
  title = {{Reverse Path Activation-based Reverse Influence Maximization in Social Networks}},
  journal = {Journal of KIISE},
  year = {2018},
  doi = {10.5626/jok.2018.45.11.1203},
}
Figure