{'fraction_non_alphanumeric': 0.05723947672866424, 'fraction_numerical': 0.015466761591172022, 'mean_word_length': 3.6319868095630667, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rooting out the Rumor Culprit from Suspects

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 {\delta}, 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 {\delta} 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 {\delta}. Second, when the suspects form a connected subgraph of the network, Pc(n) asymptotically significantly exceeds the a priori probability if {\delta}>2, and reliable detection is achieved as {\delta} becomes large; furthermore, it monotonically decreases with n and increases with {\delta}. Third, when there are only two suspects, Pc(n) is asymptotically at least 0.75 if {\delta}>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
Spreading of epidemics and information cascades through social networks is ubiquitous in the modern world [1], [2]. Examples include the propagation of infectious diseases, information diffusion in the Internet, tweeting and retweeting of The work of W. Dong  popular Twitter topics. In general, any of these situations can be modeled as an epidemic-like rumor spreading in a network [3], [4]. A key challenge is to identify the rumor source by leveraging the network topology, suspect characteristics and the observation of infected nodes. Finding this rumor source has practical applications and also allows us to better understand the role of the network in the spreading amplification effect.
In practical scenarios, there is often a priori knowledge that certain nodes are more likely to be the rumor source and the others are less likely so. Indeed, there are many situations where only a portion of nodes in the network have the potential to initiate the rumor spreading. When an infectious disease is spread, the frequent travellers from earlier infected cities have a higher suspicion of causing an epidemic outbreak in a new city. When a network of water pipes is polluted by microorganisms or chemical substances, only the suspicious vulnerable points need to be examined to identify the pollution source. When the cyberspace is hit by rumors or computer viruses, most of the victims are in fact innocent and thus not all victims should be suspected as the culprit. Therefore, it is not necessary to treat every infected node as the possible rumor source when identifying the source. Hereafter, we call the nodes that have the potential to initiate the rumor spreading in a network as suspect nodes. Indeed, as we will see in this paper, the suspect characteristics significantly affect detectability, and add an interesting dimension to identifying the source reliably.
In this paper, we consider the issue of reliably identifying a single rumor source from among a number of suspects, conditioned on a snapshot observation of infected nodes in a network. The rumor spreading process is modeled by the susceptible-infected (SI) model, a special case of the general susceptible-infected-recovered (SIR) model for infectious disease spreading [4]. In the SI model, there are two types of nodes: i) susceptible nodes that are capable of becoming infected, ii) infected nodes that can spread the rumor; and spreading occurs in a cascading manner, i.e., once a susceptible node gets infected by its neighbor, it remains infected (having the rumor) and in turn may infect its other susceptible neighbors. Our goal is to identify the rumor source based only on the knowledge of network structure, the set of suspect nodes and the snapshot observation of the infected nodes. The a priori suspect set and its characteristics like connectivity bring about new ingredients and challenges to the detection problem.

A. Related Works
Over the past decade, abundant works have dealt with the problems on epidemic outbreaks across networks. The main focus has been to understand the impacts of network structure arXiv:1301.6312v4 [cs.SI] 9 May 2013 and the infection/cure rates of diffusion processes, such as in [5]- [9]. Besides, many researchers have developed network inference techniques to learn the underlying network parameters and predict the propagation characteristics, such as in [10]- [13]. In addition, the issue of extracting the influential source nodes for epidemic spreadings has also been considered, such as in [1], [14], [15].
The rumor source estimation problem has only been recently studied in the pioneering work [3], [16] for a single rumor source identification using the SI model. In particular, for regular tree-type networks, [3], [16] proposed a maximum likelihood (ML) estimator and derived its asymptotic performance. When the node degree δ = 2, i.e., for a linear network, the asymptotic correct detection probability is zero; when δ = 3, it is 0.25; when δ > 3, it is a positive constant value φ 1 (δ), which approaches 0.307 as δ grows large. Besides, other types of networks and models have also been considered, such as geometric trees [3], random graphs [17], identification of multiple rumor sources in the SI model [18] and its counterpart in the SIR model [19], and noisy estimation of a single source [20]. However, all these works assume that every node in the network has the potential to initiate the rumor spreading.

B. Our Contributions
In this paper, we study the single rumor source estimation problem with the a priori knowledge that the rumor source is restricted to a specified suspect set S of suspect nodes in a network G. We construct a maximum a posteriori (MAP) estimator to identify the rumor source, and focus on the analysis of P c (n), the correct detection probability of the estimator upon observing n infected nodes. For regular treetype networks with node degree δ, we characterize P c (n) in the finite and the asymptotic (with the number of infected nodes tending large) regimes, using the Pólya's urn model in probability theory [21] and assuming a uniform a priori distribution of the suspects in S . To handle the analysis of the MAP estimator, we develop a key concept of local rumor center, which generalizes the notion of rumor centrality in [3] and proves to be a handy tool considerably facilitating the analysis. We also highlight new insights for the detection in general networks with suspects. We find that the introduction of the a priori knowledge of suspect set substantially enriches, rather than simplifies, the rumor source estimation problem.
Our main contributions are summarized as follows. 1) When S contains all the nodes in G, our estimator reduces to that in [3], [16], recovering the same asymptotic detection performance results on P c (n) as theirs. Our proofs are different and appear to be more natural intuitively, requiring less mathematical machinery. Furthermore, we obtain exact detection performance results on P c (n) for regular trees with any finite n and δ. In addition, we prove that P c (n) monotonically decreases with n and increases with δ even in the finite regime. This result formalizes our intuition that the earlier the observation is made the more reliable it is to estimate the rumor source.
2) In the case where S with cardinality k forms a connected subgraph of G, we obtain exact detection performance results on P c (n) for regular trees in both finite and asymptotic regimes. Asymptotically, lim n→∞ P c (n) is always a positive constant value φ 2 (δ, k). Notably, φ 2 (δ, k) significantly exceeds the a priori probability 1/k for regular trees with degree larger than two, and is at least 1/2 even with arbitrarily large cardinality k. Furthermore, the MAP estimator achieves reliable detection, i.e., lim n→∞ P c (n) → 1 as δ grows sufficiently large. We also prove that P c (n) monotonically decreases with n and increases with δ even in the finite regime. It is a striking observation that P c (n) is at least 1/2 (with δ > 2) given the a priori knowledge of suspects -even for arbitrarily large k as long as it is finite, in contrast to that P c (n) is at most 1/2 with no a priori knowledge in the case where every node in the network has the potential to initiate the rumor spreading [3]. Along with the analysis, we present an interpretation of that key observation.
3) In the case where S contains only two suspect nodes separated by their shortest path distance d (measured by number of hops), we obtain exact detection performance results on P c (n) in the finite regime; and when δ ≥ 3, we show that lim n→∞ P c (n) ≥ 0.75, which furthermore approaches one as δ grows sufficiently large. In addition, P c (n) increases with the separation distance d for general regular trees. 4) When S with cardinality k forms a general subgraph of G, we prove that the MAP estimator achieves the smallest detection probability when all the suspects form a single connected subgraph of G. This result formalizes our intuition that the more clustered the suspects are the more difficult it is to identify the rumor source.

C. Organization
First, Section II describes the framework of the SI rumor spreading model and the MAP estimator to identify the rumor source in general networks. Second, in Section III we establish analytical results on the detection probability of the MAP estimator for regular tree-type networks, under four representative scenarios. Third, we design and implement algorithms to compute the exact detection probability of the MAP estimator for regular tree-type networks in Section IV. Fourth, we carry out simulation experiments to corroborate and illustrate our analytical results in Section V. Finally we conclude the paper in Section VI.

II. Rumor Spreading Model and Rumor Source Estimator
In this section, we describe the SI rumor spreading model, give the MAP estimator for the rumor source in general networks, and introduce the notion of local rumor center. To facilitate the reader, we list the key parameters used in the paper in Table I.

A. Rumor Spreading Model
In general, an undirected network G = (V, E) consists of a set of nodes V and a set of edges E. The set of nodes V is assumed countably infinite so as to avoid any boundary effect, and any pair of nodes may infect each other if and only if they are connected by an edge in E. The network is assumed to be static, i.e., no node joins or leaves. Definition δ node degree G n snapshot observation of n infected nodes T s u subtree rooted at node u with node s as the source R(u, G n ) rumor centrality of node u in G n S suspect set s i , i ∈ N + suspect node s * original rumor sourcê s estimate of the rumor source s rumor source by assumption P s (·) prior distribution of the rumor source over the suspects probability distribution of an infection sample in the rumor spreading process or an infection sample equivalently constructed using the Pólya's urn model P c (·) correct detection probability P e (·) error detection probability, i.e., the complement of P c (·) P e1 (·) error detection probability by one specified subtree We consider the case where only a single node in an a priori specified suspect set S is the original rumor source who initiates the infection process among the susceptible nodes in G, where S = {s 1 , s 2 , · · · , s k } ⊆ V has cardinality k. Nodes in S are called suspect nodes. We assume an a priori distribution P s of the rumor source over the nodes in S , and thus P s (s) denotes the probability that s ∈ S initiates the rumor spreading. For normalization, we have Throughout this paper, we assume a uniform distribution P s over the nodes in S , i.e., P s (s) = 1/k for any s ∈ S . Admittedly this uniform prior assumption is a restriction, but we remark that our analysis can be extended to handle the more general case of non-uniform priors, with slightly more technical modifications. The rumor spreading process in an SI model unfolds as follows. Initially, only a single node s * ∈ S possesses a rumor to spread over the network G. Once a node has the rumor, it is termed as infected. An infected node may infect its neighbors, independent of all the other nodes. Let τ i j be the time it takes for node j to receive the rumor from its neighbor i after i has the rumor, where (i, j) ∈ E. We assume that {τ i j , (i, j) ∈ E} are mutually independent and exponentially distributed with a normalized rate λ = 1 (without loss of generality).

B. Rumor Source Estimator: Maximum a Posteriori (MAP)
(1) MAP estimator Suppose that a rumor originates from a node s * ∈ S . We observe the network G at some point in time and find a snapshot of n infected nodes, which are collectively denoted by G n . Due to the SI model, G n must form a connected subgraph of G and contain at least a node in S , which obviously includes s * . Our goal is to construct an estimator to identify a nodeŝ as the rumor source. The detection is correct ifŝ = s * . Now, conditioned on G n , the source node has a uniform distribution over the nodes in S G n to initiate the spreading. Utilizing the Bayes' rule, the maximum a posteriori (MAP) estimator of s * maximizes the average correct detection probability and is given bŷ where P G (G n |s) is the probability of observing G n assuming s to be the rumor source. Note that a key difference from the model in [3] is that in our work the rumor source resides in a priori suspect set S ⊆ V. Naturally, we would first evaluate P G (G n |s) for all s ∈ {S G n } and then pick the one with the maximal value to beŝ.
(2) Optimal MAP estimator for regular trees In general, the evaluation of P G (G n |s) may be computationally prohibitive since it is related to counting the number of linear extensions of a partially ordered set [3], [22]. Therefore, we leverage the concept of rumor centrality, first introduced in [3], which would enable an implementation of our estimator using only O(n) computation steps. In particular, the optimal MAP estimator for a regular tree is given bŷ where R(s, G n ) is the rumor centrality of node s in G n , and can be evaluated by where T s u is the subtree rooted at node u with node s as the source in G n and T s u is the number of nodes in T s u ; e.g., see Fig. 1.
(3) Approximate estimator for general trees and graphs For general trees, the estimator (3) with the rumor centrality can be a reasonable heuristic. So, an approximate estimator is given byŝ ∈ arg max s∈{S G n } R (s, G n ).
Besides, a message-passing algorithm has been proposed in [3] to compute the rumor centralities for all the nodes in a general tree G n with n nodes using only O(n) computation steps. For general graphs, the estimator (3) using the rumor centrality can be leveraged as a heuristic. Intuitively, a rumor tends to travel from the source to each infected node along a minimum-distance path [3], [20], and thus we approximate the diffusion tree by a breadth-first search (BFS) tree. So an approximate estimator may be given bŷ where T bfs (s) is the BFS tree with node s as its root in a general graph G n . The complexity of implementing (6) is O(n 3 ).

C. Local Rumor Center in General Trees
In the following, we develop a notion of local rumor center, which enables an efficient implementation of the estimator (3) and will be instrumental for our subsequent analysis. The local rumor center may be viewed as a "conditional" rumor center, and renders the performance analysis of the MAP estimator (3) tractable. A useful recursive relationship is that, for any two neighboring nodes u and v in a tree G n [3], Now, consider a node ω with a neighbor set N(ω) and a sub-neighborhood N l (ω) ⊆ N(ω). If R(ω, G n ) ≥ R(u, G n ) for all u ∈ N l (ω), then ω is called the local rumor center with respect to (w.r.t.) the sub-neighborhood N l (ω) of G n . More precisely, the local rumor center is characterized as follows.
Proposition 1. i) Given a tree G n of n nodes, if node ω is the local rumor center w.r.t. a sub-neighborhood N l (ω) ⊂ G n , then for any u ∈ N l (ω), we have T ω u ≤ n/2; and for any u ∈ T ω u \ {u}, we have R(u , G n ) < R(ω, G n ). ii) If there is a node ω such that T ω u ≤ n/2 for all u ∈ N l (ω), then ω is a local rumor center w.r.t. the sub-neighborhood N l (ω) ⊂ G n . iii) Furthermore, if node ω is the local rumor center w.r.t. a sub-neighborhood N l (ω) ⊂ G n , then there is at most a node u ∈ N l (ω) such that R(u, G n ) = R(ω, G n ), which holds if and only if T ω u = n/2. Remark 1: In fact, the local rumor center is a generalization of the rumor center in [3], which is defined as the node with the maximal rumor centrality in G n . When N l (ω) = N(ω), the two notions coincide. However, the rumor center may belong to the set G n \S and thus is not the solution of the estimator (3). Besides, note that we can find at most two local rumor centers from a connected suspect set S w.r.t. the sub-neighborhood restricted by S , when we are given G n . The notion of local rumor center not only generalizes the concept of rumor center, but also will prove to be a key to tackle the MAP estimator with suspects.
Next, consider u ∈ T ω u \ {u}, and let P(u, u ) be the set of nodes along the shortest path from u to u , but not including u. Repeatedly using (7), we have Since , then from (8), we have R(u, G n ) ≤ R(ω, G n ). Therefore, ω is the local rumor center w.r.t. its sub-neighborhood N l (ω) ⊂ G n .
As for Proposition 1-iii, if there is a node u ∈ N l (ω) such that R(u, G n ) = R(ω, G n ), then from (8), we have T ω u = n/2; the deduction holds backward. Besides, there can be at most a subtree T ω u (u ∈ N l (ω)) such that T ω u = n/2, since the total number of nodes in G n is n and any two subtrees with ω as the source are disjoint. As a result, if node ω is the local rumor center w.r.t. a sub-neighborhood N l (ω) ⊂ G n and there has already been a node u * ∈ N l (ω) such that R(u * , G n ) = R(ω, G n ), then for all u ∈ N l (ω) \ {u * } we have T ω u < n/2, i.e., T ω u /(n − T ω u ) < 1. Again, from (8), we have R(u, G n ) < R(ω, G n ).

III. Detection Probability in Regular Trees: Analytical Results
In this section, we analyze the performance of the MAP estimator for regular tree-type networks. Four representative scenarios are investigated: when the suspect set contains all the nodes in the network, i.e., with no a priori knowledge; when the suspect set forms a connected subgraph of the network; when the suspect set contains only two nodes; when the suspect set contains multiple nodes which are possibly disconnected. In analysis we exploit the key fact that the rumor spreading process on regular trees is equivalent to the ball drawing process in the Pólya's urn model [21], and thus establish the performance results of the MAP estimator in both finite and asymptotically regimes. In the following, we introduce our main results and provide their proofs.

A. Main Results
We focus on the correct detection probability P c (n), the probability of the MAP estimator correctly identifying the rumor source from the suspect set S upon observing G n of n infected nodes in the network G = (V, E). For a regular tree with node degree δ, we have the following four characterizations for P c (n).
(1) The case where all nodes are suspects In this case, S = V, every infected node in an observation G n has the potential to be the rumor source, i.e., without any a priori knowledge. Assuming a node s * to be the rumor source with δ neighbors v 1 , . . . , v δ , we could observe X j = x j (1 ≤ j ≤ δ) infected nodes in each subtree T s * v j rooted at v j with s * as the source in G n , where X j is a random variable; e.g., see Fig. 2. Then, we will establish the following theorem.
with s * as the source on a regular tree G with node degree δ = 3, respectively. Theorem 2. Suppose S = V, i.e., every infected node is a suspect node, then: i) When δ = 2 (linear network), and P c (n) = O(1/ √ n) with sufficiently large n. ii) When δ = 3, and P c (n) = 0.25 + O(1/n) with sufficiently large n. iii) When δ > 3, we use Algorithm 1 in Section IV to compute the exact value of P c (n) with finite n. Besides, where I x (α, β) is the incomplete Beta function with parameters α and β; and φ 1 (δ) → 1 − ln 2 ≈ 0.307 as δ → ∞.
Remark 2: When S = V, the MAP estimator (3) in effect reduces to the ML estimator established in [3], [16]. 1 The asymptotic parts of Theorem 2 have been established in [3], [16] using a different approach from ours that explicitly relies on the exponential distribution of the infection time. Therefore, without any a priori knowledge, the estimator achieves a strictly positive detection probability if the network is not linear, but it is asymptotically upper bounded by 0.307.
(2) The case of connected suspects In this case, S = {s 1 , . . . , s k } of cardinality k forms a connected subgraph of G; e.g., see Fig. 3. With this a priori knowledge, we will establish the following theorem.
Theorem 3. Suppose that S forms a connected subgraph of G, then: i) When δ = 2 (linear network), and P c (n) and P c (n) = (k + 1)/(2k) + O(1/n) with sufficiently large n. iii) When δ > 3, we use Algorithm 2 in Section IV to compute the exact value of P c (n) with finite n. Besides, Remark 3: For linear networks, P c (n) can barely exceed the a priori probability 1/k. When δ ≥ 3, P c (n) is at least max{1/k, 1/2}, which is in sharp contrast to that P c (n) is at most 1/2 with no a priori knowledge as in Theorem 2. Furthermore, the MAP estimator achieves reliable detection as δ grows sufficiently large. Therefore, the performance of the MAP estimator is significantly improved and reliable detection can be achieved when the a priori knowledge on the suspect nodes is given.
Remarkably, even with k → ∞ our results do not degenerate to the case of no a priori knowledge. This is a seemingly counter-intuitive fact, because one would expect that as k grows large Theorem 3 would recover the results in Theorem 2 (and thus [3]). To understand this fact, the key is that, no matter how large k is, the suspect set has a boundary in the infinite regular tree network. Those suspect nodes nearby the boundary are easier to identify than those further inside the suspect set. Since the performance of the MAP estimator is the correct detection probability averaged among all suspect nodes, asymptotically reliable estimation can be attained, and such a phenomenon is especially pronounced when the node degree δ is large as then most of the suspect nodes are located nearby the boundary. In particular, we need to note that this scaling behavior does not rely on n; that is, k and n can separately grow large, without dependency between each other, -indeed k can grow even faster than n. We therefore believe that Theorem 3 reveals a fundamental distinction between the MAP and the ML estimation philosophies, and indicates that the introduction of the a priori knowledge of suspect set Fig. 4. Illustration of two suspect nodes with distance d on a regular tree G with node degree δ = 3. There are d nodes from s 1 to s 2 excluding s 1 , which are sequentially denoted by does enrich, rather than simplify, the rumor source estimation problem.
(3) The case of two suspects In this case, S contains only two suspect nodes s 1 and s 2 . We let d be their shortest path distance on G (i.e., the number of hops from s 1 to s 2 ); e.g., see Fig. 4. Since we can obviously ensure correct estimation of the source if d ≥ n, we assume d < n. With this a priori knowledge of S , we have the following theorem.
Theorem 4. Suppose S only contains two suspect nodes, and denote by d their shortest path distance (d < n), then: i) When δ = 2 (linear network), ii) When δ = 3, we use Algorithm 3 in Section IV to compute the exact value of P c (n) with finite n. Besides, iii) When δ > 3, we use Algorithm 3 in Section IV to compute the exact value of P c (n) with finite n. Besides, and φ 3 (δ) → 1 as δ → ∞. iv) In general, P c (n) monotonically increases with d.
Remark 4: Theorem 4 formalizes our intuition that it is more difficult to correctly identify the rumor source if the two suspect nodes are closer. We see that when δ ≥ 3, the a priori probability 1/2 can be significantly exceeded.
(4) The case of multiple suspects with general connectivity In this case, S = {s 1 , . . . , s k } of cardinality k forms a general subgraph of G; e.g., see Fig. 5. Note that this subgraph can be disconnected in general. With the a priori knowledge of S , we will establish the following theorem. Theorem 5. Suppose S contains k suspect nodes, then: i) When δ = 2 (linear network), and and iv) In general, P c (n) is minimized, among all possible S 's with |S | = k, when the k suspect nodes constitute a connected subgraph in G as in Theorem 3.
Remark 5: Theorem 5 can be established as a consequence of Theorems 3 and 4. When there are k suspect nodes, the MAP estimator achieves the smallest detection probability in the scenario of Theorem 3. This result formalizes our intuition that the more clustered the suspects are the more difficult it is to identify the rumor source.

B. Equivalence to the Pólya's Urn Model
(1) Preliminaries We first introduce the preliminaries on the Pólya's urn model in probability theory, and then show that the rumor spreading process on regular trees is equivalent to the ball drawing process in the Pólya's urn model, a connection first utilized in [16] for asymptotic analysis. Our approach is to leverage it to derive exact detection probability in the more general finite regime (recovering the asymptotic result as a special case).
Pólya's urn model [21,Chap. 4]: initially, the urn contains b j balls of color C j (1 ≤ j ≤ δ); at each uniform drawing of a single ball, the ball is returned together with balls of the same color; after n drawings, the number X j is the number of times that the balls of color C j are drawn. Then the joint distribution of {X j , 1 ≤ j ≤ δ} is given by where b = δ j=1 b j and δ j=1 x j = n. As n → ∞, the limiting joint distribution of the ratios {X j /n, 1 ≤ j ≤ δ} converges to the Dirichlet distribution, whose density function is given by where α j = b j / , α = δ j=1 α j and δ j=1 y j = 1. Here, Γ(α) is the Gamma function with parameter α.
Besides, the marginal distribution of X 1 is In fact, it can be seen as a special case of the Pólya's urn model with two colors.
(2) Equivalence to the Pólya's urn model Next, we show that the rumor spreading on regular trees can be modeled by ball drawing in the Pólya's urn model, whose known distributions are used to obtain Theorems 2-5.
For a rumor source s * with δ neighboring nodes v 1 , . . . , v δ , let T s * v j (1 ≤ j ≤ δ) be the subtree rooted at node v j with node s * as the source in G n , and define a random variable X j as the number of nodes in T s * v j ; e.g., see Fig. 2. We denote the set of susceptible neighbors of infected nodes as the rumor boundary. In the rumor spreading process, nodes in G n are infected sequentially, and thus we have the following: initially, s * has one neighbor in each subtree T s * v j (1 ≤ j ≤ δ) that belongs to the rumor boundary; after one of those nodes is infected, it introduces δ − 1 new nodes into the rumor boundary; finally, n − 1 nodes are infected besides s * . Due to the memoryless property of exponential distribution and the independent and identically distributed (i.i.d.) property of the infection times {τ i j , (i, j) ∈ E}, in each step, the infected node is uniformly selected from the rumor boundary. Now, the resulting infection G n with X j nodes in T s * v j (1 ≤ j ≤ δ) can be constructed in an equivalent way by the Pólya's urn model [21,Chap. 4]: initially, the urn has one ball for each color C j ; at each uniform drawing of a single ball, the ball is returned together with = δ − 2 additional balls of the same color; after n − 1 draws, X j is the number of times that the balls of color C j are drawn.
Therefore, in the rumor spreading process, if we assume s * to be the rumor source with δ neighbors v 1 , . . . , v δ and observe n infected nodes G n with X j nodes in each subtree T s * v j (1 ≤ j ≤ δ), then from (22), the joint distribution of {X j , 1 ≤ j ≤ δ} is given by where δ j=1 x j = n − 1. Besides, the marginal distribution of X 1 is We are also interested in the limiting marginal distribution of the ratio X 1 /n as n → ∞. From (26), we have where lim n→∞ ξ ( n, δ) = 0 for any given δ.
(3) Markov concatenation of the Pólya's urn model Next, we focus on the case of two suspects. Notably, in Theorem 4, we use the Markov concatenation of the Pólya's urn model to derive the probability distribution of the infection observed in the rumor spreading process, focusing on the nodes along the path between two suspects s 1 and s 2 .
Assume s 1 to be the rumor source s * , and let P = {v 0 = s 1 , v 1 , · · · , v d = s 2 } be the shortest path from s 1 to s 2 ; e.g., see Fig. 4. Let a random variable Z h (1 ≤ h ≤ d) be the number of nodes in subtree T s * v h rooted at node v h with node s * as the source in G n . It is clear that In the proof of Theorem 4, we focus on the error detection probability P e (n) = 1−P c (n). Therefore, without loss of generality, we assume Z h > 0 for all 1 ≤ h ≤ d. Here, we can also construct the random variables Z h (1 ≤ h ≤ d) equivalently with the concatenation use of the Pólya's urn model.
For random variable Z 1 , we construct it using the Pólya's urn model as follows: initially, the urn has b 1 1 = 1 black ball and b 1 1 = δ−1 white balls; at each uniform drawing of a single ball, the ball is returned together with = δ − 2 additional balls of the same color; after n−1 draws, the number Z 1 is the number of times that balls of black color are drawn. Therefore, from (22), the distribution of Z 1 is we construct it using the Pólya's urn model as follows: initially, the urn has b h b = 1 black ball and b h w = δ − 2 white balls; at each uniform drawing of a single ball, the ball is returned together with = δ − 2 additional balls of the same color; after z h−1 − 1 draws, the number Z h is the number of times that balls of black color are drawn. Again, from (22), the distribution of Z h is

C. Proof of Theorem 2: Suspecting all Nodes
In the case of S = V, we only need to consider an arbitrary node s * ∈ G as the rumor source by symmetry. For a source s * with m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m } ⊂ S , let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ m) of G n . Then, we have the following lemma for the argument of Theorem 2 (m = δ) and Theorem 3 (m ≤ δ); see its proof in Appendix-A.
Lemma 6. To correctly identify source s * with m neighboring suspect nodes as the estimateŝ, we have Remark 6: Lemma 6 is deduced from Proposition 1. In order to prove Theorem 2 (and Theorem 3), we should find the conditions, under which s * is the local rumor center w.r.t. N l (s * ) of G n , such that the estimator (3) can correctly identify s * as the source.
Since S = V, the source s * has m = δ neighboring suspect nodes. Using Lemma 6, we can write P c (n) as where P G δ j=1 (X j = x j ) is given by (27). In the following, we will establish the argument of Theorem 2 for three special cases when the node degree δ = 2, δ = 3 and δ > 3, respectively.
(1) Detection probability when δ = 2 Proof of Theorem 2-i. When δ = 2, the distribution in (27) can be written as From (35), the correct detection probability is In the above, the detailed deduction is in Appendix-B. As n → ∞, by the Stirling's formula, we have (2) Detection probability when δ = 3 Proof of Theorem 2-ii. When δ = 3, the distribution in (27) can be written as From (35), the correct detection probability is In the above, the detailed deduction is in Appendix-C.
(3) Detection probability when δ > 3 When n is finite, we can numerically compute the exact detection probability using Algorithm 1 in Section IV. When n → ∞, we can obtain the asymptotic correct detection probability similarly to those in [16].
Before the argument of Theorem 2-iii, we present the following lemma, which will be also used in the argument of Theorem 3-iii; see its proof in Appendix-D. For a source s * with m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m } in S , let a random variable X j be the number of nodes in each subtree To correctly identify source s * with m neighboring suspect nodes, we have where P G (E c 1 ) and P G (F c 1 ) are the probabilities that the complements of events E 1 and F 1 occur, respectively. Proof of Theorem 2-iii. Since E 1 = {X 1 < n/2} and F 1 = {X 1 ≤ n/2}, i.e., E 1 = {X 1 /n < 1/2} and F 1 = {X 1 /n ≤ 1/2}, from (29), we have In other words, from (30), we have where lim n→∞ ξ(n, δ) = 0. Since S = V, the source s * has m = δ neighboring suspect nodes. Using Lemma 7, the asymptotic correct detection probability is Besides, we see that the asymptotic value lim n→∞ P c (n) > 0.25 if the node degree δ > 3. Furthermore, it approaches 1 − ln2 ≈ 0.307 as δ → ∞.

D. Proof of Theorem 3: Connected Suspects
Consider the case where S = {s 1 , s 2 , . . . , s k } with cardinality k forms a connected subgraph of the network G. Here the restriction of the suspect set poses challenges for analyzing the problem, and we thus leverage the concept of local rumor center and exploit the graph structure so as to tackle the MAP source estimator. By the Bayes' rule and the a priori knowledge that P s (s * ) = 1/k for any s * ∈ S , we have We first find the correct detection probability P c (n|s * ) for each suspect node s * ∈ S . Assume that s * ∈ S is the rumor source and it has m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m } ⊂ S . Let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ m) of G n , then by Lemma 6, we should find the conditions that s * is the local rumor center w.r.t. N l (s * ) of G n , and the estimator (3) can correctly identify s * as the source.
Using Lemma 6, we can write P c (n|s * ) as where P G δ j=1 (X j = x j ) is given by (27). In the following, we will establish the argument of Theorem 3 for three special cases when the node degree δ = 2, δ = 3 and δ > 3, respectively.
(1) Detection probability when δ = 2 Proof of Theorem 3-i. When δ = 2, from (36), we have From (46), the correct detection probability for a suspect node s * with m neighbors in the suspect set S is In the above, the detailed deduction is in Appendix-E. For a suspect set S with cardinality k that forms a connected subgraph of a linear network G, we know that only the two suspect nodes at the endpoints of the sub-linear network have one neighboring suspect node, and all the other suspect nodes have two neighboring suspect nodes. Therefore, from (45), we have P c (n) = 1 As n → ∞, by the Stirling's formula, we have (2) Detection probability when δ = 3 Proof of Theorem 3-ii. When δ = 3, from (39), we have From (46), the correct detection probability for a suspect node s * with m neighbors in the suspect set S is In the above, the detailed deduction is in Appendix-F. For a suspect set S with cardinality k that forms a connected subgraph of a regular tree G with node degree δ = 3, for each suspect node s * ∈ S , we first find the number of its neighboring suspect nodes. Note that given s * with m neighboring suspect nodes, P c (n|s * ) is one subtracted by a same factor, 1/4 − 1/(8 n/2 + 4), m times, each of which accounting for one neighboring suspect node of s * connected by an edge. Since there are k−1 edges connecting the k suspect nodes in S , each edge will account for a reduction of the factor twice. Therefore, from (45), we have (3) Detection probability when δ > 3 When n is finite, we can numerically compute the exact detection probability using Algorithm 2 in Section IV. When n → ∞, we can obtain the asymptotic correct detection probability using Lemma 7 and an insightful analysis into the graph structure.
Proof of Theorem 3-iii. From (43), we have where lim n→∞ ξ ( n, δ) = 0. Using Lemma 7, the correct detection probability for a suspect node s * with m neighbors in the suspect set S is Note that the residual term ξ(n, δ) is identical 2 for all m neighboring suspect nodes of s * . For a suspect set S with cardinality k that forms a connected subgraph of a regular tree G with node degree δ > 3, for each suspect node s * ∈ S , we first find the number of its neighboring suspect nodes. Note that, P c (n|s * ) is one subtracted by a common factor m times, each of which accounting for one neighboring suspect node of s * connected by an edge. Since there are k − 1 edges connecting the k suspect nodes in S , each edge will account for a reduction of the factor twice. Therefore, from (45), we have From Fig. 6, we see that I 1/2 1 δ−2 , δ−1 δ−2 > 0.75 as the node degree δ > 3. Therefore, we have for any sufficiently large n and δ > 3. Besides, since 2(k − 1)/k = 2 as k → ∞, thus from (56), we have Furthermore, since I 1/2 (0, 1) = 1 (setting δ → ∞), we thus have lim δ→∞ lim n→∞ P c (n) → 1.
Importantly, note that the growth of δ does not need to depend on the growth of n.

E. Proof of Theorem 4: Two Suspects
In the case where S = {s 1 , s 2 } contains only two suspect nodes, let d be the shortest path distance between s 1 and s 2 on G. We assume s 1 to be the rumor source s * by symmetry, let P = {v 0 = s 1 , v 1 , · · · , v d = s 2 } be the shortest path from s 1 to s 2 , and define a random variable Z h to be the number of nodes in the subtree T s In the following, we focus on the error detection probability, i.e., P e (n) = 1 − P c (n). As a result, we assume Z h > 0 for all 1 ≤ h ≤ d. Since there are only two suspect nodes in S , P e (n) can be written as where P G d h=1 (Z h = z h ) is given by (33). When n is finite, we can numerically compute the exact detection probability using Algorithm 3 in Section IV. In the following, we will establish the argument of Theorem 4.
(1) Detection probability when δ = 2 Proof of Theorem 4-i. From (4), we have R(s * , G n ) = n−1 , then z 1 ≥ (n+d+1)/2. Note that we only need to consider the distribution of Z 1 . When δ = 2, the distribution in (31) can be written as From (60), the error detection probability is In the above, the detailed deduction is in Appendix-G.
(2) Detection probability when δ = 3 Proof of Theorem 4-ii. First of all, consider the case when d = 1. From (52), the error detection probability is P e (n) = 1 − P c (n) Now, consider the case when d = 2. The distribution in (33) can be written as From (7), we have R(s 2 , G n ) = R(s * , G n ) z 1 n−z 1 z 2 n−z 2 . If R(s * , G n ) ≤ R(s 2 , G n ), then z 1 + z 2 ≥ n. Using (60) and letting n → ∞, the error detection probability is In the above, the detailed deduction is in Appendix-H.
(4) Increasing detection probability with distance Proof of Theorem 4-iv. Equivalently, we prove that P e (n) decreases with d. Without loss of generality, we assume Z h > 0 for all 1 ≤ h ≤ d. The proof will be completed by showing which leads to the contradiction that R(v d−1 , G n ) > R(s * , G n ). As a result, we have Z d−1 ≤ n/2. As Z d−1 ≤ n/2, then Z d < n/2 and thus Z d /(n − Z d ) < 1. As a result, we have which is in contradiction to the assumption of R(v d , G n ) ≥ R(s * , G n ).

F. Proof of Theorem 5: Multiple Suspects
Consider the case where S = {s 1 , s 2 , . . . , s k } with cardinality k forms a general subgraph of the network G. From (45), we have We first find the correct detection probability P c (n|s * ) for each suspect node s * ∈ S . Assume that s * ∈ S is the rumor source and it has m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m }, subject to that each subtree T s * v j (1 ≤ j ≤ m) of G contains at least one suspect node in S . In the following, we call the nodes in N l (s * ) as suspect neighbors. Let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ m) of G n , then we have the following lemma; for its proof see Appendix-I.

Lemma 8.
To correctly identify source s * with m suspect neighbors, we have where P c (n|s * , conn) is the correct detection probability for s * when all the m suspect neighbors are neighboring suspect nodes of s * .
Remark 8: Lemma 8 is deduced from Proposition 1. In order to prove Theorem 5, we shall find the lower bound of P c (n|s * ) in the following.
When the k suspect nodes in S form a connected subgraph of the network G, we can exactly compute P c (n) in both the finite and asymptotic regimes. In the following, we will establish the argument of Theorem 5.
(1) Detection probability when δ = 2 Proof of Theorem 5-i. We use Lemma 8 and (48) to obtain a lower bound of the correct detection probability for a suspect node s * with m suspect neighbors: For a suspect set S with cardinality k that forms a general subgraph of a linear network G, we know that only the two suspect nodes at the endpoints of the sub-linear network have one suspect neighbor and all other suspect nodes have two suspect neighbors. Therefore, from (70), we have As n → ∞, by the Stirling's formula, we have (2) Detection probability when δ = 3 Proof of Theorem 5-ii. We use Lemma 8 and (52) to obtain a lower bound of the correct detection probability for a suspect node s * with m suspect neighbors as For a suspect set S with cardinality k that forms a general subgraph of a regular tree G with node degree δ = 3, for each suspect node s * ∈ S , we first find the number of its suspect neighbors. Note that given s * with m suspect neighbors, the lower bound of P c (n|s * ) is one subtracted by a same factor, 1/4 − 1/(8 n/2 + 4), m times, each of which accounting for one suspect neighbors of s * connected by an edge. Since there are at most 2(k − 1) edges connecting the k suspect nodes in S and their suspect neighbors, each edge will account for a reduction of the factor once. Therefore, from (70), we have (3) Detection probability when δ > 3 Proof of Theorem 5-iii. We use Lemma 8 and (55) to obtain a lower bound of the correct detection probability for a suspect node s * with m suspect neighbors as For a suspect set S with cardinality k that forms a general subgraph of a regular tree G with node degree δ > 3, for each suspect node s * ∈ S , we first find the number of its suspect neighbors. Note that the lower bound of P c (n|s * ) is one subtracted by a common factor m times, each of which accounting for one suspect neighbors of s * connected by an edge. Since there are at most 2(k − 1) edges connecting the k suspect nodes in S and their suspect neighbors, each edge will account for a reduction of the factor once. Therefore, from (70), we have From Fig. 6, we see that I 1/2 1 δ−2 , δ−1 δ−2 > 0.75 for δ > 3. Therefore, we have for any sufficiently large n and δ > 3. Besides, since 2(k − 1)/k = 2 as k → ∞, thus from (78), we have Furthermore, since I 1/2 (0, 1) = 1 (setting δ → ∞) we thus have lim δ→∞ lim n→∞ P c (n) = 1.
Importantly, note that the growth of δ does not need to depend on the growth of n.
(4) The worst-case detection probability Before the argument of Theorem 5-iv, we present the following lemma, which will be also used in the design of the numerical algorithms in Section IV; for its proof see Appendix-J. For a source s * with m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m } in S , let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ m) of G n . Lemma 9. To correctly identify source s * with m neighboring suspect nodes as the estimateŝ, we have where P G (X 1 = x 1 ) is given by (28).
Remark 9: Lemma 9 is deduced from Proposition 1. In fact, we can use Lemma 9 to deduce the exact detection probability P c (n) in the finite regime for Theorems 2 and 3, instead of using Lemma 6.
Proof of Theorem 5-iv. First, consider the case when the k suspect nodes are connected, and we use Lemma 9 to derive the minimum of P c (n).
For a suspect set S with cardinality k that forms a connected subgraph of a regular tree G with node degree δ ≥ 2, for each suspect node s * ∈ S , we first find the number of its neighboring suspect nodes. Note that P c (n|s * ) in (82) is one subtracted by a common factor m times, each of which accounting for one neighboring suspect node of s * connected by an edge. Since there are k − 1 edges connecting the k suspect nodes in S , each edge will account for a reduction of the factor twice. Therefore, from (70), we have Next, consider the case when the k suspect nodes form a general subgraph of G. From Lemmas 8 and 9, a lower bound of the correct detection probability for a suspect node s * with m suspect neighbors is For a suspect set S with cardinality k that forms a general subgraph of a regular tree G with node degree δ ≥ 2, for each suspect node s * ∈ S , we first find the number of its suspect neighbors. Note that the lower bound of P c (n|s * ) is one subtracted by a common factor m times, each of which accounting for one suspect neighbors of s * connected by an edge. Since there are at most 2(k − 1) edges connecting the k suspect nodes in S and their suspect neighbors, each edge will account for a reduction of the factor once. Therefore, from (70), we have where this lower bound is achievable if and only if the k suspect nodes are connected.

IV. Detection Probability on Regular Trees: Numerical Computation
In this section, we propose algorithms to compute the exact detection probabilities of the MAP estimator in the finite regime for regular tree-type networks, based on the theoretical results established in Section III. We focus on three representative scenarios: First, the suspect set contains all the nodes in the network; Second, the suspect set forms a connected subgraph of the network; Third, the suspect set contains only two nodes. Their corresponding algorithms are listed in Table II. We further establish that the correct detection probability monotonically decreases with the number of infected nodes and monotonically increases with the node degree for the former two cases.

A. Suspecting all Nodes
In this case, S = V, we only need to consider an arbitrary node s * ∈ G as the rumor source by symmetry. For a source s * with δ neighbors N l (s * ) = {v 1 , . . . , v δ } ⊂ S , let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ δ) of G n . Then, we use Algorithm 1 to compute the exact detection probability for this case.
Corollary 10. Suppose S = V, i.e., every infected node is a suspect node, then: i) P c (n) monotonically decreases with n; ii) P c (n) monotonically increases with δ.
Remark 10: Corollary 10 is complementary to Theorem 2. The MAP estimator has better detection performance when n is smaller, i.e., at an earlier stage of the rumor spreading process. On the other hand, the MAP estimator performs better for a network with a richer connectivity (higher node degree).

B. Connected Suspects
In this case, S = {s 1 , s 2 , . . . , s k } with cardinality k forms a connected subgraph of the network G. Assume that s * ∈ S is the rumor source and it has m (m ≤ δ) neighbors N l (s * ) = {v 1 , . . . , v m } ⊂ S . Let a random variable X j be the number of nodes in each subtree T s * v j (1 ≤ j ≤ m) of G n . Then, we use Algorithm 2 to compute the exact detection probability for this case.
Corollary 11. Suppose that S forms a connected subgraph of G, then: i) P c (n) monotonically decreases with n; ii) P c (n) monotonically increases with δ.

C. Two Suspects
In this case, S = {s 1 , s 2 } contains only two suspect nodes. Let d be the shortest path distance between s 1 and s 2 in G. We assume s 1 to be the rumor source s * by symmetry, let P = {v 0 = s 1 , v 1 , · · · , v d = s 2 } be the shortest path from s 1 to s 2 , and define a random variable Z h to be the number of nodes in the subtree T s * v h (1 ≤ h ≤ d). Then, we have Algorithm 3 to compute the exact detection probability for this case. When δ = 2, we use (16) to compute P c (n). When δ ≥ 3, from (60), we have where P G d h=1 (Z h = z h ) is given by (33). In this section, we carry out simulation experiments to corroborate and illustrate our analysis. For verifying the asymptotic results, in each experiment run we let n = 1000 nodes be eventually infected by a rumor source node uniformly randomly chosen from the suspect set, following the SI model, and use the estimator (3) to identify this source. For the first scenario of S = V, it is shown in Fig. 7 that the correct detection probability is increasing with the node degree δ, from virtually zero when δ = 2 to 0.307 as δ exceeds 50. In Fig. 8, we consider the scenario where there are k connected suspect nodes. We observe that the correct detection probability significantly exceeds 1/k when δ > 2, and that reliable detection is achieved as δ grows large. In Fig.  9, we consider the scenario where there are two suspect nodes with a shortest path distance d. We observe that the correct detection probability significantly exceeds the prior 1/2 when δ > 2. Furthermore, the detection probability increases as d increases, and reliable detection is achieved when either δ or d is sufficiently large.

V. Numerical Experiments
In addition, to verify that even when k becomes large our results in Theorem 3 will not degenerate to the case with no a priori knowledge, we let the suspect set cardinality k range from 2 to 4000 in the scenario where the k suspect nodes form a connected subgraph, and let n = 1000 nodes be eventually infected. From Fig. 10, we observe that the correct detection probability is always at least 1/2, and accurately coincides with the theoretical prediction in Theorem 3.

VI. Conclusion
In this paper, we have studied the problem of rooting out a single rumor source from a set of suspect nodes under an SI model, focusing on the performance analysis of the MAP source estimator. In order to handle the presence of the suspect set, we have developed a key concept of local rumor center which greatly facilitates the analysis. For regular treetype networks, we have developed both finite and asymptotic detection performance results of the MAP estimator, using the Pólya's urn model in probability theory. We have investigated four representative scenarios, for each of which developing analytical results and shedding key insights into the behavior of the rumor spreading process in large-scale networks. The introduction of the a priori knowledge of suspect set dramatically improves the detection performance compared with the case of no a priori knowledge, and substantially enriches the scope of the rumor source estimation problem.

A. Proof of Lemma 6
Proof of Lemma 6. If max{x j , 1 ≤ j ≤ m} < n/2, then from Proposition 1, we know that s * is the local rumor center w.r.t. the sub-neighborhood N l (s * ) = {v 1 , . . . , v m } of G n . Again from Proposition 1, we have R(u, G n ) < R(s * , G n ) for all u ∈ T s * v j and 1 ≤ j ≤ m. Therefore, we can make sure to correctly identify s * as the rumor source.
If max{x j , 1 ≤ j ≤ m} = n/2, then from Proposition 1, we know that s * is the local rumor center w.r.t. the sub-neighborhood N l (s * ) = {v 1 , . . . , v m } of G n . Again from Proposition 1, there is only a node u ∈ N l (s * ) such that R(u, G n ) = R(s * , G n ), and R(v, G n ) < R(s * , G n ) for all v ∈ {T s * v j , 1 ≤ j ≤ m} \ {u}}. Therefore, the probability to correctly identify s * as the rumor source is 1/2.
If max{x j , 1 ≤ j ≤ m} > n/2, then from Proposition 1, we know that s * is not the local rumor center w.r.t. the sub-neighborhood N l (s * ) = {v 1 , . . . , v m } of G n . Therefore, we cannot identify s * as the rumor source.

B. Proof of (37)
Here, we only present the detailed proof of (37) when n is even. The case when n is odd can be deduced similarly.
C. Proof of (40) Here, we only present the detailed proof of (40) when n is odd. The case when n is even can be deduced similarly.
When n is odd, we have where we use the short form of P G 3 j=1 (X j = x j ) , just as From (39), we have P c (n) = 2 n(n + 1)

D. Proof of Lemma 7
Proof of Lemma 7. Since the source s * has m (1 ≤ m ≤ δ) neighbors in the suspect set S , from Proposition 1 and Lemma 6, we have Above, (a) is by the union bound over events E c 1 , . . . , E c m , and (b) by symmetry.
Again using Proposition 1 and Lemma 6, we have Above, (a) follows from the fact that events F c 1 , . . . , F c m are disjoint since there is at most a subtree such that the number of nodes in it is more than n/2, and (b) from symmetry. (48) Here, we only present the detailed proof of (48) when m = 1 with even n. The case when m = 1 with odd n can be deduced similarly, and the case when m = 2 is the same as that in Appendix-B.

E. Proof of
For m = 1 and n is even, we have where we use the short form of P G 2 j=1 (X j = x j ) , just as F. Proof of (52) Here, we only present the detailed proof of (52) when m = 2 with odd n. The case when m = 3 is the same as that in Appendix-C, and the other cases can be deduced similarly.
For m = 2 and n is odd, we have where we use the short form of P G 3 j=1 (X j = x j ) , just as From (51), we have P c (n|s * ) = 2 n(n + 1) x=(n−1)/2 x=0 n + 1 2 G. Proof of (62) Here, we only present the detailed proof of (62) when n is odd with even d. The other three cases can be deduced similarly. Since H. Proof of (65) Here, we only present the detailed proof of (65) when n is even. The case when n is odd can be deduced similarly.
Since z 1 + z 2 ≥ n if and only if R(s * , G n ) ≤ R(s 2 , G n ). Besides, z 1 ≥ z 2 + 1, thus z 1 ≥ (n + 1)/2. Therefore, from (64), we have + · · · + 2 n(n + 1) n/2 − (n − 2)/2 n/2 + (n − 2)/2 where we use the short form of P G From Proposition 1, if s * is the local rumor center w.r.t. N l (s * ) of G n , then R(s * , G n ) ≥ R(u, G n ) for all u ∈ S N l (s * ), and R(s * , G n ) > R(u , G n ) for all u ∈ S \ {N l (s * ) s * }. When all the m suspect neighbors of s * are neighboring suspect nodes of s * , from Proposition 1, the MAP estimator can correctly identify s * as the estimateŝ if and only if s * is the local rumor center. However, in general cases, the MAP estimator can correctly identify s * as the estimateŝ even if s * is not a local rumor center.

J. Proof of Lemma 9
Proof of Lemma 9.
For the error detection probability P e (n|s * ) = 1−P c (n|s * ), from Proposition 1 and Lemma 6, we have where the last equality follows from symmetry.

K. Proof of Corollary 10
For Corollary 10-i with fixed node degree δ ≥ 2, from (86), we should prove that P e1 (n) = (1 − P c (n)) /δ = 0.5P G X 1 = n 2 + x 1 >n/2 P G (X 1 = x 1 ) increases with n (n ≥ 2). Note that P e1 (n) is the error detection probability of the MAP estimator to identify the neighboring suspect node s * 1 of the rumor source s * as the estimateŝ. In the following, we deduce the relation of P e1 (n) between n = 2i and n = 2i + 1, and that between n = 2i + 1 and n = 2i + 2, for all i ∈ N + .
where P G (X 1 = x 1 |n) is given by (28) conditioned on n.
Let g 2 (δ|i) = log (δ · P G (X 1 = i + 1|n = 2i + 1)), and we use the mathematical induction once again so as to prove that the derivative of g 2 (δ|i) w.r.t. δ is non-positive for all fixed i.