Targeted Influence Maximization Based on Cloud Computing Over Big Data in Social Networks

Shiyu Chen, Xiaochun Yin, Qi Cao, Qianmu Li, Huaqiu LongIEEE Access 2020 · DOI

Abstract

This paper focuses on targeted influence maximization based on cloud computing in social networks. Most existing influence maximization works assume that influence diffusion probabilities on edges are fixed and identify the Top-k users to maximize the spread of influence assuming knowledge of the entire network graph. However, in real-world scenarios, edge probabilities typically vary based on topics and information received. Furthermore, obtaining complete network data is difficult due to privacy and computational considerations. This paper proposes a targeted influence maximization solution based on cloud computing. First, a new topic-aware model called the tag-aware IC model is presented, which considers users' interests, item characteristics, and similarity. Then, efficient algorithms with approximation guarantees are provided using a bounded number of queries to the graph structure. Empirical studies on real datasets show that the proposed techniques achieve significant speedup and storage savings compared with state-of-the-art methods.

Introduction

Influence Maximization (IM) is the task of identifying a small set of "seed" users who can trigger the largest possible cascade of information or adoption across a social network. While traditional IM has been extensively studied, it faces significant hurdles when applied to modern "Big Data" scales. Standard models often treat influence as a generic, fixed probability, ignoring the reality that influence is highly topic-dependent. Moreover, the computational complexity of finding optimal seeds is NP-hard, making standard Monte Carlo simulations prohibitively slow for graphs with billions of edges. Finally, data privacy often prevents access to complete social graphs.

This paper addresses these challenges by proposing a Targeted Influence Maximization approach that leverages cloud computing and a novel topic-sensitive diffusion model to achieve high efficiency and accuracy.

The Tag-Aware IC Model

The researchers extend the standard Independent Cascade (IC) model by incorporating "tags" to represent topics. In this Tag-Aware IC Model, the probability of influence between two users is not a static value but a dynamic function of:

  • User Interests: Specific tags associated with individual user profiles.
  • Item Characteristics: Tags associated with the specific message or product being propagated.
  • Similarity Metrics: A function calculating the alignment between the message's tags and the user's interests.

By weighting edges based on tag similarity, the model reflects real-world dynamics where an individual's influence is constrained to specific domains of expertise or interest.

Targeted Sketching and Seed Selection

To overcome the "Big Data" bottleneck, the paper introduces a Targeted Sketching technique designed for cloud-based parallelization. The algorithm operates through three main phases:

  1. Sampling Subgraphs: It constructs small, representative "sketches" of the network based on specific topic tags.
  2. $\epsilon$-Cutting: To prevent computational explosions in dense graph regions, the algorithm employs a threshold ($\tau$) to limit the size of connected components during the probing process.
  3. Greedy Selection: The problem is transformed into a "maximum coverage" problem, solved via a greedy algorithm that maintains a $(1 - 1/e - \epsilon)$ approximation guarantee.

Experimental Evaluation and Key Results

The proposed method (referred to as "NEW") was evaluated against benchmarks like BKRIS and IRIE on five real-world datasets, including the Friendster dataset with over 1.8 billion edges.

Massive Speedup and Scalability

The "NEW" algorithm consistently outperformed existing methods, achieving up to a 100x speedup in running time. Unlike heuristic methods that struggle with scale, the proposed algorithm handled billion-edge datasets with ease, showing linear growth in processing time relative to the seed set size ($k$).

Comparison of running time across different algorithms as the seed set size k increases.

Maintained Accuracy

Despite the dramatic reduction in computational overhead, the "influence spread" (the total number of users reached) remained nearly identical to the much slower state-of-the-art methods. This demonstrates that the efficiency gains do not come at the cost of solution quality.

Conclusion

By formalizing influence as a topic-dependent vector and utilizing a parallelizable sketching architecture, this research provides a viable path for running targeted marketing campaigns on global-scale social networks. Future work may involve developing dynamic tag-aware models to account for evolving user interests over time and further optimizing distributed system implementations.

Summary updated

Abstract

This paper focuses on the targeted influence maximization based on cloud computing in social networks. Most of existing influence maximization works assume that the influence diffusion probabilities on edges are fixed, and identify the Top-k users to maximize the spread of influence assuming the knowledge of the entire network graph. However, in real-world scenarios, edge probabilities are typically different based on various topics, and may be affected by information received. Meanwhile, obtaining complete network data is difficult due to privacy and computational considerations. Moreover, existing influence maximization algorithms considering target users do not discuss cloud computing which lead to low computational efficiency when dealing with big datasets in social networks. To this end, this paper proposes a targeted influence maximization solution based on cloud computing. First, a new topic-aware model called tag-aware IC model is presented, which takes into account users' interests, characteristics of the item being propagated, and the similarity between users and the related information. Then, efficient algorithms with approximation guarantee are provided using a bounded number of queries to the graph structure. These methods aim to find a seed set that maximizes the expected influence spread over target users who are relevant to given topics. Finally, empirical studies of the proposed algorithms are designed and performed on real datasets. The experimental results show that the techniques in this paper achieves speedup and savings in storage compared with the state-of-the-art methods.
BibTeX
@inproceedings{chen2020targeted,
  author = {Shiyu Chen and Xiaochun Yin and Qi Cao and Qianmu Li and Huaqiu Long},
  title = {{Targeted Influence Maximization Based on Cloud Computing Over Big Data in Social Networks}},
  booktitle = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.2978010},
}
Figure