Connection or Coincidence? Analytical Null Models for Co-occurrence in Bipartite Multigraphs

Abstract

Wenn zwei Personen dieselben Orte besuchen, zwei Spezies an denselben Standorten vorkommen oder zwei Länder dieselben Produkte exportieren – ist das ein Hinweis auf eine Verbindung oder bloßer Zufall? Diese Frage stellt sich, wann immer Forschende Netzwerke aus Daten ableiten, die erfassen, wie Entitäten einer Art (Agents) mit solchen einer anderen (Items) verknüpft sind; zwei Agents werden im projizierten Netzwerk verbunden, wenn sie mehr Items gemeinsam haben als zufällig zu erwarten wäre. Um echte von zufälliger Überlappung zu unterscheiden, braucht es ein statistisches Nullmodell für die durch Zufall erwartete Überlappung. Bestehende Nullmodelle beruhen auf impliziten Annahmen darüber, was als Zufall gilt, und erfassen nur, ob ein Agent mit einem Item verknüpft ist, nicht wie oft: Eine Person, die einen Ort fünfzigmal besucht, zählt gleich viel wie eine, die ihn einmal besucht.Wir adressieren dies, indem wir eine Familie analytisch handhabbarer Nullmodelle ableiten, die diese Annahmen explizit machen. Jede Verknüpfung eines Agents mit einem Item wird als zählbares Ereignis modelliert – ein Ball in einem Korb – wodurch erhalten bleibt, wie oft sie vorkommt. Da Verknüpfungen nun wiederholt vorkommen können, hat jeder Agent sowohl eine Gesamtzahl als auch eine Anzahl verschiedener Items. Wir zeigen, dass bei gleicher Popularität aller Items allein die Anzahl verschiedener Items, mit denen ein Agent verknüpft ist, die Verteilung der Überlappung bestimmt: die klassische hypergeometrische Verteilung, die bestehende Methoden postulieren, die hier aber aus einem With-Replacement-Prozess formal hergeleitet wird. Dieses Ergebnis gilt für jeden solchen Prozess, in dem Items ähnlicher Popularität austauschbar sind – eine Eigenschaft, die wir als Mechanismus-Agnostizität bezeichnen. Die Gruppierung von Items in Popularitätsstrata stellt diese Austauschbarkeit innerhalb jeder Gruppe sicher; die Kombination der Verteilungen pro Stratum ergibt einen einzelnen Test pro Paar. Das resultierende Modell, strat_d, benötigt nur Mikrosekunden pro Paar. Die Gruppierung bestimmt, was der Test als Hintergrund behandelt: Eine Stratifizierung nach Popularität absorbiert globale Popularitätseffekte; eine weitere kontextuelle Aufteilung kann zusätzliche Störfaktoren absorbieren. Da das Nullmodell berücksichtigt, wie oft Verknüpfungen auftreten, lässt es sich auch auf Tests erweitern, die prüfen, ob Agents wiederholt mit denselben Items verknüpft sind. Wir evaluieren die gesamte Familie an synthetischen und realen Daten hinsichtlich Kalibrierung und Detektionsstärke. In synthetischen Experimenten ist strat_d das einzige Modell der Familie, das über alle getesteten datengenerierenden Prozesse kalibriert bleibt. Auf fünf realen Datensätzen mit unabhängig beobachteten Ground-Truth-Beziehungen erzielt unser Ansatz auf jedem Datensatz das beste Ranking wahrer Verbindungen, wobei das beste Modell der Familie je nach Datensatz variiert. Unter strenger Multiple-Testing-Korrektur wird etwa jede fünfte bestätigte Verbindung, die unser Ansatz identifiziert, von keiner getesteten Alternative detektiert.

When two people visit the same places, two species occur at the same sites, or two countries export the same products, is that co-occurrence a sign of a meaningful connection or just a coincidence? This question arises whenever researchers infer networks from data recording how entities of one kind (agents) interact with those of another (items); a connection in the projected network is drawn whenever two agents share more items than expected by chance. Telling real from chance overlap requires a statistical null model: a baseline for the overlap expected by chance alone. Existing models carry implicit assumptions about what counts as coincidence and reduce each interaction to present or absent, discarding its frequency or intensity: a person who visits a place fifty times counts the same as one who visits once.We address this by deriving a family of analytically tractable null models in which each interaction with an item is a countable event, a ball placed into a bin, preserving how often each interaction occurs. Because interactions can repeat, each agent has both a total interaction count and a count of distinct items. We show that when all items are equally popular, only the number of distinct items an agent interacts with determines the overlap distribution, which is the classical hypergeometric, the distribution that existing methods postulate but that here is derived from a with-replacement process. This holds for any such process in which items of similar popularity are interchangeable, a property we call mechanism-agnosticity. Grouping items into popularity strata ensures this interchangeability within each group; combining the per-stratum distributions yields a single test per pair. The resulting model, strat_d, needs only microseconds per pair. The grouping defines what the test treats as background: stratifying by popularity absorbs global popularity effects; further partitioning by shared context can absorb additional confounders. Because the null model accounts for interaction frequencies, it also extends to testing whether agents interact with shared items repeatedly. We evaluate each model in the family on synthetic and real-world data, testing calibration, detection power, and the effect of each design choice. In synthetic stress tests probing realistic violations of model assumptions, strat_d is the only model in the family that remains calibrated across all tested scenarios. On five real-world datasets with independently observed ground-truth relationships, our approach ranks true connections highest on every dataset; the best-performing model in the family varies with the data. Under strict multiple-testing correction, roughly one in five of the connections our approach identifies are not recovered by any tested alternative.