How many asymmetric communities are there in multi-layer directed networks?

Huan Qing

math.STFeb 25, 2026

How many asymmetric communities are there in multi-layer directed networks?

Authors: Huan Qing

Organizations: School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, China

Abstract

Estimating the asymmetric numbers of communities in multi-layer directed networks is a challenging problem due to the multi-layer structures and inherent directional asymmetry, leading to possibly different numbers of sender and receiver communities. This work addresses this issue under the multi-layer stochastic co-block model, a model for multi-layer directed networks with distinct community structures in sending and receiving sides, by proposing a novel goodness-of-fit test. The test statistic relies on the deviation of the largest singular value of an aggregated normalized residual matrix from the constant 2. The test statistic exhibits a sharp dichotomy: Under the null hypothesis of correct model specification, its upper bound converges to zero with high probability; under underfitting, the test statistic itself diverges to infinity. With this property, we develop a sequential testing procedure that searches through candidate pairs of sender and receiver community numbers in a lexicographic order. The process stops at the smallest such pair where the test statistic drops below a decaying threshold. For robustness, we also propose a ratio-based variant algorithm, which detects sharp changes in the sequence of test statistics by comparing consecutive candidates. Both methods are proven to consistently determine the true numbers of sender and receiver communities under the multi-layer stochastic co-block model.

Figures & tables

$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$	$m$	$(k_{s},k_{r})$
1	(1,1)	11	(1,5)	21	(6,1)	31	(3,6)	41	(5,5)	51	(6,5)	61	(7,5)	71	(9,4)	81	(6,9)	91	(7,10)
2	(1,2)	12	(2,4)	22	(1,7)	32	(4,5)	42	(6,4)	52	(7,4)	62	(8,4)	72	(10,3)	82	(7,8)	92	(8,9)
3	(2,1)	13	(3,3)	23	(2,6)	33	(5,4)	43	(7,3)	53	(8,3)	63	(9,3)	73	(4,10)	83	(8,7)	93	(9,8)
4	(1,3)	14	(4,2)	24	(3,5)	34	(6,3)	44	(8,2)	54	(9,2)	64	(10,2)	74	(5,9)	84	(9,6)	94	(10,7)
5	(2,2)	15	(5,1)	25	(4,4)	35	(7,2)	45	(9,1)	55	(10,1)	65	(3,10)	75	(6,8)	85	(10,5)	95	(8,10)
6	(3,1)	16	(1,6)	26	(5,3)	36	(8,1)	46	(1,10)	56	(2,10)	66	(4,9)	76	(7,7)	86	(6,10)	96	(9,9)

Table 1: Search order of candidate pairs

\mathcal{P}

for

K_{\text{cand}}=10

	$\hat{T}_{n}$
$n$	$H_{0}$ : (3,5)	$H_{1}$ : (2,5)	$H_{1}$ : (3,4)	$H_{1}$ : (2,4)
200	-0.014(0.024)	3.259 (0.229)	0.165 (0.112)	3.324 (0.277)
400	-0.012(0.014)	5.270 (0.339)	0.626 (0.357)	5.458 (0.408)
600	-0.008 (0.010)	6.900 (0.437)	0.893 (0.262)	7.187 (0.489)
800	-0.007 (0.010)	8.282 (0.516)	1.247 (0.322)	8.629 (0.546)
1000	-0.007 (0.006)	9.438 (0.627)	1.493 (0.384)	9.769 (0.709)

Table 2: Behavior of the test statistic

\hat{T}_{n}

under various hypotheses for true structure

(K_{s},K_{r})=(3,5)

. Values are mean (standard deviation) over 200 replications.

True $(K_{s},K_{r})$	Hypothesized $(K_{s0},K_{r0})$	Underfitting type	$\mathbb{P}(\hat{T}_{n}<t_{n})$ for $H_{0}$	$\mathbb{P}(\hat{T}_{n}\geq t_{n})$ for $H_{1}$
$(2,3)$	$(2,3)$	True model ( $H_{0}$ )	1.00 (0.000)	–
	$(1,3)$	Sender only ( $H_{1}^{(s)}$ )	–	1.00 (0.000)
	$(2,2)$	Receiver only ( $H_{1}^{(r)}$ )	–	1.00 (0.000)
	$(1,2)$	Both ( $H_{1}^{(b)}$ )	–	1.00 (0.000)
$(2,4)$	$(2,4)$	True model ( $H_{0}$ )	1.00 (0.000)	–
	$(1,4)$	Sender only ( $H_{1}^{(s)}$ )	–	1.00 (0.000)

Table 3: Discrimination power of the

\hat{T}_{n}

statistic. Values are empirical probabilities (standard errors) over 200 replications.

$(K_{s},K_{r})$	$n$	MLDiGoF					MLRDiGoF
$(K_{s},K_{r})$	$n$	$\rho=0.1$	$\rho=0.2$	$\rho=0.3$	$\rho=0.4$	$\rho=0.5$	$\rho=0.1$	$\rho=0.2$	$\rho=0.3$	$\rho=0.4$	$\rho=0.5$
(1,1)	200	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00
	400	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00
	600	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00
	800	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00
	1000	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00	1.00

Table 4: Estimation accuracy of MLDiGoF and MLRDiGoF under selected challenging asymmetric settings. Values are accuracy over 100 replications.

Figure 1: Sensitivity analysis of MLDiGoF and MLRDiGoF to threshold parameters ( $n=800$ , $L=15$ , $\rho=0.2$ , $(K_{s},K_{r})=(3,5)$ ). For each method, the $x$ -axis index $1$ to $10$ corresponds to an increasing sequence of the associated threshold parameter: $\varepsilon$ for MLDiGoF (blue circles), constant $\tau$ for MLRDiGoF (red squares), and scale factor $a$ for MLRDiGoF with $\tau_{n}=a\log n$ (yellow triangles). Accuracy is computed over independent replications.

Panel of Figure 2 — Figure 2: Test statistic $\hat{T}_{n}(m)$ and ratio statistic $r_{m}$ for ordered candidate pairs $1\leq m\leq 100$ (i.e., $K_{\mathrm{cand}}=10$ ) for the FAO network. The red circle in the right panel marks the global maximum of $r_{m}$ at $m=42$ , corresponding to the candidate pair $(k_{s},k_{r})=(6,4)$ .

Graph Clustering

Graph clustering groups network nodes by connectivity, attributes, or shared roles to reveal communities and other mesoscale structure.

See all 78 papers

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection
Oct 1, 2026Alexandra Dache, Manon Rustin, Arnaud Vandaele +1Non-Negative Matrix Factorization Graph Clustering
Department of Mathematics and Operational Research, University of Mons, Mons, Belgium
Optimal Clustering of Multi-layer Networks under Mixture Block Models
Nov 27, 2023Zhongyuan Lyu, Ting Li, Dong XiaClustering Stochastic Block Model
Department of Mathematics, Hong Kong University of Science and Technology · Department of Applied Mathematics, The Hong Kong Polytechnic University
Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
Oct 6, 2026Soroor GhandaliBelief Propagation Low-Degree Polynomial Method

Oct 1, 2026J/K move · Enter open · S save

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Alexandra Dache, Manon Rustin, Arnaud Vandaele, Nicolas Gillis

Department of Mathematics and Operational Research, University of Mons, Mons, Belgium

Non-Negative Matrix Factorization Graph Clustering

Open paper AskPDF arXiv

Multilayer networks allow the modeling of interactions between the same entities across different contexts, such as temporal observations, varying settings, or interactions of different types. The goal of community detection in multilayer networks is to identify groups of nodes exhibiting similar connectivity patterns, which may vary across layers. We propose a method based on a joint nonnegative symmetric matrix trifactorization for community detection in multilayer networks, where each graph is approximated by a nonnegative symmetric matrix trifactorization. Our approach enforces constraints on the factor matrices so that communities are disjoint and shared across layers, while allowing each layer to have its own connectivity patterns and node degrees. This flexibility enables the model to capture both local and global structural variations across layers. We also develop an algorithm to efficiently solve this problem. We evaluate multilayer community detection methods using the multilayer degree-corrected stochastic block model (MDCBM), a flexible framework for generating realistic multilayer graphs with heterogeneous degrees and varying connectivity patterns. Experiments show that our method reliably detects communities across diverse regimes, whereas existing state-of-the-art approaches are often limited by restrictive structural assumptions.

Abstract

Graph Clustering

Explore similar work

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Optimal Clustering of Multi-layer Networks under Mixture Block Models

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models