Source-linked AI summary
Community detection for interaction networks
Harry Crane, Walter Dempsey
TL;DR
Thresholding interaction counts can make community detection depend on the chosen cutoff, complicating analysis of network data. The paper fits the original interaction data with statistical methods and introduces a hidden Markov model for time-varying communities. Its methods outperform prevailing approaches in the examples, while weighted Newman–Girvan modularity can remain inconclusive when multiple local optima occur.
Problem
Researchers often threshold interaction counts into networks, but Newman–Girvan modularity can depend strongly on that cutoff.
Source: §1 · p. 3Method
The paper models original interaction counts directly and introduces a hidden Markov model for temporally varying community structures.
Source: §1 · p. 4, §7 · p. 25Results
Straightforward statistical methods fit to observed data outperform prevailing community-detection methods in the examples.
Source: §1 · p. 4, §2.4 · p. 7Takeaways & Limitations
Threshold choice can undermine modularity-based inference, while interaction counts can be analyzed without projecting them to an unweighted network.
Source: §1 · pp. 3–4For Senate voting, weighted Newman–Girvan modularity has several local optima with the same value and therefore cannot confirm or deny the true clustering.
Source: §6.2 · p. 23
Abstract
from arXiv · showhide
In many applications, it is common practice to obtain a network from interaction counts by thresholding each pairwise count at a prescribed value. Our analysis calls attention to the dependence of certain methods, notably Newman--Girvan modularity, on the choice of threshold. Essentially, the threshold either separates the network into clusters automatically, making the algorithm's job trivial, or erases all structure in the data, rendering clustering impossible. By fitting the original interaction counts as given, we show that minor modifications to classical statistical methods outperform the prevailing approaches for community detection from interaction datasets. We also introduce a new hidden Markov model for inferring community structures that vary over time. We demonstrate each of these features on three real datasets: the karate club dataset, voting data from the U.S.\ Senate (2001--2003), and temporal voting data for the U.S. Supreme Court (1990--2004).
1. Introduction
Community detection compresses complex networks into groups, but inference from observed networks is complicated by uncertainty about how they were sampled. This paper examines threshold sensitivity and models interaction counts directly, showing advantages over network-based methods.
1. Introduction
- Community detection represents complex networks through clusters, reducing O(n^2) interactions to a smaller number of community-level relationships.Vertices within a cluster can be regarded as interchangeable.Source: §1 · p. 2
- Statistical network models should reflect both the network-generating process and the sampling mechanism, which is often insufficiently understood.The paper does not address modeling that sampling mechanism.Source: §1 · p. 2
- Interaction datasets can retain counts, frequencies, and other covariates that are lost when pairwise relationships are reduced to binary indicators.The paper uses karate club interactions and voting data from the U.S. Senate and Supreme Court as examples.Source: §1 · p. 3
- Newman–Girvan modularity is sensitive to the sampling procedure and threshold used to project interaction data into a network.The paper relates this sensitivity to the concern that small network changes can alter community-finding outcomes.Source: §1 · p. 3
- Modeling interaction counts directly lets straightforward statistical methods outperform prevailing network methods across the three examples.A two-parameter Poisson model recovers the karate club structure, while a degree-corrected stochastic blockmodel uses 36 parameters and misclassifies one individual.Source: §1 · pp. 3–4
2. Motivating examples
The examples use karate club interactions, Senate voting alignments, and Supreme Court decisions to illustrate community detection from interaction data, threshold sensitivity, and clustering that changes over time.
2. Motivating examples
- The motivating examples comprise karate club interactions, 107th U.S. Senate voting, and U.S. Supreme Court decisions from 1990–2004.The Court data illustrate temporal clustering, while the Senate data are introduced here for network analysis.Source: §2 · p. 4, §2.2 · p. 5
2.1. Karate club dataset
- The karate club dataset records interaction counts among 34 members and is a canonical community-detection example because its two-group split is well understood.Its unweighted network connects pairs with positive interaction counts.Source: §2.1 · pp. 4–5
2.2. Senate dataset
- Senate voting alignments can be summarized as pairwise counts of agreements and shared votes, but Newman–Girvan modularity is sensitive to the agreement-proportion cutoff.Every pair of senators agreed at least once during the 107th Senate term, leaving many possible cutoff choices.Source: §2.2 · p. 5
2.3. Supreme Court dataset
- A hidden Markov chain on partitions models Supreme Court community dynamics despite changes in Court membership over the study period.The analysis uses the 1990–2004 voting data to illustrate temporally varying clusters.Source: §2.3 · p. 6
2.4. Summary of analysis
- Straightforward modifications of classical statistical methods fit to observed data outperform the methods of Bickel and Chen and Karrer and Newman.The analysis also introduces partition-valued Markov-chain developments for detecting changes in clustering over time.Source: §2.4 · pp. 6–7
3. Interaction data
The paper treats repeated pairwise interactions as data in their own right and defines how those data can be projected into a network. It argues that threshold choices can distort inference, while simple models fitted to the observed data preserve more information.
3. Interaction data
- Interaction arrays record repeated pairwise measurements, and the paper favors simple models when they make sense for the application.Interactions may represent counts of one type or multiple types, such as agreement and disagreement.Source: §3 · pp. 7–8, §3.1 · p. 8
3.1. General setup
- The general setup represents sampled individuals as partitioned into non-overlapping classes and records their pairwise interaction strengths in an array.The array can contain counts for one interaction type or information about multiple types.Source: §3.1 · p. 8
- A projected network is a binary adjacency array formed by applying a thresholding function to the interaction data.The cutoff determines whether a pair becomes an edge; for Senate and Supreme Court data, agreement proportion is a natural thresholding quantity.Source: §3.1 · p. 8
3.2. Interpreting the data
- Thresholding is common, but choosing a cutoff after examining the data can affect inference and make modularity-based clustering fragile.In the karate club example, Newman–Girvan modularity misclassifies one individual at cutoff 0 but gives the correct clustering at cutoff 1; Senate cutoffs can either separate clusters automatically or erase structure.Source: §3.2 · p. 9
4. Modeling the interaction array
The section models the full interaction array rather than projecting counts to a binary network, adapting block models to count, typed, and temporal interaction data.
4.1. Interaction count data
- Independent Poisson counts with block-dependent intensities model interaction-count data directly, and the paper calls this the Poisson stochastic blockmodel.The model can be simplified by assigning one intensity to within-cluster pairs and another to between-cluster pairs, a choice motivated by expected similarity and avoidance of overfitting.Source: §4.1 · pp. 10–11
- A two-parameter Poisson stochastic blockmodel fitted to karate-club interaction counts recovers the correct clustering, unlike approaches that misclassify one individual.The model specifies a shared intensity for within-cluster interactions and another for between-cluster interactions.Source: §4.1 · pp. 10–11
4.2. Interactions with types
- For typed interactions, the Binomial stochastic blockmodel assigns agreement probabilities by block pair, with within- and between-cluster probabilities reflecting prior understanding of the application.The data pair each dyad’s interaction count with the number of agreements; non-interactions are assumed random and independent of observed interactions.Source: §4.2 · pp. 11–12
4.3. Temporal network clustering
- For Supreme Court voting across 1990–2004, the model combines each term’s Binomial blockmodel with a Markov chain over justice partitions.The chain’s sampling consistency allows modeling membership changes over time, while its exchangeability and reversibility support label invariance and analysis in either time direction.Source: §4.3 · pp. 12–14
- The temporal model seeks cluster changes that are smooth with respect to short-term irregularities, using the Ewens cut-and-paste chain with a maximum cluster count.The chain’s parameters include α > 0 and k ≥ 2, where k bounds the number of clusters in each partition.Source: §4.3 · pp. 12–13
5. Cluster analysis
The section searches over partitions to optimize clustering objectives, using bounded-partition randomized search and alternating global and local moves.
5. Cluster analysis
- For temporal clustering, the estimated partition sequence is built sequentially by taking posterior modes using the current partition as the next-state prior.The initial prior uses k = 2 and α = 1; sensitivity analysis reports robust estimates to that α choice.Source: §5 · pp. 14–15
5.1. Randomized search algorithms
- For moderate or large samples, randomized search optimizes the clustering objective over partitions bounded by a maximum cluster count, while modularity uses label switching.The maximum k is only an upper bound, so the search does not require exactly k clusters.Source: §5.1 · p. 15
5.2. Global search: cut-and-paste algorithm
- The cut-and-paste global chain gives every transition in the search space positive probability and converges to its stationary distribution in O(log n) steps (Crane and Lalley, 2013).Its transitions are used to make global moves across partitions.Source: §5.2 · p. 16
5.3. Local search: cocktail algorithm
- The search alternates accepted global moves with Metropolis–Hastings local cocktail moves, and quickly finds the right answer among 6.3 × 10^29 Senate partitions on a laptop.The example searches partitions of 100 senators into at most two blocks from a randomly chosen starting state.Source: §5.3 · p. 17
6. Applications
Across the three applications, models fitted to interaction data recover community structure, while projected-network results depend on the cutoff. The temporal model also recovers a reported shift in Supreme Court clustering using interaction arrays alone.
6.1. Karate club
- The two-parameter Poisson stochastic blockmodel recovers the karate club’s known split, while the degree-corrected model uses 36 parameters and still misclassifies one member.The correct clustering has log-likelihood −348.26, compared with −349.81 for the clustering found by the degree-corrected model and Newman–Girvan modularity.Source: §6.1 · pp. 17, 19
6.1.1. Fitting the projected network
- On the karate club projection, Newman–Girvan misclassifies one member at cutoff c = 0 but recovers the correct clustering at c = 1.The member’s single interaction with a hub in one faction and two with a hub in the other collapse to one edge at c = 0; thresholding at c = 1 removes the former tie.Source: §6.1.1 · pp. 19–20
6.2. Senate voting
- The Binomial stochastic blockmodel recovers Crane’s Senate clustering, including Zell Miller and Jim Jeffords in clusters opposite their parties.The inferred departures are consistent with the passage’s descriptions of Miller’s support for President Bush and Jeffords’s later party switch.Source: §6.2 · p. 22
- Newman–Girvan recovers the Senate clusters only for cutoffs between the 45th and 55th percentiles; outside that range, cutoff choices can leave structure erased or vertices isolated.The 30th-percentile projection obscures much of the structure, while the 70th-percentile projection isolates some vertices; at the 50th percentile, the clusters separate clearly.Source: §6.2 · p. 22, Figure 3 · p. 23
6.3. Temporal clustering in the Supreme Court
- The temporal hidden Markov model handles changing Court membership and infers the reported shift in David Souter’s cluster affiliation using interaction arrays alone.The independently fitted Newman–Girvan cutoff windows move substantially across terms, with no single threshold yielding the correct clustering for every term.Source: §6.3 · p. 24
7. Concluding remarks
The authors conclude that straightforward modifications of classical methods perform as well as prevailing approaches for interaction data, while a temporal Binomial blockmodel detects Souter’s ideological shift. Newman–Girvan modularity cannot adequately handle changing clusters, and no single cutoff recovers the latent clusters across all years.
7. Concluding remarks
- The Binomial blockmodel detects Souter’s shift between the 1992 and 1993 terms, whereas no single cutoff recovers the latent clusters across all years.The authors also conclude that Newman–Girvan modularity cannot adequately handle temporal variation in the underlying clustering.Source: §7 · pp. 24–25, Table 2 · p. 25
- Straightforward modifications of standard statistical methods perform just as well as prevailing clustering algorithms and blockmodel approaches for interaction datasets.The authors caution that Newman–Girvan modularity behaves precariously depending on how interaction counts are sampled.Source: §7 · p. 26
- The authors call for greater attention to sampling in network inference, an issue they say is largely ignored in the methodology literature.They frame this as a reason to consider how network data are sampled from interaction counts.Source: §7 · p. 26