Cascade source inference in networks: a Markov chain Monte Carlo approach

Area of Science:

• Network Science
• Computer Science
• Information Theory

Background:

• Information, ideas, rumors, and viruses spread dynamically through complex networks, forming cascades.
• Identifying the initial source of these cascades is essential for understanding and controlling their spread.

Purpose of the Study:

• To address the source inference problem within the Independent Cascade (IC) model.
• To develop an efficient algorithm for identifying cascade origins in large-scale networks.
• To evaluate the algorithm's performance on real-world social network data.

Main Methods:

• Proving the #P-completeness of the source inference problem.
• Developing a Markov chain Monte Carlo (MCMC) algorithm for source inference.
• Conducting experiments on real social network datasets to validate the algorithm.

Main Results:

• The source inference problem is formally proven to be #P-complete.
• A novel MCMC algorithm is proposed, capable of handling large networks.
• The algorithm successfully identifies the true source with high probability across various experimental settings.
• The developed method does not require prior knowledge of the cascade's start time.

Conclusions:

• The proposed MCMC algorithm offers a robust solution for the computationally challenging source inference problem.
• The algorithm's effectiveness in large networks and independence from cascade timing make it a valuable tool for network analysis.
• Empirical validation on real social networks confirms the algorithm's high accuracy in identifying cascade origins.