PaperlayerView exact revision on arXiv

Source-linked AI summary

How Many Communities Are There?

Diego Franco Saldana, Yi Yu, Yang Feng

arXiv:1412.1684v2stat.MEstat.APstat.COstat.ML

TL;DR

Selecting the number of communities is difficult because common stochastic blockmodel assumptions of conditional edge independence may fail in real networks. The paper proposes composite likelihood BIC (CL-BIC) for this selection problem, reporting stronger model-selection performance than traditional BIC and variational Bayes in its evaluations. In a simulation with within-community correlation ρDec = 0.60, CL-BIC selected correctly in all cases, while BIC succeeded in 14% of 200 trials.

  • Problem

    Community-number selection is challenging because stochastic blockmodels assume conditional independence among edges, an assumption often violated in real applications.

    Source: §1 · pp. 2–3, §3.1 · p. 7

  • Method

    The paper develops composite likelihood BIC (CL-BIC) to select the number of communities while allowing assumed edge independencies to be misspecified.

    Source: §1 · p. 3

  • Results

    At within-community correlation ρDec = 0.60, CL-BIC selected correctly in all cases, while BIC succeeded in 14% of 200 trials.

    Source: §4.1 · p. 16

  • Takeaways & Limitations

    The authors report that CL-BIC outperforms traditional BIC and the variational Bayes criterion in model-selection consistency on simulated and real data.

    Source: §1 · p. 3

    Composite-likelihood estimators may be inconsistent when internal correlation among components of the composite score is too strong.

    Source: §3.2 · p. 9

Abstract

from arXiv · show

Stochastic blockmodels and variants thereof are among the most widely used approaches to community detection for social networks and relational data. A stochastic blockmodel partitions the nodes of a network into disjoint sets, called communities. The approach is inherently related to clustering with mixture models; and raises a similar model selection problem for the number of communities. The Bayesian information criterion (BIC) is a popular solution, however, for stochastic blockmodels, the conditional independence assumption given the communities of the endpoints among different edges is usually violated in practice. In this regard, we propose composite likelihood BIC (CL-BIC) to select the number of communities, and we show it is robust against possible misspecifications in the underlying stochastic blockmodel assumptions. We derive the requisite methodology and illustrate the approach using both simulated and real data. Supplementary materials containing the relevant computer code are available online.

1. INTRODUCTION

Community detection seeks a disjoint partition of network nodes, but choosing the number of communities remains a model-selection problem. The paper proposes CL-BIC to select that number robustly when stochastic blockmodel assumptions are misspecified.

1. INTRODUCTION

  • Community detection is framed as finding a disjoint partition of network nodes into communities, often understood as tightly knit groups with loose connections between them.The paper focuses on undirected networks.Source: §1 · pp. 1–2
  • The number of communities K is often prespecified, and existing selection approaches include BIC-type criteria and variational Bayes methods.The introduction also discusses Bayesian methods for finite but unknown K, including approaches based on allocation sampling and Dirichlet process mixtures.Source: §1 · p. 2
  • CL-BIC is proposed for selecting the number of communities under possible misspecification of stochastic blockmodel assumptions.The authors report better model-selection consistency than traditional BIC and the variational Bayes criterion in simulations and real data.Source: §1 · p. 3
  • The paper motivates CL-BIC by noting that conditional independence among edges given endpoint communities is usually violated in real applications.The introduction describes this as a restrictive assumption of the stochastic blockmodel.Source: §1 · p. 3

2. BACKGROUND

The background introduces network notation and three blockmodel variants, then describes spectral clustering and SCORE as computational approaches for estimating communities. These models differ in their assumptions about node membership and edge probabilities.

2.1.1 Standard Stochastic Blockmodel

  • The standard stochastic blockmodel assigns each node one unknown community and assumes conditionally independent Bernoulli edges whose probabilities depend on endpoint communities.For fixed assignments, its likelihood uses community sizes and edge counts to estimate block probabilities.Source: §2.1.1 · pp. 3–4

2.1.2 Degree-Corrected Stochastic Blockmodel

  • The degree-corrected blockmodel adds individual effects to edge probabilities to represent degree heterogeneity within communities.Its common formulation permits multi-edges and self-edges and uses independent Poisson observations for technical derivations.Source: §2.1.2 · p. 4

2.1.3 Mixed Membership Stochastic Blockmodel

  • The mixed-membership blockmodel allows each node a distribution over communities and uses edge-specific membership indicators for directed interactions.Node-specific vectors encode membership probabilities, while the model’s edge-generation process uses sender and receiver memberships.Source: §2.1.3 · p. 5

2.2 Spectral Clustering and SCORE

  • Spectral clustering uses leading Laplacian eigenvectors followed by K-means, while SCORE clusters ratios of leading adjacency-matrix eigenvectors for the degree-corrected model.The background presents these algorithms as computationally feasible alternatives to directly maximizing the standard blockmodel likelihood.Source: §2.2 · pp. 6–7

3. MODEL SELECTION FOR THE NUMBER OF COMMUNITIES

The section motivates CL-BIC as a way to select community number when conditional edge independence may fail. It adapts composite likelihood to penalize model complexity and develops calculations for several blockmodel variants.

3.1 Motivation

  • CL-BIC is proposed because edges sharing a node may remain dependent even after conditioning on endpoint communities, and it complements existing detection methods to select K.The authors also note potential loss of precision from spectral clustering.Source: §3.1 · p. 7

3.2 Composite Likelihood Inference

  • Composite likelihood compounds first-order marginal log-likelihood contributions; its inference accounts for variance loss under working-independence misspecification, unlike Fisher-information variance.The CLE may be inconsistent when internal correlation among composite-score components is too high.Source: §3.2 · pp. 8–9

3.3 Composite Likelihood BIC

  • CL-BIC selects K by combining composite log-likelihood with a model-complexity penalty, which is larger than BIC’s for dependent relational data.The authors anticipate consistency under limited correlation and regularity conditions, but leave its theoretical study for future work.Source: §3.2 · p. 8, §3.3 · pp. 9–10

3.4.1 Standard Stochastic Blockmodel

  • For the standard stochastic blockmodel, the estimated complexity is k(k + 1)/2, so CL-BIC reduces to traditional BIC.The complexity estimator uses the jackknife covariance matrix.Source: §3.4.1 · p. 11

3.4.2 Degree-Corrected Stochastic Blockmodel

  • For DCBM, the authors derive corresponding CL-BIC results using first- and second-order partial derivatives of the composite log-likelihood.Source: §3.4.2 · p. 12

3.4.3 Mixed Membership Stochastic Blockmodel

  • For MMB, estimated model complexity uses second-order derivatives with respect to θ and α and a jackknife covariance estimator.The authors also state that CL-BIC can be used with latent-space cluster and local-dependence models, leaving details for future work.Source: §3.4.3 · pp. 12–13

4. EXPERIMENTS

The experiments compare CL-BIC with BIC and variational Bayes in correlation-contaminated simulations, then apply the criteria to international trade and school friendship networks.

4.1 Simulations

  • The simulations vary edge dependence and network settings, compare selection criteria over 200 generated adjacency matrices, and use spectral clustering or SCORE to obtain labels.The simulations include standard and degree-corrected blockmodels with imposed correlation among edges.Source: §4.1 · pp. 13–14
  • At within-community correlation ρDec = 0.60, CL-BIC selected the correct community number in every case, while BIC succeeded in 14% of 200 trials.In the hub-community simulation at ρEq = 0.20, CL-BIC selected correctly in 85% of networks, while VB failed in all cases and yielded a median of 9 communities.Source: §4.1 · p. 16
  • As the true K grows, CL-BIC outperforms BIC and VB in the standard blockmodel simulations, and it more frequently selects the correct K than BIC in degree-corrected settings.For increasing K in the degree-corrected example, CL-BIC does not appear model-selection consistent; the authors point to parameter-estimation difficulty when vertices have low degrees.Source: §4.1 · pp. 17–18

4.2.1 International Trade Networks

  • For 1995 trade data, CL-BIC selected 3 GDP-related communities, compared with 7 under VB and 10 under BIC, whose partition fragmented South American and high-GDP countries.The authors judged CL-BIC's grouping of countries with similar GDP values more useful than BIC's model, which included communities as small as one.Source: §4.2.1 · pp. 19–20, Figure 2 · p. 20

4.2.2 School Friendship Networks

  • In the 433-student school network, CL-BIC selected K = 6 and roughly matched grade labels except for the 12th-grade group, while BIC selected 9 and split 7th and 8th graders.CL-BIC's GF was 0.811 versus BIC's 0.810; their MR values were 40.8 and 33.3, respectively.Source: §4.2.2 · pp. 20–21, Figure 3 · p. 21

5. DISCUSSION

The discussion advocates CL-BIC for community-number selection under stochastic blockmodels and variants, citing its simplicity and robustness to correlated binary data. It identifies extensions and scope boundaries, including unresolved consistency for degree-corrected models.

5. DISCUSSION

  • The paper advocates CL-BIC for selecting community numbers under stochastic blockmodels and variants, citing simplicity and robustness to correlated binary data.Source: §5 · p. 22
  • The methodology relies on spectral clustering and SCORE, and combining CL-BIC with other community-detection methods remains a possible extension.Source: §5 · p. 22
  • Most examples use dense graphs, and consistency for the degree-corrected stochastic blockmodel remains an open question.Source: §5 · p. 22

SUPPLEMENTARY MATERIALS

Supplementary materials provide R code for replicating the analyses and include the international trade network dataset.

SUPPLEMENTARY MATERIALS

Related papers

Loading 1412.1684v2…