PaperlayerView exact revision on arXiv

Source-linked AI summary

Rooting out the Rumor Culprit from Suspects

Wenxiang Dong, Wenyi Zhang, Chee Wei Tan

arXiv:1301.6312v4cs.SIcs.IT

TL;DR

The paper asks how to identify a single rumor source when prior knowledge limits possible sources to a suspect set. It builds a MAP estimator using local rumor centers and analyzes its correct detection probability on regular trees with Pólya’s urn methods. Detection improves with network degree and favorable suspect separation, while connected suspect configurations are hardest among multiple-suspect patterns.

  • Problem

    The paper addresses single-source estimation from an infected snapshot when only a specified suspect set can contain the rumor source.

  • Method

    It constructs a MAP estimator, introduces local rumor center as a generalized rumor-centrality concept, and analyzes regular-tree detection using Pólya’s urn methods.

  • Results

    For two suspects, limn→∞Pc(n) is at least 0.75 when δ≥3 and approaches one as δ grows sufficiently large.

  • Takeaways & Limitations

    Suspect-set structure strongly affects detectability: connected suspect subgraphs are hardest among multiple-suspect patterns, while larger degree generally improves detection.

Abstract

from arXiv · show

Suppose that a rumor originating from a single source among a set of suspects spreads in a network, how to root out this rumor source? With the a priori knowledge of suspect nodes and an observation of infected nodes, we construct a maximum a posteriori (MAP) estimator to identify the rumor source using the susceptible-infected (SI) model. The a priori suspect set and its associated connectivity bring about new ingredients to the problem, and thus we propose to use local rumor center, a generalized concept based on rumor centrality, to identify the source from suspects. For regular tree-type networks of node degree δ, we characterize Pc(n), the correct detection probability of the estimator upon observing n infected nodes, in both the finite and asymptotic regimes. First, when every infected node is a suspect, Pc(n) asymptotically grows from 0.25 to 0.307 with δ from 3 to infinity, a result first established in Shah and Zaman (2011, 2012) via a different approach; and it monotonically decreases with n and increases with δ. Second, when the suspects form a connected subgraph of the network, Pc(n) asymptotically significantly exceeds the a priori probability if δ>2, and reliable detection is achieved as δ becomes large; furthermore, it monotonically decreases with n and increases with δ. Third, when there are only two suspects, Pc(n) is asymptotically at least 0.75 if δ>2; and it increases with the distance between the two suspects. Fourth, when there are multiple suspects, among all possible connection patterns, that they form a connected subgraph of the network achieves the smallest detection probability. Our analysis leverages ideas from the Polya's urn model in probability theory and sheds insight into the behavior of the rumor spreading process not only in the asymptotic regime but also for the general finite-n regime.

I. Introduction

The paper studies reliable identification of a single rumor source when prior knowledge restricts possible sources to a suspect set. It develops a MAP estimator and characterizes its detection probability on regular trees across several suspect configurations and observation sizes.

  • Problem: The problem is to identify one rumor source among suspect nodes from a snapshot of infected nodes under the SI model.The paper treats suspect characteristics as prior information rather than assuming every infected node could be the source.
  • Approach: The paper constructs a MAP estimator and uses the local rumor center to handle suspect-set connectivity.The estimator is analyzed through a generalized form of rumor centrality tailored to candidate sources.
  • Analysis: The analysis covers both finite and asymptotic regimes, using Pólya’s urn ideas and simulation experiments to support the analytical results.The paper presents exact detection results for regular tree-type networks under four representative scenarios.
  • All nodes suspect: When every node is a suspect, Pc(n) decreases with n and increases with δ, with asymptotic detection rising from 0.25 at δ=3 toward 0.307 as δ grows.The paper also derives exact finite-n and finite-δ results for regular trees.
  • Connected suspect subgraph: When k suspects form a connected subgraph, asymptotic detection exceeds the a priori probability 1/k for δ>2 and approaches 1 as δ becomes sufficiently large.In the finite regime, Pc(n) decreases with n and increases with δ.
  • Suspect configuration: With two suspects, limn→∞Pc(n) is at least 0.75 for δ≥3, approaches one as δ grows, and increases with their separation distance d.For multiple suspects, a connected suspect subgraph yields the smallest detection probability among connection patterns.

II. Rumor Spreading Model and Rumor Source Estimator

The paper models rumor spreading on a static network with the SI process and estimates the source among a priori suspects using MAP inference. On trees, local rumor centers and rumor centrality make the estimator analytically tractable and computationally efficient.

  • Model: The network is an undirected, static graph, and the source is one node in a specified suspect set S.The model assumes nodes can infect one another only across network edges.
  • SI spreading: The SI process begins with one infected source, and infected nodes independently infect neighbors with exponentially distributed transmission times.The infected snapshot Gn is connected and contains at least one suspect.
  • MAP estimation: The MAP estimator evaluates the posterior source probability over suspects consistent with the infected snapshot and selects the maximum.Under the paper’s uniform prior, the source is uniformly distributed over S intersected with Gn after conditioning on the observation.
  • Regular trees: On regular trees, rumor centrality enables an optimal MAP implementation using O(n) computation steps.Rumor centrality is computed from subtree sizes rooted at each candidate source.
  • General graphs: For general graphs, the estimator approximates diffusion using a BFS tree rooted at each candidate, with implementation complexity O(n^3).The approximation reflects the tendency of rumors to travel along minimum-distance paths.
  • Local rumor center: A local rumor center is a conditional rumor center defined by maximal rumor centrality within a restricted suspect sub-neighborhood.When the restriction includes all neighbors, it coincides with the ordinary rumor center; a connected suspect set has at most two such centers.

III. Detection Probability in Regular Trees: Analytical Results

The paper analyzes MAP rumor-source detection on regular trees across four suspect-set structures, deriving finite- and asymptotic-regime behavior for the correct detection probability Pc(n). Results show how node degree, observation size, suspect connectivity, and suspect separation shape detection performance.

  • Analytical framework: The analysis covers all suspects, connected suspects, two suspects, and multiple suspects with general connectivity on regular trees.The MAP estimator is evaluated through exact or asymptotic characterizations of Pc(n).
  • All nodes are suspects: When every node is a suspect, Pc(n) is O(1/√n) for δ = 2 and 0.25 + O(1/n) for δ = 3.For δ > 3, finite-n values are computed algorithmically, while the asymptotic probability approaches 1 − ln 2 ≈ 0.307 as δ grows.
  • Connected suspects: For connected suspects, Pc(n) equals 1/k + O(1/√n) when δ = 2 and (k + 1)/(2k) + O(1/n) when δ = 3.For δ > 3, exact finite-n computation is available; asymptotically, detection exceeds 1/k and becomes reliable as δ grows.
  • General connectivity: Among all suspect sets of size k, Pc(n) is minimized when the suspects form a connected subgraph.Thus, more clustered suspects yield the smallest detection probability under the MAP estimator.
  • Finite-regime behavior: The analysis uses the Polya urn structure of infection growth and establishes that Pc(n) decreases with n but increases with δ in key finite-regime cases.These monotonicity results are stated for the all-suspect and connected-suspect settings.

IV. Detection Probability on Regular Trees: Numerical Computation

The paper provides exact finite-regime algorithms for computing MAP detection probabilities across three suspect-set scenarios, alongside analytical monotonicity results for regular trees.

  • Numerical computation: Exact detection probabilities are computed for all-node suspects, connected suspects, and two suspects using scenario-specific algorithms.The algorithms are summarized in Table II and include formulas or enumeration procedures for each case.
  • Implementation: For all-node suspects, the computation uses separate formulas for δ = 2, δ = 3, and δ > 3.The corresponding procedures evaluate Pc(n) from finite-regime expressions and probability terms.
  • All nodes are suspects: For S = V, Pc(n) monotonically decreases with n and monotonically increases with δ.The MAP estimator performs better earlier in the spreading process and on networks with higher node degree.
  • Connected suspects: For connected suspect sets, Pc(n) also monotonically decreases with n and monotonically increases with δ.This conclusion is stated for the finite regime on regular trees.
  • Two suspects: The two-suspect case uses the shortest-path distance between suspects and enumerates infection configurations to compute Pc(n).The method applies a dedicated exact algorithm for two suspects.

V. Numerical Experiments

Simulations with 1,000 eventually infected nodes test the analytical predictions across all-node, connected-suspect, and two-suspect settings.

  • Experimental setup: The experiments use a rumor source chosen uniformly from the suspect set and simulate the SI process until n = 1000 nodes are infected.The estimator used in each run is the paper's MAP estimator.
  • S = V: With S = V, the correct detection probability rises from virtually zero at δ = 2 to 0.307 when δ exceeds 50.This simulation reproduces the predicted increase with node degree.
  • Connected suspects: With k connected suspects and δ > 2, the correct detection probability significantly exceeds the prior 1/k, reaching reliable detection as δ grows large.The simulations examine connected suspect sets using n = 1000 infected nodes.
  • Connected suspects: When k ranges from 2 to 4000 for connected suspects, the correct detection probability is always at least 1/2 and matches the theoretical prediction.This experiment tests whether the connected-suspect result degenerates as the suspect set grows large.

VI. Conclusion

The paper analyzes MAP rumor-source detection from suspect sets under the SI model, using local rumor centers and Pólya's urn methods on regular trees.

  • Conclusion: The study addresses rooting out a single rumor source from a set of suspect nodes under an SI model.It focuses on the performance analysis of the MAP source estimator.
  • Conclusion: A local rumor center facilitates analysis, while Pólya's urn methods yield finite and asymptotic detection results on regular tree-type networks.The analysis covers four representative suspect-set scenarios.
  • Conclusion: Introducing prior knowledge of the suspect set dramatically improves detection performance compared with having no prior knowledge.The conclusion frames this improvement as a broader extension of the rumor-source estimation problem.

A. Proof of Lemma 6

The proof characterizes when the true source is or is not the local rumor center by comparing the largest infected subtree with half of the infection size.

  • Proof of Lemma 6: If every infected subtree around the source has fewer than n/2 nodes, the source is the local rumor center and is correctly identified.The proof uses the local neighborhood and rumor-centrality comparisons to exclude nodes in the source's subtrees.
  • Proof of Lemma 6: If the largest infected subtree contains exactly n/2 nodes, the source ties with one neighboring node and is selected with probability 1/2.All other nodes have lower rumor centrality in this case.
  • Proof of Lemma 6: If the largest infected subtree exceeds n/2 nodes, the source is not the local rumor center and cannot be identified as the rumor source.This establishes the failure condition used in the lemma's case analysis.
  • Proof of Lemma 6: The proof treats even and odd n separately, with the odd case presented in detail and the even case deduced similarly.The derivation uses the short form of PG in the displayed calculations.

D. Proof of Lemma 7

The proof of Lemma 7 analyzes MAP detection through suspect-neighbor configurations, symmetry, subtree events, and separate parity cases for the infection count and distance.

  • Proof setup: The proof conditions on the number m of suspect neighbors of the rumor source and invokes Proposition 1 and Lemma 6.Detailed derivations are presented for representative cases, with other configurations deduced similarly.
  • Event decomposition: The argument uses union bounds and symmetry to combine detection-error events across suspect subtrees.It also uses disjointness when at most one subtree can contain more than n/2 infected nodes.
  • Case analysis: The proof treats odd and even infection counts separately, with additional distinctions based on the parity of the distance between suspects.Representative cases include odd n with even d and even n; remaining cases are stated to follow similarly.

I. Proof of Lemma 8

Lemma 8 characterizes when the MAP estimator identifies the source using the local rumor-center condition, while distinguishing a special neighbor configuration from general cases.

  • Local rumor center criterion: If s∗ is the local rumor center with respect to its suspect neighbors, its rumor centrality is at least that of suspect neighbors and strictly exceeds that of other suspects.This comparison follows from Proposition 1.
  • Local rumor center criterion: When all m suspect neighbors of s∗ are neighboring suspect nodes, MAP identifies s∗ if and only if s∗ is the local rumor center.In general cases, MAP may still identify s∗ even when it is not a local rumor center.

J. Proof of Lemma 9

The proof expresses the error detection probability as the complement of correct detection probability and invokes symmetry in the resulting relation.

  • Error probability: The error detection probability is defined as Pe(n|s∗) = 1−Pc(n|s∗).The subsequent equality follows from symmetry.

K. Proof of Corollary 10

The proof of Corollary 10 establishes how the MAP estimator’s error probability varies with infection count and node degree by analyzing parity cases and derivatives.

  • Dependence on infection count: Pe1(n) is the MAP error probability for identifying the neighboring suspect node s∗ as the rumor source estimate.The proof compares consecutive infection counts, beginning with n = 2i and n = 2i + 1.
  • Derivative argument: The derivation represents conditioned subtree-size probabilities using PG(X1 = x1|n) and combines logarithmic derivative bounds.The functions g1 and g2 are introduced to prove the required derivative is non-positive.
  • Dependence on node degree: The proof shows that δ · Pe1(n) = 1 − Pc(n) decreases with δ for fixed infection number n ≥ 2.It establishes non-positive derivatives by mathematical induction, starting from n = 2.
  • Dependence on infection count: Pe1(n = 2i + 1) = Pe1(n = 2i), according to the proof’s induction step.This equality is used to relate error probabilities at successive infection counts.
Loading 1301.6312v4…