A Note on the Identifiability of the Degree-Corrected Stochastic Block Model
John Park, Yunpeng Zhao, Ning Hao · 2024
Read A Note on the Identifiability of the Degree-Corrected Stochastic Block Model by John Park, Yunpeng Zhao, Ning Hao (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03833.txt.
Introduction
John Park and co-authors settle a basic question about a popular network model. The degree corrected block model sorts nodes into groups while letting each node vary in link count. The note proves its numbers are pinned down by the data. Aside from a shared scale factor and a swap of group labels, no two settings give the same odds. The proof needs only a mild condition.
Catalog record
| CREATOR | John Park, Yunpeng Zhao, Ning Hao |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03833
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Note on the Identifiability of the Degree-Corrected Stochastic Block Model John Park, Yunpeng Zhao, Ning Hao Abstract In this short note, we address the identifiability issues inherent in the Degree-Corrected Stochastic Block Model (DCSBM). We provide a rigorous proof demonstrating that the parameters of the DCSBM are identifiable up to a scaling factor and a permutation of the community labels, under a mild condition. Keywords: Clustering, Community Detection, Networks. 1 Introduction The Stochastic Block Model (SBM) is a foundational framework for modeling community structures in networks. It groups nodes into distinct communities, with the probability of an edge between two nodes determined solely by their community memberships ( Holland and Leinhardt,, 1981 ; Nowicki and Snijders,, 2001 ; Bickel and Chen,, 2009 ; Choi et al.,, 2012 ) . SBM extends the Erdős-Rényi model ( Erdős and Rényi,, 1959 ) , which assumes a uniform edge probability across all node pairs, thereby offering a simpler framework without community differentiation. In contrast, SBM captures both inter-community and intra-community connection patterns, making it a valuable tool for community detection ( Abbe,, 2017 ; Zhao,, 2017 ) . However, SBM assumes homogeneity within each community, limiting its applicability to real-world networks where significant degree variability exists among nodes within the same community. To address this limitation, the Degree-Corrected Stochastic Block Model (DCSBM) was introduced. DCSBM extends SBM by incorporating degree heterogeneity, allowing nodes within a community to exhibit varying degrees of connectivity ( Karrer and Newman,, 2011 ; Ball et al.,, 2011 ) . This enhancement improves the model’s flexibility, making DCSBM particularly suited for networks such as social, biological, and communication systems, where nodes often exhibit varying connectivity patterns even within the same community. It is well known that parameters in an SBM, like those in other clustering models such as Gaussian mixture models, are not identifiable due to the possible permutation of community labels. For the DCSBM, this issue is further compounded by the non-identifiability of degree parameters due to scaling factors ( Karrer and Newman,, 2011 ; Ball et al.,, 2011 ; Zhao et al.,, 2012 ) . Despite these challenges, researchers generally agree that these identifiability issues pose only minor technical obstacles and that no additional identifiability problems exist for the DCSBM. However, formal references addressing the identifiability of the DCSBM are limited. In this note, we point out a small gap in a commonly used argument and provide a rigorous proof confirming that the parameter system of the DCSBM is identifiable up to a scaling factor and a permutation of the community labels, under a mild condition that each community has at least three members. To our best knowledge, this condition has never been explicitly stated in the literature. In addition, we show that this condition is necessary using a counterexample. Together, our results fill a critical gap in the theoretical understanding of the identifiability of the DCSBM. 2 Model Description Consider an undirected graph G=(V,E) with n nodes. The adjacency matrix A represents the presence or absence of edges between nodes. The DCSBM with n nodes and K communities is characterized by the following components with technical conditions. 1. Community Membership Matrix Z : Z is an n\times K binary matrix where Z_{ik}=1 if node i belongs to community k , and 0 otherwise. We require that each community has at least 1 member. We use z_{i} to denote the community label of node i . That is, z_{i}=k if and only if Z_{ik}=1 . 2. Degree Parameter Matrix \Theta : \Theta is an n\times n diagonal matrix where \Theta_{ii}=\theta_{i}>0 represents the degree parameter for node i . 3. Community Connection Matrix B : B is a symmetric full rank K\times K matrix where B_{kl} represents the intensity of connection between nodes in community k and community l . A triple \{Z,\Theta,B\} defines a DCSBM, where the off-diagonal elements of the adjacency matrix A are generated independently with \mathbb{E}[A_{ij}]=\Delta_{ij} , and \Delta=\Theta ZBZ^{\top}\Theta. (1) We assume that all triples \{Z,\Theta,B\} satisfy the conditions listed above throughout this paper. Now, we introduce useful notations and technical lemmas. We use [n] to denote the set of integers \{1,\dots,n\} . A partition of [n] is a collection of nonempty, mutually disjoint subsets of [n] whose union is [n] . A permutation matrix is a square binary matrix with exactly one entry of 1 in each row and each column, with all other entries being 0. A K\times K permutation matrix P corresponds to a permutation of a set with K elements. The operator \mathrm{diag}(\cdot) is defined as \mathrm{diag}:\mathbb{R}^{n}\to\mathbb{R}^{n\times n} , mapping a vector to a diagonal matrix such that [\mathrm{diag}(v)]_{ii}=v_{i} for a vector v=(v_{1},\dots,v_{n})^{\top} . Finally, we use 1_{n} to denote an n -dimensional vector where all entries are equal to 1. Every equivalence relation on a set defines a partition of that set, and vice versa. For a matrix Q , we define its i -th row and j -th row to be equivalent if they are identical. Using this equivalence relation, any matrix Q with n rows defines a partition of [n] . The following lemmas will be useful in our theoretical derivations. Lemma 1 . An n\times K community membership matrix Z defines a partition of [n] based on row equivalence. Two community membership matrices Z and \tilde{Z} define the same partition if and only if \tilde{Z}=ZP for a permutation matrix P . Proof of Lemma 1 : Define subset C_{k}\subset[n] as \{i\in[n]\mid Z_{ik}=1\} . It is straightforward to verify that \{C_{1},\dots,C_{K}\} is a partition of [n] . Similarly, we can define another partition \{\tilde{C}_{1},\dots,\tilde{C}_{K}\} based on \tilde{Z} . The partitions \{C_{1},\dots,C_{K}\} and \{\tilde{C}_{1},\dots,\tilde{C}_{K}\} are identical if and only if there exists a permutation \pi:[K]\to[K] such that \tilde{C}_{\pi(k)}=C_{k} . This permutation \pi induces a permutation matrix P with P_{k,\pi(k)}=1 , and it follows that \tilde{Z}=ZP . \Box Lemma 2 . Let Z and \tilde{Z} be two n\times K community membership matrices, and R and \tilde{R} be two full row-rank K\times K^{\prime} matrices where K^{\prime}\geq K . The matrices ZR and \tilde{Z}\tilde{R} define the same partition of [n] based on row equivalence if and only if \tilde{Z}=ZP for a permutation matrix P . Proof of Lemma 2 : All rows of R are distinct, since R has full row rank. The rows of ZR are replications of rows of R , and the i -th row of ZR is identical to the k -th row of R if and only if Z_{ik}=1 . As a result, ZR and Z define the same partition of [n] based on row equivalence. The same conclusion holds for \tilde{Z}\tilde{R} and \tilde{Z} . Thus, ZR and \tilde{Z}\tilde{R} define the same partition of [n] if and only if Z and \tilde{Z} define the same partition, and by Lemma 1 , if and only if \tilde{Z}=ZP for a permutation matrix P . \Box For a matrix Q , we define its i -th row and j -th row to be proportionally equivalent if they are proportional to each other up to a positive scaling factor. Any matrix Q with n rows defines a partition of [n] via this proportional equivalence. Lemma 3 . The matrices Z , \tilde{Z} , R and \tilde{R} are defined