论文标题
在严重程度异质性下的最佳网络会员估计
Optimal Network Membership Estimation Under Severe Degree Heterogeneity
论文作者
论文摘要
真实网络通常具有严重的异质性，最高，平均和最小节点度的差异很大。本文探讨了程度异质性对网络数据分析统计限制的影响。在由学位校正的混合成员网络模型下引入异质性分布（HD），我们表明混合成员估计的最佳速率是HD的明确功能。该结果证实，即使总体稀疏性保持不变，严重的异质性也可能会减速错误率。 为了获得速率最佳方法，我们通过添加PRE-PCA归一化步骤来修改现有光谱算法（混合得分）。此步骤通过由$ b $ th节点学位的功率组成的对角矩阵将邻接矩阵归一化，对于\ Mathbb {r} $中的某些$ b \。我们发现$ b = 1/2 $是普遍有利的。对于具有任意程度异质性的网络，所得的光谱算法是最佳的速率。我们证明中的技术组成部分是对标准化图拉普拉斯的入门特征向量分析。
Real networks often have severe degree heterogeneity, with the maximum, average, and minimum node degrees differing significantly. This paper examines the impact of degree heterogeneity on statistical limits of network data analysis. Introducing the heterogeneity distribution (HD) under a degree-corrected mixed-membership network model, we show that the optimal rate of mixed membership estimation is an explicit functional of the HD. This result confirms that severe degree heterogeneity may decelerate the error rate, even when the overall sparsity remains unchanged. To obtain a rate-optimal method, we modify an existing spectral algorithm, Mixed-SCORE, by adding a pre-PCA normalization step. This step normalizes the adjacency matrix by a diagonal matrix consisting of the $b$th power of node degrees, for some $b\in \mathbb{R}$. We discover that $b = 1/2$ is universally favorable. The resulting spectral algorithm is rate-optimal for networks with arbitrary degree heterogeneity. A technical component in our proofs is entry-wise eigenvector analysis of the normalized graph Laplacian.
