Network Analysis & Computational Thinking

0. Why this chapter

Network analysis is named in three places at once: as a technique agencies use, as one of Schrepel's three stated specialisms, and as the natural method for cartel detection. It is also the one technique where you can describe a concrete method without claiming to have built it.

1. The vocabulary, with a worked graph

Term	Plain meaning	In a co-bidding graph
Node (vertex)	A thing	A firm
Edge	A relationship between two things	These two firms bid for the same tender
Weighted edge	The relationship has a strength	They co-bid 47 times
Directed edge	The relationship has a direction	A owns B — ownership is directed, co-bidding is not
Degree	How many edges a node has	How many distinct firms this one has competed against
Neighbourhood	The nodes one step away	This firm's direct competitors
Path / shortest path	A route along edges; the shortest such route	How many co-bidding steps separate two firms
Component	A group where everyone is reachable from everyone, with no edges to outside	A regionally separated market — or a market-sharing agreement
Clique	A group where every member is connected to every other	The shape a closed bidding ring makes
Bipartite graph	Two kinds of node, edges only between kinds, never within	Firms on one side, tenders on the other. This is what procurement data actually is
Adjacency matrix	A table with nodes as rows and columns, and a 1 (or a weight) where an edge exists	An n-by-n grid. Mostly zeros, so stored sparse

One small graph, used for the rest of the chapter

        Acme ------- Borex
          |  \         / |
          |   \       /  |
          |    \     /   |
          |     Civic    |          Zeta --- Yuri
          |    /     \   |
          |   /       \  |
          |  /         \ |
        Delta ------- Echo

                  |
                  |  one single edge
                  |
              Nadir


  DEGREES:
    Acme  3   (Borex, Civic, Delta)
    Borex 3   (Acme, Civic, Echo)
    Civic 4   (Acme, Borex, Delta, Echo)
    Delta 3   (Acme, Civic, Echo)
    Echo  4   (Borex, Civic, Delta, Nadir)
    Nadir 1   (Echo)
    Zeta  1   (Yuri)
    Yuri  1   (Zeta)

  COMPONENTS: two.
    { Acme, Borex, Civic, Delta, Echo, Nadir }
    { Zeta, Yuri }                  <- separate market?
                                       or market sharing?

  THE DENSE CORE: Acme-Borex-Civic-Delta-Echo
    nearly every pair connected -> near-clique

  THE BRIDGE: Echo--Nadir is the ONLY way into Nadir.
    Remove Echo and Nadir is isolated.
    -> Echo has high BETWEENNESS (see below)

Three features to notice, because they are the three things you look for in real data: a dense core where everyone bids against everyone, a separate component that may be a distinct market or a divided one, and a single node whose removal disconnects part of the graph. Each maps to a different theory of harm.

2. The four centrality measures — and they mean different things

*Central* is ambiguous, and the four standard measures answer four different questions. Choosing the wrong one is the most common error in applied network analysis, because they often rank nodes quite differently.

C_{\text{deg}}(v) = \frac{\deg(v)}{n-1}

Degree centrality is a node's number of connections, divided by the number of other nodes.The simplest: how many people you are connected to, scaled to sit between 0 and 1. In the worked graph Civic and Echo both score 4 over 7, about 0.57. Answers: who is busiest. Cheap to compute and often enough. Its blind spot: it treats all connections as equally valuable.

C_{\text{btw}}(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}

Betweenness centrality sums, over every pair of other nodes, the fraction of shortest paths between that pair which run through this node.How often you sit on the route between other people. Sigma-s-t is the number of shortest paths from s to t; the numerator is how many of those pass through v. Answers: who is a broker or bottleneck. In the worked graph Echo has high betweenness because every path to Nadir goes through it. This is the measure that finds the hub in a hub-and-spoke cartel, and it is frequently the most legally interesting one — a broker can be central without being busy.

C_{\text{clo}}(v) = \frac{n-1}{\sum_{u \neq v} d(v,u)}

Closeness centrality is the number of other nodes divided by the sum of the shortest-path distances from this node to all of them.How near you are to everyone else on average. High closeness means information or coordination reaches you quickly. Answers: who is well placed to coordinate. Caution: it is undefined or misleading across disconnected components, because the distance to an unreachable node is infinite — so compute it per component, which is the kind of detail that separates someone who has run this from someone who has read about it.

C_{\text{eig}}(v) = \frac{1}{\lambda}\sum_{u \in \mathcal{N}(v)} C_{\text{eig}}(u)

Eigenvector centrality says a node's score is proportional to the sum of its neighbours' scores.Recursive: you are important if you are connected to important people. Formally it is the leading eigenvector of the adjacency matrix. PageRank is a variant with a damping factor that makes it behave on directed graphs. Answers: who is connected to the well-connected. A firm with three connections to the dense core can outrank one with ten connections to isolated firms. Note it is the only one of the four that is self-referential, which is why it needs linear algebra rather than counting.

3. Density, clustering and community detection

\text{density} = \frac{2m}{n(n-1)} \qquad\qquad C(v) = \frac{2 \, |\{\text{edges among } v\text{'s neighbours}\}|}{\deg(v)\,(\deg(v)-1)}

Density is twice the number of edges divided by the number of possible pairs. The local clustering coefficient of a node is the fraction of pairs among its neighbours that are themselves connected.Density: what share of all possible relationships actually exist. n(n−1)/2 is the number of possible pairs, so this runs from 0 to 1. Clustering coefficient: do your contacts know each other? If a firm's three competitors all also compete with each other, its clustering coefficient is 1. High clustering is the signature of a closed group — and it is also the measure that the trap in section 5 silently inflates.

Q = \sum_{c} \left[ \frac{m_c}{m} - \left(\frac{d_c}{2m}\right)^{2} \right]

Modularity sums, over each detected community, the share of edges inside that community minus the share you would expect if edges were placed at random given the same node degrees.The subtraction is the whole idea. Any partition puts *some* edges inside groups; modularity asks whether it puts in more than chance would, holding degrees fixed. Roughly, Q above about 0.3 suggests real community structure. Louvain and Leiden are the standard algorithms that search for the partition maximising Q — Leiden is the better-behaved one. Its known weakness is a resolution limit: it can miss communities smaller than a certain size relative to the graph, which matters because a three-firm cartel in a large market is exactly that case.

Method	What it finds	The cartel shape it maps to
Connected components	Groups with no edges at all to the outside	Market sharing — firms that never compete across a boundary. Also just separate geographic markets, which is why this one needs context
Clique detection	Groups where every member is connected to every other	A closed bidding ring. The purest signal, and rare in raw form
k-core decomposition	The subgraph where every node has at least k connections within it. Peels the periphery away	Excellent first pass — it strips out the one-off bidders and leaves the persistent core. Cheap and interpretable
Louvain / Leiden modularity	Partitions maximising internal against expected edges	Sector or regional structure usually dominates, so this finds markets before it finds cartels. Useful as the thing you must control for
Structural holes / brokerage	Nodes bridging otherwise unconnected groups	Hub-and-spoke coordination, and the natural companion to betweenness

4. How you would actually do it, start to finish

The pipeline, with the decision points marked

  STEP 1 - GET THE RIGHT DATA SHAPE
  ==================================================
   procurement records are BIPARTITE:
     firms  <----bid on---->  tenders

   tender_id | firm_id | bid_amount | date
   ----------+---------+------------+--------
     T001    | Acme    | 1,200,000  | 2019-03
     T001    | Borex   | 1,245,000  | 2019-03
     T001    | Civic   | 1,260,000  | 2019-03
     T002    | Acme    |   890,000  | 2019-06
     ...

  STEP 2 - PROJECT TO A FIRM-FIRM GRAPH
  ==================================================
   two firms get an edge if they appeared on the
   same tender. weight = how many times.

     Acme --47-- Borex
     Acme --43-- Civic
     Borex --45-- Civic

   *** DECISION POINT ***
   What counts as an edge? co-bid once? five times?
   Within what time window? Same lot or same tender?
   EVERY ANSWER GIVES A DIFFERENT GRAPH.
   This choice is the analysis.

  STEP 3 - PRUNE
  ==================================================
   raw projections are nearly complete graphs and
   tell you nothing. Options:
     . weight threshold (edge only if co-bid >= k)
     . keep statistically significant edges only
       (backbone extraction / disparity filter)
     . k-core to strip the periphery

  STEP 4 - DESCRIBE
  ==================================================
   degree distribution, density, clustering,
   components, then the FOUR centralities --
   and say WHICH and WHY

  STEP 5 - COMPARE AGAINST A NULL MODEL   <-- the
  ==================================================      step
   generate many random graphs with the SAME degree       most
   sequence (configuration model). Ask:                    people
     is this cluster denser than chance?                    skip
     is this firm's betweenness higher than chance?

   WITHOUT THIS YOU HAVE NOTHING. Dense clusters
   appear in random graphs too.

  STEP 6 - CONTROL FOR THE OBVIOUS CONFOUNDERS
  ==================================================
   firms in the same sector and region co-bid for
   innocent reasons. Compare WITHIN sector-region
   strata, or model sector and region explicitly.

  STEP 7 - TRIANGULATE
  ==================================================
   network signal + price screens (bid dispersion,
   margin, rotation) + Benford on submitted figures.
   One signal is a hypothesis. Three agreeing is a
   lead.


  TOOLS: networkx (Python, readable, slower),
         igraph (faster, scales better),
         Gephi (visualisation only).

Steps 5 and 6 are what separate analysis from storytelling. Any real network has dense clusters and high-betweenness nodes; the question is whether it has *more* than a random graph with the same degrees would. Without a null model and without controlling for sector and geography, every finding is unfalsifiable.

What a bid-rotation ring actually looks like, numerically

Four firms repeatedly appear on the same tenders, and the winner rotates. In the network: density within the group near 1 — every pair connected. Clustering coefficient near 1 for each member. Very few edges leaving the group — they rarely co-bid with outsiders. In the auxiliary data: the winner changes in sequence while the losing bids cluster just above the winning one, and the margin between first and second is unusually tight and unusually *stable*. Compare a competitive market: similar density is possible, but the winner does not rotate, the margin varies, and the group has many external edges. The network finds the candidate group; the price pattern distinguishes rotation from ordinary rivalry. Neither alone is sufficient, and saying that is the answer.

5. The trap that invalidates most of this — and three others

THE one to know: bipartite projection manufactures cliques

This is subtle, it is fatal, and almost nobody mentions it. When you project firms-and-tenders down to a firm-to-firm graph, every tender with five bidders becomes a five-way clique by construction — all ten pairs get an edge because they appeared together. So the projected graph has high clustering automatically, as an artefact of the projection, not as a property of the firms. A single large tender can create a dense cluster out of nine firms that have no relationship whatsoever. Consequence: you cannot interpret clustering coefficient or density on a projected graph at face value. The fixes are to compare against a bipartite null model that preserves both degree sequences, to weight edges by something that penalises large tenders, or to analyse the bipartite graph directly without projecting. If you say one technical thing about network analysis, say this — it demonstrates you have thought about the method rather than read a list of metrics.

Trap	Why it bites	What to do
Co-bidding is not collusion	Firms in the same sector, size class and region co-bid constantly for entirely innocent reasons. The base rate of co-bidding among genuine competitors is very high	Compare within sector-and-region strata, or include them in a model. An unconditional co-bidding network mostly recovers market structure, not conspiracy
The edge definition is the finding	Co-bid once, or five times? Within a year, or ever? Per lot or per tender? Each choice yields a different graph and a different set of suspicious firms	State the definition, and report how the conclusion changes under alternatives. That sensitivity analysis is the same move as the market-definition point in the economic law chapter
Missing data distorts structure far more than it distorts averages	A firm absent from the data looks like a firm with no relationships. In a network, a missing node can create an apparent structural hole or break a real cluster — the error is not random noise, it changes topology	Know the coverage of your source. Procurement data below threshold values is often simply not published, which systematically removes small firms
Guilt by association	A relational model scores a firm partly on who it is connected to, so a firm with no suspicious conduct of its own can be flagged by its neighbourhood	This is Wisman's objection and it is the right one. It is close to what the UN Special Rapporteur criticised about SyRI — targeting by neighbourhood without individual suspicion. And the counterfactual explanation breaks: had your turnover been lower is actionable; had your competitors been differently connected to each other is not

6. Computational thinking — the habit underneath all of it

The phrase gets used loosely. It has a conventional four-part definition, and then a version adapted to what you would actually be doing — which is more useful.

The standard four	What it means	On a cartel screen
Decomposition	Break a problem into parts you can solve separately	Detect bid rigging becomes: assemble the data, define a relationship, find candidate groups, test against chance, control confounders, triangulate with prices
Pattern recognition	Notice that this problem has the shape of one you already know	Rotation is a sequence problem. Co-bidding is a graph problem. Bid spread is a distribution problem. Recognising which shape determines the tool
Abstraction	Strip away what does not matter and keep the structure	A tender is not a legal document here — it is a set of firms and a vector of numbers. And knowing what you threw away is part of the abstraction
Algorithmic design	Specify steps precise enough that they could be executed without judgment	The seven-step pipeline above. *If a step requires you to look at it and decide, it is not yet specified*

And the four questions that are the version worth having

This is the one to say if asked what computational thinking means to you, because it is specific to enforcement rather than generic. One: what shape is this question? A label per document, a label per token, a relationship across documents, a number over time. The shape picks the tool, and most failures are a tool applied to the wrong shape. Two: what shape is the data, really? Procurement data is bipartite, not a table. Police records are reports, not offences. Convictions are detections, not occurrences. Three: what would this look like if nothing were going on? The null model. If you cannot say what chance alone would produce, you cannot claim to have found anything. Four: what would change my mind? If no answer exists, the finding is unfalsifiable and should not be put in a decision. Those four, in order, every time.

7. How this connects to ATLANTIS, and what is unexplored

Project	The question	Method
A null model for enforcement networks	Agencies run co-bidding analyses. Against what baseline? If dense clusters appear in random graphs with the same degree sequence, a cluster is not evidence	Build the bipartite configuration-model null for real procurement data, and report how many apparently suspicious clusters survive it. Cheap, and it would either validate or undermine a technique already in use
The projection artefact, quantified	How much of the clustering in agency co-bidding graphs is manufactured by bipartite projection rather than present in the relationships?	Compare clustering in projected graphs against the bipartite original across tender-size distributions. A purely methodological finding with direct enforcement consequences
Relational evidence and the rights of defence	A firm flagged because of its neighbourhood cannot act on that in the way it could act on its own attributes. Is a relational flag contestable at all?	Doctrinal, paired with a demonstration: show that a counterfactual explanation for a relational model is either unavailable or not actionable by the firm. This is Wisman's objection turned into a paper

8. If you remember ten things

Network analysis is descriptive statistics on a relational structure — no training, no labels. A graph *neural* network is the ML version and a different thing. Agencies use the first.
Four centralities, four questions. Degree: who is busiest. Betweenness: who is a broker — this finds the hub. Closeness: who can coordinate. Eigenvector: who is connected to the well-connected.
**Saying *we ran a centrality analysis* is not a method.** Saying which measure and why is.
Procurement data is bipartite — firms and tenders — not a table.
Bipartite projection manufactures cliques. A five-bidder tender becomes a five-way clique by construction, so clustering in a projected graph is partly an artefact. This is the one technical point to make.
Modularity subtracts what chance would produce, holding degrees fixed. Q above roughly 0.3 suggests real structure. Louvain and Leiden find it; both have a resolution limit that can hide small cartels.
Without a null model you have nothing. Dense clusters and high-betweenness nodes occur in random graphs too. Configuration model, degree-preserving.
Co-bidding is not collusion. Same sector and region co-bid innocently and constantly. Control for it or you recover market structure, not conspiracy.
The edge definition is the finding. State it, and report how conclusions change under alternatives.
Computational thinking, your version: what shape is the question, what shape is the data really, what would this look like if nothing were going on, and what would change my mind. All four come from your own papers.