Detecting Bot Networks With Graph Analysis

Coordinated inauthentic accounts are found by their coordination, not by their content. But a dense cluster of accounts doing the same thing is also what a fan community, a newsroom and a conference audience look like, so topology alone produces a detector that cannot be deployed. The pipeline that works has three stages and the third is arithmetic about base rates.

The follow graph is the wrong graph

The instinct is to cluster the follow or friend graph and look for dense blocks. It does not work well, for a reason worth stating plainly: following is cheap, permanent and mostly organic. Bot accounts follow real accounts to look real, real accounts follow bots by accident, and the resulting blocks are dominated by genuine interest communities that are denser than most bot networks.

The graph that carries signal is one you construct from behavioural co-occurrence rather than from a declared relationship. The approach set out in Uncovering Coordinated Networks on Social Media (Pacheco et al., ICWSM 2021) is to build a similarity network in which nodes are accounts and an edge means the two accounts behaved alike in some traceable respect: they amplified the same posts, posted the same URLs, used the same handle-sharing pattern, or acted within seconds of each other. Coordination shows up here because acting together is the thing the operator is paying for and therefore cannot avoid.

Building and thresholding a co-activity graph

Start bipartite again — accounts on one side, actions on the other — then project, exactly as on fraud ring detection, where the projection and density arithmetic is worked in full. Two decisions differ here and both are consequential.

• What counts as one action. Two accounts sharing one popular link is nothing. Two accounts sharing forty links, of which thirty are obscure, is a great deal. Weight each shared action by inverse frequency so common actions cannot manufacture edges, then require a minimum count of shared actions before an edge exists at all.
• Where the edge threshold sits. Co-activity similarity is continuous, and the graph you analyse is whatever survives your cut. Set it low and the graph is one giant component; set it high and every cluster is a pair. There is no principled value — the workable practice is to sweep the threshold, look at how the size of the largest component changes, and pick a point in the stable region rather than on the cliff.

Then cluster, with a connected-components pass at a strict threshold or a modularity method at a looser one, and score each candidate cluster by its induced density and its size.

Behavioural signals layered on topology

A candidate cluster is a hypothesis. What separates a bot network from a fandom is per-account behaviour, and these are the features that carry weight because they reflect operational constraints rather than taste:

• Timing regularity. Human posting is bursty and follows a daily cycle. Scheduled automation is not. The measurable version is the entropy of the inter-post interval distribution and the entropy of posting time across the 24-hour clock — a genuine account has a sleep gap, and an account with a flat hour-of-day histogram is either automated or shared.
• Account age and creation clustering. Registration timestamps that cluster into a few minutes across a whole component are hard to explain innocently, and the operator cannot retroactively age accounts.
• Content near-duplication. Not exact matching, which is trivially defeated by token substitution, but similarity of normalised text or of embeddings across the cluster. Rate of near-duplicate reuse within a cluster is more informative than any one duplicate.
• Profile completeness and reuse. Default avatars, handles matching a generated pattern, bios reused across accounts, stock images reused from elsewhere.
• The action mix. Amplification with almost no original posting, or replies with almost no reading behaviour, is a shape that recurs because it is what the account was purchased to do.

Fuse these rather than chaining them. A cascade of hard thresholds throws away a cluster that fails one test badly and passes four others overwhelmingly. A model that takes cluster-level aggregates (median account age, mean timing entropy, near-duplicate rate, induced density, component size) as features and produces one score keeps that information, and it gives you a per-feature attribution you can put in front of a reviewer.

The base rate decides everything

This is the calculation that determines whether a detector can ship, and it is routinely skipped. Assume a platform with 10,000,000 active accounts and suppose 0.5% of them are part of coordinated networks. The prevalence figure is an assumption — pick your own, the arithmetic is the point — and everything below follows from it.

assumptions
  accounts            N  = 10,000,000
  prevalence          p  = 0.5%          → 50,000 coordinated
  legitimate                             → 9,950,000
  recall (sensitivity)   = 95%
  specificity            = 99%

true positives    = 0.95 × 50,000     =  47,500
false positives   = 0.01 × 9,950,000  =  99,500

precision = 47,500 / (47,500 + 99,500) = 47,500 / 147,000 = 32.3%

A detector that is right 99% of the time on legitimate accounts flags two innocent accounts for every guilty one. That is not a bad detector — 99% specificity is a high bar — it is what rare events do to precision. Push specificity to 99.9% and the same recall gives 47,500 true positives against 9,950 false, or 82.7% precision; the difference between a system you can act on and one you cannot is entirely in the third nine.

Two consequences follow. First, report precision at the operating point rather than accuracy or AUC, for the same reason as on link prediction. Second, this is why clustering first is not merely a modelling choice: reviewing 147,000 individual accounts is impossible, while reviewing a few thousand clusters — each with its shared evidence attached — is a real workload. The graph is what makes the false-positive rate affordable.

The adversary adapts

Every signal above has a cost to defeat, and a network that survives one enforcement round has paid it. Timing regularity is defeated by adding jitter and a fake sleep cycle. Creation clustering is defeated by aging accounts before use, or by buying compromised real ones — which also defeats account-age and profile-completeness features entirely. Content duplication is defeated by generating variants.

What is expensive to defeat is co-activity itself. The network exists to act in concert; if it stops acting in concert it stops delivering what it was paid for. That is why the topology layer is the durable part of the pipeline and the behavioural features are the perishable part, and why the behavioural half needs retraining on a much shorter cycle than you would use for an ordinary model.