Locating Sources of Negative Influence Under the Independent Cascade Model Based on Timeliness

Locating Sources of Negative Influence Under the Independent Cascade Model Based on Timeliness

Introduction

In today’s rapidly evolving digital landscape, social networks have become a dominant medium for information dissemination. While these platforms facilitate communication and knowledge sharing, they also serve as breeding grounds for harmful content such as rumors, fake news, and computer viruses. The rapid spread of such misinformation poses significant threats to social stability, public health, and cybersecurity. Consequently, identifying and neutralizing the sources of harmful information is crucial for mitigating its adverse effects.

Traditional approaches to source localization often overlook the temporal dynamics of information credibility. In reality, the persuasiveness of harmful content diminishes over time as users become skeptical or the information loses relevance. Ignoring this temporal decay leads to inaccuracies in source identification. To address this gap, this paper introduces a novel method for locating multiple sources of negative influence under the Independent Cascade (IC) model, incorporating a time-based decay factor to enhance accuracy.

Problem Definition

The source localization problem in social networks involves inferring the origin of misinformation based on observations from a subset of infected nodes. Given a directed graph representing a social network, where edges denote influence propagation probabilities, the goal is to identify a set of k source nodes responsible for initiating the spread. The challenge lies in leveraging limited observations—infected nodes and their infection timestamps—to backtrack to the most probable sources.

The Independent Cascade Model serves as the foundational framework for this study. In this model, nodes exist in either an infected or uninfected state. Infected nodes attempt to propagate influence to their neighbors with a certain probability, and once infected, a node remains in that state. The propagation process continues until no new infections occur.

A critical aspect of this problem is accounting for the temporal decay of influence. As misinformation spreads, its credibility diminishes over time, reducing the likelihood of further propagation. This paper introduces an attenuation coefficient to model this decay, ensuring that the source localization method reflects real-world dynamics more accurately.

Methodology

The proposed Timeliness-based Source Detection (TLSD) algorithm consists of two main phases: (1) candidate source selection based on posterior probabilities and influence propagation, and (2) refinement of candidate sources using infection timestamps and network distances.

Phase 1: Calculating Posterior Probabilities and Influence

The first step involves computing the posterior probability that a node was infected by a specific neighbor. Using Bayes’ theorem, the probability that an infected node received misinformation from a particular in-neighbor is derived. This probability depends on the edge weights and the node’s in-degree.

Next, the algorithm estimates the influence of each node by simulating a reverse propagation process. Starting from observed infected nodes, a random walk-based approach traces back potential sources. The influence of a node is weighted by the attenuation coefficient, which discounts contributions from longer propagation paths. Nodes with influence scores exceeding a predefined threshold are added to the candidate source set.

Phase 2: Refining Candidate Sources Using Temporal Consistency

The second phase leverages the temporal aspect of infections. Each candidate source is evaluated based on its consistency with observed infection times. For a candidate to be plausible, the computed infection times of observed nodes—based on their network distance from the candidate—must align with actual observations.

The algorithm groups observed nodes that are best explained by the same candidate source, ensuring temporal coherence. A greedy selection process then identifies the k most influential candidates that cover the maximum number of observed nodes while maintaining temporal consistency.

Experimental Evaluation

The performance of the TLSD algorithm was evaluated on both real-world and synthetic networks. Real-world datasets included social and communication networks such as Facebook, USAir, and sports team interactions. Synthetic networks were generated using Erdős-Rényi (ER), Watts-Strogatz (WS), and Barabási-Albert (BA) models to test scalability and robustness.

Key Metrics

Two primary metrics were used to assess performance:

1. Error Distance: The average shortest path distance between estimated sources and ground-truth sources. Lower values indicate higher accuracy.
2. Precision: The ratio of correctly identified sources to the total number of true sources.

Comparative Analysis

TLSD was benchmarked against several state-of-the-art methods, including Maximum Likelihood-based approaches (MLISD), Random Walk-based methods (RWBA), degree centrality, and MaxLikel. The results demonstrated that TLSD consistently outperformed competing algorithms in both precision and error distance.

• Real-World Networks: In datasets like Facebook and USAir, TLSD achieved near-zero error distances for single-source scenarios. Even with multiple sources, the error remained low, primarily within one hop of the true sources.

• Synthetic Networks: TLSD exhibited superior precision across ER, WS, and BA networks, particularly in scenarios with higher observer coverage.

Impact of Temporal Decay

Additional experiments examined the effect of the attenuation coefficient on precision. Higher decay coefficients (slower credibility loss) improved accuracy, underscoring the importance of incorporating temporal dynamics in source localization.

Discussion

The success of TLSD can be attributed to its dual focus on influence propagation and temporal consistency. Unlike methods relying solely on network centrality or static propagation trees, TLSD dynamically adjusts for the diminishing credibility of misinformation over time. This approach not only enhances accuracy but also reduces computational overhead by narrowing candidate sources early in the process.

However, the algorithm assumes a homogeneous decay rate across all nodes, which may not hold in real-world scenarios where user susceptibility varies. Future work could explore adaptive decay models or integrate node-specific attributes to further improve realism.

Conclusion

This paper presents a robust method for locating multiple sources of negative influence in social networks, emphasizing the role of temporal decay in information credibility. By combining Bayesian inference with time-aware influence propagation, the TLSD algorithm achieves higher precision and lower error rates than existing techniques.

The implications extend beyond rumor control, offering potential applications in cybersecurity (e.g., tracing malware origins) and public health (e.g., identifying outbreak sources). Future directions include extending the framework to more complex propagation models like SIR or SEIR and incorporating heterogeneous node behaviors.

doi.org/10.19734/j.issn.1001-3695.2024.06.0201

Was this helpful?

YesNo

0 / 0