betaFeedback

WorksMathematics

Local Clustering Tests and Botnet Localization in Sparse Random Geometric Networks

Abstract

We use local clustering to test for botnets in sparse random geometric networks. Under the null hypothesis, the vertices are independent uniform points on a fixed-dimensional torus, with edges determined by a distance threshold. Under the alternative, an unknown set of vertices ignores the geometry and connects independently with the same marginal edge probability. Every prescribed vertex has the same marginal binomial degree law under both hypotheses, so its degree alone carries no information. Triangle closure, however, distinguishes the two models. Under the null, conditional on a degree of at least two, the local clustering coefficient has exact mean Cd>0C_d>0, a known constant that depends only on the dimension. Under the alternative, the corresponding mean is pnp_n for a bot. For a non-bot, the corresponding mixture mean converges to CdC_d when the botnet size is o(n)o(n). We prove non-asymptotic concentration bounds, an exponential bound on the worst-case risk of a scan test, and exact-support recovery. For every deterministic sequence 1≤kn=o(n)1\leq k_n=o(n), if μn=(n−1)pnμ_n=(n-1)p_n satisfies μn/log⁡n→∞μ_n/\log n\to\infty, the local rule recovers the botnet with probability tending to one, uniformly over all label sets of size knk_n. The proof combines geometric U-statistics, bounded differences on random neighborhoods, and a stability bound showing that genuine vertices retain their geometric clustering when bots form only a vanishing fraction of their neighbors. The test does not use the latent positions. The theorem assumes that the model parameters are known, although CdC_d can instead be estimated consistently. In the high-expected-degree regime, the rule also works for a single bot.

Paper details

vlnc:W_m3799jee
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…