Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
复制标题
通过正则化张量幂迭代进行超图网络的社区检测
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Dong Xia
中科院分区：
文献类型：
--
作者：
Z. Ke;Feng Shi;Dong Xia
迄今为止，社交网络分析主要集中在两两互动上。通过超图网络对高阶相互作用的研究带来了新的见解。我们研究了超图网络中的社区检测。一种流行的方法是将超图投影到图上，然后对图网络应用社区检测方法，但我们表明这种方法可能会导致不必要的信息丢失。我们提出了一种直接在超图上操作的社区检测新方法。我们的方法的核心是一个正则化的高阶正交迭代（reg-HOOI）算法，该算法计算网络邻接张量的近似低秩分解。与现有的HOSVD和vanilla HOOI等张量分解方法相比，reg-HOOI具有更好的性能，特别是在超图是稀疏的情况下。给定张量分解的输出，然后我们将社区检测方法SCORE （Jin, 2015）从图网络推广到超图网络。我们把我们的新方法称为Tensor-SCORE。
To date, social network analysis has been largely focused on pairwise interactions. The study of higher-order interactions, via a hypergraph network, brings in new insights. We study community detection in a hypergraph network. A popular approach is to project the hypergraph to a graph and then apply community detection methods for graph networks, but we show that this approach may cause unwanted information loss. We propose a new method for community detection that operates directly on the hypergraph. At the heart of our method is a regularized higher-order orthogonal iteration (reg-HOOI) algorithm that computes an approximate low-rank decomposition of the network adjacency tensor. Compared with existing tensor decomposition methods such as HOSVD and vanilla HOOI, reg-HOOI yields better performance, especially when the hypergraph is sparse. Given the output of tensor decomposition, we then generalize the community detection method SCORE (Jin, 2015) from graph networks to hypergraph networks. We call our new method Tensor-SCORE.
In theory, we introduce a degree-corrected block model for hypergraphs (hDCBM), and show that Tensor-SCORE yields consistent community detection for a wide range of network sparsity and degree heterogeneity. As a byproduct, we derive the rates of convergence on estimating the principal subspace by reg-HOOI, with different initializations, including the two new initialization methods we propose, a diagonal-removed HOSVD and a randomized graph projection.
We apply our method to several real hypergraph networks which yields encouraging results. It suggests that exploring higher-order interactions provides additional information not seen in graph representations.
影响因子：
2.5
作者：
Ming Yuan;Cun-Hui Zhang
通讯作者：
Ming Yuan;Cun-Hui Zhang
DOI：
10.1214/21-aos2089
发表时间：
2019-04
期刊：
The Annals of Statistics
影响因子：
--
作者：
Jiashun Jin;Z. Ke;Shengming Luo
通讯作者：
Jiashun Jin;Z. Ke;Shengming Luo