Mathematics – Probability
Scientific paper
2012-01-17
Mathematics
Probability
Scientific paper
Let $\mathcal{G}_n=(V_n,E_n)$ be a growing sequence of deterministic finite graphs, with $V_n$ denoting the vertices and $E_n$ denoting the edges. Consider the random graph $\mathcal{G}_n(p_n)=(V_n, E_n(p_n))$ obtained by including any given edge with probability $p_n$, independent of other edges, and let $P_n^{p_n}$ denote the corresponding probability measure on $\mathcal{G}_n$. Now tamper with the random graph in some regular way. For example, if $\mathcal{G}_n$ is the complete graph on $n$ vertices, so that $\mathcal{G}_n(p_n)$ is the Erdos-Renyi graph, then one might tamper with it by disconnecting all the edges of a randomly chosen vertex, or by adding all the edges of a randomly chosen Hamiltonian path from $\mathcal{G}_n$, or by adding all the edges of a randomly chosen clique of order $k_n$ from $\mathcal{G}_n$. Denote the resulting induced measure on $\mathcal{G}_n$ by $P_n^{p_n,\text{tamper}}$. The tampering is called \it detectable\rm\ if $\lim_{n\to\infty}||P_n^{p_n,\text{tamper}}-P_n^{p_n}||_{\text{TV}}=1$, \it strongly undetectable\rm\ if the above limit is 0, and \it weakly undetectable\rm\ if $\{||P_n^{p_n,\text{tamper}}-P_n^{p_n}||_{\text{TV}}\}_{n=1}^\infty$ is bounded away from 0 and 1. We study the tampering problem for a variety of examples.
No associations
LandOfFree
Detecting Tampering in Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Detecting Tampering in Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting Tampering in Random Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-97858