text:
\section*{Appendix}\label{sec:appendix}

\subsection{Proof of Proposition~\ref{pro:subOPT}}
First, note that the {\bf SUB-OPT} is represented by
\begin{align}
  \label{eq:trade1}
&\max_{v \in C_r} \bprob{G_N,A_{r} | v=v_1} \cr
& =  \max_{v \in C_r} \bprob{G_N,A_{r}|v=v_1, v_1 \in C_r} \times \prob{v_1 \in
  C_r}.
\end{align}
We will prove that the RC-based algorithm maximizes for both probabilities
in \eqref{eq:trade1}. First, we consider the second probability.
To see this, suppose $V_{K/r} :=\{v(1),\ldots, v(K/r)\}$ is the
set which contains $K$-largest rumor centrality nodes and let $P(v(i)
=v_1) ~(1\leq i \leq K/r)$ be the source detection probability {\it i.e.}, the
probability that the $i$-th largest rumor centrality node is the rumor
source. Let $S$ be a set of infected nodes with $|S|=K$ then our
objective is to find
\begin{equation*}
\begin{aligned}
S^* =\arg\max_{S\subset G_N, |S|=K/r}\mathbb{P}(v_1 \in S |G_N).
\end{aligned}
\end{equation*}
Since the probability $P(v_1 \in S |G_N)$ is given by
\begin{align*}
\mathbb{P}(v_1 \in S |G_N)&=\sum_{v \in
  S}\mathbb{P}(v=v_1|G_N)\\ &=\sum_{v \in S}\frac{\mathbb{P}(v=v_1 ,
  G_N)}{\mathbb{P}(G_N)}\\ &=\sum_{v \in S}\frac{P(v=v_1 ,
  G_N)}{\mathbb{P}(v=v_1)}\frac{\mathbb{P}(v=v_1)}{\mathbb{P}(G_N)}\\ &=\sum_{v
  \in
  S}\mathbb{P}(G_N|v=v_1)\frac{\mathbb{P}(v=v_1)}{\mathbb{P}(G_N)},\\
\end{align*}
where $P(G_N)=\sum_{v \in G_N}P(G_N |v)P(v=v_1)$ is independent how
choose the set $S$ and $P(v=v_1)$ is same for all $v \in G_N $. Hence,
we have
\begin{equation*}
\begin{aligned}
\mathbb{P}(v_1 \in S |G_N) &\propto \sum_{v \in
  S}\mathbb{P}(G_N|v=v_1)\propto \sum_{v \in S}R(v, V_N).
\end{aligned}
\end{equation*}
Therefore, the probability $\mathbb{P}(v_1 \in S |G_N)$ is maximum
when $S=V_{K/r}$. Next, we consider the first probability in \eqref{eq:trade1}.
Indeed, this term is also decomposed by
\begin{equation}  \label{eq:trade2}
\begin{aligned}
\bprob{G_N,A_{r}&|v=v_1, v_1 \in C_r}\\
&= \bprob{G_N|v=v_1, v_1 \in C_r}\bprob{A_{r}|v=v_1, v_1 \in C_r}.
\end{aligned}
\end{equation}
Then, one can check that the first probability in \eqref{eq:trade2} is maximized
when the $C_r =V_{K/r}$. Furthermore, the second probability is independent of
set $C_r$ because the querying data is independent to this set. Hence, we obtain
$C_{r}^* = V_{K/r}$ and this completes the proof of
Proposition~\ref{pro:subOPT}.

\subsection{Proof of Lemma \ref{lem:majority}}
Since the case $p=1$ is trivial,
it is enough to show that if $1/2<p<1$ then
    \begin{align}\label{eqn:induct}
     \frac{I_{p}(r-\lfloor r/2\rfloor, \lfloor
       r/2\rfloor+1)-p}{1-p}\geq 1-e^{-p^{2}\log r},
    \end{align}
for any $r\geq 1$. To see this, we use the induction on $r$. First,
for $r=1$, it is holds because the \textbf{LHS} of \eqref{eqn:induct} zero due to
$I_p (1,1)=p$. Clearly, the \textbf{RHS} is also zero. Let
$f_p (r):=(I_{p}(r-\lfloor r/2\rfloor,
\lfloor r/2\rfloor+1)-p)/(1-p)$ and we assume that \eqref{eqn:induct} is holds for $r>1$.
By taking the derivative of $f_p (r+1)$ with respect to $r$, one
can obtain
\begin{equation*}
    \begin{aligned}
    \frac{\partial(f_p (r+1))}{\partial r}&
    \geq\frac{1}{1-p}\left(\frac{\partial I_{p}(r/2, r/2)}{\partial
      r}\right)\stackrel{(a)}{\geq}
    \left(\frac{r+1}{r}\right)^{p^2}-1\\ &\geq
    r^{-p^2}((r+1)^{p^2}-r^{p^2})\\ &\geq
    r^{-p^2}(r+1)^{-p^2}((r+1)^{p^2}-r^{p^2})\\ &=
    \frac{1}{r^{p^2}}-\frac{1}{(r+1)^{p^2}}= e^{-p^{2}\log
      r}-e^{-p^{2}\log (r+1)}.\\
    \end{aligned}
  \end{equation*}
where $(a)$ follows from the derivative of the incomplete
function. From the concavity of $I_{p}(r-\lfloor r/2\rfloor, \lfloor
r/2\rfloor+1)$ to $r$, we have
\begin{equation*}
    \begin{aligned}
    f_p (r+1)&\geq f_p (r)+\frac{\partial(f_p (r+1))}{\partial
      r}((r+1)-r)\\ &\geq 1-e^{-p^{2}\log r}+(e^{-p^{2}\log
      r}-e^{-p^{2}\log (r+1)})\\ &=1-e^{-p^{2}\log (r+1)},
    \end{aligned}
  \end{equation*}
and this completes the proof of Lemma~\ref{lem:majority}.

\subsection{Proof of Lemma \ref{lem:major}}
For a given $r\geq 1$, consider each positive constant $\varepsilon_j>0$ for $1\leq j \leq d$. Then, we have
    \begin{align*}
     \prob{Z_1 (v) &> Z_j (v),~ \forall j}=\bprob{\sum_{i=1}^{r}Y^{1}_i (v) >
      \sum_{i=1}^{r}Y^{j}_i (v),~\forall j\neq 1}\\ &\geq
      \bprob{\sum_{i=1}^{r}Y^{1}_i (v) \geq \mu_1
      +\varepsilon_1}\\ &\qquad +\left(1-
      \bprob{\sum_{i=1}^{r}Y^{j}_i (v) \geq \mu_1+\varepsilon_1
      ~\forall j\neq 1}\right)\\ &\stackrel{(a)}{\geq} 1-
      \sum_{j=2}^{d}\prob{\sum_{i=1}^{r}Y^{j}_i (v) \geq
      \mu_j+\varepsilon_j }\\ &\stackrel{(b)}{\geq}
      1-(d-1)e^{-\frac{\varepsilon^2 \mu_j}{ 3}}\geq 1-
      e^{-\frac{\varepsilon^2(d-1)r}{3dq(1-q)}},
    \end{align*}
where $\mu_1=\mathbb{E}[Z_j (v) =\sum_{i=1}^{r}Y^{j}_i (v)]=rq$ and
$\mu_j=\mathbb{E}[Z_j (v) =\sum_{i=1}^{r}Y^{j}_i
  (v)]=r(1-q)/(d-1)$. The inequality $(a)$ comes from the fact that
$\mu_1 \geq \mu_j$ for $2\leq j \leq d$ and the union
bound of probability. From Chernoff-Hoeffding bound of $Y^{j}_i (v)$,
we obtain the inequality $(b)$ by setting $\varepsilon_j =\varepsilon \mu_j$.
If we set $\varepsilon = q^{1/2}(q-1/d)$, we obtain
$\hat{q}\geq 1-e^{-\frac{r(d-1)(q-1/d)^2}{3d(1-q)}},$ which completes the proof
of Lemma~\ref{lem:major}.

\section{Model and Preliminaries}
\label{sec:model}

\subsection{Model}
\noindent{\bf \em Rumor diffusion.} We describe the rumor spreading
model which is commonly adopted in other related work, e.g.,
\cite{shah2010,shah2012,zhu2013}.  We consider an undirected graph
$G=(V,E),$ where $V$ is a countably infinite set of nodes and $E$ is
the set of edges of the form $(i,j)$ for $i, j\in V$.  Each node
represents an individual in human social networks or a computer host
in the Internet, and each edge corresponds to a social relationship
between two individuals or a physical connection between two Internet
hosts.  We assume a countably infinite set of nodes for avoiding the
boundary effects. As a rumor spreading model, we consider a SI model,
where each node is in either of two states: {\em susceptible} or {\em
  infected}. All nodes are initialized to be susceptible except the
rumor source, and once a node $i$ has a rumor, it is able to spread
the rumor to another node $j$ if and only if there is an edge between
them.  Let a random variable $\tau_{ij}$ be the time it takes for node
$j$ to receive the rumor from node $i$ if $i$ has the rumor. We assume
the $\tau_{ij}$ are exponentially distributed with rate $\lambda>0$
independently with everything else. Without loss of generality, we
assume that $\lambda=1$. We denote $v_1 \in V$ by the rumor source, which
acts as a node that initiates diffusion and denote $V_N \subset V$ of $N$ infected
nodes under the observed snapshot $G_N\subset G$. In this paper, we consider
the case when $G$ is a regular tree
and our interest is when $N$is large, as done in many prior work
\cite{shah2010,shah2012,Khim14,dong2013,Zhang2014}.

\begin{comment}
  For general loopy graphs, the rumor source detection problem is not
  easy to analyze, and most properties derived in the tree graphs do
  not extend, e.g., the ML estimator is NP-hard to compute.  However,
  following the implications from the results in regular trees, one
  can design a heuristic algorithm that performs well for general
  graphs.  For example, in \cite{shah2010tit}, they suggest to choose
  BFS (Breadth First Search) first, and use the rumor centrality of
  the tree as the rumor source estimator for the general graph.
\end{comment}

\begin{comment}
of the estimator by introducing the concept of \emph{querying}. We
consider two kinds of querying which are interactive and
non-interactive querying.  Interactive querying scenario assumes that
we can obtain additional information with each single query. Then we
can utilize those additional information to determine the next
estimator and iterate queries.  However, non-interactive querying
scenario involves simultaneous querying without interactive
question-and-answer mechanism. In non-interactive case we cannot
obtain additional information from each query.

The notion of \emph{querying budget} will be used throughout this
paper.  We say there are $K$ querying budgets when we have $K$ chances
of question-and-answering in interactive querying scenario or we have
$K$ amount of nodes that can be simultaneously picked in
non-interactive querying scenario. We will closely investigate each
querying scenario and derive the lower-bound guarantee of improved
detection probability with given amount of $K$ querying budgets.

So far we discussed about the performance of ML estimator for
detecting rumor sources. However, the detection probability was quite
low; less than 1/2 in every case.  In practical situations, we do not
usually determine various properties of a stochastic process in a
single guess. Rumor source detection is a part of these estimation
processes, and we can think about doing simultaneous/sequential
multiple guesses instead of doing a single guess in order to improve
the credibility of the estimation.

We aim at improving detection probability of the estimator by
introducing the concept of \emph{querying}. We consider two kinds of
querying which are interactive and non-interactive querying.
Interactive querying scenario assumes that we can obtain additional
information with each single query. Then we can utilize those
additional information to determine the next estimator and iterate
queries.  However, non-interactive querying scenario involves
simultaneous querying without interactive question-and-answer
mechanism. In non-interactive case we cannot obtain additional
information from each query.

The notion of \emph{querying budget} will be used throughout this
paper.  We say there are $K$ querying budgets when we have $K$ chances
of question-and-answering in interactive querying scenario or we have
$K$ amount of nodes that can be simultaneously picked in
non-interactive querying scenario. We will closely investigate each
querying scenario and derive the lower-bound guarantee of improved
detection probability with given amount of $K$ querying budgets.
\end{comment}

\begin{figure}
\begin{center}
\subfigure[A simple batch querying.
]{\includegraphics[width=0.24\textwidth]{figs/Noninter}\label{fig:Noninter}}
\hspace{-0.2cm} \subfigure[Interactive querying with direction.
]{\includegraphics[width=0.24\textwidth]{figs/Inter}\label{fig:Inter}}
\hspace{0cm}
 \end{center}
\caption{Examples of two querying types with untruthful
  feedbacks. In (a), the querier selects a candidate set (a dotted
  circle) and asks just one question (i.e., $r=1)$ in a batch. In (b),
  starting from the initial node, the querier first asks ``Are you the
  rumour source?'', and if no, she further asks ``Who spreads the rumor to
  you?'', where the querier interactively tracks the true source, but the
  queriees may be untruthful (RS: Rumor Source). }
\label{fig:querying}
\end{figure}

\smallskip
\noindent{\bf \em Querying with untruthful answers.}  A detector is
allowed to query the nodes, where querying refers to a process of
asking some questions (which will be shortly clarified depending on
the querying scenarios).  The detector is given some querying budget
$K,$ where we assume that one budget is used to ask one question.  In
this paper, we consider two types of queries (see
Fig.~\ref{fig:querying}), where a queriee may be untruthful, as
modeled in what follows:

\smallskip
\begin{compactenum}[$\circ$]
\item {\bf \em Simple batch querying.}  This query is parameterized by
  $r$, where a querier first chooses $K/r$  ($K$ is a multiple of $r$ for expositional convenience)
  candidate nodes to each of which an {\em identity question} of ``Are
  you the rumour source?'' is asked $r$ times. We call $r$ the
  {\em repetition count} throughout this paper.
  Each queriee $v$ is
  truthful in answering each question only with probability $p_v,$ i.e.,
  even if she is the rumour source, she lies with probability $1-p_v.$
  We assume that the answers are independent over the $r$ queries across
  the queriees. We assume the homogeneous case when $p_v = p$ for all
  $v \in V_N,$ and $p > 1/2,$ i.e., all users are biased with truthful
  answers. For example, Fig~\ref{fig:Noninter} shows a
  candidate set of nodes insides a dotted circle, where with $r=1$ we
  have four ``yes'' nodes and five ``no'' nodes.

\smallskip
\item {\bf \em Interactive querying with direction.}  In this querying
  type, there are two questions, where one is the identity question, as
  in the simple batch querying and another is the {\em direction
    question} of ``From whom you have heard the rumor?.''  This query is
  also parameterized also by $r,$ where the querying process occurs in
  the following interactive manner: A querier first chooses an initial
  node to ask the identity question, and further asks the direction
  question $r$ times (i.e., repetition count), if the queriee answers
  that she is not the rumor source, but the querying process stops when
  the queriee says that she is the rumor source or the entire budget $K$
  is exhausted. A querier determines the next queriee from $r$
  questions, where each queriee $v$ is truthful for the identity
  question, but she is truthful for the direction question only with
  probability $q_v.$\footnote{In this type of query, we model
    untruthfulness only in the direction question, because we aim at
    purely focusing on the impact of untruthfulness in the interactive
    search of the true rumour source, which seems to be the critical
    component in this type of querying.} In other words, she lies for
  the direction question with probability $1-q_v$ and designates a node
  uniformly at random out of all neighbors except for the node who truly
  spreads the rumor to $v$ as a bogus ``parent''. Then, the querier
  chooses one of neighbor node as parent of $v$ and repeats the same procedure.
  As in the simple batch
  querying, we assume the homogeneity in truthfulness that $q=q_v$ for
  all $v \in V_N,$ and $q > 1/d,$ i.e., users' bias for truthful
  answers\footnote{In $d$-regular trees, when $q=1/d$, the answer for
    the direction question turns out to be uniformly random.}
  Fig~\ref{fig:Inter} shows an example scenario that starting from the
  initial node, a sequence of nodes answer the interactive queries
  truthfully or untruthfully.

\end{compactenum}

\smallskip
\noindent{\bf \em Goal.} Our goal is to propose the efficient estimation
algorithms for both types of queries with users' untruthfulness that are
practically implementable. Especially, we aim at theoretically
quantifying the detection performance of our proposed algorithms by
providing the lower bound of the required budget $K$ to satisfy any
arbitrary detection probability, i.e., the sufficient budget $K$ for the
target detection quality.

\vspace{-0.2cm}
\subsection{Preliminaries: Rumor Centrality}
\label{sec:rumor_center}

As a preliminary, we explain the notion of {\em rumor centrality,} which is a
graph-theoretic score metric and is originally used in detecting the
rumor source in absence of querying and users' untruthfulness, see
\cite{shah2010}. This notion is also importantly used in our framework
as a sub-component of the algorithms for simple batch querying and
interactive querying with direction.
In regular tree graphs, Shah and Zaman \cite{shah2010} showed that the
source chosen by the Maximum Likelihood Estimator (MLE) becomes the node
with hightest rumor centrality. Formally, the estimator chooses $v_{RC}$ as
a rumor source defined as
\begin{eqnarray}\label{eqn:ML}
v_{RC} &=& \arg\max_{v \in V_N} \mathbb{P}(G_N | v=v_1)\cr
       &=&\arg\max_{v \in V_N} R(v, G_N),
\end{eqnarray}
where $v_{RC}$ is called \emph{rumor center} and $R(v, G_N)$ is the
rumor centrality of node $v$ in $V_N$. The rumor centrality of a
particular node is calculated only by understanding the graphical
structure of the rumor spreading snapshot, i.e., $R(v, G_N) =N!
\prod_{u \in V_N} (1/T^v_u)$ where $T^v_u$ denotes the number of nodes
in the subtree rooted at node $u$, assuming $v$ is the root of tree
$G_N$ (see \cite{shah2010} for details).

\section{Conclusion}
\label{sec:conclusion}
In this paper, we have considered the querying framework with
untruthful answers in rumor source detection. We have provided some
theoretical performance guarantees when the underlying network has
regular tree structure.  We obtain how much query budget is required
for two querying types to achieve the target probability
when the truth probabilities are homogeneous in the queriees.
We perform various simulations based on these algorithms.  As future
works, we will consider the hidden heterogeneous truth probabilities in answers for
both querying scenarios.

\section{Interactive Querying with Detection}
\label{sec:interactive}
\subsection{Algorithm based on ML for next node selection}
A source finding algorithm for interactive queries consists of the
following steps: We first need to appropriately choose the repetition
count $r$ and the initial node $v_I$ to ask the identity question.
If she is not the source then ask the direction questions $r$ times.
From the answers of querying, the querier chooses a next node to perform
the same procedure. Hence, the next queried node is determined by the previous
queried node when the initial node is $v_I$. Let $\mathcal{P}(v_I)$ be a
policy that chooses the next queried
node and let $V^r =\{v^1, v^2, \ldots, v^{K/r}\}$ be the set of queried nodes by next
node selection policy $\mathcal{P}.$ Then, we will be given an instance of the direction
answers, which we denote by a vector
$D_{r}^{i} = D_{r}(q)=[y_1, y_2, \ldots, y_{d}]$ with $0\leq y_j \leq d$ that
represents the number of ``indications'' answers of the $j$-th neighbor
node by the queried node $v^i$. Let $pa(v)$ be the true parent of a node $v \in V_N$
and let $nb(v)$ be the set of all neighbors of $v$.
Then, the next queried node is selected by some ML from the data
$D_{r}^{i}$ and repeat same procedure as in the first step.
Then, to maximize the detection performance, that solves the following optimization:
\vspace{-0.3cm}
\separator
\vspace{-0.4cm}
\begin{align}\label{eqn:OPT1}
\text{\bf OPT-I:} &  \quad \max_{1\leq r \leq K} \max_{\mathcal{P}(v_I)}
\left(\prod _{i=1}^{K/r}\max_{v \in nb(v^i)}\bprob{G_N,D_{r}^{i}| v=pa(v^i)}\right),
\end{align}
where the most inner max corresponds to the ML estimator given the
diffusion snapshot $G_N$ and the query answer snapshot $D_{r}^{i}$
which are independent to $1\leq i \leq K/r$.
\vspace{-0.3cm}
\separator

\smallskip
\noindent{\bf \em Challenges.} We now explain the technical challenges
in solving {\bf OPT-I}. To that end, let us
consider the following sub-optimization in {\bf OPT-I} for a fixed $ 1\le
r \le K$:
\begin{align}\label{eqn:subOPT1}
\text{\bf SUB-OPT-I:} &  \quad \max_{\mathcal{P}(v_I)}
 \left(\prod _{i=1}^{K/r}  \max_{v \in nb(v^i)}\bprob{G_N,D_{r}^{i}| v=pa(v^i)}\right).
\end{align}
To solve {\bf SUB-OPT-I}, let $\bprob{G_N, \mathcal{D}_r|V^r}$ be the probability
in the parentheses of \eqref{eqn:subOPT1} then
\begin{align}
  \label{eq:tra}
\max_{\mathcal{P}(v_I)}
& \bprob{G_N, \mathcal{D}_r|V^r}\cr
& =\max_{\mathcal{P}(v_I)}\left(\bprob{v_1 \in V^r }\times \bprob{G_N, \mathcal{D}_r|V^r, v_1 \in V^r}\right)\cr
& =\underbrace{\max_{\mathcal{P}(v_I)}\bprob{v_1 \in V^r }}_{(a)}\times
\underbrace{\max_{\mathcal{P}(v_I)}\bprob{G_N, \mathcal{D}_r|V^r, v_1 \in V^r}}_{(b)},\cr
\end{align}
where we will discuss the analytical challenges in $(a)$ and $(b),$
respectively.
First, the term $(a)$ is difficult to analyze, because
it is not easy to obtain the optimal policy $\mathcal{P}(v_I)$
because the number of candidate sets may be very large to handle.
Second, to see the challenging in $(b)$,
let $D_{r}^{i}=[x_1, x_2,\ldots, x_{d}]$ be the vector where
$0 \leq x_i\leq r$ is the number of indications by the queried node as
the parent node. Then, we can also
obtain the MLE for the parent of $v^i$ as
\begin{equation}\label{eqn:MAP2}
\begin{aligned}
\hat{v}_{\tt ml}^{i+1}&=\arg\max_{v \in nb(v^i)}\bprob{G_N,
D_{r}^{i}|v=pa(v^i)}\\ &\stackrel{(a)}{=}\arg\max_{v \in
  nb(v^i)}\bprob{G_N,|v=pa(v^i)}\bprob{D_{r}^{i}|v=pa(v^i)}.\\
\end{aligned}
\end{equation}
In this case, the first term in \eqref{eqn:MAP2} is given
by $\prob{G_N,|v=pa(v^i)}=\sum_{u \in T_v}R(u,G_N)$ where $T_v$
is the subtree rooted at node $v$ because if $v$ is the parent of
$v^i$ then one of node in $T_v$ is the rumor source. the second
term is Multinomial distribution that $pa(v^i)$ has the probability
$q$ and $(1-q)/(d-1)$, for other neighbor nodes of $v^i$.
However, it is not easy to characterize this probability and obtaining the second
probability in \eqref{eqn:MAP2} for every queried node $v^i$.

Motivated by this, we propose an algorithm producing an
approximate solution of {\bf OPT-I}. The key of our approximate algorithm
is to choose $V^r$ that allows us to analytical compute the detection
probability for a given $r$ so as to compute $r$ easily, yet its
performance is close to that of {\bf OPT-I}.
\subsection{Algorithm based on Parent node and Majority Rule}

\begin{algorithm}[t!]
 \KwIn{Rumor set $V_N$, querying budget $K$, degree $d$, and truth
   probabilities $q>1/d$} \KwOut{Estimated rumor source $\hat{v}$}
 Calculate the rumor centrality $R(v, G_N)$ for all $v \in G_N$ as in
\cite{shah2010} and let $ s \leftarrow \arg\max_{v \in V_N} R(v, G_N)$\;
 $r \leftarrow \left\lfloor1+\frac{2d(1-q)^2 \log\log
   K}{3(d-1)}\right\rfloor$\; \While{}{ \eIf{$s = v_1$} { Return $s$\;
     $K \leftarrow K-1$\; } {\If{$K\geq r$} {Count the number of
       ``indication'' (i.e., She has spread the rumor to me) for the
       direction question among $nb(s)$, and choose the largest
       counted node with a random tie breaking \; Denotes the selected
       node by $s$\; $K \leftarrow K-r$\; } } { Return $s$\;} } Return
 $\hat{v}=s$\;

 \caption{Estimation for Interactive Querying with Direction}
\label{alg:interactive}
\end{algorithm}

We now propose an algorithm that overcomes the afore-mentioned
challenges in $(a)$ and $(b)$ in \eqref{eq:trade}. The key idea is that
for $(a)$ we adopt a {\em  parent selection} as the next queried node
and for $(b)$ we simply apply a {\em majority-based rule}, as
will be clarified soon.

We first formally describe our algorithm in {\bf
  Algorithm~\ref{alg:interactive}} and explain how it operates,
followed by presenting the rationale behind it: we first calculate the
rumor centrality of all nodes in $G_N$ (Line 1), where $s$ is set to be
the rumor center. Then, we appropriately choose the repetition count as
in Line 3, and query the identity question to the rumor center $s$ (Lines 4-6).
If she is not the source then ask the direction questions $r$ times, and count the
number of ``indications'' for its neighbor (Line 9). Then, it chooses the largest
counted node with a random tie breaking and repeat the same procedure (Line 12).
The algorithm stop when there is a node which reveals itself as the rumor
source within $K$ queries, otherwise, it output the last queried node as
the estimator.

\smallskip
\noindent{\bf \em Rationale.} We now provide the rationale of {\bf
  Algorithm~\ref{alg:interactive}} from the perspective of how we handle the
analytical challenges in \eqref{eq:trade}  so as to approximately solve
{\bf OPT-I} in an approximate manner.

\smallskip
\begin{itemize}
\item[$\circ$] {\em Selection of initial node and Parent as the next queried node:}
From the fact that the rumor source is nearby the rumor center with high probability,
we see that the best
strategy for selecting the initial node to query is selecting the rumor center. Furthermore,
even though there is untruthful answer of queries, selecting the parent as the next queried
node is quite good from the same reason.

\item[$\circ$] {\em  Majority rule
    to select the parent:} Instead of using the exact calculation of MLE in \eqref{eqn:subOPT},
  because \note{...}
\end{itemize}

Using the above approximation techniques, we are able to have the closed
and approximate form of {\bf SUB-OPT-I}, which allows us to compute the
best $r^\star$ that maximizes the detection probability as in
$r^*= \left\lfloor1+\frac{2d(1-q)^2 \log\log K}{3(d-1)}\right\rfloor.$

\subsection{Detection Performance}
We now provide analytical results on the detection performance of {\bf
  Algorithm~\ref{alg:interactive}}. We first start by the result that presents the lower
bound of the detection probability for a given repetition count $r$ in
Proposition~\ref{prop:inter_prob} Then, in
Theorem~\ref{thm:interactive}, we present the lower bound on the
budget for any given detection probability $0< 1-\delta<1.$

\begin{proposition}
  \label{prop:inter_prob}
  For $d$-regular trees ($d\geq 3$), the detection probability of the
  Interactive Querying with Direction for given $K,$ $q > 1/d$ and $r$ is
  lower-bounded by:
\begin{align}
  \label{eqn:detect2}
  \bprob{\hat{v}=v_1}\geq 1-ce^{-2 g_d (r,q)^3
  \left(\frac{K}{r+1}\right)\log \left(\frac{K}{r+1}\right)},
\end{align}
where $g_d (r,q):= 1- e^{-\frac{r(d-1)}{3d(1-q)}}$ and
$c=(8d+1)/d$.
\end{proposition}
\smallskip
This result implies that the error probability of detecting the source decaying
exponentially with respect to $K$ for a given $r$. Furthermore, we see that there
is a tradeoff for selecting $r$ to maximize the probability in \eqref{eqn:detect2}.
From this result, we obtain the
best $r*$ which maximizes the probability in \eqref{eqn:detect} and we have the following
theorem.

\smallskip
\begin{theorem}
\label{thm:interactive}
For any given sufficiently small $\delta>0,$ the detection probability for $d$-regular
tree is at least $1-\delta,$ if
\begin{align}
\label{eqn:elower1}
    K\geq \frac{(2d-3)/d(\log(7/\delta))}{q^3\log \Big(\log (7/\delta)\Big)}.
    \end{align}
\end{theorem}

\smallskip
This result implies that if there is untruthful answer of direction
with probability $q>1/d$ for the interactive query then it requires
$1/q^3$ times more budget compared to the case without lying to
guarantee the target detection probability. Furthermore, if $q\simeq
1/2$ then, it requires about 8 times more budget for $d$-regular
tree. Furthermore, if $q=0.4$ then it needs $K\geq 51$ to achieve
the detection probability at least 95\% for $d=3$.
Therefore, it requires much less queries than that of batch
querying which reducing the order of $1/\delta$ to $\log (1/\delta)$
because the answer of direction gives the path information of the
rumor source from the queried node whereas the batch querying consider
all nodes regardless of the path.

\section{Interactive Querying with Direction}
\label{sec:interactive}

In this section, we study the case of interactive querying with
direction. Recall that a source finding algorithm for interactive
queries consists of the following steps: We first need to appropriately
choose the repetition count $r$ and the initial node $v_I$ to ask the
identity question.  If she is not the source then ask the direction
questions $r$ times.  From the answers of querying, the querier chooses
a next node to perform the same procedure.

\subsection{Ideal Algorithm and Challenges}
\label{sec:interactive_mle}
Two key components for high detection probability are the choice of the
repetition count and a smart policy which selects the next queriee based
on the answer sample for the direction questions.

Let $\mathcal{P}(v_I)$ be a set of all policies, each of which provides
a rule of choosing a next queriee at each querying step, when the
initial queriee is $v_I.$ Once a policy $P \in \mathcal{P}(v_I)$ and $r$
are chosen, the estimated node $\hat{v}$ is determined, {\it i.e.}, the node who
reveals itself as the rumor source for the identity question, or the
last queriee, otherwise.  Then, it is natural to choose $r$ and $P$ so
as to solve the following optimization:

\vspace{-0.2cm}
\separator
\vspace{-0.2cm}
\begin{align}
\label{eqn:OPT1}
\text{\bf OPT-I:} &  \quad \max_{1\leq r \leq K} \max_{v_I \in
                    V_N}\max_{ P \in \mathcal{P}(v_I)}
\bprob{\hat{v}=v_1|v_I}.
\end{align}
\vspace{-0.2cm}
\separator

We now explain the technical challenges in solving {\bf OPT-I}.  We
first introduce some notations for expositional convenience as well as
our analytical results later.  Let $w_i$ be the $i$-th queriee for
$1\leq i \leq K/r$ \footnote{In out model, $i$ can be strictly less than
  $K/r$ if there exists $i$ such that $i$-th queriee answers ``yes'' for
  the identity question
}, and let $Z_r := Z_r(P) = (z_1, z_2, \ldots, z_{K/r})$ be the sequence
of answers for the identity questions to each queriee for a given
policy $P,$ where $z_i \in \{\text{no},\text{yes}\}$ for the queriee $w_i$. We also let
$D_{r}^{i} := D_{r}^i(q)=[y_1, y_2, \ldots, y_{d}]$ be the answer vector
for the queriee $i$, where $0\leq y_j \leq r$ that represents the number
of ``designations'' to $j$-th neighbor ($1 \leq j \leq d$) as $w_i$'s
parent.

As in the simple batch querying, it is important to obtain an analytical
form of the solution of the following problem, to choose the right $r$:
for a fixed $ 1\le r \le K$:
\begin{align}\label{eqn:subOPT1}
\text{\bf SUB-OPT-I:} &  \quad \max_{v_I \in V_N}\left(\max_{P \in\mathcal{P}(v_I)}
\bprob{\hat{v}=v_1|v_I}\right).
\end{align}

To solve {\bf SUB-OPT-I}, consider the probability
$\prob{\hat{v}=v_1|v_I}$ in \eqref{eqn:subOPT1} for a given $v_I$.
First, it is pretty challenging to find an optimal policy $P$, because
$P$'s action at each $i$-th queriee can be considered as a
mapping ${\cal F}_i$ that uses the entire history of the queriees and their answers:
\begin{align}\label{eqn:policy}
\mathcal{F}_i : \{D_{r}^{1},D_{r}^{2},\ldots,D_{r}^{i-1}; w_1, \ldots, w_{i-1}\}\rightarrow V_N,
\end{align}
for each $i$. As an approximation, it is natural consider the mapping
$\mathcal{F}_i : (D_{r}^{i-1}, w_{i-1}) \rightarrow V_N$, {\it i.e.}, the next
queriee is determined only by the information at the moment.  Even under
this approximation, it also remains to estimate the true parent node of
the queriee, using her answers. To handle this issue, we may consider
the MLE to estimate the true parent node, {\it i.e.},
$\max_{v \in nb(w_i)} \prob{G_N, D_r^{i-1} | v = \text{parent}(w_i)},$
where $nb(w_i)$ is the set of the neighbors of $w_i.$
However, this is also not easy to analyze, because for some $v$ the
probability that it is a true parent requires to compute the probability
that the true source is located in $v$'s subtree which does not contain
$w_i.$

Thus, we propose a heuristic algorithm that is designed to produce an
approximate solution of {\bf OPT-I}. The key of our approximate
algorithm is to choose the policy that allows us to analytically compute
the detection probability for a given $r$ so as to compute $r$ easily,
yet its performance is close to that of {\bf OPT-I}.

\begin{algorithm}[t!]
 \KwIn{Diffusion snapshot $G_N$, querying budget $K$, degree $d$, and truth
   probabilities $q>1/d$} \KwOut{Estimated rumor source $\hat{v}$}
 Calculate the rumor centrality $R(v, G_N)$ for all $v \in G_N$ as in
\cite{shah2010} and let $ s \leftarrow \arg\max_{v \in V_N} R(v, G_N)$\;
\While{}{ \eIf{$s = v_1$} {
     $K \leftarrow K-1$\;
     Break \;} {\If{$K\geq r$} {Count the number of
       ``designations'' ({\it i.e.}, She has spread the rumor to me) for the
       direction question among $s$'s neighbors, and choose the largest
       counted node with a random tie breaking\;
       Set such chosen node by $s$\;
       $K \leftarrow K-r$\; } } { } } Return
 $\hat{v}=s$\;

 \caption{{\bf ID-Q}$(r)$: $r$: Repetition Count}
\label{alg:interactive}
\end{algorithm}

\subsection{Algorithm based on Majority Rule}

The key idea our algorithm is that we simply apply a {\em majority-based
  rule}, as will be clarified soon. We first formally describe our
algorithm, called {\bf ID-Q}$(r)$ and explain how it operates and its
rationale. Again, {\bf ID-Q}$(r)$ is parameterized by the repetition
count $r$: we first calculate the rumor
centrality of all nodes in $G_N$ (Line 1), where $s$ is set to be the
rumor center. Then, we query the identity question to the rumor center
$s$ (Lines 3-5).  If she is not the source then ask the direction
questions $r$ times, and count the number of ``designations'' for its
neighbor (Lines 7-8). Then, we choose the largest counted node with a
random tie breaking and repeat the same procedure. The
algorithm stops when there is a node which reveals itself as the rumor
source within $K$ queries, otherwise, it outputs the last queried node
as the estimator.

In selecting a parent node of the target queriee, instead of the exact
calculation of MLE, a simple majority voting is used by selecting the
node with the highest number of designations, motivated by the fact that
when $q>1/d$, such designation sample can provide a good clue of who is
the true parent. Using this idea, we are able to have an
approximate, but closed form solution of {\bf SUB-OPT-I}, which allows us to compute the
best $r^*$ that maximizes the detection probability under such an
approximation, as will be given in the next section.

\subsection{Detection Performance}
We now provide analytical results on the detection performance of {\bf
  ID-Q}$(r)$. We first start by presenting the lower bound of the detection
  probability for a given repetition count $r$ in Proposition~\ref{prop:inter_prob}

\smallskip
\begin{proposition}
  \label{prop:inter_prob}
  For $d$-regular trees ($d\geq 3$), a snapshot $G_N,$ a given budget
  $K,$ our estimator $\hat{v}(G_N,r)$ from {\bf ID-Q}$(r)$ has the
  detection probability lower-bounded by:
\begin{multline}
  \label{eqn:detect2}
\lim_{N \to \infty}  \bprob{\hat{v}(G_N,r)=v_1} \ge \cr
 1-c \cdot \exp\left [-2 (g_d (r,q))^3\left(\frac{K}{r+1}\right)\log \left(\frac{K}{r+1}\right) \right],
\end{multline}
where $g_d (r,q):= 1- e^{-\frac{r(d-1)}{3d(1-q)}}$ and
$c=(8d+1)/d$.
\end{proposition}
\smallskip

The proof is presented in Section~\ref{sec:proof}. The term $g_d (r,q)$ in
\eqref{eqn:detect2} is the probability that the
queriee reveals the true parent for given $r$ and $q$.
Next, Theorem~\ref{thm:interactive} quantifies the amount of querying
budget that is sufficient to obtain arbitrary detection probability by
choosing the optimal $r^*$ in the sense of the lower bound in
\eqref{eqn:detect2}.

\smallskip
\begin{theorem}
\label{thm:interactive}
Using {\bf ID-Q}$(r^*),$ where
$$r^*= \left\lfloor1+\frac{2d(1-q)^2 \log\log
   K}{3(d-1)}\right\rfloor,$$
for any given $0< \delta <1,$ the detection
probability under $d$-regular
tree is at least $1-\delta,$ if
\begin{align}
\label{eqn:elower1}
    K\geq \frac{(2d-3)/d(\log(7/\delta))}{(q-1/d)^3\log (\log (7/\delta))}.
    \end{align}
\end{theorem}

\smallskip The proof is presented in Section~\ref{sec:proof}. This
theorem indicates that if queriees are truthful with probability $q=1/d+\varepsilon$,
for an arbitrary small number $\varepsilon$ we need $1/\varepsilon^3$ times more querying budget.
As an example, suppose $q=0.6$ and $d=3,$ where we need
$K\geq 166$ to achieve at least 95\% accuracy of detection.

It is expected that the querying with direction helps and thus requires less
budget than simple batch querying. Our contribution lies in quantifying
this difference: for small $\delta,$ with respect to the scaling of
$1/\delta$, the amount of querying
is asymptotically reduced from $1/\delta$ to $\log (1/\delta),$ which
should be significant especially when high detection quality is necessary.

\section{Introduction}

Information spread is universal in many types of online/offline and
social/physical networks. Examples include the propagation of infectious
diseases, the technology diffusion, the computer virus/spam infection in
the Internet, and tweeting and retweeting of popular topics.  Finding a
``culprit'' of the information spreading is of great significance,
because, for a harmful diffusion, its spreading can be mitigated or even
blocked by vaccinating humans or installing security updates.  Detecting
the rumor source has been regarded as a challenging task unless
sufficient side information is provided. The seminal work by Shah and
Zaman~\cite{shah2010} analytically provides the detection performance of
the MLE (maximum-likelihood estimator) under regular tree topologies,
where the detection probability is upper-bounded by 31\% if the number
of infected nodes goes to infinity and much less
for other practical topologies.  Since then, extensive attentions have
recently been made in various types of network topologies and diffusion
models \cite{shah2012,zhu2013,Luo2013,bubeck2014}, whose major interests
lie in constructing an efficient estimator and providing theoretical
limits on the detection performance.

In practice, the effort of finding the rumor source is made in
conjunction with extra processes with the aim of obtaining more side
information and thus improving the detection performance. In this
paper, we aim at quantifying the impact of querying, where querying
refers to the process of asking some questions. Obviously, it is
expected that such queries improves the detection performance, but
little attention has been made to quantification of the detection
performance in presence of querying. In literature, it has been
studied what happens if multiple snapshot observations are provided
\cite{Zhang2014}, or if a restricted node subset (also called a
suspect set) is given \cite{dong2013} a priori.

In this paper, we study the impact of querying in a highly generalized
setup. Users\footnote{In this paper, the terms ``user" and ``queriee" are used interchangeably. }
may be untruthful with some probability, where two different
types of querying are considered: {\em (a) simple batch querying} and {\em (b)
  interactive querying with direction.} In simple batch querying, for a
given querying budget, a candidate queriee set is first chosen, and the
question of ``Are you the rumor source?'' (referred to as {\em identity question}) can be asked to the queriees
in the set multiple times. Due to limited budget, a source estimation
algorithm should strike a good balance between the size of the candidate
set and the number of questions, depending on the amount of budget, the
degree of untruthfulness, and the underlying graph topology.  In
interactive querying with direction, we start with some initial quieree,
and iteratively ask a series of questions ``Are you the rumor source?''
and ``If not, who spreads the rumor to you?'' (referred to as {\em
  direction question}) to the current queriee,
and determine the next queriee, using the (possibly untruthful) answers
for the second question, where this iterative querying process lasts
until the entire querying budget $K$ is exhausted. A source estimation
algorithm in this query type should smartly consider the tradeoff
between the number of questions and the number of queriees we can ask.

We propose the estimation algorithms for both types of queries and
analyze their detection performances as well as the minimum budget to
satisfy an arbitrary detection performance.  We summarize our main
contributions as follows:
\begin{itemize}
\item[$\circ$] {\bf \em Simple batch querying.}  We first formulate an
  optimization problem that maximizes the detection probability over the
  number of questions to be asked, the
  candidate queiree set, and the estimators for a given diffusion
  snapshot and the answer samples. We discuss its analytical challenges
  and propose an approximate estimation algorithm that selects the
  candidate queriee set based on the hop-distance from the rumor center
  and the MLE for the ``filtered'' candidate nodes by including
  only nodes with many positive answers.  We prove that for a given
  probability $p >1/2$ that users are truthful, $d$-regular tree, and a
  budget $K,$ for any $0< \delta <1,$ if
  $K\geq \frac{c(2/\delta)}{(p-1/2)^{2}\log (\log(2/\delta))}$ with some
  constant $c$ (depending on the degree $d$) then the detection
  probability is at least $1-\delta.$

\smallskip
\item[$\circ$] {\bf \em Interactive querying with directions.}  In this
  querying type, we also consider an optimization problem that maximizes
  the detection probability and discuss the technical challenges in
  solving it, where we assume that users are only untruthful for the
  direction question for simplicity. We propose an estimation algorithm
  that starts with a ``rumor center" as the initial queriee, and apply a
  kind of majority rule in determining the next queriee, {\it i.e.}, selecting
  the node with highest vote for multiple direction questions. We
  analyze this simple, yet powerful estimation algorithm and
  characterize its detection probability for given parameters. From
  this, we establish the minimum budget for any given detection
  probability: for the probability $q > 1/d$ that users are truthful for
  a direction question, $d$-regular tree, and a given budget $K,$ for
  any $0< \delta <1,$ if
  $K\geq \frac{c\log(7/\delta)}{(q-1/d)^3\log (\log (7/\delta))}$ with some
  constant $c$ (which depends on the degree $d$), then the detection
  probability is at least $1-\delta.$ This result quantifies the power
  of the direction question in addition to the identity question, reducing
  the required budget to satisfy the detection probability $1-\delta$ by
  a logarithmic factor with respect to the scaling of $1/\delta$ for
  small $\delta >0.$

\smallskip
\item[$\circ$] {\bf \em Evaluation over synthetic and real-world
    graphs.} Our analytical results above provide useful guidelines on
  how much budget is required to guarantee a given detection performance
  for different querying types when users are untruthful. We validate
  our findings via extensive simulations over popular random graphs
  (\emph{Erd\"{o}s-R\'{e}nyi}  and scale-free graphs) and a real-world
  Facebook network. As an example, in Facebook network,
the interactive querying requires about 200 queries to achieve almost
one detection probability when $q>0.5$ because
the tracking by the direction is efficient due to the small diameter of the
network.
\end{itemize}
 \vspace{-0.4cm}

\iffalse

\note{----------------------- writing on the motivation of source detection in
earlier papers -------------------}

Identification of malicious information sources in a network, be it in
the case of an online spam spreading in the Internet or a
misinformation or rumor propagating in an online social network,
allows timely quarantine of the epidemic-like spreading to limit the
damage caused. For example, law enforcement agencies may be interested
in identifying the perpetrators of false information used to
manipulate the market prices of certain stocks.

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 re-tweeting of popular Twitter topics. In general,
any of these situations can be modeled as an epidemic-like rumor
spreading in a network [3], [4].
Imagine a computer virus has spread through a large network, and all
that is known about the outbreak is which computers are infected and
which computers have been communicating with each other. In this case,
is it possible to reliably find the source of the computer virus?

Imagine a rumor spreads through a network, and after a certain amount
of time, we only know who has heard the rumor and the underlying network
structure. With only this information, is it possible to determine who
was the rumor source? Finding rumor sources is a very general type of
problem which arises in many different contexts. For example, the rumor
could be a computer virus on the Internet, a contagious disease in a
human population, or some trend in a social network. In each of these
scenarios, detection of the source is of interest as this source may be
a malicious agent, patient zero, or an influential person.

It is challenging to understand how the source of the spreading can be
identified in a reliable manner from a number of snapshot observations
of the spread conditions, {\it e.g.}, infected nodes in virus propagation or
users possessing the rumor, and the underlying connectivity of the
network. This can lead to a fundamental understanding of the role of
network in aiding or constraining epidemic-like spreading [1, 2].

In this paper, we consider the issue of reliably detecting a single
rumor source with multiple observations from a statistical point of
view of a spreading. Our goal is to find the rumor source in order to
control and prevent network risks based on limited information about
the network structure and multiple snapshot observations.

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.

\fi

\section{Proof of Lemmas}
\label{sec:lemma}

\section{Model and Preliminaries}
\label{sec:model}

\subsection{Model}
\vspace{-0.06cm}
\noindent{\bf \em Rumor diffusion.} We describe a rumor spreading
model which is commonly adopted in other related work, {\it e.g.},
\cite{shah2010,shah2012,zhu2013}.  We consider an undirected graph
$G=(V,E),$ where $V$ is a countably infinite set of nodes and $E$ is
the set of edges of the form $(i,j)$ for $i, j\in V$.  Each node
represents an individual in human social networks or a computer host
in the Internet, and each edge corresponds to a social relationship
between two individuals or a physical connection between two Internet
hosts.  We assume a countably infinite set of nodes for avoiding the
boundary effect. As a rumor spreading model, we consider a SI model,
where each node is in either of two states: {\em susceptible} or {\em
  infected}. All nodes are initialized to be susceptible except the
rumor source, and once a node $i$ has a rumor, it is able to spread
the rumor to another node $j$ if and only if there is an edge between
them.  Let a random variable $\tau_{ij}$ be the time it takes for node
$j$ to receive the rumor from node $i$ if $i$ has the rumor. We assume
the $\tau_{ij}$ are exponentially distributed with rate $\lambda>0$
independently of everything else. Without loss of generality, we
assume that $\lambda=1$. We denote $v_1 \in V$ by the rumor source, which
acts as a node that initiates diffusion and denote $V_N \subset V$ by $N$ infected
nodes under the observed snapshot $G_N\subset G$. In this paper, we consider
the case when $G$ is a regular tree
and our interest is when $N$ is large, as done in many prior work
\cite{shah2010,shah2012,Khim14,dong2013,Zhang2014}.

\begin{comment}
  For general loopy graphs, the rumor source detection problem is not
  easy to analyze, and most properties derived in the tree graphs do
  not extend, {\it e.g.}, the ML estimator is NP-hard to compute.  However,
  following the implications from the results in regular trees, one
  can design a heuristic algorithm that performs well for general
  graphs.  For example, in \cite{shah2010tit}, they suggest to choose
  BFS (Breadth First Search) first, and use the rumor centrality of
  the tree as the rumor source estimator for the general graph.
\end{comment}

\begin{comment}
of the estimator by introducing the concept of \emph{querying}. We
consider two kinds of querying which are interactive and
non-interactive querying.  Interactive querying scenario assumes that
we can obtain additional information with each single query. Then we
can utilize those additional information to determine the next
estimator and iterate queries.  However, non-interactive querying
scenario involves simultaneous querying without interactive
question-and-answer mechanism. In non-interactive case we cannot
obtain additional information from each query.

The notion of \emph{querying budget} will be used throughout this
paper.  We say there are $K$ querying budgets when we have $K$ chances
of question-and-answering in interactive querying scenario or we have
$K$ amount of nodes that can be simultaneously picked in
non-interactive querying scenario. We will closely investigate each
querying scenario and derive the lower-bound guarantee of improved
detection probability with given amount of $K$ querying budgets.

So far we discussed about the performance of ML estimator for
detecting rumor sources. However, the detection probability was quite
low; less than 1/2 in every case.  In practical situations, we do not
usually determine various properties of a stochastic process in a
single guess. Rumor source detection is a part of these estimation
processes, and we can think about doing simultaneous/sequential
multiple guesses instead of doing a single guess in order to improve
the credibility of the estimation.

We aim at improving detection probability of the estimator by
introducing the concept of \emph{querying}. We consider two kinds of
querying which are interactive and non-interactive querying.
Interactive querying scenario assumes that we can obtain additional
information with each single query. Then we can utilize those
additional information to determine the next estimator and iterate
queries.  However, non-interactive querying scenario involves
simultaneous querying without interactive question-and-answer
mechanism. In non-interactive case we cannot obtain additional
information from each query.

The notion of \emph{querying budget} will be used throughout this
paper.  We say there are $K$ querying budgets when we have $K$ chances
of question-and-answering in interactive querying scenario or we have
$K$ amount of nodes that can be simultaneously picked in
non-interactive querying scenario. We will closely investigate each
querying scenario and derive the lower-bound guarantee of improved
detection probability with given amount of $K$ querying budgets.
\end{comment}

\begin{figure}
\begin{center}
\subfigure[A simple batch querying.]{\includegraphics[width=0.24\textwidth]{figs/Noninter}\label{fig:Noninter}}
\hspace{-0.2cm}
\subfigure[Interactive querying with direction.]{\includegraphics[width=0.24\textwidth]{figs/Inter}\label{fig:Inter}}
\hspace{0cm}
 \end{center}
\caption{Examples of two querying types with untruthful
  answers. In (a), the querier selects a candidate set (a dotted
  circle) and asks just one identity question ({\it i.e.}, $r=1)$ in a batch. In (b),
  starting from the initial node, the querier first asks ``Are you the
  rumor source?'', and if no, she further asks ``Who spreads the rumor to
  you?'', where the querier interactively tracks the true source, but the
  queriees may be untruthful (RS: Rumor Source). }
\label{fig:querying}
\end{figure}

\smallskip
\noindent{\bf \em Querying with untruthful answers.}  A detector is
allowed to query the nodes, where querying refers to a process of
asking some questions (which will be shortly clarified depending on querying scenarios).
The detector is given some querying budget
$K,$ where we assume that one budget is used to ask one question.  In
this paper, we consider two types of queries (see
Fig.~\ref{fig:querying}), where a queriee may be untruthful, as
modeled in what follows:

\smallskip
\begin{compactenum}[$\circ$]
\item {\bf \em Simple batch querying.}  This query is parameterized by
  $r$, where a querier first chooses $K/r$  ($K$ is a multiple of $r$ for expositional convenience)
  candidate nodes to each of which an {\em identity question} of ``Are
  you the rumor source?'' is asked $r$ times. We call $r$ the
  {\em repetition count} throughout this paper.
  Each queriee $v$ is
  truthful in answering each question only with probability $p_v,$ {\it i.e.},
  even if she is the rumor source, she lies with probability $1-p_v.$
  We assume that the answers are independent over the $r$ queries across
  the queriees. We assume the homogeneous case when $p_v = p$ for all
  $v \in V_N,$ and $p > 1/2,$ \footnote{In the case $p<1/2$, one can flip the sign of the
  final estimation to achieve the same guarantee.} {\it i.e.}, all users are biased with truthful
  answers. For example, Fig~\ref{fig:Noninter} shows a
  candidate set of nodes inside a dotted circle, where with $r=1$ we
  have four ``yes'' nodes and five ``no'' nodes.

\smallskip
\item {\bf \em Interactive querying with direction.}  In this querying
  type, there are two questions, where one is the identity question, as
  in the simple batch querying and another is the {\em direction
    question} of ``Who spreads the rumor to you?.''  This query is also
  parameterized by $r,$ where the querying process occurs in the
  following interactive manner: A querier first chooses an initial node
  to ask the identity question, and further asks the direction question
  $r$ times ({\it i.e.}, repetition count), if the queriee answers that she is
  not the rumor source.  The querying process stops when the queriee
  says that she is the rumor source or the entire budget $K$ is
  exhausted. A querier determines the next queriee from $r$ direction
  questions, where each queriee $v$ is truthful for the direction
  question only with probability $q_v.$\footnote{We model untruthfulness
    only in the direction question, because we aim at purely focusing on
    the impact of untruthfulness in the interactive search of the true
    rumor source, which seems to be the critical component in this type
    of querying.} In other words, she lies for the direction question
  with probability $1-q_v$ and designates a node uniformly at random out
  of all neighbors except for the node who truly spreads the rumor to
  $v$ as a bogus ``parent''. Then, the querier chooses one of her
  neighbors as the parent of $v$ and repeats the same procedure.  As in
  the simple batch querying, we assume the homogeneity in truthfulness
  that $q=q_v$ for all $v \in V_N,$ and $q > 1/d,$ {\it i.e.}, users' bias for
  truthful answers\footnote{In $d$-regular trees, when $q=1/d$, the
    answer for the direction question turns out to be uniformly
    random.}.  Fig~\ref{fig:Inter} shows an example scenario that
  starting from the initial node, a sequence of nodes answer the
  interactive queries truthfully or untruthfully.

\end{compactenum}

\smallskip
\noindent{\bf \em Goal.} Our goal is to propose efficient estimation
algorithms that are practically implementable, for both types of queries
with users' untruthfulness. Especially, we aim at theoretically
quantifying the detection performance of our proposed algorithms by
providing the lower bound of the required budget $K$ to satisfy any
arbitrary detection probability, {\it i.e.}, the sufficient budget $K$ for the
target detection quality.
\vspace{-0.1cm}

\subsection{Preliminaries: Rumor Centrality}
\vspace{-0.06cm}
\label{sec:rumor_center}
\vspace{-0.06cm}
As a preliminary, we explain the notion of {\em rumor centrality,} which is a
graph-theoretic score metric and is originally used in detecting the
rumor source in absence of querying and users' untruthfulness, see
\cite{shah2010}. This notion is also importantly used in our framework
as a sub-component of the algorithms for both simple batch querying and
interactive querying with direction.
In regular tree graphs, Shah and Zaman \cite{shah2010} showed that the
source chosen by the MLE becomes the node
with highest rumor centrality. Formally, the estimator chooses $v_{RC}$ as
the rumor source defined as
\begin{eqnarray}\label{eqn:ML}
       \vspace{-0.4cm}
v_{RC} &=& \arg\max_{v \in V_N} \mathbb{P}(G_N | v=v_1)\cr
       &=&\arg\max_{v \in V_N} R(v, G_N),
              \vspace{-0.4cm}
\end{eqnarray}
where $v_{RC}$ is called \emph{rumor center} and $R(v, G_N)$ is the
rumor centrality of a node $v$ in $V_N$. The rumor centrality of a
particular node is calculated only by understanding the graphical
structure of the rumor spreading snapshot, {\it i.e.}, $R(v, G_N) =N!
\prod_{u \in V_N} (1/T^v_u)$ where $T^v_u$ denotes the number of nodes
in the subtree rooted at node $u$, assuming $v$ is the root of tree
$G_N$ (see \cite{shah2010} for details).

\section{Detection Using Simple Batch Queries}
\label{sec:noninteractive}

\subsection{Algorithm based on MLE and Rumor Centrality}

A source estimation algorithm for simple batch queries consists of the
following steps: We first need to appropriately choose the repetition
count $r$ and the candidate set $C_r \subset V_N$ of size $K/r$ and ask the queries
to the nodes in $C_r.$ Then, we will be given an instance of the
answers, which we denote by a vector
$A_r = A_{r}(p)=[x_1, x_2, \ldots, x_{K/r}]$ with $0\leq x_i \leq r$ that
represents the number of ``yes'' answers of the $i$-th node of $C_r.$

Then, it is natural to consider an algorithm based on ML, to maximize
the detection performance, that solves the following optimization:
\separator
\vspace{-0.2cm}
\begin{align}\label{eqn:OPT}
\text{\bf OPT:} &  \quad \max_{1\leq r \leq K} \max_{C_r}
  \max_{v \in C_r} \bprob{G_N,A_{r}| v=v_1},
\end{align}
where the most inner max corresponds to the ML estimator given the
diffusion snapshot $G_N$ and the query answer snapshot $A_r.$
\vspace{-0.2cm}
\separator

\begin{comment}
Note that
\begin{align}\label{eqn:MAP}
\hat{v}_{\tt ml}&=\arg\ \max_{v \in C_r} \bprob{v=v_1|G_N,A_{r}}\\
&\stackrel{(a)}{=}\arg\max_{v \in
  C_r}\bprob{G_N|v=v_1}\bprob{A_{r}|v=v_1},
\end{align}
where $(a)$ is from the fact that $G_N$ and $A_{r}$ are independent.
\end{comment}

\smallskip
\noindent{\bf \em Challenges.} We now explain the technical challenges
in solving {\bf OPT}. To that end, let us
consider the following sub-optimization in {\bf OPT} for a fixed $ 1\le
r \le K$:
\begin{align}\label{eqn:subOPT}
\text{\bf SUB-OPT:} &  \quad \max_{C_r}
  \max_{v \in C_r} \bprob{G_N,A_{r} | v=v_1}.
\end{align}
Then, the following proposition provides the solution of {\bf SUB-OPT}.
\begin{proposition}
  Construct $C_r^*$ by including the $K/r$ nodes in the decreasing order
  of rumor centrality. Then, $C_r^*$ is the solution of {\bf SUB-OPT}.
\end{proposition}

\smallskip
Despite our knowledge of the solution of {\bf SUB-OPT},
solving {\bf OPT} requires an analytical form of the objective value of
{\bf SUB-OPT} for $C_r^*$ to find the optimal repetition count, say
$r^\star.$ However, analytically computing the detection probability for
a given general snapshot is highly challenging due to the following
reasons. We first note that
\begin{align}
  \label{eq:trade}
&\max_{v \in C_r} \bprob{G_N,A_{r} | v=v_1} \cr
& =  \max_{v \in C_r} \bprob{G_N,A_{r}|v=v_1, v_1 \in C_r} \times \prob{v_1 \in
  C_r}.\cr
& =  \underbrace{\prob{v_1 \in  C_r}}_{(a)} \times \underbrace{\max_{v \in C_r} \bprob{G_N,A_{r}| v=v_1, v_1 \in C_r}}_{(b)},
\end{align}
where we will discuss the analytical challenges in $(a)$ and $(b),$
respectively.

First, the term $(a)$ is difficult to analyze, because
\note{....}. Second, to see the challenging in $(b)$, we first observe
that using the independence between $G_N$ and $A_r,$ by letting the
event ${\cal A}(v) = \{v=v_1, v_1 \in C_r\},$
\begin{align}
\label{eq:2}
\hat{v} &= \arg \max_{v \in C_r} \bprob{G_N,A_{r} \mid  {\cal A}(v)} \cr
&= \arg \max_{v \in C_r} \bprob{A_r
  \mid {\cal A}(v)} \times \bprob{G_N\mid {\cal A}(v)}.
\end{align}
Then, the node $\hat{v}$ maximizing $(b)$ is the node $v$
that has the maximum {\em weighted} rumor centrality where the weight is
$\prob{A_r| {\cal A}(v)}$. As opposed to the case of characterizing the
rumor center in the non-weighted setup, as in \cite{shah2010},
analytically obtaining or graphically characterizing $\hat{v}$ in this
weighted setup is hard, thus which value of $r$ maximizes the detection
probability as formulated in {\bf OPT}.

\begin{comment}
First, it is not easy to find the optimal set $V^r$ for a given budget
$K$ because we do not know what the best strategy to select the set
which maximizes the probability of containing the source. Second, for
calculating the MLE, the first term in \eqref{eqn:MAP} can be obtained
by $R(v,G_N)$ from \eqref{eqn:ML} easily but, the probability
$\mathbb{P}(K^{r}_{p}|v=v_1)$ is quite complex because we have to
consider the all possible cases as varying $r$ which output the data of
each nodes in $V^r$. To handle these issues, we first provide an optimal
solution in \eqref{eqn:OPT} for a given $r$. To see this, consider the
following proposition.
\end{comment}

One can numerically compute it, which, however, needs to generate a lot
of $A_r$ samples (one sample requires a vector of answers for $K$
questions).  Motivated by this, we propose an algorithm producing an
approximate solution of {\bf OPT}. The key of our approximate algorithm
is to choose $C_r$ that allows us to analytical compute the detection
probability for a given $r$ so as to compute $r$ easily, yet its
performance is close to that of {\bf OPT}.

\begin{comment}
However, to obtain the optimal solution in \eqref{eqn:OPT}, there are
some challenging issues. First, it is not easy to find the optimal set
$V^r$ for a given budget $K$ because we do not know what the best
strategy to select the set which maximizes the probability of
containing the source. Second, for calculating the MLE, the first term
in \eqref{eqn:MAP} can be obtained by $R(v,G_N)$ from \eqref{eqn:ML}
easily but, the probability $\mathbb{P}(K^{r}_{p}|v=v_1)$ is quite
complex because we have to consider the all possible cases as varying
$r$ which output the data of each nodes in $V^r$. To handle these
issues, we first provide an optimal solution in \eqref{eqn:OPT} for a
given $r$. To see this, consider the following proposition.

\smallskip
\begin{proposition}\label{proposition:optimalN}
For a given $G_N$, suppose $v(i)$ be the infected node with $i$-th
largest rumor centrality in $V_N$ and let $V_K :=\{v(1),\ldots,
v(K)\}$. Then,
\begin{equation}\label{eqn:opt}
\begin{aligned}
\mathbb{P}(v_1 \in V_K)\geq \mathbb{P}(v_1 \in V),
\end{aligned}
\end{equation}
for any subset $V\subset G_N$ with $|V|=K$.
\end{proposition}
\smallskip
This result implies that it is the optimal for choosing the set which
maximizes the probability of containing source when the size of
candidate set is $K$. We will provide the proof of this in
Section~\ref{sec:proof}. Based on this result, for a given $K/r$
queried nodes, we have
\begin{equation}\label{eqn:trade}
\begin{aligned}
\mathbb{P}(&\hat{v}_{\tt ml}=v_1 |G_N,K^{r}_{p})\\
& =\mathbb{P}(\hat{v}_{\tt ml}=v_1|G_N,K^{r}_{p},v_1 \in V^r)\mathbb{P}(v_1 \in V^r).\\
\end{aligned}
\end{equation}
Hence, from the result in Proposition~\ref{proposition:optimalN}, it
is an optimal solution of \eqref{eqn:OPT} for a given $r$ which
selects the candidate set $V^r$ by order of the rumor centrality and
find the source by MLE after queries. However, unfortunately, it is
technically challenging to obtain tractable analytical results for the
candidate set choice based on rumor centrality, because it is not easy
to characterize the probability $\mathbb{P}(v(i) = v_1)$ for obtaining
the probability that $\mathbb{P}(v_1 \in
V^r)=\sum_{i=1}^{K/r}\mathbb{P}(v(i) = v_1)$. Furthermore, to obtain
the solution in \eqref{eqn:OPT}, we have to consider all possible $r$
which maximizes the detection probability because if we increase $r$
to obtain better probability by the MLE in \eqref{eqn:trade}, the
detection probability $\mathbb{P}(v_1 \in V^r)$ becomes decreasing due
to the reducing of the size for candidate set $V^r$.
\end{comment}

\begin{algorithm}[t!]
 \caption{Estimation for Simple Batch Querying}
\label{alg:noninteractive}
 \KwIn{Rumor set $G_N$, budget $K$, degree $d$, and truth probability
   $p>1/2$} \KwOut{Estimator $\hat{v}$}
$C_r = \hat{V} = \emptyset$\;
Calculate the rumor centrality $R(v, G_N)$ for all $v \in G_N$ as in
\cite{shah2010} and let $ s \leftarrow \arg\max_{v \in V_N} R(v, G_N)$\;
Set the repetition count $ r \leftarrow \left \lfloor 1+\frac{(1-p)\log K}{2e\log(d-1)}\right\rfloor$ \;
Construct a candidate
set $C_r$ by including each node $v$ that satisfies $d(v,s)\leq l
,$ where $l=\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)}$ and
$d(v,s)$ is the hop distance between nodes $v$ and $s$\;

\For{each $v \in C_r$}{
Count the number of ``yes'' (i.e., I am the rumour source) for the
identity question, stored at $\mu(v),$ and if $\mu(v)/r \geq 1/2$ then
include $v$ in $\hat{V}$\; }

\While{$K-r|C_r|\geq r$}{ Select a node $v$ satisfying $d(v,s)= l+1$
  uniformly at random\; Do the same procedure in Lines 6-7\; }

 \If{$\hat{V}=\emptyset$}{ $ \hat{v} \leftarrow \arg\max_{v\in C_r}
   R(v, G_N)$\; } \Else{ $ \hat{v} \leftarrow \arg\max_{v\in\hat{V}}
   R(v, G_N)$\; }
\end{algorithm}

\subsection{Algorithm based on Hop Distance and Majority Rule}

We now propose an algorithm that overcomes the afore-mentioned
challenges in $(a)$ and $(b)$ in \eqref{eq:trade}.  The key idea is that
for $(a)$ we adopt a {\em hop-distance based selection} of the candidate
set $C_r$ and for $(b)$ we simply apply a {\em majority-based rule}, as
will be clarified soon.

We first formally describe our algorithm in {\bf
  Algorithm~\ref{alg:noninteractive}} and explain how it operates,
followed by presenting the rationale behind it: we first calculate the
rumor centrality of all nodes in $G_N$ (Line 1), where $s$ is set to be
the rumor center. Then, we appropriately choose the repetition count as
in Line 3, and construct the candidate set $C_r$ by the nodes within the
hop-distance given in Line 5 from the rumor center $s.$ Next, for each
node in $C_r,$ we ask the identity question $r$ times, and count the
number of ``yes''es in $\mu(v)$ (Lines 5-6). Using this, we filter out
the candidate set $C_r$ and construct $\hat{V}$ by including the nodes
with $\mu(v)/r \geq 1/2$ (majority rule), i.e., the nodes with higher
chance to be the rumor source.  When $K$ is not a multiple of $r,$ we
handle the remaining $K-r |C_r|$ nodes as in Lines 7-9. Finally we
choose the node in $\hat{V}$ with highest rumor centrality, where if
$\hat{V} = \emptyset,$ we simply do the same task for $C_r.$

\smallskip
\noindent{\bf \em Rationale.} We now provide the rationale of {\bf
  Algorithm 1} from the perspective of how we handle the
analytical challenges in \eqref{eq:trade}  so as to approximately solve
{\bf OPT} in an approximate manner.

\smallskip
\begin{itemize}
\item[$\circ$] {\em Hop Distance based $C_r$ selection:} Selecting
  $C_r$ based on the distance from the rumor center, rather than based
  on the sorted rumor centrality permits us to have the closed form of
  $\prob{v_1 \in C_r}.$ This is because \note{.......}.\vspace{2cm}

\item[$\circ$] {\em Construction of filtered candidate set $\hat{V}$
    from querying:} Instead of using the exact weight rumor centrality,
  We use more simple scheme to approximate this. Consider that if the
  node $v_i$ output the querying data by $x_i$ then for $r$ times
  questions, from the fact that $p>1/2$, we know that if $x_i \geq r/2$
  then the weight becomes high and vise versa. Since we will find the
  maximum weighted centrality nodes in $C_r$, we set
  $\bprob{A_r|{\cal A}(v)}=1$ if $x_i \geq r/2$ and $\bprob{A_r|v_i}=0$
  if $x_i < r/2$.
\end{itemize}

Using the above approximation techniques, we are able to have the closed
and approximate form of {\bf SUB-OPT}, which allows us to compute the
best $r^\star$ that maximizes the detection probability as in
$r^*= \left \lfloor 1+\frac{(1-p)\log K}{2e\log(d-1)}\right\rfloor.$

---------------------------------------
In
our algorithm, we first choose the node with the largest rumor
centrality $s$ (Line 3), and select the query repetition count $r$ as
in Line 3.  For a given budget $K,$ the size of the candidate set can
be $K/r,$ where we choose the queriee candidate set based on their hop
distance to $s,$ where the distance is appropriately chosen such that
we use the budget $K/r$ (Line 5).  We believe that this scheme is a
good approximation because the source is nearby the rumor center with
high probability, which is also quantified for the case of truthful
users by \cite{Khim14} as following lemma.
By choosing this set as a candidate set, we address the
first issue (a) that how to choose the candidate set properly because
this is very simple scheme and has a good detection performance as in
\cite{Khim14} which is derived by rumor centrality.
\begin{comment}
 which is derived by MLE calculations of rumor centrality. Hence, we
 use this criteria for selecting the candidate set. Clearly, the
 detection probability will increase compared to the single point
 estimation for the case of $p_v=1$ for all $v\in V_N$.  However, if
 $p_v<1,$ we do not know how much query can guarantees the detection
 performance which is depends on the number of queries $K$ and the
 probability $p_v$. For the tractability of analysis, we consider the
 case of $p_v=p$ for all node $v\in V_L$. In the following sections,
 we will introduce the proposed simple batch querying algorithm and
 derive the performance guarantee that how many budget is required to
 guarantee the target probability under $d$-regular trees.
\end{comment}

Next, to consider second issue (b), the right value of the query
repetition count $r$ is of critical importance in achieving high
detection probability, where $r$ trade offs the size and the quality
of the selected queriees. For example, when $r=1,$ i.e., we choose a
large candidate set, but only one query can be asked for each node in
the candidate set, in which case, we have to estimate the rumor source
from too many possible candidate nodes without chance of confirming
who is close to the true rumor source.  Hence, the detection
probability can not close to one even for sufficiently large budget
$K$. Due to this reason, we analytically study and
derive the ``optimal'' value of $r^*= \left \lfloor 1+\frac{(1-p)\log
  K}{2e\log(d-1)}\right\rfloor$ that maximizes the detection
probability under our framework, which is thus used in our
algorithm. By selecting this proper $r$, we avoid the issue that needs
to consider all possible $r$ to maximizes this probability in
\eqref{eqn:OPT}. Then, by using this $r$, we calculate the maximal
distance $l<L$ from the rumor center. Indeed, from the fact that there
are $K_l:=\frac{d(d-1)^{l}-2}{d-2}$ nodes in the distance $l<L$ from
the rumor center of the $d$-regular tree, for a given $K$ and $r$, we
have $K\geq r K_l$. By using this, we obtain
$l=\lfloor\log\left(\frac{K(d-2)}{rd}+2\right)/ \log(d-1)\rfloor$.

\begin{comment}
In fact, Theorem~\ref{thm:r1} states a poor detection probability for
a wrong choice of $r$, implying that it is impossible to obtain high
detection quality whatever the budget size $K$ is.

\begin{theorem}\label{thm:r1}
  Consider the $d$-regular tree and MLE algorithm with the single
  noisy feedback with probability $p$. Then for any $K\geq 1$, the
  detection probability of MLE is upper bounded by
\begin{equation}\label{eqn:upper}
   \begin{aligned}
  \text{Pr}(\hat{v}_{\tt ml}=v_{1})\leq \alpha_d+(1-\alpha_d)(p^2
  +(1-p)^2).
   \end{aligned}
 \end{equation}
\end{theorem}

First, this result implies that if there is a noisy feedback for the
non-interactive querying, then the number of budget can not make the
probability close to one even though for the extremely large $K$
because when $p\neq 1$ in \eqref{eqn:upper} then this is strictly
small than one. For example, if $p=3/4$ then $\text{Pr}(\hat{v}_{\tt
  ml}=v_{1})$ can not beyond 0.75.
\end{comment}

\smallskip
\noindent{\bf \em (b) Filtering and final estimation.}

\note{how (5) is approximated by majority based filtering and RC-based selection...}
Instead of using the exact weight rumor centrality, We use more simple scheme
to approximate this. Consider that if the node $v_i$ output the querying
data by $x_i$ then for $r$ times questions, from the fact that $p>1/2$, we know that if $x_i \geq r/2$
then the weight becomes high and vise versa. Since we will find the
maximum weighted centrality nodes in $C_r$, we set $\bprob{A_r|v_i}=1$ if $x_i \geq r/2$
and $\bprob{A_r|v_i}=0$ if $x_i < r/2$. This is the explanation of
line 6-14 in the Algorithm~ \ref{alg:noninteractive}.
From
the fact that each queried node answer the truth with probability $p$
for each time, the algorithm cumulates the number of reveals as the
rumor source. In the line 7, $\mu(v)$ is the total count of revealing
itself as the rumor source for the infected node $v \in V_c$. If
$\mu(v)$ is greater than half of $r$ then it selects the node as the
candidate node and put the node in the candidate set $\hat{V}$. From
the fact that $p>1/2$, the source will be in $\hat{V}$ with
probability larger than $p$ and other queried node will not be in this
set with probability larger than $p$. Hence, it is rational to search
the source in the set $\hat{V}$.  In addition to this, since the
candidate set is defined by the distance from the rumor center, there
may be remained budget after selecting $r$ and $l$ for a given budget
$K$. Hence, we use this budget for asking additional $l+1$ hop nodes
uniformly at random in line 8-10.  Finally, in the third part (line
11-14), the algorithm chooses the node with maximum centrality in the
selected candidate set $\hat{V}$. If this set is empty, then it
chooses the node with maximum centrality in the original set $V_c$.

\begin{comment}
In this algorithm, even though we use the $L$-hop criteria to select
the candidate set for simplicity, as described before, this is
somewhat nice compared to the optimal selection which is based on the
rumor centrality.  In addition to this, we derive the optimal $r$
instead of using just one query ($r=1$) so that the performance of
detection increases. In Appendix, we derive that if there is only one
query to each node, then the detection probability can not beyond the
probability $p$ even for sufficiently large budget $K$ in this
algorithm \footnote{We also prove that the detection probability by
  using MLE can not goes to one for any $K$.}. Finally, we use also
the information of snapshot which is the rumor centrality so that it
guarantees the proper estimation among the nodes in the candidates
set.
\end{comment}

\subsection{Detection Performance}

As a main result, we state the following theorem for the analytic
performance of Algorithm~\ref{alg:noninteractive}. We first obtain the
lower bound of detection probability for a given $r$, then by using
this, we find the optimal $r^*$ and derive that for a given
$\delta>0$, how many query budget is required to achieve the detection
probability at least $1-\delta$ as follows.

\smallskip
\begin{theorem}
For $d$-regular trees ($d\geq 3$), the detection probability of the Simple Batch
Querying ($p>1/2$) for given $K, p$ and $r$ is given by
\begin{equation}\label{eqn:detect}
    \begin{aligned}
\mathbb{P}(\hat{v}=v_1)\geq\frac{r+p}{r+1}\left(1-c\cdot exp\left(-h_d
(K,r)/2\right)\right),\\
    \end{aligned}
  \end{equation}
where $h_d
(K,r):=\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\log\left(
\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\right)$ and $c = 7(d+1)/d.$
Furthermore, by obtaining the optimal $ r^*$ in \eqref{eqn:detect}, we have for
sufficiently small $\delta>0,$ if
\begin{equation}\label{eqn:elower}
    \begin{aligned}
     K\geq \frac{c(2/\delta)}{p^2\log (\log (2/\delta))},
    \end{aligned}
  \end{equation}
then the detection probability is at least $1-\delta$ where
$c=4(d-1)/(d-2)$ is a constant depends on $d$.
\label{thm:noninteractive}
\end{theorem}
\smallskip
This results indicates that if there is untruthful answer with
probability $p>1/2$, then we need $1/p^2$ times more budget of
querying to satisfy the same target probability compared to the case
of $p=1$ which is also derived in \cite{Khim14}. If $p\simeq 1/2$ then
it needs about 4 times more budget to guarantee the same target
detection probability. Furthermore, if $p=0.6$ then it needs $K\geq 684$
budget to achieve at least 95\% accuracy for detection probability
when $d=3$.

\section{Simulation Results}
\label{sec:numerical}

In this section, we will provide simulation results of our two proposed
algorithms over three types of graph topologies: (i) regular trees, (ii)
two random graphs, and (ii) a Facebook graph. We propagate a rumor from
a randomly chosen source up to 400 infected nodes, and plot the
detection probability from 200 iterations.
\begin{figure}[t!]
\subfigure[SB-Q as varying $p$.]{\includegraphics[width=0.52\columnwidth]{figs/Simple}\label{fig:interactive_hop}}
\hspace{-1.5cm}
\subfigure[SB-Q as varying $K$.]{\includegraphics[width=0.52\columnwidth]{figs/queryK}\label{fig:interactive_1hop}}
\subfigure[ID-Q as varying $q$.]{\includegraphics[width=0.52\columnwidth]{figs/Inter1}\label{fig:interactive_multihop_a}}
\hspace{-0.6cm}
\subfigure[ID-Q as varying $K$.]{\includegraphics[width=0.52\columnwidth]{figs/Inter2}\label{fig:interactive_multihop_b}}
\caption{Detection probabilities for $d$-regular trees ($d=3$) in batch
  querying ((a),(b)) and interactive querying with direction ((c),(d)),
  respectively.}
\label{fig:regular}
\end{figure}

\smallskip
\noindent{\bf \em Regular trees.}
We use $d$-regular tree with $d=3$, where we compare three algorithms
for both simple batch querying (SB-Q) and interactive querying with direction (ID-Q): our algorithms, denoted by
$L$-hop multi query, MLE single query, and MLE multi query.  MLE single
query and MLE multi query are the algorithms that we use $r=1$ and
$r=r^*$ (as described in Theorems~\ref{thm:noninteractive} and
\ref{thm:interactive}), respectively, but for those fixed $r,$ MLE based
estimation algorithms are used as discussed in
Sections~\ref{sec:simple_mle} and \ref{sec:interactive_mle}. Although
MLE multi query is not theoretically optimal, we believe that it is
close to optimal, providing the information on how closely our
algorithms perform compared to optimal ones.
Fig.~\ref{fig:interactive_hop} shows the detection probabilities for
simple batch querying, as the truth probability $p$ varies from 0.55 to
1 when $K=766$ (corresponding to the number of nodes within 8 hop
distance).  As expected, the probability increase as $p$ increases and
we see that if $p=0.7$ then the detection probability is about 40\% for
the MLE single query whereas above 90\% for multi query.  In
Fig.~\ref{fig:interactive_1hop}, we vary the query budget for
$p=0.6$. For multi querying, 1000 queries are enough to achieve the
detection probability is at least 90\% however, it is not beyond 50\%
even for $K=1500$ for the single querying even for MLE, implying that
just selecting a large number of candidate nodes is not enough for
untruthful users, and a certain procedure of learning in presence of
untruthfulness such as multi querying becomes essential.
Figs.~\ref{fig:interactive_multihop_a} and
\ref{fig:interactive_multihop_b} show the similar kind of plots for
interactive querying as $p$ and $K$ vary, respectively.  We observe that
when the detection probability is above 99\% even for MLE single query
if $q>0.9$.  However, for
$q=0.4$ in Fig.~\ref{fig:interactive_multihop_b}, we see that the detection probability is below 90\% when
$K=200$ whereas those of both multi querying schemes are almost one,
showing the power of interactiveness in querying.

\begin{figure}[t!]
\begin{center}
\subfigure[SB-Q as varying $K$.]{\includegraphics[width=0.517\columnwidth]{figs/ERN1}\label{fig:batch_ersf}}
\hspace{-0.55cm}
\subfigure[ID-Q as varying $K$.]{\includegraphics[width=0.517\columnwidth]{figs/ERI1}\label{fig:interactive_ersf}}
\end{center}
\caption{Detection probabilities for ER and SF graphs. (Without querying is the detection probability by BFS estimator.)}
\label{fig:random}
\end{figure}

\smallskip
\noindent{\bf \em Random graphs.}
We consider \emph{Erd\"{o}s-R\'{e}nyi} (ER) and scale-free (SF) graphs.
In the ER graph, we choose its parameter so that the average degree by 4
for 2000 nodes. In the SF graph, we choose the parameter so that the
average ratio of edges to nodes by 1.5 for 2000 nodes. It is known that obtaining MLE
is hard for the graphs with cycles, which is $\sharp$P-complete. Due to
this reason, we first construct a diffusion tree from the Breadth-First
Search (BFS) as used in \cite{shah2010}: Let $\sigma_{v}$ be the
infection sequence of the BFS ordering of the nodes in the given graph,
then we estimate the source $v_{\tt bfs}$ that solves the following:
\begin{equation}\label{eqn:BFS}
\begin{split}
  v_{\tt bfs}=\arg \max_{v\in
    G_{N}}\mathbb{P}(\sigma_{v}|v)R(v,T_{b}(v)),
\end{split}
\end{equation}
where $T_{b}(v)$ is a BFS tree rooted at $v$ and the rumor spreads along
it.  Then, by using those selected nodes, we perform our algorithms with
querying.  Figs.~\ref{fig:batch_ersf} and \ref{fig:interactive_ersf}
show the detection probabilities with varying $K$ for batch and
interactive querying, where we observe similar trends to those in
the regular trees. We see that only about 50 questions
need to asked to achieve 99\%
detection probability when $q=0.7$ for the interactive querying scheme.

\begin{figure}[t!]
\begin{center}
\subfigure[Facebook Network.]{\includegraphics[width=0.45\columnwidth]{figs/facebook}\label{fig:facebook}}
\subfigure[Two querying schemes as varying $K$ in Facebook network.]{\includegraphics[width=0.51\columnwidth]{figs/FaceB1}\label{fig:facebook_result}}
\caption{Detection probabilities for Facebook network. (Without querying is the detection probability by BFS estimator.)}
\label{fig:general}
\end{center}
\end{figure}

\smallskip
\noindent{\bf \em Real world graph.}  Finally, we show the results for a
Facebook network as depicted in Fig.~\ref{fig:facebook}.  We use the
Facebook ego network in \cite{NIPS2012} which is an undirected graph
consisting of 4039 nodes and 88234 edges where each edge corresponds to
a social relationship (called FriendList) and the diameter is 8 hops. We
perform the same algorithm used for random graphs based on the BFS
heuristic and show the results in Fig.~\ref{fig:facebook_result}.
The results show that how fast the detection probabilities goes to one as $K$ increases.
For example, the interactive querying requires about 200 queries to achieve almost
one detection probability when $q>0.5$.

\section{Estimating Rumor Sources with Querying}

\section{Proofs of Results}
\label{sec:proof}
In this section, we will provide the proof of Propositions and Theorems.

\subsection{Proof of Proposition~\ref{prop:simple_prob}}

To obtain the lower bound of the detection probability, consider that for a given
$r$, we have
the detection probability as
\begin{equation}\label{eqn:detection}
    \begin{aligned}
      \mathbb{P}(\hat{v}=v_{1})&=\mathbb{P}
      (\hat{v}=v_1,v_1 \in V_{l}) \\ &=\mathbb{P}
      (\hat{v}=v_1|v_1 \in V_{l})\cdot\mathbb{P}(v_1 \in
      V_{l}) \\
    \end{aligned}
  \end{equation}
where $V_l$ be the set of infected nodes which distance to the rumor
center is $l\leq L$. To obtain the probability $\mathbb{P}(v_1 \in V_{l})$,
we consider the following lemma.

\smallskip
\begin{lemma}(\cite{Khim14})\label{lem:L-hop}
For a $d$-regular tree ($d\geq 3$), let $V_L$ be the set of infected nodes in
$L$-hop distance to the rumor center. Then, for $L\geq 2$,
\begin{equation}\label{eqn:L-hop}
    \begin{aligned}
   \mathbb{P}(v_1 \notin V_L)\leq c e^{- \frac{L}{2}\log L}.
    \end{aligned}
  \end{equation}
where $c = 7(d+1)/d.$
\end{lemma}
\smallskip
This result\footnote{This result has been simplified by constant term from
the result in \cite{Khim14}.} implies that the probability of distance between the
source and rumor center decaying exponentially with respect to the
distance. Hence, it remains to find the probability $\mathbb{P}
(\hat{v}=v_1|v_1 \in V_{l})$ in \eqref{eqn:detection}. To do this,
consider that
\begin{equation}\label{eqn:detection1}
    \begin{aligned}
    \mathbb{P}(\hat{v}=v_1&|v_1 \in V_{l})=\mathbb{P}(v_1 \in \hat{V}, v_1 =v_{LRC}|v_1 \in V_{l})\\
    &=\mathbb{P}(v_1 \in \hat{V}|v_1 \in V_{l})\mathbb{P}(v_1 =v_{LRC}|v_1 \in V_{l}),\\\\
    \end{aligned}
  \end{equation}
where $v_{LRC}$ is the \emph{Local Rumor Center} (LRC) which is the nodes with maximum rumor centrality in
$\hat{V}$. To obtain the first term in \eqref{eqn:detection1}, let
 $\hat{p}:=\mathbb{P}(v_{1} \in \hat{V}|v_1 \in V_{l})$ which is the probability that the source
is in the final candidate set by the majority-based decision rule in
the Algorithm ~\ref{alg:noninteractive} and let $X_i(v)$ be the random
variable with which takes $+1$ if the queried node answer ``yes" and
takes $0$, otherwise for a given $r\geq 1$. Then, one can easily check that this follows the
Bernoulli random variable with probability $p>1/2$.  Let
$Z(v)=\sum_{i=1}^{r}X_i (v)$ then, we have
\begin{equation}\label{eqn:majority}
    \begin{aligned}
     \hat{p}:=\mathbb{P}\left(Z(v)\geq r/2\right)&=\sum_{j=0}^{\lfloor
       r/2\rfloor}\binom{r}{j}(1-p)^{j}p^{r-j}\\ &=I_{p}(r-\lfloor
     r/2\rfloor, \lfloor r/2\rfloor+1),
    \end{aligned}
  \end{equation}
where $I_{p}(\cdot)$ is the regularized incomplete beta
function. Clearly, this probability becomes larger than $p$ when
$p>1/2$ and it goes to one for $r$ increases. Next,
we need to obtain the second term in \eqref{eqn:detection1}. To do this,
consider the following lemma.

\smallskip
\begin{lemma}(\cite{dong2013})\label{lem:suspect}
For a $d$-regular tree ($d\geq 3$), suppose that there are $k$ suspect nodes which
contains the rumor source and let $\varphi_{d}(k):=\lim_{N\rightarrow
  \infty} \mathbb{P}(\hat{v}_{MAP}=v_1)$.  Then
\begin{equation}\label{eqn:suspect}
    \begin{aligned}
      \varphi_{d}(k) \geq 1-\frac{2(k-1)}{k}\left(1-I_{1/2} \left(
      \frac{1}{d-2}, \frac{d-1}{d-2} \right)\right).
    \end{aligned}
  \end{equation}
Here, $I_\alpha (a, b)$ is a regularized incomplete Beta function:
\begin{equation*}
I_\alpha (a, b) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} \int_0^\alpha t^{a-1} (1-t)^{b-1}dt,
\end{equation*}
where $\Gamma(\cdot)$ is the standard Gamma function.
\end{lemma}
\smallskip
The inequality in \eqref{eqn:suspect} becomes the equality if the
suspect set is connected. This result provides the detection
probability of MAPE when the size of suspect set is given.
In other
words, if there are $k$ infected nodes in the suspect set then the
probability that the local rumor center is the source
is given by \eqref{eqn:suspect}. Let $V_{l,\hat{p}}$ be
the set of final candidate node in $V_l$ after $r$ queries under the
probability $p>1/2$ and let $\varphi_{d}(V_{l,\hat{p}})$ be the
detection probability when the estimator chooses the maximum rumor
centrality node among $V_{l,\hat{p}}$ then, we have $\mathbb{P}
(\hat{v}=v_1|v_1 \in
V_{l})=\hat{p}\cdot\varphi_{d}(V_{l,\hat{p}}).$ From
\eqref{eqn:detection}, the detection probability is given by
\begin{equation}\label{eqn:result1}
    \begin{aligned}
     \mathbb{P}(&\hat{v}=v_{1})\geq\hat{p}\cdot\varphi_{d}(V_{l,\hat{p}})\left(1-c
     \cdot e^{-\frac{l}{2}\log l}\right),\\
    \end{aligned}
  \end{equation}
where $c=7(d+1)/d$. However, the first two terms $\hat{p}$ and
$\varphi_{d}(V_{l,\hat{p}})$ are somewhat difficult to handle because
these term contains the incomplete beta functions. To simplify the
result, we first consider the following lemma.

\smallskip
\begin{lemma}
For a given $r$, if $p>1/2$ then
\begin{equation*}
\begin{aligned}
\hat{p}\geq p+(1-p)(1-e^{-p^{2}\log r}),
\end{aligned}
\end{equation*}
where $\hat{p}$ is given by \eqref{eqn:majority}.
\label{lem:majority}
\end{lemma}
\smallskip
This is more simple form compared to \eqref{eqn:majority} and this
result also shows that how the parameters $p$ and $r$ effect the
changing of the probability $\hat{p}.$ We will provide the proof of
this in the technical paper in []. By multiple queries to each node, the size
of $V_{l,\hat{p}}$ will decrease so that the detection probability
will be larger. Based on this, we also obtain the simple bound for the
probability $\varphi_{d}(V_{l,\hat{p}})$ as follows.

\smallskip
\begin{lemma}
For a $d$-regular tree ($d\geq3$), if $p>1/2$ then
\begin{equation*}
\begin{aligned}
\varphi_{d}(V_{l,\hat{p}})\geq 1-e^{-p^{2}r\log r}.
\end{aligned}
\end{equation*}
\label{lem:noninteractive}
\end{lemma}
In this lemma, the result shows that how fast this probability
converges to one as the function of $r$ and $p$. The proof of this
lemma also will be given in [].  Then, from the results
in Lemma~\ref{lem:majority} and Lemma~\ref{lem:noninteractive}, we
have
\begin{equation*}
\begin{aligned}
\hat{p}\varphi_{d}(V_{l,\hat{p}})&\geq \left(p+(1-p)(1-e^{-p^{2}\log
  r})\right)\left(1-e^{-p^{2}r\log r}\right)\\ &\geq 1- e^{-p^{2}\log
  r}\stackrel{(a)}{\geq} 1-\frac{1-p}{r+1}=\frac{r+p}{r+1},
\end{aligned}
\end{equation*}
where $(a)$ is from the fact that $e^{-p^2\log r}\leq (1-p)/(r+1)$. Next, consider
that
\begin{equation*}
\begin{aligned}
l\log l
&=\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)}\log\left(\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)}\right)\\ &
\geq
\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\log\left(\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\right):=h_d
(K,r).\\
\end{aligned}
\end{equation*}
Then, we obtain the following simple form as a lower bound:
\begin{equation}\label{eqn:part1}
\begin{aligned}
\mathbb{P}(&\hat{v}=v_{1})\geq\frac{r+p}{r+1}\left(1-c \cdot exp\left(-h_d
(K,r)/2\right)\right),\\
\end{aligned}
\end{equation}
where $c=7(d+1)/d$ and which proves the first part of Proposition
~\ref{prop:simple_prob}.

\subsection{Proof of Theorem~\ref{thm:noninteractive}}

\smallskip
 Next, we will obtain the optimal $r^*$
which maximizes the detection probability in \eqref{eqn:part1} as
follows.

\smallskip
\begin{lemma}
For $d$-regular tree, if $p>1/2$ then the optimal $r^*$ is given by
\begin{equation*}
\begin{aligned}
r^* \simeq\left\lfloor 1+\frac{(1-p)\log
     K}{2e\log(d-1)}\right\rfloor.
\end{aligned}
\end{equation*}
\label{lem:redundancy}
for a given budget $K$.
\end{lemma}
\smallskip
We will provide the proof of
Lemma~\ref{lem:redundancy} in Section~\ref{sec:proof}. By using these
lemmas, we will provide the required budget to obtain the detection
probability at least $1-\delta$ for a given $\delta >0$. To do this,
we consider the error probability for given $K$ and $p$. The detection
error can be occurred as following two cases. First, the source is not
in $V_l$ and second, the source is in $V_l$ but the estimator can not
find the source. To obtain the probability, let $E_1:=\{d(v_{RC},v_1)
\geq l\}$ be the event for the first case and let $E_2:=\{\hat{v}\neq
v_{1}|d(v_{RC},v_1) < l\}$ be the second case then the error
probability is givne by
\begin{equation}\label{eqn:disjoint}
\begin{aligned}
&\mathbb{P}(\hat{v}\neq v_{1})=\mathbb{P}(E_1 \cup
  E_2)\stackrel{(a)}{=}\mathbb{P}(E_1)+\mathbb{P}(E_2),\\
\end{aligned}
\end{equation}
where $(a)$ is due to the disjoint events of $E_1$ and $E_2$.  The
first error is bounded by $\mathbb{P}(E_1)\leq c\cdot e^{- l\log
  l}$ by Lemma~\ref{lem:L-hop}. To obtain the second error, we use
Lemma~\ref{lem:majority} and Lemma~\ref{lem:noninteractive} such as
\begin{equation*}
\begin{aligned}
\hat{p}\varphi_{d}(V_{l,\hat{p}})&\geq p+(1-p)(1-e^{-p^{2}\log
  r})(1-e^{-p^{2}r\log r})\\ &\geq 1-(1-p)e^{-p^{2}r\log r}.\\
\end{aligned}
\end{equation*}
Hence, by using this, the error probability $\text{Pr}(E_2)$ is
bounded by
\begin{equation*}
\begin{aligned}
\mathbb{P}(E_2) &\leq (1-\hat{p}\cdot\varphi_{d}(V_{l,\hat{p}}))(1-c
\cdot e^{- \frac{l}{2}\log l})\\ &\leq (1-p)e^{-p^{2}r\log r}.
\end{aligned}
\end{equation*}
Then, by combining the probabilities $\text{Pr}(E_1)$ and
$\text{Pr}(E_2)$, we have the total error probability as
\begin{equation*}
\begin{aligned}
\mathbb{P}(\hat{v}\neq v_{1})&=\mathbb{P}(E_1)+\mathbb{P}(E_2)\\ &\leq
(1-p)e^{-p^{2}r\log r}+c\cdot e^{- \frac{l}{2}\log l}.\\
\end{aligned}
\end{equation*}
By using this, let $(1-p)e^{-r\log r} \leq \delta_1 /2$ and $c \cdot
e^{- \frac{l}{2}\log l} \leq \delta_2 /2$ then we can find the minimum number
of budget $K_1$ for the first case and $K_2$ for the second case.  By
the result of Lemma~ \ref{lem:L-hop} in \cite{Khim14}, we obtain that if
$K_2 \geq \frac{c_2 (2/\delta_2)}{\log (\log (2/\delta_2))}$ where
$c_2 = (d-1)/(d-2)$ then $c
\cdot e^{- \frac{l}{2}\log l} \leq \delta_2 /2$. Hence, as a next step, we
need to show that if $K_1 \geq \frac{c_1 (1-p^2)(2/\delta_1)}{p^2\log
  (\log (2/\delta_1))}$ then $(1-p)e^{-p^{2}r\log r} \leq \delta_1
/2$. To see this, consider the equivalent form as $\frac{e^{p^2 r\log
    r}}{1-p}\geq \frac{2}{\delta_1}$ and taking logarithm to both
sides, then after some manipulations, we have
\begin{equation*}
    \begin{aligned}
    r\log r \geq \frac{(1-p)^2 (1+p)}{p^2}\log
    \left(\frac{2}{\delta_1}\right).
    \end{aligned}
  \end{equation*}
By using the result in Lemma~\ref{lem:redundancy} which is $r=\Theta
((1-p)\log K)$ and by similar approach in \cite{Khim14}, one can check
that if $K_1 \geq \frac{c_1 (1-p^2)(2/\delta_1)}{p^2\log (\log
  (2/\delta_1))}$ where $c_1 = 4(d-1)/(d-2)$ then $(1-p)e^{-p^{2}r\log r} \leq \delta_1 /2$. By
combing these, we have if
\begin{equation*}
    \begin{aligned}
    K&\geq K_1 +K_2 \\ &\geq\frac{c_1 (1-p^2)(2/\delta_1)}{p^2\log
      (\log (2/\delta_1))}+\frac{c_2 (8/\delta_2)}{\log (\log
      (2/\delta_2))}\\ &=\frac{c_1 (1-p^2)(2/\delta_1)}{p^2\log (\log
      (2/\delta_1))}+\frac{c_2 p^2 (2/\delta_2)}{p^2\log (\log
      (2/\delta_2))}\\ &\geq\frac{c(2/\delta)}{p^2\log (\log
      (2/\delta))},\\
    \end{aligned}
  \end{equation*}
then $\text{Pr}(\hat{v}= v_{1})\geq 1-\delta$ where $\delta:=\min \{\delta_1, \delta_2\}$
and $c:=\max\{c_1 ,c_2\}=4(d-1)/(d-2)$, respectively. Hence, we complete the
Theorem~\ref{thm:noninteractive}.

\subsection{Proof of Proposition~\ref{prop:inter_prob}}

To prove this, we first obtain the upper bound of the error
probability when $r=1$ {\it i.e.} only one direction question is allowed.
After obtaining the result, we easily extend the probability for
general $r$ which will be provide in later.
From the fact that the interactive querying consists of two kinds of
questions, we assume that $K$ is even \footnote{One can obtain for odd
  $K$ by similar approach. } for the simple analysis. Then, as similar
to the approach in the proof of Theorem~\ref{thm:noninteractive}, we
define two error events $E_1:=\{d(v_{RC},v_1) > K/2\}$ and
$E_2:=\{\hat{v}\neq v_{1}|d(v_{RC},v_1) \leq K/2\}$. Due to the
disjoint of these events, the error probability is represented by
$\mathbb{P}(\hat{v}\neq v_{1})=\mathbb{P}(E_1)+\mathbb{P}(E_2)$.
However, by the result in Lemma~\ref{lem:L-hop}, we have
$\mathbb{P}(E_1)=\mathbb{P}(d(v_{RC},v_1) > K/2)\leq c \cdot e^{-
  K/\log (K/2)},$ where $c=7(d+1)/d$. To obtain the error probability $\mathbb{P}(E_2)$, we
divide this event by conditioned on the distance $d(v_{RC},v_1) =i$
then
\begin{equation*}
\begin{aligned}
&\mathbb{P}(E_2)\\ &=P(\hat{v}\neq v_{1}|d(v_{RC},v_1) <
  K/2)\mathbb{P}(d(v_{RC},v_1) <
  K/2)\\ &=\sum_{i=1}^{K/2}P(\hat{v}\neq
  v_{1}|d(v_{RC},v_1)=i)\mathbb{P}(d(v_{RC},v_1) =i),
\end{aligned}
\end{equation*}
where the case $\mathbb{P}(d(v_{RC},v_1) =0)$ is omitted since the
probability $\mathbb{P}(\hat{v}\neq v_{1}|d(v_{RC},v_1)=0)$ becomes
zero.  Then, we first find the probability $\mathbb{P}(\hat{v}\neq
v_{1}|d(v_{RC},v_1)=i)$ when the total budget is $K.$ To do this, let
$X_j$ be the random variable which takes values $+1$ if the answer is
correct and takes $-1$ if the answer is incorrect at $j$-th query
because if the answer is correct then the distance of next queried
node will be deducted by one from the rumor source and vice
versa. Then, for the error event, it should be $\sum_{j=1}^{K/2}X_j <
i$ for all $1\leq j \leq K/2$. Then if $q>1/d$,
\begin{equation*}
\begin{aligned}
\mathbb{P}(\hat{v}\neq v_{1}&|d(v_{RC},v_1)=i)\\ &\leq
\sum_{j=0}^{i-1}\binom{K/2}{j}q^{j}(1-q)^{K/2-j}\\ &=I_{1-q}(K/2-i,i)\\ &=(K/2-i)\binom{K/2}{i-1}\int_{0}^{1-q}t^{K/2-i}(1-t)^{i-1}dt\\ &
\stackrel{(a)}{\leq}
exp\left(-\frac{2((K/2)q-(i-1))^3}{K/2}\right)\\ &\leq exp\left(-2q^3
(K/2)^2\right),\\
\end{aligned}
\end{equation*}
where $(a)$ is due to the Hoeffding bound for the regularized
incomplete beta function $I_{1-q}(K/2-i,i)$ when $q>1/d$. Hence, from
the fact that $\mathbb{P}(d(v_{RC},v_1) \leq K/2)\leq 1$, we obtain
\begin{equation*}
\begin{aligned}
\mathbb{P}(E_2)\leq (K/2)e^{-2q^3 (K/2)^2}.
\end{aligned}
\end{equation*}
Then, combining the probabilities $\text{Pr}(E_1)$ and
$\mathbb{P}(E_2)$, we have the total error bound as
\begin{equation}\label{eqn:error}
\begin{aligned}
\mathbb{P}(\hat{v}\neq v_{1})&=\mathbb{P}(E_1)+\mathbb{P}(E_2)\\ &\leq
c \cdot e^{- K\log (K/2)}+(K/2)e^{-2q^3 (K/2)^2}\\ &\leq( c
+1)(K/2)e^{-2q^3 (K/2)^2}\\ &\stackrel{(a)}{\leq} c_1 e^{-2q^3
  (K/2)\log(K/2)},\\
\end{aligned}
\end{equation}
where $c_1=c+1$ and the inequality $(a)$ is from the fact that
$(K/2)e^{-(K/2)}\leq K/2 = e^{\log (K/2)}$. Then, from this result
we extend \eqref{eqn:error} for the general $r$. In this case, we also
use the majority result of answer for the
additional question with noisy probability $q$.
To obtain this, consider the total number of direction queries is $r\geq1$ and let
$Y^{1}_i(v)$ be the random variable with probability $q$ for the
parent node $i$ takes $+1$ at the $i$-th query and let
$Y^{j}_i(v)$ for other neighbor node $2\leq j\leq d$ with probability
$(1-q)/(d-1)$ takes $+1$ at the $i$-th query. Let $Z_j (v)
=\sum_{i=1}^{r}Y^{j}_i (v)$ and let $\hat{q}:=\mathbb{P}(Z_1 (v) > Z_j
(v),~ 2\leq j \leq d)$ then from the result in \eqref{eqn:error}, we have
\begin{equation}\label{eqn:err}
\begin{aligned}
\mathbb{P}(\hat{v}\neq v_{1})&\leq ce^{-2\hat{q}^3
  (K/(r+1))\log(K/(r+1))},\\
\end{aligned}
\end{equation}
$c=(8d+1)/d$. To obtain the optimal $r^*$, we consider the following
lemma.

\smallskip
\begin{lemma}
For the redundancy $r$, if $q>1/d$ then
\begin{equation*}
\begin{aligned}
\hat{q}\geq 1- e^{-\frac{r(d-1)}{3d(1-q)}}.
\end{aligned}
\end{equation*}
\label{lem:major}
\end{lemma}
\smallskip
This result is similar version of Lemma~ \ref{lem:majority} which the
proof will be in the next section. If we set $g_d (r,q):= 1-
e^{-\frac{r(d-1)}{3(1-q)}}$ then we complete the proof of Proposition~\ref{prop:inter_prob}.

\subsection{Proof of Theorem~\ref{thm:interactive}}

To finish the proof, we will obtain
the following lemma for the optimal choice of $r$ from \eqref{eqn:err}
and Lemma~\ref{lem:major}.

\smallskip
\begin{lemma}
For $q>1/d$, the optimal $r^*$ in \eqref{eqn:result1} is given by
\begin{equation}
\begin{aligned}
r^* \simeq \left\lfloor1+\frac{2d(1-q)^2 \log\log
  K}{3(d-1)}\right\rfloor.
\end{aligned}
\end{equation}
\label{lem:redundancy2}
\end{lemma}
\smallskip
By using these two results and \eqref{eqn:error}, we consider the error
probability for a given $r$ as
\begin{equation*}
\begin{aligned}
\mathbb{P}(\hat{v}\neq v_{1})&=\mathbb{P}(E_1)+\mathbb{P}(E_2)\\ &\leq
ce^{-2\hat{q}^3 (K/(r+1))\log(K/(r+1))}\\ &\leq ce^{-2\left(1-
  e^{-\frac{r(d-1)}{3d(1-q)}}\right)^3 (K/(r+1))\log(K/(r+1))}\\ &\leq
ce^{-2\left(1- e^{-(1-q)\log\log K}\right)^3
  (K/(r+1))\log(K/(r+1))}\\ &\stackrel{(a)}{=} ce^{-2\left(1- (\log
  K)^{-(1-q)}\right)^3
  (K/(r+1))\log(K/(r+1))}\\ &\stackrel{(b)}{\leq} ce^{-2e^{q^3} K^2
  \log(K/(r+1))}\\ &\leq ce^{-2e^{q^3} K\log K},\\
\end{aligned}
\end{equation*}
where the equality $(a)$ is from the fact that $1-x \simeq e^{-x}$ for
$x\simeq 0$ and $(b)$ is from the fact that $q>1/d$. Therefore, let
$\delta\geq ce^{-2e^{q^3} K\log K}$ then, by similar approach in \cite{Khim14}, we have if
\begin{equation*}
    \begin{aligned}
     K\geq \frac{c\log(7/\delta)}{q^3\log (\log (7/\delta))},
    \end{aligned}
  \end{equation*}
then $\text{Pr}(\hat{v}= v_{1})\geq 1-\delta$ where $c=(2d-3)/d$.
Hence, we complete the proof of
Theorem~\ref{thm:interactive}.

\section{Estimating Rumor Sources with Querying}

\section{Proofs of Results}
\label{sec:proof}

\subsection{Proof of Proposition~\ref{prop:simple_prob}}

First, for a given $r,$ we introduce the notation $V_l,$ which is
equivalent to $C_r,$ where the hop distance $l$ is given in Line 3 of
{\bf SB-Q}$(r).$ This is for presentational simplicity due to a
complex form of $l.$ Also for notational simplicity, we simply use $
\prob{\hat{v}=v_{1}}$ to refer to $\lim_{N \to \infty }\prob{\hat{v}(G_N,r)=v_{1}}$
in the proof section.
Then, the detection probability is expressed as the product of the three
terms:
    \begin{align}
      \label{eqn:detection}
      \prob{\hat{v} = v_{1}} &=   \prob{v_1 \in  V_{l}}\times  \prob{\hat{v}=v_1|v_1 \in V_{l}} \cr
                               & = \prob{v_1 \in  V_{l}} \times \prob{v_1
                                 \in \hat{V}|v_1 \in V_{l}}   \cr
                               &  \times \prob{v_1 =v_{LRC}|v_1 \in \hat{V}},
    \end{align}
where $\hat{V}$ is the filtered candidate set (Lines 4-5 of {\bf
  SB-Q}$(r)$) and  $v_{LRC}$ is the node in $\hat{V}$ that has the
highest rumor centrality, where $LRC$ means the local rumor center.
We will drive the lower bounds of the first, second, and the third terms
of RHS of \eqref{eqn:detection}.
The first term of RHS of \eqref{eqn:detection} is bounded by
\begin{align}
  \label{eq:first}
  \prob{v_1 \in V_{l}} \geq 1-c\cdot e^{-(l/2)\log l},
\end{align}
where the constant $c = 7(d+1)/d$ from Corollary 2 of \cite{Khim14}.
The second and the third terms are handled by the following two lemmas,
whose proofs are will be provided in our technical report \cite{Jae16}:
 \vspace{0.2cm}
\begin{lemma}
When $p>1/2,$
\begin{eqnarray*}
\prob{v_1 \in \hat{V}|v_1 \in V_{l}}  & \geq &p+(1-p)(1-e^{-p^{2}\log r}).
\end{eqnarray*}
\label{lem:majority}
\end{lemma}

\begin{lemma}
  When $d\geq3$ and $p>1/2$,
  \begin{eqnarray*}
    \prob{v_1 =v_{LRC}|v_1 \in \hat{V}}  & \geq & 1-e^{-p^{2}r\log r}.
  \end{eqnarray*}
  \label{lem:noninteractive}
\end{lemma}
 \vspace{-0.2cm}
Then a simple algebra gives us the result that the product of two lower bounds in Lemmas~\ref{lem:majority} and
\ref{lem:noninteractive} is also lower-bounded by $1- e^{-p^{2}\log
  r}\geq 1-\frac{1-p}{r+1}=\frac{r+p}{r+1},$ where we use the fact that $e^{-p^2\log
  r}\leq (1-p)/(r+1).$ Merging this lower-bound with the lower-bound in
\eqref{eq:first} where we plug in
$l=\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)},$ the result
follows. This completes the proof.

\subsection{Proof of Theorem~\ref{thm:noninteractive}}

We first note that the event that our algorithm does not detect the
source to derive the detection error probability is the union of the
following two disjoint events: $E_1:=\{d(v_{RC},v_1) > l\}$  and
$E_2:=\{\hat{v}\neq v_{1}|d(v_{RC},v_1) \leq l\}$, where $E_1$ is the event
that the source is not in the candidate set $V_l$ and $E_2$ is the event
that our estimator fails to detect the source conditioned that the
source is in $V_l.$
Then, from Lemmas~\ref{lem:majority} and \ref{lem:noninteractive}, we get:
\begin{align}
  \label{eq:ppp}
  \prob{\hat{v}\neq v_{1}} \leq (1-p)e^{-p^{2}r\log r}+c\cdot e^{- \frac{l}{2}\log l},
\end{align}
where the constant $c$ is the same as that in \eqref{eq:first}.
Now, we first put
$l=\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)}$ into
\eqref{eq:ppp} and obtained the upper-bound of \eqref{eq:ppp}, expressed
as a function of $r,$ for a given $p,$ and the constant $c.$ Then, we take $r^*$ in the theorem
statement which is derived in \cite{Jae16} and put it to the obtained upper-bound which is expressed as a
function of $K,$ as follows:
\begin{align}
  \label{eq:kkk}
 &  \prob{\hat{v} \neq v_{1}} \cr
&  \leq  \ (1-p)p^{2}e^{-\log K\log (\log K)}+cp^{2} e^{- \frac{\log K}{2}\log (\log K)}\cr
&   \leq  \ (1-p)p^{2}e^{-\frac{\log K}{2}\log (\log K)}+c p^{2}e^{-\frac{\log K}{2}\log (\log K)}\cr
&    \leq  \ c_1 e^{-\frac{(p-1/2)^{2}\log K}{2}\log (\log K)},
\end{align}
where $c_1=c+1$. If we set $\delta \geq c_1 e^{-(p-1/2)^{2}\frac{\log K}{2}\log (\log K)},$ we find the value of $K$ such that its assignment to
\eqref{eq:kkk} produces the error probability $\delta,$ and we get the
desired lower-bound of $K$ as in the theorem statement. This completes
the proof.

\subsection{Proof of Proposition~\ref{prop:inter_prob}}

As a first step, we will obtain the upper bound of the error
probability when $r=1$ {\it i.e.}, only one direction question is used.
After obtaining this, we can easily extend the result for
general $r$ which will be provided in later.
By similar approach in the proof of Theorem~\ref{thm:noninteractive}, we
define two error events such as $E_1:=\{d(v_{RC},v_1) > K/2\}$ and
$E_2:=\{\hat{v}\neq v_{1}|d(v_{RC},v_1) \leq K/2\}$ which are disjoint.
From Lemma~\ref{lem:noninteractive}, we have $\prob{E_1}\leq c \cdot e^{- (K/4)\log (K/2)}$
since we use additional direction query with identity question.
Next, by conditioning on the distance $d(v_{RC},v_1) =i$,
the probability for the event $E_2$ is given by
\begin{equation*}
\begin{aligned}
\prob{E_2}&=\sum_{i=1}^{K/2}\prob{\hat{v}\neq
  v_{1}|d(v_{RC},v_1)=i}\prob{d(v_{RC},v_1) =i}.
\end{aligned}
\end{equation*}
We first obtain $\prob{\hat{v}\neq
v_{1}|d(v_{RC},v_1)=i}$ when the total budget is $K.$ To do this, let
$X_j$ be the random variable which takes $+1$ if the answer is
correct at $j$-th direction query by the querier and takes $-1$, otherwise.
Then, the error event is occurred when $\sum_{j=1}^{K/2}X_j <
i$ for all $1\leq j \leq K/2$ because the querier can not meet the source
for the case. Hence, for a given $q>1/d$, we have
\begin{align*}
&\prob{\hat{v}\neq v_{1}|d(v_{RC},v_1)=i}\\ &\leq
\sum_{j=0}^{i-1}\binom{K/2}{j}q^{j}(1-q)^{K/2-j}=I_{1-q}(K/2-i,i)\\ &=(K/2-i)\binom{K/2}{i-1}\int_{0}^{1-q}t^{K/2-i}(1-t)^{i-1}dt\\ &
\stackrel{(a)}{\leq}
\exp\left(-\frac{2((K/2)q-(i-1))^3}{K/2}\right)\leq \exp\left(-2q^3
(K/2)^2\right),
\end{align*}
where $(a)$ is due to the Hoeffding bound for the regularized
incomplete beta function $I_{1-q}(K/2-i,i)$ when $q>1/d$. Hence, from
the fact that $\prob{d(v_{RC},v_1) \leq K/2}\leq 1$, we obtain
$\prob{E_2}\leq (K/2)e^{-2q^3 (K/2)^2}.$
By combining the probabilities $\prob{E_1}$ and
$\prob{E_2}$, the total probability of error is bounded by
\begin{equation}\label{eqn:error}
\begin{aligned}
&\prob{\hat{v}\neq v_{1}}\leq
c \cdot e^{- (K/4)\log (K/2)}+(K/2)e^{-2q^3 (K/2)^2}\\ &\leq( c
+1)(K/2)e^{-2q^3 (K/2)^2}\stackrel{(a)}{\leq} c_1 e^{-2q^3
  (K/2)\log(K/2)},
\end{aligned}
\end{equation}
where $c_1=c+1$ and the inequality $(a)$ is from the fact that
$(K/2)e^{-(K/2)}\leq K/2 = e^{\log (K/2)}$. Hence, we conclude the
result for $r=1$. Based on this,
we extend \eqref{eqn:error} for general $r$. First,
consider the total number of direction queries is $r\geq1$ for each queriee and let
$Y^{1}_i(v)$ be the random variable which takes $+1$ for the $i$-th query
when the true parent node is designated by the queriee $v$ with probability $q$ and let
$Y^{j}_i(v)$ be the random variable which takes $+1$ for the $i$-th query
when one of other neighbor nodes $2\leq j\leq d$ is designated by $v$ with probability
$(1-q)/(d-1)$. Define $Z_j (v)
:=\sum_{i=1}^{r}Y^{j}_i (v)$ be the total number of designations by the node
$v$ for the $j$-the neighbor $(1\leq j \leq d)$. Then, we need to find $\prob{Z_1 (v) > Z_j
(v),~ \forall j}$ which is the probability that the true parent is the node with maximum designations
by queriee $v$. This probability is handled by the following lemma whose proof is given in \cite{Jae16}.

\smallskip
\begin{lemma}
If $q>1/d$ then
\begin{align*}
\prob{Z_1 (v) > Z_j
(v),~ \forall j}\geq 1- e^{-\frac{r(d-1)(q-1/d)^2}{3d(1-q)}}.
\end{align*}
\label{lem:major}
\vspace{-0.5cm}
\end{lemma}
\smallskip
From this result and \eqref{eqn:error}, we obtain
\begin{align}\label{eqn:err}
\prob{\hat{v}\neq v_{1}}&\leq ce^{-2(g_d (r,q))^3
  (K/(r+1))\log(K/(r+1))},
\end{align}
where $c=(8d+1)/d$ and $g_d (r,q):= 1- e^{-\frac{r(d-1)(q-1/d)^2}{3d(1-q)}}$. Hence, we complete
the proof of Proposition~\ref{prop:inter_prob}.

\subsection{Proof of Theorem~\ref{thm:interactive}}

By $r^*$ in the theorem
statement which is derived in \cite{Jae16} and put it to the obtained upper-bound in \eqref{eqn:err} then
\begin{align}\label{eqn:choi}
\prob{\hat{v}\neq v_{1}}&\leq ce^{-2\left(1-
  e^{-\frac{r(d-1)(q-1/d)^2}{3d(1-q)}}\right)^3 (K/(r+1))\log(K/(r+1))}\cr &\leq
ce^{-2\left(1- e^{-(1-q)\log\log K}\right)^3
  (K/(r^* +1))\log(K/(r^* +1))}\cr &\stackrel{(a)}{\leq} ce^{-2\left(1- (\log
  K)^{-(1-q)}\right)^3
  (K/(r^* +1))\log(K/(r^* +1))}\cr &\stackrel{(b)}{\leq} ce^{-2(q-1/d)^3 K^2
  \log(K/(r^* +1))}\cr
 & \leq ce^{-2(q-1/d)^3 K\log K},
\end{align}
where the inequality $(a)$ is from the fact that $1-x \leq e^{-x}$ for
$0 \leq x \leq 1$ and $(b)$ is due to the fact that $q>1/d$ with $K\log (K/(r^* +1))>\log K$. Let
$\delta\geq ce^{-2(q-1/d)^3 K\log K}$ then, we obtain the value of $K$ which
 produces the error probability $\delta$ in \eqref{eqn:choi} and we obtain the
desired lower-bound of $K$ as in the theorem statement. This completes
the proof.

\subsection{Related Work}

\bigskip
\noindent{\bf \em Related work.}
The research on rumor source detection has recently received
significant attentions.
The first theoretical approach was done by Shah and Zaman
\cite{shah2010,shah2012,shah2010tit} and they introduced the metric
called {\em rumor centrality}, which is a simple topology-dependent
metric.  They proved that the rumor centrality describes the likelihood
function when the underlying network is a regular tree and the diffusion follows
the SI (Susceptible-Infected) model, which is
extended to a random graph network in \cite{shah2011}.  Zhu and Ying
\cite{zhu2013} solved the rumor source detection problem under the SIR
(Susceptible-Infected-Removed) model and took a sample path approach to
solve the problem, where a notion of {\em Jordan center} was introduced,
being extended to the case of sparse observations \cite{zhu2014}. The
authors of \cite{bubeck2014}, \cite{fuchs2015} and \cite{frieze2014}
studied the problem of estimating the source for random growing trees,
where unlike aforementioned papers, they did not assume an underlying
network structure. The authors in \cite{farajtabar2015} inferred the
historical diffusion traces and identifies the diffusion source from
partially observed cascades, and similarly in \cite{pinto2012}, partial
diffusion information is utilized. Recently, there has been some
approaches for the general graphs in \cite{Kai2016, Chang2015} to find
the information source of epidemic. All the detection mechanisms so far
correspond to point estimators, whose detection performance tends to be
low.  There was several attempts to boost up the detection probability.
Wang \etal \cite{Zhang2014} showed that observing multiple different
epidemic instances can significantly increase the the detection
probability. Dong \etal \cite{dong2013} assumed that there exist a
restricted set of source candidates, where they showed the increased
detection probability based on the MAPE (maximum a posterior estimator).
Choi \etal \cite{Choi2016,Choi2016w} showed that the anti-rumor spreading under
some distance distribution of rumor and anti-rumor sources helps finding
the rumor source by using the MAPE.
The authors in \cite{bubeck2014, Khim14,Moon2016} introduced the notion of {\em
  set estimation} and provide the analytical results on the detection
performance. These are close to our work, where querying is considered
in detecting the rumor source. However, our work is done in a much more
generalized and practical setup in the sense that we consider the case
when users may be untruthful, and also two types of practical querying
scenarios are studied.

\section{Detection Using Simple Batch Queries}
\label{sec:noninteractive}
\vspace{-0.1cm}
\subsection{Algorithm based on MLE and Rumor Centrality}
\label{sec:simple_mle}
\vspace{-0.1cm}
A source estimation algorithm for simple batch queries consists of the
following steps: We first need to appropriately choose the repetition
count $r$ and the candidate set $C_r \subset V_N$ of size $K/r$ and ask the queries
to the nodes in $C_r.$ Then, we will be given a sample of the
answers, which we denote by a vector
$A_r := A_{r}(p)=[x_1, x_2, \ldots, x_{K/r}]$ with $0\leq x_i \leq r$
representing the number of ``yes'' answers of the $i$-th node of $C_r.$
Then, it is natural to consider an algorithm based on MLE, to maximize
the detection probability, that solves the following optimization:
\vspace{-0.3cm}
\separator
\vspace{-0.3cm}
\begin{align}\label{eqn:OPT}
\text{\bf OPT-S:} &  \quad \max_{1\leq r \leq K} \max_{C_r}
  \max_{v \in C_r} \bprob{G_N,A_{r}| v=v_1},
\end{align}
where the inner-most max corresponds to the MLE given the
diffusion snapshot $G_N$ and the query answer sample $A_r.$
\vspace{-0.3cm}
\separator
\begin{comment}
Note that
\begin{align}\label{eqn:MAP}
\hat{v}_{\tt ml}&=\arg\ \max_{v \in C_r} \bprob{v=v_1|G_N,A_{r}}\\
&\stackrel{(a)}{=}\arg\max_{v \in
  C_r}\bprob{G_N|v=v_1}\bprob{A_{r}|v=v_1},
\end{align}
where $(a)$ is from the fact that $G_N$ and $A_{r}$ are independent.
\end{comment}

\smallskip
\noindent{\bf \em Challenges.} We now explain the technical challenges
in solving {\bf OPT-S}. To that end, let us
consider the following sub-optimization in {\bf OPT-S} for a fixed $ 1\le
r \le K$:
\begin{align}\label{eqn:subOPT}
\text{\bf SUB-OPT-S:} &  \quad \max_{C_r}
  \max_{v \in C_r} \bprob{G_N,A_{r} | v=v_1}.
\end{align}
Then, the following proposition provides the solution of {\bf SUB-OPT}
whose proof is provided in our technical report \cite{Jae16}.

\smallskip
\begin{proposition}\label{pro:subOPT}
  Construct $C_r^*$ by including the $K/r$ nodes in the decreasing order
  of their rumor centralities. Then, $C_r^*$ is the solution of {\bf SUB-OPT-S}.
\end{proposition}

\smallskip
Despite our knowledge of the solution of {\bf SUB-OPT-S},
solving {\bf OPT-S} requires an analytical form of the objective value of
{\bf SUB-OPT-S} for $C_r^*$ to find the optimal repetition count, say
$r^*.$ However, analytically computing the detection probability for
a given general snapshot is highly challenging due to the following
reasons. We first note that
\begin{align}
  \label{eq:trade}
&\max_{v \in C_r} \bprob{G_N,A_{r} | v=v_1} \cr
& =  \underbrace{\prob{v_1 \in  C_r^*}}_{(a)} \times \underbrace{\max_{v \in C_r^*} \bprob{G_N,A_{r}| v=v_1, v_1 \in C_r^*}}_{(b)}.
\end{align}
First, the term $(a)$ is difficult to analyze, because only the rumor
center allows graphical and thus analytical characterization as
discussed in Section~\ref{sec:rumor_center}, but other
nodes with high rumor centrality is difficult to handle due to the
randomness of the diffusion snapshot.
Second, in $(b)$, we observe
that using the independence between $G_N$ and $A_r,$ by letting the
event ${\cal A}(v) = \{v=v_1, v_1 \in C_r^*\},$
\begin{align}
\label{eq:2}
\hat{v} &= \arg \max_{v \in C_r^*} \bprob{G_N,A_{r} \mid  {\cal A}(v)} \cr
&= \arg \max_{v \in C_r^*} \bprob{A_r
  \mid {\cal A}(v)} \times \bprob{G_N\mid {\cal A}(v)}.
\end{align}
Then, the node $\hat{v}$ maximizing $(b)$ is the node $v$ that has the
maximum {\em weighted} rumor centrality where the weight is
$\prob{A_r| {\cal A}(v)}$. As opposed to the case of characterizing the
rumor center in the non-weighted setup \cite{shah2010}, analytically
obtaining or graphically characterizing $\hat{v}$ in this weighted setup
is also hard due to the randomness of the answer for querying,
thus resulting in the challenge of computing $r$ that
maximizes the detection probability in {\bf OPT-S}.

\begin{comment}
First, it is not easy to find the optimal set $V^r$ for a given budget
$K$ because we do not know what the best strategy to select the set
which maximizes the probability of containing the source. Second, for
calculating the MLE, the first term in \eqref{eqn:MAP} can be obtained
by $R(v,G_N)$ from \eqref{eqn:ML} easily but, the probability
$\mathbb{P}(K^{r}_{p}|v=v_1)$ is quite complex because we have to
consider the all possible cases as varying $r$ which output the data of
each nodes in $V^r$. To handle these issues, we first provide an optimal
solution in \eqref{eqn:OPT} for a given $r$. To see this, consider the
following proposition.
\end{comment}

One can numerically solve {\bf OPT-S}, which, however, needs to generate
a lot of $A_r$ samples (one sample requires a vector of answers for $K$
questions).  Motivated by this, we propose an algorithm producing an
approximate solution of {\bf OPT-S}. The key of our approximate
algorithm is to choose $C_r$ that allows us to analytically compute the
detection probability for a given $r$ so as to compute a good $r$
easily, yet its performance is close to that of {\bf OPT-S}, as
numerically validated in Section~\ref{sec:numerical}.

\begin{comment}
However, to obtain the optimal solution in \eqref{eqn:OPT}, there are
some challenging issues. First, it is not easy to find the optimal set
$V^r$ for a given budget $K$ because we do not know what the best
strategy to select the set which maximizes the probability of
containing the source. Second, for calculating the MLE, the first term
in \eqref{eqn:MAP} can be obtained by $R(v,G_N)$ from \eqref{eqn:ML}
easily but, the probability $\mathbb{P}(K^{r}_{p}|v=v_1)$ is quite
complex because we have to consider the all possible cases as varying
$r$ which output the data of each nodes in $V^r$. To handle these
issues, we first provide an optimal solution in \eqref{eqn:OPT} for a
given $r$. To see this, consider the following proposition.

\smallskip
\begin{proposition}\label{proposition:optimalN}
For a given $G_N$, suppose $v(i)$ be the infected node with $i$-th
largest rumor centrality in $V_N$ and let $V_K :=\{v(1),\ldots,
v(K)\}$. Then,
\begin{equation}\label{eqn:opt}
\begin{aligned}
\mathbb{P}(v_1 \in V_K)\geq \mathbb{P}(v_1 \in V),
\end{aligned}
\end{equation}
for any subset $V\subset G_N$ with $|V|=K$.
\end{proposition}
\smallskip
This result implies that it is the optimal for choosing the set which
maximizes the probability of containing source when the size of
candidate set is $K$. We will provide the proof of this in
Section~\ref{sec:proof}. Based on this result, for a given $K/r$
queried nodes, we have
\begin{equation}\label{eqn:trade}
\begin{aligned}
\mathbb{P}(&\hat{v}_{\tt ml}=v_1 |G_N,K^{r}_{p})\\
& =\mathbb{P}(\hat{v}_{\tt ml}=v_1|G_N,K^{r}_{p},v_1 \in V^r)\mathbb{P}(v_1 \in V^r).\\
\end{aligned}
\end{equation}
Hence, from the result in Proposition~\ref{proposition:optimalN}, it
is an optimal solution of \eqref{eqn:OPT} for a given $r$ which
selects the candidate set $V^r$ by order of the rumor centrality and
find the source by MLE after queries. However, unfortunately, it is
technically challenging to obtain tractable analytical results for the
candidate set choice based on rumor centrality, because it is not easy
to characterize the probability $\mathbb{P}(v(i) = v_1)$ for obtaining
the probability that $\mathbb{P}(v_1 \in
V^r)=\sum_{i=1}^{K/r}\mathbb{P}(v(i) = v_1)$. Furthermore, to obtain
the solution in \eqref{eqn:OPT}, we have to consider all possible $r$
which maximizes the detection probability because if we increase $r$
to obtain better probability by the MLE in \eqref{eqn:trade}, the
detection probability $\mathbb{P}(v_1 \in V^r)$ becomes decreasing due
to the reducing of the size for candidate set $V^r$.
\end{comment}

\subsection{Algorithm based on Hop Distance and Majority Rule}

We now propose an algorithm that overcomes the afore-mentioned
challenges in $(a)$ and $(b)$ of \eqref{eq:trade}.  The key idea is that
for $(a)$ we adopt a {\em hop-distance based selection} of the candidate
set $C_r$ and for $(b)$ we simply apply a {\em majority-based rule}.

We first formally describe our algorithm in {\bf SB-Q}$(r)$
parameterized by a repetition counter $r$, and explain how it operates,
followed by presenting the rationale behind it: we first calculate the
rumor centrality of all nodes in $G_N$ (Line 2), where $s$ is set to be
the rumor center. Then, using the parameter $r,$ we
construct the candidate set $C_r$ by the nodes within the
hop-distance $l$ given in Line 3 from the rumor center $s$ using the relation
that $K\geq r|C_r|=r\frac{d(d-1)^{l}-2}{d-2}$ (Line 3). Next, for each
node $v$ in $C_r,$ we ask the identity question $r$ times, and count the
number of ``yes''es in $\mu(v)$ (Lines 4-5). Using this, we filter out
the candidate set $C_r$ and construct $\hat{V}$ by including the nodes
with $\mu(v)/r \geq 1/2$ (majority rule), {\it i.e.}, the nodes with higher
chance to be the rumor source.  When $K$ is not a multiple of $r,$ we
handle the remaining $K-r |C_r|$ nodes as in Lines 6-8. Finally we
choose the node in $\hat{V}$ with highest rumor centrality, where if
$\hat{V} = \emptyset,$ we simply do the same task for $C_r.$

\begin{algorithm}[t!]
 \caption{{\bf SB-Q}$(r)$, $r$: Repetition Count}
\label{alg:noninteractive}
 \KwIn{Diffusion snapshot $G_N$, budget $K$, degree $d$, and truthfulness probability
   $p>1/2$} \KwOut{Estimator $\hat{v}$}
$C_r = \hat{V} = \emptyset$\;
Calculate the rumor centrality $R(v, G_N)$ for all $v \in G_N$ as in
\cite{shah2010} and let $ s \leftarrow \arg\max_{v \in V_N} R(v, G_N)$\;
Construct a candidate
set $C_r$ by including each node $v$ that satisfies $d(v,s)\leq l
,$ where $l=\frac{\log\left(\frac{K(d-2)}{rd}+2\right)}{\log(d-1)}$ and
$d(v,s)$ is the hop distance between nodes $v$ and $s$\;

\For{each $v \in C_r$}{
Count the number of ``yes'' ({\it i.e.}, I am the rumor source) for the
identity question, stored at $\mu(v),$ and if $\mu(v)/r \geq 1/2$ then
include $v$ in $\hat{V}$\; }

\While{$K-r|C_r|\geq r$}{ Select a node $v$ satisfying $d(v,s)= l+1$
  uniformly at random\; Do the same procedure in Lines 5\; }

 \If{$\hat{V}=\emptyset$}{ $ \hat{v} \leftarrow \arg\max_{v\in C_r}
   R(v, G_N)$\; } \Else{ $ \hat{v} \leftarrow \arg\max_{v\in\hat{V}}
   R(v, G_N)$\; }
\end{algorithm}

\smallskip
\noindent{\bf \em Rationale.} We now provide the rationale of {\bf SB-Q}$(r)$ from the perspective of how we handle the
analytical challenges in \eqref{eq:trade}  so as to solve
{\bf OPT-S} in an approximate manner.

\smallskip
\begin{itemize}
\item[$\circ$] {\em Hop Distance based $C_r$ selection:} Selecting
  $C_r$ based on the distance from the rumor center, rather than based
  on the sorted rumor centrality permits us to have the closed form of
  $\prob{v_1 \in C_r}.$ However, it is not
  difficult to obtain the lower bound of this probability when we consider
  the hop distance based $C_r$ by using some
  preliminary results in \cite{shah2012, Khim14}. Furthermore, the authors
  in \cite{Khim14} shows the probability of distance between rumor source and center
  decays exponential with respect to the distance, {\it i.e.}, the source is
  nearby the rumor center with high probability. Hence, it is a good
  approximation to the centrality based $C_r$ with analytical guarantees.

\item[$\circ$] {\em Construction of the filtered set $\hat{V}$ from
    querying:} Consider the answer sample of node $v$ for $r$ questions,
  $x_v ~(1\leq x_v \leq r),$ where one can easily check that for
  $x_v \geq r/2$ then the weight $\prob{A_r| {\cal A}(v)}$ becomes
  larger than that for $x_v < r/2$ due to $p>1/2.$ We use an
  approximated version of the weight from the answer samples by setting
  $\prob{A_r|{\cal A}(v)}=1$ if $x_v \geq r/2,$ and
  $\prob{A_r|{\cal A}(v)}=0$ if $x_v < r/2.$
\end{itemize}

\smallskip Using the above techniques, we are able to have an
approximate, but closed form solution of {\bf SUB-OPT-S}, which allows us to compute the
best $r^*$ that maximizes the detection probability under such an
approximation, as $r^*$ is given in the next section.

\subsection{Detection Performance}

We now provide analytical results on the detection performance of {\bf
  SB-Q}$(r).$ We first start by presenting the lower bound
of the detection probability for a given repetition count $r$ in
Proposition~\ref{prop:simple_prob}.

\begin{proposition}
  \label{prop:simple_prob}
  For $d$-regular trees ($d\geq 3$), a snapshot $G_N,$ a given budget
  $K,$ our estimator $\hat{v}(G_N,r)$ from {\bf SB-Q}$(r)$ has the
  following lower-bound of the detection probability:
\begin{multline}
  \label{eqn:detect}
\lim_{N \to \infty}  \bprob{\hat{v}(G_N,r)=v_1}\geq \cr
  \left(\frac{r+p}{r+1}\right) \cdot \Bigg(1-c\cdot
  \exp\Bigg( \frac{-h_d
  (K,r)}{2}\Bigg)\Bigg),
\end{multline}
where $c = 7(d+1)/d$ and
$$h_d (K,r):=\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\log\left(
\frac{\log\left(\frac{K}{r}\right)}{\log(d-1)}\right).$$
\end{proposition}

The proof is presented in Section~\ref{sec:proof}. The second term of RHS of \eqref{eqn:detect} is the probability that the
source is in the candidate set for given $K$ and $r$. Hence, one can see
that for a fixed $K$, large $r$ leads to the decreasing detection
probability due to the smaller candidate set.  However, increasing $r$
positively affects the first term of RHS of \eqref{eqn:detect}, so that
there is a trade off in selecting a proper $r$.

Now, Theorem~\ref{thm:noninteractive} quantifies the amount of querying
budget that is sufficient to obtain arbitrary detection probability by
choosing the optimal $r^*$ in the sense of the lower bound in
\eqref{eqn:detect}. We provide the proof in Section~\ref{sec:proof}.

\smallskip
\begin{theorem}
\label{thm:noninteractive}
Using {\bf SB-Q}$(r^*),$ where
$$r^*= \left \lfloor 1+\frac{(1-p)\log K}{2e\log(d-1)}\right\rfloor,$$
for any given $0< \delta <1,$ the detection
probability under $d$-regular
tree is at least $1-\delta,$ if
\begin{align}
\label{eqn:elower}
     K & \geq \frac{4(d-1)/(d-2) (2/\delta)}{(p-1/2)^2\log (\log (2/\delta))}.
    \end{align}
\end{theorem}

\smallskip This results indicates that if untruthfulness probability is
such that $p=1/2+\varepsilon$ for an arbitrary small number $\varepsilon$,
then we need $1/\varepsilon^2$ times more budget of querying to
satisfy the same target probability. To
illustrate, consider $p=0.7$ and $d=3,$ where we need $K\geq 6156$ to
achieve at least 95\% accuracy of detection.

redpajama_set_name: RedPajamaArXiv