论文标题
关于加权随机块模型下高阶光谱聚类的功效
On the efficacy of higher-order spectral clustering under weighted stochastic block models
论文作者
论文摘要
网络的高阶结构，即网络的少量子图（也称为网络图案），对网络的组织而言至关重要，至关重要。研究社区检测问题已经有一些工作 - 网络分析中的一个基本问题，在图案级别上。特别是，已经开发了高阶光谱聚类，其中将基序矩阵的概念作为算法的输入引入。但是，在很大程度上，尚不清楚高阶光谱聚类的工作原理以及其性能何时比基于边缘的对应物更好。为了阐明这些问题，我们从统计角度研究了高阶光谱聚类。特别是，我们从理论上研究了加权随机块模型下高阶光谱聚类的聚类性能，并将结果边界与基于边缘的光谱聚类的相应结果进行比较。事实证明，当网络致密而权重弱信号时，高阶光谱聚类确实会导致聚类的性能增长。我们还使用仿真和实际数据实验来支持发现。
Higher-order structures of networks, namely, small subgraphs of networks (also called network motifs), are widely known to be crucial and essential to the organization of networks. There has been a few work studying the community detection problem -- a fundamental problem in network analysis, at the level of motifs. In particular, higher-order spectral clustering has been developed, where the notion of motif adjacency matrix is introduced as the input of the algorithm. However, it remains largely unknown that how higher-order spectral clustering works and when it performs better than its edge-based counterpart. To elucidate these problems, we investigate higher-order spectral clustering from a statistical perspective. In particular, we theoretically study the clustering performance of higher-order spectral clustering under a weighted stochastic block model and compare the resulting bounds with the corresponding results of edge-based spectral clustering. It turns out that when the network is dense with weak signal of weights, higher-order spectral clustering can really lead to the performance gain in clustering. We also use simulations and real data experiments to support the findings.
