Community-Size Biases in Statistical Inference of Communities in Temporal Networks

Technical Summary: Community-Size Biases in Statistical Inference of Communities in Temporal Networks

Problem Statement
In the analysis of temporal networks, researchers frequently employ statistical inference to detect the evolution of communities—sets of densely connected nodes. A critical, yet often overlooked, issue in this domain is the bias inherent in the generative models used to assign community memberships over time. The authors identify that standard approaches, which rely on either a uniform distribution over community assignments or discrete-time Markov processes, systematically bias the inference against communities with very large or very small numbers of nodes. Specifically, these models tend to produce community-size distributions that become increasingly "localized" (concentrated around moderate sizes) as the temporal network evolves. Consequently, statistical-inference methods utilizing these generative models perform poorly when attempting to identify communities that deviate significantly from the average size, a common feature in real-world temporal networks.

Methodology
The paper investigates this phenomenon by representing temporal networks as multilayer networks, where each layer corresponds to a discrete time step. The authors analyze the performance of three distinct classes of generative models for community assignments ($P(g)$):

1. Uniform Distribution: Assigns community labels independently and uniformly at random for each node-layer.
2. Discrete-Time Markov Processes: Models the evolution of community assignments where a node's label at time $\ell$ depends probabilistically on its label at time $\ell-1$. The authors specifically examine and implement priors from Yang et al. [65] and Bazzi et al. [4], which utilize transition kernels and laziness parameters.
3. Layerwise-Exchangeable Count-Splitting (LECS) Prior: A novel approach proposed by the authors. Instead of updating each node individually based on its previous state, the LECS prior updates the counts of nodes within communities. It treats nodes within a community as indistinguishable (exchangeable) and employs a two-stage process:
   • Geometric Retention: The number of nodes remaining in a community is drawn from a truncated geometric distribution.
   • Microcanonical Labeling: The remaining "mover" nodes are reassigned to other communities by uniformly sampling a weak composition of the remaining nodes, followed by uniform assignment of labels.

To evaluate these models, the authors utilize a Bayesian framework to sample from the posterior distribution $P(g|A)$ using Gibbs sampling augmented with multilayer label swaps to escape local extrema. They quantify the "localization" of community-size distributions using the Inverse Participation Ratio (IPR), where a higher IPR indicates a more localized (biased) distribution.

Key Contributions

• Identification of Bias: The authors demonstrate that both uniform distributions and standard discrete-time Markov processes lead to community-size distributions that become increasingly localized over time. This localization implies a low probability of generating or correctly inferring very small or very large communities in later time steps.
• Novel Generative Model (LECS): They introduce the Layerwise-Exchangeable Count-Splitting (LECS) prior. By updating community assignments based on the aggregate counts of the previous layer rather than individual node transitions, this model mitigates the accumulation of localization bias.
• Theoretical Guarantees: The paper provides theoretical results (Theorem 4.1 and Corollary 4.2) proving that, in the limit of infinitely many layers, the LECS prior with a fixed retention probability yields a stationary distribution that is substantially less localized than Markov-process models, particularly for community sizes that are not extreme.
• Algorithmic Implementation: The authors detail the posterior sampling algorithms required for these models, including the derivation of closed-form expressions for the LECS prior's transition probabilities and the implementation of multilayer swaps to handle label equivariance issues in temporal SBMs.

Results
Through empirical experiments on synthetic networks with $N=50$ nodes and $L=5$ layers, the authors report:

• Localization Metrics: The IPR values for the LECS prior remain significantly lower and more stable across layers compared to the Yang et al. and Bazzi et al. Markov-process models, whose IPR values increase over time. The uniform distribution exhibits the highest localization.
• Detection Performance: In networks with known community structures of varying sizes ($q \in \{50, 60, 70, 80, 90\}$ out of 100 nodes), the LECS-prior-based approach outperforms the Markov-process approaches (Yang et al. and Bazzi et al.) in detecting large communities (e.g., $q=70, 80, 90$). While the Bazzi et al. approach performs slightly better for moderate sizes ($q=50, 60$), the LECS approach demonstrates superior robustness for large communities.
• Multilayer Swaps: The inclusion of multilayer label swaps in the sampling algorithm significantly improves the performance of both the LECS and Bazzi et al. approaches, preventing the sampler from getting stuck in local extrema caused by label misalignment across layers.

Significance and Claims
The paper claims that the choice of generative model for community assignments is a primary determinant of the accuracy of statistical inference in temporal networks, particularly regarding community size. The authors argue that existing methods relying on Markov processes or uniform priors are fundamentally biased against detecting communities with disparate sizes. By introducing the LECS prior, they provide a generative model that "greatly mitigates the bias against large and small communities," making it a more suitable tool for studying temporal networks where community sizes vary significantly. The authors conclude that their approach is beneficial for studying community structure in networks with large or small communities and suggest that similar group-size biases may affect the detection of other mesoscale structures, such as core–periphery patterns.