PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Source Detection in the SIR Model: A Sample Path Based Approach

Kai Zhu, Lei Ying

arXiv:1206.5421v2cs.SIphysics.soc-ph

TL;DR

The paper asks how to identify an information source from an infected-node snapshot under the SIR model, where recovery obscures node histories. It uses a most-likely sample-path estimator and a reverse infection algorithm, proving bounded-distance performance on regular trees and reporting stronger results than closeness centrality in simulations.

  • Problem

    The problem is to detect an information source from a snapshot of infected nodes under SIR when susceptible and recovered nodes cannot be distinguished.

  • Method

    The paper chooses the source associated with the sample path most likely to produce the observed snapshot and uses reverse infection to find the estimator in general graphs.

  • Results

    Around 60% detection rate is achieved on regular trees, exceeding infection closeness centrality; on real-world networks, reverse infection significantly outperforms random guesses.

  • Takeaways & Limitations

    On infinite trees, the estimator is a Jordan infection center, and on g-regular trees with gq>1 it remains within constant distance of the actual source with high probability.

Abstract

from arXiv · show

This paper studies the problem of detecting the information source in a network in which the spread of information follows the popular Susceptible-Infected-Recovered (SIR) model. We assume all nodes in the network are in the susceptible state initially except the information source which is in the infected state. Susceptible nodes may then be infected by infected nodes, and infected nodes may recover and will not be infected again after recovery. Given a snapshot of the network, from which we know all infected nodes but cannot distinguish susceptible nodes and recovered nodes, the problem is to find the information source based on the snapshot and the network topology. We develop a sample path based approach where the estimator of the information source is chosen to be the root node associated with the sample path that most likely leads to the observed snapshot. We prove for infinite-trees, the estimator is a node that minimizes the maximum distance to the infected nodes. A reverse-infection algorithm is proposed to find such an estimator in general graphs. We prove that for $g$-regular trees such that $gq>1,$ where $g$ is the node degree and $q$ is the infection probability, the estimator is within a constant distance from the actual source with a high probability, independent of the number of infected nodes and the time the snapshot is taken. Our simulation results show that for tree networks, the estimator produced by the reverse-infection algorithm is closer to the actual source than the one identified by the closeness centrality heuristic. We then further evaluate the performance of the reverse infection algorithm on several real world networks.

I. INTRODUCTION

The paper addresses information source detection under the SIR model, where recovery makes susceptible and recovered nodes indistinguishable. It replaces an intractable maximum-likelihood search with a sample-path estimator and reverse infection algorithm, with theoretical and simulation-based guarantees.

  • Approach: The sample path approach selects the source associated with the sample path most likely to produce the observed snapshot.On trees, the source is a Jordan infection center: a node minimizing the maximum distance to infected nodes.
  • Approach: The reverse infection algorithm finds the sample-path estimator in general graphs by broadcasting infected-node identities and using distance sums to break ties.Its running time equals the minimum infection eccentricity, and each node’s messages per iteration are bounded by its degree.
  • Results: On g-regular trees with gq>1, the estimator is within a constant distance of the actual source with high probability, independently of infected-node count and observation time.The paper also evaluates the algorithm on regular trees and several real-world network topologies.
  • Results: Around 60% detection rate is reported on regular trees, exceeding the infection closeness centrality heuristic; on real-world networks, reverse infection significantly outperforms random guesses.Infection closeness centrality is the inverse of the sum of distances to infected nodes.
  • Problem and motivation: SIR source detection is harder than SI detection because recovered and susceptible nodes are indistinguishable, making every node a possible source.Recovery occurs in practical scenarios such as deleted rumors, removed computer viruses, and deleted contraband files.
  • Problem and motivation: The maximum-likelihood formulation requires considering all possible infection sample paths, whose number is at least on the order of t^N.For healthy nodes, infection and recovery times must be specified; for infected nodes, infection times must be specified.

D. Sample Path Based Detection

The paper selects the sample path most likely to produce the observed infected set, then uses its associated source as the estimator. On infinite trees, the estimator is a Jordan infection center: a node minimizing the maximum distance to infected nodes.

  • The estimator is the source associated with the sample path that most likely leads to the observed infection topology.The optimization ranges over possible durations and sample paths consistent with the observation.
  • Infection eccentricity is the maximum distance from a node to any observed infected node, and Jordan infection centers minimize it.For the illustrated graph, v1 is the Jordan infection center with infection eccentricity 2.
  • If one node has smaller infection eccentricity than a neighboring node, its optimal sample path has higher probability.The proof compares neighboring roots and then follows paths along which infection eccentricity decreases.
  • For a fixed candidate source, the optimal sample-path duration equals its infection eccentricity.This is the minimum time required to produce the observed infection topology from that source.
  • The optimal path probability is non-increasing with duration, so extending a compatible sample path by one time slot cannot improve its likelihood.The proof establishes this first for the single-infected-node case and then extends it by induction over infection eccentricity.
  • The proof partitions infection topologies by their largest source-to-infected-node distance and uses induction over these subsets.For subtrees containing infected nodes, it constructs a shorter path with higher probability; empty subtrees are handled separately.

B. The Sample Path Based Estimator

The sample-path estimator selects the source associated with the most likely sample path leading to the observed infection topology. On infinite trees, this source is a Jordan infection center, minimizing the maximum distance to infected nodes.

  • The estimator chooses the root of the sample path that most likely produces the observed infection topology.The proof compares optimal sample paths rooted at neighboring nodes and favors the one with higher probability.
  • The proof constructs a more probable sample path when moving from a node with larger infection eccentricity toward a Jordan infection center.Repeated application of the neighboring-node comparison establishes the theorem.
  • A tree has at most two Jordan infection centers, and if two exist, they are adjacent.This follows from the tree structure and the strict decrease of infection eccentricity along paths toward a center.
  • On infinite trees, the optimal sample-path root is a Jordan infection center minimizing infection eccentricity.Infection eccentricity is the maximum distance from a node to the infected nodes.

IV. REVERSE INFECTION ALGORITHM

The reverse infection algorithm identifies Jordan infection centers in general graphs by propagating infected-node identities and resolving ties using infection closeness.

  • The algorithm lets every infected node broadcast its identity through the network until a node receives all infected-node identities.That node claims to be the information source when the collection is complete.
  • Ties are broken using maximum infection closeness, defined as the inverse sum of distances to infected nodes.The algorithm can also break ties at random in its stated implementation.
  • The candidate set consists of nodes that receive all distinct infected-node messages when the algorithm terminates.This set is the set of Jordan infection centers.
  • The running time equals the minimum infection eccentricity, while each node sends and receives at most its degree in messages per time slot.

V. PERFORMANCE ANALYSIS

The performance analysis models infection spread on regular trees using Galton–Watson branching processes. Under gq>1, the estimator remains within a constant distance of the actual source with high probability, independently of snapshot time and infection count.

  • For g>2 and gq>1, the estimator is within a constant distance dϵ of the actual source with probability 1−ϵ.The constant dϵ is independent of the number of infected nodes and the snapshot time.
  • The analysis represents infected descendants across tree levels as a branching process whose offspring distribution depends on infection duration.The process Bτ tracks infected and recovered nodes whose parents were infected within τ time slots.
  • When no infected node appears at level L, the minimum infection eccentricity is at most L−1 and the estimator is at most 2(L−1) from the actual source.
  • If two B1 branching processes survive by level L, nodes at or below level (τ+1)L−1 cannot be Jordan infection centers.The argument uses an infected node whose distance from such a candidate exceeds the snapshot time.
  • For sufficiently large τ and L, the relevant events occur with probability at least 1−ϵ independently of snapshot time and infected-node count.The proof combines branching-process survival and extinction bounds.

VI. SIMULATIONS

The simulations evaluate the reverse infection algorithm across multiple network types. The evaluation includes both tree networks and real-world networks.

  • The experiments evaluate the reverse infection algorithm on different network structures.
  • The evaluation includes multiple tree networks.
  • The evaluation also includes several real-world networks.

A. Tree Networks

The reverse infection algorithm is evaluated against closeness centrality on tree networks, where closeness centrality selects the node with maximum infection closeness.

  • Closeness centrality selects the node with maximum infection closeness as the information source.On regular trees under the SI model, this node is also the maximum likelihood estimator.

1) Small-size tree networks:

Small-size regular-tree experiments compare reverse infection with maximum likelihood estimation and closeness centrality across node degrees from 2 to 10.

  • Experiments vary the degree g from 2 to 10 under randomly selected infection and recovery probabilities and infection durations.The total number of infected and recovered nodes is restricted to at most 100.
  • The detection rate is the fraction of experiments in which the estimator coincides with the actual source.
  • Reverse infection has nearly the same detection rate as MLE and exceeds closeness centrality by approximately 20% at small degree and 10% at large degree.

2) General g-regular tree networks:

Large-size g-regular-tree simulations show that detection rates rise with degree, while reverse infection outperforms closeness centrality.

  • The simulations use infection durations uniformly selected from [3, 20] and retain networks with at most 500 infected and recovered nodes.
  • Detection rates for both reverse infection and closeness centrality increase with degree and exceed 60% when g > 6.
  • Reverse infection achieves a higher detection rate than closeness centrality, with an average difference of 8.86%.

3) Binomial random trees:

On binomial random trees, increasing branching density raises detection rates, and reverse infection outperforms closeness centrality on average.

  • Figure 8 reports detection rates for reverse infection and closeness centrality on binomial random trees.
  • Reverse infection outperforms closeness centrality by 10.16% on average.
  • As β increases, denser trees increase the number of survived branching processes and the detection rate.The experiments fix g′ = 10 and vary β from 0.1 to 0.9.

B. Real World Networks

Experiments evaluate reverse infection on three real-world networks under varied infection and recovery probabilities. Across the reported networks, reverse infection generally places estimators closer to actual sources than random guessing, consistent with the paper’s broader conclusion.

  • Experimental setup: Experiments use the IAS, Wikipedia who-votes-on-whom, and power grid networks, comparing reverse infection with random guessing.The infection probability q was sampled uniformly from (0, 0.05), recovery probability p from (0, q), and infected-plus-recovered nodes numbered 50–500.
  • Internet Autonomous Systems network: More than 80% of IAS estimators are within two hops of the actual sources, compared with 10% under random guessing.The IAS network contains 10,670 nodes and 22,002 edges.
  • Wikipedia who-votes-on-whom network: On Wikipedia, most reverse-infection estimators are within two hops, whereas fewer than 20% of random-guessing estimators meet that distance.The network has 7,066 nodes and 100,736 links.
  • Power grid network: On the power grid, reverse infection performs better than random guessing, with its peak at the third hop versus the seventeenth hop for random guessing.The power grid contains 4,941 nodes and 6,594 edges.
  • Overall findings: The reported real-world evaluations support the reverse-infection approach as a method for locating information sources in network snapshots.The paper states that it further evaluates reverse infection on several real-world networks after establishing its sample-path estimator.

APPENDIX A NOTATION TABLE

The notation defines the source, estimator, infection eccentricity, node distances, SIR timing variables, snapshots, and valid sample paths used throughout the paper.

  • Sources and estimator: v∗ denotes the actual information source, while v† denotes the estimator of that source.The notation table distinguishes the true source from the algorithm’s estimated source.
  • SIR parameters and timing: q and p denote infection and recovery probabilities, while tI_v and tR_v denote infection and recovery times for node v.These variables describe the SIR transition parameters and node-specific timing in a sample path.
  • Graph structure: d(v, u) is the shortest-path length, C(v) is v’s child set, and ẽ(v) is v’s infection eccentricity.The notation supports distance-based analysis on trees rooted at candidate source nodes.
  • States and snapshot: Y is the snapshot of node states, and X_v(t) and X(t) represent the state of node v and all nodes at time t.The snapshot and state-process notation distinguish observed network information from the evolving diffusion process.
  • Sample paths: X[0,t] denotes a sample path, while X([0,t], T^−v_u) and X(t, T^−v_u) denote paths restricted to the tree with a branch removed.X(t) and X(t, T^−v_u) denote the corresponding sets of valid sample paths.
  • Observed infection set: I denotes the set of infected nodes.This set identifies the infected portion of the observed snapshot.
Loading 1206.5421v2…