Building Claim-Provider Graphs with NetworkX

This page is a focused implementation guide under Entity Network Analysis for Organized Claims Fraud: it builds a bipartite claim-to-provider graph in networkx, projects it onto the provider layer, and computes the degree, betweenness, and connected-component features that surface provider rings — then persists a flagged subgraph with the audit context an investigator needs.

A provider ring shares customers. A body shop, a diagnostic clinic, and a tow operator that collude route the same small pool of claimants between them, so on the provider layer they form a tightly interconnected cluster, while an honest provider connects to its claimants and almost no other provider. The relationship you want to reason about — provider-to-provider — is not in the data directly; the data has claims that each reference a provider. The connection between two providers is implicit in the claimants (or claims) they share, and extracting it is a graph projection.

Doing this naively fails in specific ways. Building a single flat graph and asking “which providers are connected” conflates the two node types and produces meaningless adjacency. Iterating every provider pair to count shared claims is O(providers²) and does not scale past a few thousand nodes. And computing centrality on the raw bipartite graph answers the wrong question — the high-degree nodes are just the busiest providers, not the collusive ones. The correct construction is a typed bipartite graph, a weighted projection onto the provider layer where an edge weight is the count of shared claims, and centrality and connected-component analysis on that projection. This guide builds exactly that.

This pattern targets Python 3.10+ and uses networkx for the graph model, its bipartite projection helpers, and the centrality algorithms, with structlog for the audit line. It assumes claim records already carry resolved provider identifiers, as described in the parent entity network analysis guide. Pin the library so algorithm behaviour is stable:

Copy
python -m venv .venv && source .venv/bin/activate
pip install "networkx==3.*" "structlog==24.*"

Add claim nodes and provider nodes with a bipartite attribute marking each side, and connect a claim to every provider it references. Namespacing the ids by type prevents a claim and a provider from colliding on a shared raw value, and the bipartite attribute is what the projection helper uses to know which layer to keep.

Copy
from __future__ import annotations

from dataclasses import dataclass

import networkx as nx
import structlog
from networkx.algorithms import bipartite

log = structlog.get_logger("fraud.graph.provider")


class GraphBuildError(Exception):
    """Raised when a claim record cannot be placed into the bipartite graph."""


@dataclass(frozen=True, slots=True)
class ClaimProviderLink:
    claim_id: str
    provider_ids: tuple[str, ...]


def build_bipartite(links: list[ClaimProviderLink]) -> nx.Graph:
    """Claims on bipartite layer 0, providers on layer 1; edge = 'claim used provider'."""
    g = nx.Graph()
    for link in links:
        if not link.claim_id:
            raise GraphBuildError("empty claim_id")
        claim = f"claim:{link.claim_id}"
        g.add_node(claim, bipartite=0, ntype="claim")
        for pid in link.provider_ids:
            if not pid:
                raise GraphBuildError(f"empty provider id on claim {link.claim_id}")
            provider = f"provider:{pid}"
            g.add_node(provider, bipartite=1, ntype="provider")
            g.add_edge(claim, provider)
    log.info("bipartite.built", claims=sum(1 for _, d in g.nodes(data=True)
             if d["bipartite"] == 0), providers=sum(1 for _, d in g.nodes(data=True)
             if d["bipartite"] == 1))
    return g

Project the bipartite graph onto its provider nodes. networkx’s weighted_projected_graph produces exactly the graph we want: one edge between two providers that share at least one claim, weighted by the number of shared claims. That weight is the collusion signal — two providers sharing many claimants is the suspicious pattern.

Copy
def project_providers(g: nx.Graph) -> nx.Graph:
    """Collapse to provider-provider edges weighted by shared-claim count."""
    providers = {n for n, d in g.nodes(data=True) if d["bipartite"] == 1}
    if not providers:
        raise GraphBuildError("no provider nodes to project")
    projected = bipartite.weighted_projected_graph(g, providers)
    log.info("bipartite.projected", provider_nodes=projected.number_of_nodes(),
             provider_edges=projected.number_of_edges())
    return projected

Run degree and betweenness centrality on the projection to find broker providers, then break the projection into connected components and score each by internal density and the total shared-claim weight. A small, dense, heavily-weighted component of providers is a candidate ring.

Copy
from dataclasses import field


@dataclass(frozen=True, slots=True)
class ProviderRing:
    providers: tuple[str, ...]
    size: int
    density: float
    total_shared_weight: int
    top_broker: str | None
    broker_betweenness: float


def flag_provider_rings(
    projected: nx.Graph, *, min_size: int, density_threshold: float
) -> list[ProviderRing]:
    """Return connected components dense enough to be candidate provider rings."""
    rings: list[ProviderRing] = []
    for component in nx.connected_components(projected):
        if len(component) < min_size:
            continue
        sub = projected.subgraph(component)
        density = round(nx.density(sub), 4)
        if density < density_threshold:
            continue
        weight = sum(d["weight"] for _, _, d in sub.edges(data=True))
        bc = nx.betweenness_centrality(sub) if sub.number_of_nodes() > 2 else {}
        broker, broker_bc = (max(bc.items(), key=lambda kv: kv[1]) if bc else (None, 0.0))
        ring = ProviderRing(
            providers=tuple(sorted(component)),
            size=len(component),
            density=density,
            total_shared_weight=weight,
            top_broker=broker,
            broker_betweenness=round(broker_bc, 4),
        )
        log.info("provider.ring_flagged", size=ring.size, density=density,
                 total_shared_weight=weight, top_broker=broker)
        rings.append(ring)
    return rings

The tests pin the two properties that matter: the projection weight equals the shared-claim count, and a colluding cluster is flagged while an isolated legitimate provider is not.

Copy
def test_projection_weight_is_shared_claim_count() -> None:
    links = [
        ClaimProviderLink("K1", ("PA", "PB")),   # PA & PB share K1
        ClaimProviderLink("K2", ("PA", "PB")),   # ...and K2  → weight 2
        ClaimProviderLink("K3", ("PA", "PC")),   # PA & PC share K3 → weight 1
    ]
    proj = project_providers(build_bipartite(links))
    assert proj["provider:PA"]["provider:PB"]["weight"] == 2
    assert proj["provider:PA"]["provider:PC"]["weight"] == 1


def test_dense_cluster_flags_isolated_provider_does_not() -> None:
    ring = [ClaimProviderLink(f"K{i}", ("PA", "PB", "PC")) for i in range(5)]
    honest = [ClaimProviderLink("H1", ("PZ",))]      # unconnected provider
    proj = project_providers(build_bipartite(ring + honest))
    flagged = flag_provider_rings(proj, min_size=3, density_threshold=0.6)
    assert len(flagged) == 1
    assert set(flagged[0].providers) == {"provider:PA", "provider:PB", "provider:PC"}
    assert flagged[0].density == 1.0                 # complete triangle
    assert flagged[0].total_shared_weight == 15      # three pairs × 5 shared claims

Run the suite with python -m pytest -q. The projection weight is an exact integer count, so the assertions have no tolerance band — the flag is fully reproducible from the recorded graph.

A flagged provider ring can trigger an investigation and, ultimately, adverse action against a provider, so the flag must be reconstructable. Persist the ProviderRing together with the underlying subgraph — the provider nodes, the weighted edges, and the specific claim ids that produced each shared-claim weight — plus the graph snapshot id and rule version, to the append-only trail specified in the audit log schema design guide. That record is what lets an investigator open the exact set of claims linking two providers before anyone acts on the flag, and what answers a regulator asking how a provider came to be referred. A bare flagged=true is indefensible; the persisted weighted subgraph, showing which claimants moved between the providers, is the evidence.

• Projection produces a near-complete graph. Symptom: almost every provider pair has an edge, so components are useless. Cause: a shared aggregator or clearinghouse id was modelled as a provider, connecting everyone. Fix: exclude clearinghouse and aggregator node types before projecting, or raise the density threshold and require a minimum edge weight.
• Legitimate high-volume provider dominates betweenness. Symptom: the busiest honest shop is always the top broker. Cause: raw betweenness rewards degree. Fix: interpret betweenness only within a component that already cleared the density and shared-weight thresholds, not across the whole projection.
• A real ring falls below minimum size. Symptom: a known collusive pair is never flagged. Cause: min_size set too high for two-provider rings. Fix: lower min_size to the smallest ring worth reviewing and lean on the shared-weight and density signals to control false positives.
• Weights are all 1. Symptom: no pair ever looks suspicious. Cause: projected_graph used instead of weighted_projected_graph, dropping the shared-claim count. Fix: use the weighted projection so the edge weight carries the shared-claim signal.
• Components differ between runs. Symptom: the same snapshot flags different providers. Cause: iteration order fed into a nondeterministic step. Fix: sort provider ids into stable tuples (as the code does) and pin the networkx version so a rebuild reproduces identical components.

• Entity Network Analysis for Organized Claims Fraud — the parent guide this construction feeds
• Duplicate Claim Detection at Ingestion Scale — where shared-claimant edges originate upstream
• Statistical Anomaly Scoring — consumes provider-ring features as fraud-score inputs
• Audit Log Schema Design — the append-only trail flagged subgraphs are persisted into
• SIU Referral Orchestration — where a flagged provider ring is escalated to investigators