arxiv: 2601.10502 · v2 · submitted 2026-01-15 · 💻 cs.SI

Recognition: 2 theorem links

· Lean Theorem

Higher order trade-offs in hypergraph community detection

Jiaze Li , Michael T. Schaub , Leto Peel

Authors on Pith no claims yet

Pith reviewed 2026-05-16 13:54 UTC · model grok-4.3

classification 💻 cs.SI

keywords hypergraph community detectionstochastic block modelBethe Hessianspectral clusteringdetectability thresholdnon-uniform hypergraphshigher-order networksbelief propagation

0 comments

The pith

A Bethe Hessian operator for non-uniform hypergraphs enables spectral clustering whose detectability threshold diverges from belief propagation limits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a framework for community detection in hypergraphs whose hyperedges can connect any number of nodes. It introduces a signal-to-noise ratio that quantifies the distinct trade-offs arising when hyperedges of different orders span communities in different ways. From this ratio the authors construct a Bethe Hessian operator that performs efficient spectral clustering while selecting the number of communities automatically. The resulting spectral threshold matches the belief-propagation limit exactly when all hyperedges have the same order, but the two limits separate once orders vary. Real systems routinely mix hyperedge sizes, so the separation implies that detection performance can be improved or degraded by the choice of which orders to emphasize.

Core claim

Under the Hypergraph Stochastic Block Model, a Bethe Hessian operator can be derived for non-uniform hypergraphs that supports spectral clustering with principled model selection; the associated detectability threshold coincides with belief-propagation limits for uniform hypergraphs but diverges once hyperedge orders differ.

What carries the argument

The Bethe Hessian operator generalized to non-uniform hypergraphs, which encodes higher-order connectivity into a matrix whose eigenvectors yield community assignments and whose eigenvalues guide model selection.

If this is right

Spectral and belief-propagation methods produce identical detectability thresholds when all hyperedges share one order.
The thresholds separate in non-uniform cases, so optimal performance depends on the distribution of hyperedge orders.
Detection on synthetic data systematically favors higher-order and balanced hyperedges over lower-order or unbalanced ones.
The same trade-offs appear in empirical hypergraphs, altering which communities are recovered in practice.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

When hyperedge orders vary widely, a practitioner may obtain better recovery by deliberately retaining only the highest-order hyperedges even if they are scarce.
The computational advantage of the spectral method could be traded against the statistical accuracy of belief propagation depending on how uniform the input hypergraph is.
The signal-to-noise construction could be adapted to generative models other than the HSBM by re-deriving the ratio for each new edge-probability rule.

Load-bearing premise

The Hypergraph Stochastic Block Model generates every hyperedge independently according to fixed probabilities that depend only on the community labels of its nodes.

What would settle it

Generate non-uniform hypergraphs from the HSBM near the predicted spectral threshold and measure whether the Bethe Hessian recovers communities exactly at the calculated limit while belief propagation recovers them at a different limit.

Figures

Figures reproduced from arXiv: 2601.10502 by Jiaze Li, Leto Peel, Michael T. Schaub.

**Figure 1.** Figure 1: Different configurations of community structure in graphs and hypergraphs. (a) In dyadic networks, there is a single type of edge connecting pairs of nodes and edges can only be split across communities in one way. (b) In hypergraphs, hyperedges of different orders connect varying numbers of nodes and we must choose which order of hyperedge to split across communities, e.g., do we prefer to preserve the … view at source ↗

**Figure 2.** Figure 2: Spectral methods exhibit a weaker detectability limit in non-uniform hypergraphs. An experiment with nonuniform hypergraphs with n = 30, 000 nodes, q = 3 communities, K = {2, 3} hyperedge orders and d = 10 mean node degree. For each value of ϵ, we run our Bethe Hessian spectral clustering 100 times and belief propagation for 5 times and calculate the mean AMI with the planted community partition. The yel… view at source ↗

**Figure 3.** Figure 3: Hyperedge shape preferences in community detection. (a) An illustration of the planted community structure in hypergraphs used in experiments to explore the effect of hyperedge shape. All the hyperedges are 4-order and connect 2 of the 4 communities. The balanced hyperedges are represented by rectangle shapes between communities {0, 1} or {2, 3}. The imbalanced hyperedges are represented by triangle shapes… view at source ↗

**Figure 4.** Figure 4: Hyperedge order preferences in community detection. (a) Synthetic hypergraphs with 4 planted communities and all the hyperedges between communities {0, 1} or {2, 3} are of order κ ∗ , the hyperedges between communities {0, 2} or {1, 3} are of order κ. All hypergraphs have n = 8000 nodes. The average degree is either d = 50 (b-c) or d = 10 (d-e). We see the AMI01;23 and AMI02;13 as we vary ρ the ratio of … view at source ↗

**Figure 5.** Figure 5: Comparison between detected communities and class structure in human contact hypergraphs. Confusion matrices of communities detected and school classes in hypergraphs of human contact interactions in (a) the primary school and (b) the high school. The rows are normalized such that each entry represents the proportion of individuals in the class assigned to each community. Human contact interaction First, … view at source ↗

**Figure 6.** Figure 6: Hyperedge distributions in the high school data. The distribution of hyperedges by the maximum number of nodes in the same school class (left panel) and maximum number of nodes in the same detected community (middle panel). The frequency of hyperedges of each order (right panel). contains a significant proportion of students from all the other classes. One might be tempted to attribute this deviation from … view at source ↗

**Figure 7.** Figure 7: Geographical distribution of detected communities in the Yelp data. The bottom right corner is the confusion matrix of communities detected by Bethe Hessian-based spectral clustering with state metadata for yelp data. We highlight some communities composed of business in the Alberta province (AB) and show their geographical distribution. includes businesses across all states because these businesses are re… view at source ↗

**Figure 8.** Figure 8: The spectrum of non-backtracking matrix (a) and Bethe Hessian matrix (b) for a network generate by symmetric SBM. The number of nodes n = 300, number of communities q = 3, average degree d = 10, edge probability ratio pout/pin = 0.2. The light blue circle is the bulk with radius √ d. Each column of red to green points in (b) is the spectrum of Bη where η is x-axis value. Here the spectrum of Bη is scaled f… view at source ↗

**Figure 9.** Figure 9: The spectrum of non-backtracking matrix (a, b) and Bethe Hessian matrix (c, d) for hypergraphs generated by κ = 3 uniform HSBM (a, c) and K = {2, 3, 4} nonuniform HSBM (b, d). In both settings, n = 100, q = 2 and degree parameters din = 10 and dout = 1. The light blue circle is the uninformative bulk of NB with radius P κ∈K p d (κ)(κ − 1). 32 [PITH_FULL_IMAGE:figures/full_fig_p032_9.png] view at source ↗

**Figure 10.** Figure 10: The factor graph representation of hypergraph. The red square represent the hyperedge, the circle represent the node. The message and marginal probability on directed hyperedge and node are also shown as b j→f , b i→e , ˆb f→i and b i . The blue directed hyperedge form a nonbacktracking path b j→f → ˆb f→i → b i→e . Next we discuss the ˆb e→i ψi based on existence of hyperedge e. E.1 Discussion on hyper… view at source ↗

**Figure 11.** Figure 11: The approximate message passing tree in belief propagation. E.4.1 Transition matrix at trivial fixed point Based on belief propagation (83), we can write the full update function of b i→e x without hyperedge to node message as b i→e x = 1 Zi→e nxexp(−h i x ) Y g∈∂i/e∩E X −−→ψg/i∈[q] |g|−1, −→ψi=x C−→ψg Y l∈g/i b j→g ψl , (86) where Z i→e is normalization term over community label x. We define the numerato… view at source ↗

**Figure 12.** Figure 12: The experiment run on 3-uniform hyper graph. The blue line is the AMIBH at different ϵ. For each point, we run experiment for 50 times. The orange vertical dash line is the critical ϵ ∗ where the detectability phase transition happen. Combined with average κ-degree (8), we can get the d (κ) in , d(κ) out at the detectability threshold: d (κ) in = 1 q κ−1  d (κ) + (q κ−1 − 1)s d (κ) κ − 1   d (κ) out … view at source ↗

**Figure 13.** Figure 13: The experiment run on nonuniform hyper graph with 2 communities. For each ϵ, we run bethe hessian method 100 times and belief propagation for 10 times. F.2 Experiment on nonuniform hyper graph We fix the nonuniform hyper graph size n = 30000, number of communities q = 2, K = {2, 3} and average degree d = 10. For different ϵ, we calculate the cin and cout with equation (113) and generate a hyper graph with… view at source ↗

**Figure 14.** Figure 14: If we apply Bethe Hessian-based spectral clustering algorithm 1 to detect 2 communities in this hypergraph considering only the assortative case, two distinct, coarse-grained community structures could be detected: 54 [PITH_FULL_IMAGE:figures/full_fig_p054_14.png] view at source ↗

**Figure 14.** Figure 14: Illustration of community structure of hypergraph used in experiment for exploring the effect of order to detectability. • κ ∗ -dominated structure with communities {0, 1} are merged into one community, {2, 3} are merged into the second. • κ-dominated structure with communities {0, 2} are merged into one community, {1, 3} are merged into the second. Intuitively, if the number of κ-order hyperedges |E(κ) |… view at source ↗

**Figure 15.** Figure 15: Experimental results with n = 8000, d = 50, κ = 2 and κ ∗ = 3. We show the AMI01;23 and AMI02;13 as the AMI of detected communities by Bethe Hessian based-spectral clustering to the κ ∗ and κ dominated community structure. We observed that the derived ρ ∗ theo has a little bias to the sharp transition point. Instead, the transition point ρ ∗ can be better aligned by the cross point of two manually modifie… view at source ↗

**Figure 16.** Figure 16: Experimental results with general κ and κ ∗ . All experiments are proceed on n = 8000 hypergraphs. For first row, the average degree d = 50 for better observing the sharp transition. For others d = 10 is enough. We show the AMI01;23 and AMI02;13 as the AMI of detected communities by Bethe Hessian based-spectral clustering to the κ ∗ and κ dominated community structure. 63 [PITH_FULL_IMAGE:figures/full_fi… view at source ↗

**Figure 17.** Figure 17: (a) Illustration of community structure of hypergraph used in experiment for exploring the effect of shape to detectability. All the hyperedges are 4-order, only the different shape. The hyperedges shaped by rectangle between communities {0, 1} or {2, 3} are balanced, the hyperedges shaped by triangle between communities {0, 2} or {1, 3} are imbalanced. (b) Experimental results with n = 8000, d = 10, κ … view at source ↗

**Figure 18.** Figure 18: (a) Illustration of community structure of hypergraph used in experiment for exploring the effect of shape to detectability. All the hyperedges are 5-order, only the different shape. The hyperedges shaped by trapezoid between communities {0, 1} or {2, 3} are more balanced, composed by 2 nodes in one community, 3 nodes in another. The hyperedges shaped by triangle between communities {0, 2} or {1, 3} are… view at source ↗

read the original abstract

Extending community detection from pairwise networks to hypergraphs introduces fundamental theoretical challenges. Hypergraphs exhibit structural heterogeneity with no direct graph analogue: hyperedges of varying orders can connect nodes across communities in diverse configurations, introducing new trade-offs in defining and detecting community structure. We address these challenges by developing a unified framework for community detection in non-uniform hypergraphs under the Hypergraph Stochastic Block Model. We introduce a general signal-to-noise ratio that enables a quantitative analysis of trade-offs unique to higher-order networks, such as which hypergedges we choose to split across communities and how we choose to split them. Building on this framework, we derive a Bethe Hessian operator for non-uniform hypergraphs that provides efficient spectral clustering with principled model selection. We characterize the resulting spectral detectability threshold and compare it to belief propagation limits, showing the methods coincide for uniform hypergraphs but diverge in non-uniform settings. Synthetic experiments confirm our analytical predictions and reveal systematic biases toward preserving higher-order and balanced-shape hyperedges. Application to empirical data demonstrates the practical relevance of these higher-order detectability trade-offs in real-world systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper derives a Bethe Hessian for non-uniform hypergraphs and shows spectral thresholds diverge from belief propagation when edge orders mix, but the analysis stays inside the HSBM.

read the letter

The main thing here is that they extend spectral community detection to hypergraphs with mixed edge sizes by building a Bethe Hessian operator and then show that its detectability threshold lines up with belief propagation only for uniform cases. In non-uniform settings the two split, which highlights some higher-order effects that uniform methods overlook. They also give a general signal-to-noise ratio that quantifies trade-offs like which hyperedges to split across communities and how to split them. Synthetic runs match the math and turn up consistent biases that favor preserving higher-order and balanced hyperedges. The derivations are careful and the non-uniform extension is distinct from the uniform-hypergraph results they cite. The soft spot is that everything is derived under the hypergraph stochastic block model with fixed community-dependent probabilities. When they apply the method to real data they claim practical relevance for social and biological systems, but they do not test whether the observed hyperedge patterns actually fit that generative assumption. If real data follows different dependencies, the predicted thresholds and trade-offs may shift. This is for network scientists who already work with hypergraph clustering and want to handle varying edge orders. The math is grounded enough and the divergence result is new enough that it deserves a serious referee to check the steps and the empirical translation.

Referee Report

1 major / 0 minor

Summary. The manuscript develops a unified framework for community detection in non-uniform hypergraphs under the Hypergraph Stochastic Block Model (HSBM). It introduces a general signal-to-noise ratio to quantify trade-offs in hyperedge splitting across communities, derives a Bethe Hessian operator for spectral clustering with principled model selection, characterizes the resulting spectral detectability threshold, and shows that this threshold coincides with belief-propagation limits for uniform hypergraphs but diverges in non-uniform settings. Synthetic experiments confirm the analytic predictions, and the framework is applied to empirical data to illustrate practical relevance of the higher-order trade-offs.

Significance. If the derivations and comparisons hold, the work provides a valuable extension of spectral methods to non-uniform hypergraphs, quantifying structural trade-offs absent from graphs or uniform hypergraphs. The explicit divergence between the Bethe Hessian threshold and belief propagation in non-uniform cases, together with the model-selection mechanism, would be a substantive contribution to higher-order network analysis. Synthetic validation is a strength; the empirical section would carry more weight with direct checks on model fit.

major comments (1)

[Empirical application section] Empirical application section: the claim that the identified higher-order detectability trade-offs are relevant to real-world systems rests on the assumption that observed hyperedges are generated by the fixed-probability HSBM used to derive the SNR and thresholds. No diagnostic (e.g., goodness-of-fit test or comparison to alternative generative processes) is reported to verify this assumption on the empirical datasets, which is load-bearing for the practical-relevance assertion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the theoretical contributions and for highlighting the need to strengthen the empirical section. We address the major comment below and will incorporate the suggested diagnostics in the revision.

read point-by-point responses

Referee: Empirical application section: the claim that the identified higher-order detectability trade-offs are relevant to real-world systems rests on the assumption that observed hyperedges are generated by the fixed-probability HSBM used to derive the SNR and thresholds. No diagnostic (e.g., goodness-of-fit test or comparison to alternative generative processes) is reported to verify this assumption on the empirical datasets, which is load-bearing for the practical-relevance assertion.

Authors: We agree that the empirical claims would be strengthened by explicit checks on the HSBM assumption. In the revised manuscript we will add a diagnostic subsection that (i) estimates HSBM parameters from each dataset, (ii) generates synthetic hypergraphs under the fitted model, and (iii) compares observed hyperedge-order distributions, intra- versus inter-community edge fractions, and community-size statistics against the synthetic ensembles. Any systematic deviations will be discussed in relation to the relevance of the derived trade-offs. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations follow directly from HSBM assumptions as standard theoretical analysis.

full rationale

The paper assumes the Hypergraph Stochastic Block Model (HSBM) as the generative process and derives the signal-to-noise ratio, Bethe Hessian operator, spectral clustering method, and detectability thresholds as mathematical consequences of that model. Synthetic experiments generated from the same HSBM confirm the analytic predictions, which is the expected verification procedure rather than a circularity. No quoted steps reduce by construction to fitted parameters renamed as predictions, self-definitional loops, or load-bearing self-citations that lack independent support. The empirical section applies the method to real data but does not alter the internal derivation chain, which remains self-contained under the stated model assumptions. This is a normal, non-circular theoretical contribution in the community detection literature.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The framework rests on the Hypergraph Stochastic Block Model as the generative assumption and on standard spectral and belief-propagation techniques extended to hypergraphs; no new particles or dimensions are introduced.

free parameters (1)

hyperedge probability parameters
Probabilities governing intra- and inter-community hyperedge formation are part of the HSBM definition and must be set or estimated for any concrete instance.

axioms (1)

domain assumption Hyperedges are generated independently according to community membership probabilities under the HSBM
Invoked throughout the derivation of the SNR and the Bethe Hessian operator.

pith-pipeline@v0.9.0 · 5488 in / 1322 out tokens · 35167 ms · 2026-05-16T13:54:13.117982+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive a Bethe Hessian operator for non-uniform hypergraphs... SNR_BH := (∑_κ (κ−1)(d_in^(κ)−d_out^(κ)))^2 / ∑_κ (κ−1)d^(κ) = 1
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Synthetic experiments confirm our analytical predictions and reveal systematic biases toward preserving higher-order and balanced-shape hyperedges.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model
stat.ML 2026-04 unverdicted novelty 8.0

Weak recovery in the non-uniform HSBM is possible above the sum of per-layer SNRs equaling 1, achieved by an optimally weighted non-backtracking spectral algorithm.
Detectability of minority communities in networks
cs.SI 2026-04 unverdicted novelty 7.0

Minority communities in stochastic block models enter three phases of detectability—detectable, distinguishable, and resolvable—separated by the Kesten-Stigum threshold and two additional thresholds from the eigenvalu...

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · cited by 2 Pith papers · 1 internal anchor

[1]

Community detection in graphs

S. Fortunato. “Community detection in graphs”. In:Physics reports486.3-5 (2010), pp. 75–174

work page 2010
[2]

Communities in networks

M. A. Porter, J.-P. Onnela, P. J. Mucha, et al. “Communities in networks”. In: (2009)

work page 2009
[3]

Fast unfolding of communities in large networks

V. D. Blondel et al. “Fast unfolding of communities in large networks”. In:Journal of statistical mechanics: theory and experiment2008.10 (2008), P10008. 19

work page 2008
[4]

A tutorial on spectral clustering

U. Von Luxburg. “A tutorial on spectral clustering”. In:Statistics and computing 17.4 (2007), pp. 395–416

work page 2007
[5]

Stochastic blockmodels: First steps

P. W. Holland, K. B. Laskey, and S. Leinhardt. “Stochastic blockmodels: First steps”. In:Social networks5.2 (1983), pp. 109–137

work page 1983
[6]

Asymptotic analysis of the stochastic block model for modu- lar networks and its algorithmic applications

A. Decelle et al. “Asymptotic analysis of the stochastic block model for modu- lar networks and its algorithmic applications”. In:Physical Review E—Statistical, Nonlinear, and Soft Matter Physics84.6 (2011), p. 066106

work page 2011
[7]

Spectral redemption in clustering sparse networks

F. Krzakala et al. “Spectral redemption in clustering sparse networks”. In:Proceed- ings of the National Academy of Sciences110.52 (2013), pp. 20935–20940

work page 2013
[8]

Spectral clustering of graphs with the bethe hessian

A. Saade, F. Krzakala, and L. Zdeborov´ a. “Spectral clustering of graphs with the bethe hessian”. In:Advances in neural information processing systems27 (2014)

work page 2014
[9]

What are higher-order networks?

C. Bick et al. “What are higher-order networks?” In:SIAM review65.3 (2023), pp. 686–731

work page 2023
[10]

Newman.Networks

M. Newman.Networks. Oxford university press, 2018

work page 2018
[11]

High-order interactions distort the functional land- scape of microbial consortia

A. Sanchez-Gorostiaga et al. “High-order interactions distort the functional land- scape of microbial consortia”. In:PLoS biology17.12 (2019), e3000550

work page 2019
[12]

Networks beyond pairwise interactions: Structure and dynam- ics

F. Battiston et al. “Networks beyond pairwise interactions: Structure and dynam- ics”. In:Physics reports874 (2020), pp. 1–92

work page 2020
[13]

The physics of higher-order interactions in complex systems

F. Battiston et al. “The physics of higher-order interactions in complex systems”. In:Nature physics17.10 (2021), pp. 1093–1098

work page 2021
[14]

Generative hypergraph clustering: From blockmodels to modularity

P. S. Chodrow, N. Veldt, and A. R. Benson. “Generative hypergraph clustering: From blockmodels to modularity”. In:Science Advances7.28 (2021), eabh1303

work page 2021
[15]

Consistency of spectral hypergraph partition- ing under planted partition model

D. Ghoshdastidar and A. Dukkipati. “Consistency of spectral hypergraph partition- ing under planted partition model”. In: (2017)

work page 2017
[16]

Nonbacktracking spectral clustering of nonuniform hypergraphs

P. Chodrow, N. Eikmeier, and J. Haddock. “Nonbacktracking spectral clustering of nonuniform hypergraphs”. In:SIAM Journal on Mathematics of Data Science5.2 (2023), pp. 251–279

work page 2023
[17]

Spectral detection on sparse hypergraphs

M. C. Angelini et al. “Spectral detection on sparse hypergraphs”. In:2015 53rd An- nual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE. 2015, pp. 66–73

work page 2015
[18]

Message-passing on hypergraphs: de- tectability, phase transitions and higher-order information

N. Ruggeri, A. Lonardi, and C. De Bacco. “Message-passing on hypergraphs: de- tectability, phase transitions and higher-order information”. In:Journal of Statistical Mechanics: Theory and Experiment2024.4 (2024), p. 043403

work page 2024
[19]

Sparse random hypergraphs: Non-backtracking spectra and community detection

L. Stephan and Y. Zhu. “Sparse random hypergraphs: Non-backtracking spectra and community detection”. In:Information and Inference: A Journal of the IMA 13.1 (2024), iaae004. 20

work page 2024
[20]

Consistency of spectral partitioning of uni- form hypergraphs under planted partition model

D. Ghoshdastidar and A. Dukkipati. “Consistency of spectral partitioning of uni- form hypergraphs under planted partition model”. In:Advances in Neural Informa- tion Processing Systems27 (2014)

work page 2014
[21]

Reconstruction and estimation in the planted partition model

E. Mossel, J. Neeman, and A. Sly. “Reconstruction and estimation in the planted partition model”. In:Probability Theory and Related Fields162.3 (2015), pp. 431– 461

work page 2015
[22]

Community detection thresholds and the weak Ramanujan prop- erty

L. Massouli´ e. “Community detection thresholds and the weak Ramanujan prop- erty”. In:Proceedings of the forty-sixth annual ACM symposium on Theory of com- puting. 2014, pp. 694–703

work page 2014
[23]

Community detection and stochastic block models: recent developments

E. Abbe. “Community detection and stochastic block models: recent developments”. In:Journal of Machine Learning Research18.177 (2018), pp. 1–86

work page 2018
[24]

Information theoretic measures for clusterings comparison: is a correction for chance necessary?

N. X. Vinh, J. Epps, and J. Bailey. “Information theoretic measures for clusterings comparison: is a correction for chance necessary?” In:Proceedings of the 26th annual international conference on machine learning. 2009, pp. 1073–1080

work page 2009
[25]

Detectability of hierarchical communities in networks

L. Peel and M. T. Schaub. “Detectability of hierarchical communities in networks”. In:Physical Review E110.3 (2024), p. 034306

work page 2024
[26]

High-resolution measurements of face-to-face contact patterns in a primary school

J. Stehl´ e et al. “High-resolution measurements of face-to-face contact patterns in a primary school”. In:PloS one6.8 (2011), e23176

work page 2011
[27]

Contact Patterns in a High School: A Comparison between Data Collected Using Wearable Sensors, Contact Diaries and Friendship Surveys

R. Mastrandrea, J. Fournet, and A. Barrat. “Contact Patterns in a High School: A Comparison between Data Collected Using Wearable Sensors, Contact Diaries and Friendship Surveys”. In:PLOS ONE10.9 (2015). Ed. by C. Viboud, e0136497.doi: 10.1371/journal.pone.0136497.url:https://doi.org/10.1371/journal. pone.0136497. [28]url:https://www.yelp.com/dataset

work page doi:10.1371/journal.pone.0136497.url:https://doi.org/10.1371/journal 2015
[28]

Graph wavelets for multiscale community mining

N. Tremblay and P. Borgnat. “Graph wavelets for multiscale community mining”. In:IEEE Transactions on Signal Processing62.20 (2014), pp. 5227–5239

work page 2014
[29]

Hierarchical community structure in networks

M. T. Schaub, J. Li, and L. Peel. “Hierarchical community structure in networks”. In:Physical Review E107.5 (2023), p. 054305

work page 2023
[30]

The ground truth about metadata and community detection in networks

L. Peel, D. B. Larremore, and A. Clauset. “The ground truth about metadata and community detection in networks”. In:Science advances3.5 (2017), e1602548

work page 2017
[31]

Detectability of communities in heterogeneous networks

F. Radicchi. “Detectability of communities in heterogeneous networks”. In:Phys. Rev. E88 (1 2013), p. 010801.doi:10.1103/PhysRevE.88.010801

work page doi:10.1103/physreve.88.010801 2013
[32]

Community detection in networks with unequal groups

P. Zhang, C. Moore, and M. Newman. “Community detection in networks with unequal groups”. In:Physical review E93.1 (2016), p. 012303

work page 2016
[33]

Revisiting the bethe-hessian: im- proved community detection in sparse heterogeneous graphs

L. Dall’Amico, R. Couillet, and N. Tremblay. “Revisiting the bethe-hessian: im- proved community detection in sparse heterogeneous graphs”. In:Advances in neu- ral information processing systems32 (2019). 21

work page 2019
[34]

On random graphs I

P. Erd˝ os and A. R´ enyi. “On random graphs I”. In:Publ. math. debrecen6.290-297 (1959), p. 18

work page 1959
[35]

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

C. Moore et al. “The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness”. In:Bulletin of EATCS1.121 (2017)

work page 2017
[36]

Spectral Inference Methods on Sparse Graphs: Theory and Applications

A. Saade. “Spectral inference methods on sparse graphs: theory and applications”. In:arXiv preprint arXiv:1610.04337(2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016
[37]

G. H. Golub and C. F. Van Loan.Matrix computations. JHU press, 2013

work page 2013
[38]

Mezard and A

M. Mezard and A. Montanari.Information, physics, and computation. Oxford Uni- versity Press, 2009. 22 A Detectability limit and the Bethe Hessian for dyadic networks In this section, we first introduce the Stochastic Block Model, a generative model for networks with community structure. Then we review the non-backtracking matrix and Bethe Hessian matrix u...

work page 2009