PaperlayerView exact revision on arXiv

Source-linked AI summary

How to Identify an Infection Source with Limited Observations

Wuqiong Luo, Wee Peng Tay, Mei Leng

arXiv:1309.4161v2cs.SIphysics.soc-ph

TL;DR

The paper asks how to estimate an infection source when only some infected nodes can be observed. It develops estimators for tree and general networks and reports better performance than distance, closeness, and betweenness heuristics in simulations.

  • Problem

    Estimating an infection source is difficult when applications reveal only a limited subset of infected nodes, which may not include the source.

    Source: §I · p. 1

  • Method

    For SI networks, the paper uses a Jordan center for trees and proposes approximate source estimators for general networks, including an MIQCQP and a heuristic.

    Source: §IV · p. 7, §VI · p. 10

  • Results

    Simulations suggest the proposed estimators outperform distance, closeness, and betweenness centrality methods; on general networks, RG has smaller average error distances in almost all tested cases.

    Source: B. Our Contributions · p. 2, B. General Networks · p. 10

  • Takeaways & Limitations

    The estimated source is on average within a few hops of the actual source, providing a narrowed set of potential sources rather than guaranteeing exact identification.

    Source: A. Related Works · p. 2, §VI · p. 10

    The work assumes very limited information, and extending limited-observation source estimation to richer SIS models remains future work.

    Source: §VI · p. 10

Abstract

from arXiv · show

A rumor spreading in a social network or a disease propagating in a community can be modeled as an infection spreading in a network. Finding the infection source is a challenging problem, which is made more difficult in many applications where we have access only to a limited set of observations. We consider the problem of estimating an infection source for a Susceptible-Infected model, in which not all infected nodes can be observed. When the network is a tree, we show that an estimator for the source node associated with the most likely infection path that yields the limited observations is given by a Jordan center, i.e., a node with minimum distance to the set of observed infected nodes. We also propose approximate source estimators for general networks. Simulation results on various synthetic networks and real world networks suggest that our estimators perform better than distance, closeness, and betweenness centrality based heuristics.

I. INTRODUCTION

The paper studies infection-source estimation when only a subset of infected nodes is observable, a constraint arising in rumor monitoring and disease surveillance. It distinguishes source estimation for a particular spread from identifying nodes expected to influence many others, then develops tree and general-network estimators.

I. INTRODUCTION

  • Estimating a source matters for tracing rumors and identifying a disease's index case, but practical observation may cover only a subset of infected nodes.Some network nodes may be inaccessible to monitors, and some individuals may be immune or asymptomatic.Source: §I · p. 1

A. Related Works

  • Earlier work on influential nodes maximizes expected influence across infection realizations, whereas this paper seeks the source of a particular realized spread.Prior source-estimation work generally assumes all infected nodes are observed; one limited-observation approach additionally assumes infection times and transmitting neighbors are known.Source: A. Related Works · pp. 1–2

B. Our Contributions

  • For tree networks, the proposed source estimator is associated with a most likely infection path yielding the observed infected subset, and an O(n) algorithm finds it.Here, n is the number of nodes in the subtree spanning the observed infected nodes.Source: B. Our Contributions · p. 2
  • For general networks, the paper proposes an approximate estimator using an MIQCQP and a heuristic algorithm with time complexity O(n3).The MIQCQP has high complexity; n in the heuristic's complexity is the network size.Source: B. Our Contributions · p. 2
  • Simulations on synthetic trees, small-world networks, a U.S. power-grid network, and part of Facebook show better performance than distance, closeness, and betweenness centrality estimators.The paper presents this as a comparison across its evaluated network types.Source: B. Our Contributions · p. 2

II. PROBLEM FORMULATION

  • The problem formulation estimates a source from the most likely infection path under a system model and stated assumptions.The section also summarizes notation and definitions used in the paper.Source: §II · p. 2

A. Infection Spreading Model

The paper models rumor or disease spread with a discrete-time SI process, while allowing infected nodes to remain unobserved. It estimates the source from the observed explicit nodes using a most-likely-infection-path criterion.

A. Infection Spreading Model

  • The model uses a discrete-time SI process: infected nodes stay infected, and each susceptible node becomes infected independently with probability p.The authors note that this model does not cover all infection processes and place continuous-time SI, SIR, and SIS models outside the paper’s scope.Source: A. Infection Spreading Model · p. 3
  • Infected nodes may be non-explicit, so the observer sees only the explicit infected set and may mistake non-observable nodes for uninfected ones.A node’s explicit status is independently determined, with probability q_u.Source: A. Infection Spreading Model · p. 3

B. Most Likely Infection Path and Source Estimator

  • The source estimator uses the source associated with a most likely infection path consistent with the observed explicit nodes, rather than maximizing the likelihood of the observed set.The elapsed time is not assumed known, and the criterion selects among possible paths and feasible elapsed times.Source: B. Most Likely Infection Path and… · pp. 3–4
  • The paper characterizes most-likely paths for trees, proposes approximate source estimators for general networks, and evaluates the estimators in simulations.The supplied passage gives no specific simulation outcomes.Source: B. Most Likely Infection Path and… · p. 4

C. Some Notations and Definitions

The paper defines infection range as the farthest distance from a candidate source to an explicit node, and calls a node minimizing that range a Jordan center. For trees, it characterizes most-likely infection paths and connects their source to this center.

C. Some Notations and Definitions

  • For a candidate node v, its infection range is the largest distance to any explicit node; a node with minimum infection range is a Jordan center.The observed explicit set is assumed non-empty, and elapsed time is not assumed known.Source: C. Some Notations and Definitions · p. 4

III. SOURCE ESTIMATION FOR TREES

  • The tree case uses the Jordan center of the explicit nodes as the source estimator associated with a most-likely infection path.The paper frames this as its tree-network source-estimation result.Source: §III · p. 5

A. A Most Likely Infection Path

  • On a tree, a latest infection path is a most-likely path for a fixed feasible elapsed time, with non-observable subtrees left uninfected.The path uses the minimum connected subtree spanning the explicit nodes and source, and delays infections within it as late as possible.Source: A. A Most Likely Infection Path · p. 5
  • For a candidate source, feasible elapsed times begin at its infection range, and the probability of its latest infection path decreases as elapsed time grows.Thus, the most likely elapsed time is the infection range itself.Source: A. A Most Likely Infection Path · p. 5

B. Source Associated with a Most Likely Infection Path

For tree networks, the source associated with a most-likely infection path is a Jordan center of the explicit nodes. The paper also notes that this estimator matches those for SIR and SIS processes.

B. Source Associated with a Most Likely Infection Path

  • The proof compares neighboring nodes in the spanning subtree: moving toward lower infection range yields a higher-probability most-likely path.The comparison constructs a path for the nearer node from the neighboring node’s path.Source: B. Source Associated with a Most… · p. 6
  • For a tree, a Jordan center of the explicit nodes is the source estimator associated with a most-likely infection path.The proof establishes that a Jordan center’s most-likely path has higher probability than the path for nodes farther along the spanning subtree.Source: B. Source Associated with a Most… · p. 6
  • The estimator is the same as the source estimator for SIR and SIS processes, despite their different spreading models.The authors characterize the Jordan center as a universal source estimator under their statistical criterion.Source: B. Source Associated with a Most… · pp. 6–7

C. Finding a Jordan Center

The Jordan center in the observed-node spanning subtree can be found by checking path lengths around candidate nodes. The proposed message-passing algorithm finds it in linear time and can be implemented distributively.

C. Finding a Jordan Center

  • A Jordan center in H has degree at least 2, and its two longest branch paths differ in length by at most 1.These are necessary and sufficient conditions when |H| > 2.Source: C. Finding a Jordan Center · p. 7
  • JCE uses upward messages from leaves to a root, then moves downward along the longest branch until the center condition is met.The messages carry node identity and longest-path length; the downward pass compares the two longest paths at each node.Source: C. Finding a Jordan Center · p. 7
  • JCE takes O(|H|) time, with one upward message per node and a downward pass bounded by H’s diameter.A centralized tree algorithm also finds a Jordan center in linear time by computing a diameter and returning a midpoint.Source: C. Finding a Jordan Center · p. 7

IV. SOURCE ESTIMATION FOR GENERAL NETWORKS

For general networks, the paper approximates the most likely infection tree consistent with observed infected nodes to estimate a source. It proposes two heuristics for finding such trees and applies the estimator over the finite network.

IV. SOURCE ESTIMATION FOR GENERAL NETWORKS

  • For general networks, the paper proposes an approximate estimator for the source associated with the most likely infection path and two heuristics for finding it.The estimator is based on approximating the most likely infection tree consistent with the observed infected nodes.Source: §IV · p. 7
  • Without loss of optimality, candidate infection trees for a source can be restricted to those whose non-source leaves are observed nodes.The paper approximates these trees using spanning trees of a subgraph built from shortest-path trees to the observed nodes and their incident edges.Source: §IV · pp. 7–8
  • The likelihood of a consistent infection tree depends on infection probability and the subtree heights that determine how long nodes remain susceptible.The likelihood calculation uses infection times derived from distances and subtree heights.Source: §IV · p. 8
  • The proposed methods are iterated over all nodes of the finite graph to find the source estimator.The theoretical analysis assumes an infinite graph, while practical use has access to a finite graph.Source: §IV · p. 8

A. MIQCQP

The MIQCQP formulates the approximate tree objective using binary edge choices and subtree-height variables. Its constraints approximate the optimization, so it does not recover the exact optimum; the authors note that standard solvers are unsuitable for large networks.

A. MIQCQP

  • The MIQCQP expresses the approximate objective as an optimization over spanning trees of H_v, using binary edge variables and subtree-height variables.E_ij indicates whether an edge is selected, while D_i represents the subtree height of node i.Source: A. MIQCQP · p. 8
  • The MIQCQP does not find the exact optimal tree because its feasible set is restricted and quadratic constraints approximate subtree heights.The constraints encode tree-height inequalities and add an upper bound on D_i to improve convergence speed.Source: A. MIQCQP · p. 8
  • The optimization solvers have high complexity and are not suitable for large networks, motivating a low-complexity heuristic.The paper compares the heuristic’s performance in Section V.Source: A. MIQCQP · p. 8

B. Reverse Greedy

Reverse Greedy adjusts an infection tree to reduce degrees near the source and increase them farther away, guided by the objective’s degree and subtree-height terms. It begins with a shortest-path tree and has overall O(|V|^3) complexity when evaluated for every source candidate.

B. Reverse Greedy

  • The Reverse Greedy objective favors smaller degrees for nodes with larger subtree heights, motivating lower degrees near the source and higher degrees farther away.The algorithm attempts to reshape the infection tree according to this pattern.Source: B. Reverse Greedy · p. 8
  • For each candidate source, RG starts with a breadth-first-search shortest-path tree spanning H_v and repeatedly reattaches a farthest leaf to a neighboring node with the largest distance from the source.The process proceeds up the tree until reaching the source.Source: B. Reverse Greedy · pp. 8–9
  • RG costs O(|H_v|^2) per candidate source and O(|V|^3) overall when run over all nodes.The overall complexity includes iterating over every node to find the source estimator.Source: B. Reverse Greedy · p. 9

V. SIMULATION RESULTS

The simulations compare the proposed estimators with distance, closeness, and betweenness centrality baselines. The section defines these benchmark measures and notes a condition under which the distance center is maximum-likelihood.

V. SIMULATION RESULTS

  • The proposed estimators are compared with distance, closeness, and betweenness centrality benchmarks.The section introduces these three common centrality measures as baselines.Source: §V · p. 9
  • For regular trees under the SI model with all infected nodes observed, the distance center is a maximum-likelihood estimator.Source: §V · p. 9
  • Betweenness centrality is based on the fraction of shortest paths between node pairs that pass through a given node.Source: §V · p. 9

A. Tree Networks

Tree-network simulations find that JCE’s error distance remains relatively stable as the trees become less regular, while benchmark errors increase. The evaluation uses three synthetic tree types with differing degree-generation rules.

A. Tree Networks

  • The evaluation uses regular trees with node degree randomly chosen from, random-1 trees with degrees in, and random-2 trees with degrees in {3, 6}.The authors characterize random-1 as less regular than regular trees and random-2 as even less regular.Source: A. Tree Networks · p. 9
  • As tree networks become less regular, benchmark error distances increase while JCE’s remain relatively stable.The authors note that practical tree structures are usually far from regular.Source: A. Tree Networks · pp. 9–10, Figure 3 · p. 9

B. General Networks

On general networks, MIQCQP and RG outperform the centrality benchmarks in the first comparison, and RG has smaller average error distances in almost all tested explicit-ratio cases. The conclusion describes the proposed algorithms and identifies richer infection models as a future direction.

B. General Networks

  • RG has smaller average error distances than all benchmarks in almost all tested explicit-ratio cases, while both RG and MIQCQP outperform the benchmarks in the first comparison.The first comparison restricts infection size to 50 because MIQCQP’s average running time is about 2000 times RG’s; the later comparison uses infections larger than 200 nodes and explicit ratios from 10% to 100%.Source: B. General Networks · p. 10, Figure 5 · p. 10

VI. CONCLUSION

  • The tree estimator is a Jordan center found in O(n) time, while general-network estimators use a high-complexity MIQCQP formulation and an O(n^3) heuristic.Simulations place estimated sources on average within a few hops of the actual source.Source: §VI · p. 10
  • The authors identify source estimation for richer models such as SIS with limited observations as a future research direction.Source: §VI · p. 10

APPENDIX A PROOF OF LEMMA 1

The appendices prove tree-network lemmas by induction, modifying most-likely infection paths while preserving or improving their probability. The arguments establish conditions on infection times in non-observable subtrees and subtrees containing explicit nodes.

APPENDIX A PROOF OF LEMMA 1

  • For Lemma 1, induction on elapsed time constructs a path that leaves nodes in non-observable subtrees uninfected without reducing the path probability.The proof handles subtrees farther than one hop from the source through the induction hypothesis, then adjusts neighbor-rooted subtrees by changing infection states.Source: Appendix A · pp. 10–11

APPENDIX B PROOF OF LEMMA 2

  • For Lemma 2, induction on the maximum distance to explicit nodes establishes infection-time conditions for non-source nodes in the tree.The proof first shifts a neighbor’s infection to time t, then extends the construction to deeper subtrees using the induction hypothesis.Source: Appendix B · p. 11
Loading 1309.4161v2…