我们考虑检测混合成员加权网络的潜在社区信息的问题，其中节点具有混合成员资格，并且在节点之间连接的边缘可以是有限的实数。我们为此问题提出了一般混合成员分布的模型。该模型没有边缘的分布限制，而是只有预期值，并且可以被视为某些以前模型的概括。我们使用高效的频谱算法来估计模型下的社区成员资格。我们还使用精致光谱分析来得出算法下提出算法的收敛速度。当边缘遵循不同的分布时，我们展示了混合成员资格分布模型的优势在于利用应用于小规模的模拟网络。

在网络分析中广泛研究了未加权网络的社区检测，但加权网络的情况仍然是一个挑战。在本文中，提出了一种可分布的模型（DFM），用于网络中的网络被划分为不同的社区。DFM是未加权网络和加权网络的一般，可解释和可识别的模型。所提出的模型不需要先前了解邻接矩阵元素的特定分布，但仅是预期值。DFM的无分配性能甚至允许邻接矩阵具有负元素。我们开发一种高效的谱算法来适合DFM。通过引入噪声矩阵，我们在扰动分析构建一个理论框架，以表明所提出的算法在DFM下稳定地产生一致的群落检测。综合网络和来自文献的两个社交网络的数值实验用于说明算法。

无向网络的混合隶属问题在网络分析中得到了很好的研究近年来。但是，对于定向网络的混合成员资格的更常例案例仍然是一个挑战。在这里，我们提出了一个可解释和可识别的模型：针对定向混合隶属网络定向混合成员资格随机块模型（短路）。 DIMMSB允许邻接矩阵的行节点和列节点可以是不同的，并且这些节点可以在定向网络中具有不同的社区结构。我们还开发了一种有效的谱算法，称为DISP，基于人口邻接矩阵的左右奇异矢量中固有的单纯x结构，以估计定向网络中的两行节点和列节点的混合成员资格。我们以使用精细光谱分析的每个行节点和每个列节点的推断成员载体和每个列节点的误差限制，显示该分辨率在温和条件下是渐近的一致性。我们展示了DISP与模拟定向混合会员网络，指导政治博客网络和论文引文网络的优势。

考虑带有$ k_ {r} $行社区和$ k_ {c} $列社区的定向网络。以前的作品发现，建模定向网络，其中所有节点都具有重叠属性需要$ k_ {r} = k_ {c} $ for可识别性。在本文中，我们提出了一个重叠和正当的模型，以研究指示网络，其中行节点在列节点不具有重叠的属性。当$ k_ {r} \ leq k_ {c} $时，所提出的模型是可识别的。同时，我们提供一个可识别的模型，作为ONM的扩展到模型的指导网络，具有节点度的变化。两种谱算法具有一致估计的理论保证，旨在适合模型。小规模的数值研究用于说明算法。

定向网络出现在各种领域，例如生物学，社会学，生理学和计算机科学。在本文中，我们构建一种基于邻接矩阵的奇异分解的光谱聚类方法，以检测定向随机块模型（DISBM）中的群落。通过考虑稀疏性参数，在轻度条件下，我们显示所提出的方法可以始终如一地恢复隐藏的行和列社区以进行不同程度的缩放。通过考虑行和列节点的程度异质性，我们进一步修改了所提出的方法，并为导向度校正随机块模型（DIDCSBM）建立理论框架，并显示了这种情况的修改方法的一致性。我们在DIBM和DIDCSBM下的理论结果提供了一些特殊定向网络的一些创新，例如具有平衡集群的定向网络，具有相似程度的节点的定向网络，以及指导的ERD \“OS-R”enyi图。此外，理论上，理论Didcsbm下的结果与分数下的结果一致。

网络可能具有弱信号和严重程度的异质性，并且可能在一次出现时非常稀疏，但在另一个发生中非常致密。得分（Jin，2015）是最近网络社区检测的方法。它适应严重的程度异质性，并适应不同水平的稀疏性，但它对具有弱信号的网络的性能尚不清楚。在本文中，我们认为，在广泛的网络设置中，我们允许弱信号，严重程度异质性和广泛的网络稀疏性，得分实现了完善的聚类，并且在汉明集群中具有所谓的“指数率”错误。证据对网络邻接矩阵的领先特征向量进行了最新的进出方程。理论分析向我们保证，在弱信号设置中，得分继续运行，但它不排除分数可以进一步提高的可能性，以在实际应用中具有更好的性能，特别是对于具有弱信号的网络。作为纸张的第二份贡献，我们提出得分+作为改进的分数版本。我们调查了8个网络数据集的得分+，发现它优于几种代表性的方法。特别是，对于具有相对强烈的信号的6个数据集，得分+具有与得分相似的性能，但对于2个数据集（Simmons，Caltech）具有可能弱信号，得分+的误差率较低。得分+提出了几个变化以得分。我们使用理论和数值研究的混合物仔细解释每个变化的基本原理。

我们提出了对学度校正随机块模型（DCSBM）的合适性测试。该测试基于调整后的卡方统计量，用于测量$ n $多项式分布的组之间的平等性，该分布具有$ d_1，\ dots，d_n $观测值。在网络模型的背景下，多项式的数量（$ n $）的数量比观测值数量（$ d_i $）快得多，与节点$ i $的度相对应，因此设置偏离了经典的渐近学。我们表明，只要$ \ {d_i \} $的谐波平均值生长到无穷大，就可以使统计量在NULL下分配。顺序应用时，该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作，因此在学位上有条件，因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法，即在测试$ K $社区时根据$（k+1）$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量，我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案，因此其效用超出了顺序测试，可用于同时测试DCSBM家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

网络研究中最根本的问题之一是社区检测。随机块模型（SBM）是一种流行的模型，具有不同的估计方法，其社区检测一致性结果揭晓。但是，SBM受到强烈假设的限制：同一社区中的所有节点在随机上都是等效的，这可能不适合实际应用。我们引入了成对协变量调整后的随机块模型（PCABM），这是SBM的概括，该模型包含成对协变量信息。我们研究协变量和社区分配系数的最大似然估计。结果表明，在适当的稀疏条件下，协变量和社区分配的系数估计均一致。引入了带有调节的光谱聚类（SCWA），以有效地求解PCABM。在某些条件下，我们得出了SCWA下社区检测的错误限制，并表明它是社区检测一致的。此外，研究了模型的选择，并研究了成对协变量的特征选择，并提出了两种相应的算法。当可访问协变量信息时，PCABM与SBM或学位校正的随机块模型（DCBM）进行比较。

光谱聚类是网络中广泛使用的社区检测方法之一。然而，大型网络为其中的特征值分解带来了计算挑战。在本文中，我们研究了从统计角度使用随机草图算法的光谱聚类，在那里我们通常假设网络数据是从随机块模型生成的，这些模型不一定是完整等级的。为此，我们首先使用最近开发的草图算法来获得两个随机谱聚类算法，即基于随机投影和基于随机采样的光谱聚类。然后，我们在群体邻接矩阵的近似误差，错误分类误差和链路概率矩阵的估计误差方面研究得到的算法的理论界限。事实证明，在温和条件下，随机谱聚类算法导致与原始光谱聚类算法相同的理论界。我们还将结果扩展到校正的程度校正的随机块模型。数值实验支持我们的理论发现并显示随机化方法的效率。一个名为rclusct的新R包是开发的，并提供给公众。

本文考虑了Pensky和Wang（2021）中引入的各种多重（Dimple）网络模型，该网络的所有层都具有相同的节点集合，并配备了随机块模型。此外，所有层都可以分为具有相同社区结构的组，尽管同一组中的层可能具有不同的块连接概率矩阵。 Dimple模型概括了许多论文，这些论文在所有层中研究具有相同社区结构的多层网络，以及混合物多层随机块模型（MMLSBM），同一组中的层具有相同的块连接概率的矩阵。彭斯基和王（2021）将光谱聚类应用于邻接张量的代理，而本文则使用稀疏的子空间聚类（SSC）来识别具有相同社区结构的层组。在轻度条件下，后者导致层间聚类非常一致。此外，SSC允许比Pensky和Wang（2021）的方法处理更大的网络，并且非常适合应用并行计算。

我们通过证明PABM是GRDPG的一种特殊情况，其中社区对应于潜在矢量的相互正交子空间，我们连接两个随机图模型，即受欢迎程度调整块模型（PABM）和广义随机点产品图（GRDPG）。这种见解使我们能够为PABM构建用于社区检测和参数估计的新算法，并改善了依赖稀疏子空间聚类的现有算法。利用邻接光谱嵌入GRDPG的渐近特性，我们得出了这些算法的渐近特性。特别是，我们证明，随着图形顶点的数量倾向于无穷大，社区检测误差的绝对数量趋于零。仿真实验说明了这些特性。

现实世界网络经常具有侧面信息，可以帮助提高网络分析任务等群集的性能。尽管在过去十年中对网络聚类方法进行了大量的实证和理论研究，但侧面信息的附加值和用于在聚类算法中最佳地结合的方法的附加值相对较少理解。我们向群集网络提出了一种新的迭代算法，其中包含节点的侧面信息（以协调因子的形式）提出并表明我们的算法在上下文对称随机块模型下是最佳的。我们的算法可以应用于一般上下文随机块模型，并避免与先前提出的方法相比，避免了HyperParameter调整。我们在综合数据实验中确认我们的理论结果，其中我们的算法显着优于其他方法，并表明它也可以应用于签名的图表。最后，我们展示了我们对实际数据方法的实际兴趣。

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this paper we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We establish the identifiability of our model and propose a computationally efficient estimation procedure based on the higher-order orthogonal iteration algorithm (HOOI) for tensor SVD composed with a simplex corner-finding algorithm. We then demonstrate the consistency of our estimation procedure by providing a per-node error bound, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the $\ell_{2,\infty}$ tensor perturbation bound for HOOI under independent, possibly heteroskedastic, subgaussian noise that may be of independent interest. Our analysis uses a novel leave-one-out construction for the iterates, and our bounds depend only on spectral properties of the underlying low-rank tensor under nearly optimal signal-to-noise ratio conditions such that tensor SVD is computationally feasible. Whereas other leave-one-out analyses typically focus on sequences constructed by analyzing the output of a given algorithm with a small part of the noise removed, our leave-one-out analysis constructions use both the previous iterates and the additional tensor structure to eliminate a potential additional source of error. Finally, we apply our methodology to real and simulated data, including applications to two flight datasets and a trade network dataset, demonstrating some effects not identifiable from the model with discrete community memberships.

随机奇异值分解（RSVD）是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $，原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数，$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中，我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性，即，观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $（频谱规范）和$ \ ell_ {2 \ to \ infty} $（最大行行列$ \ ell_2 $ norm）$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比（SNR）和功率迭代$ g $的数量。观察到一个相变现象，其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明，每当噪声矩阵满足一定的痕量生长条件时，这些相变发生的$ g $的阈值都会很清晰。最后，我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

当无法获得网络结构知识并且知识仅限于粗略摘要时，我们考虑大规模线性网络动力学系统的可控性。我们提供条件下，通过（合成，减少）粗尺度系统的平均可控性可以很好地近似细尺度系统的平均可控性。为此，我们需要了解精细尺度网络的某些固有参数结构，这使这种类型的近似结构成为可能。因此，我们假设潜在的细尺度网络是由随机块模型（SBM）生成的 - 经常在社区检测中进行研究。然后，我们提供了一种算法，该算法直接使用SBM的粗摘要直接估算细尺度系统的平均可控性。我们的分析表明，基本结构（例如，内建立的社区）的必要性能够准确地量化从粗体表征的网络动力学中的可控性。我们还将我们的方法与减少订单方法的方法进行比较，并突出显示了双方都可以相互表现的制度。最后，我们提供了模拟，以确认网络大小和密度不同尺度的理论结果，以及捕获粗略摘要中保留多少社区结构的参数。

本文研究了由$ N $-$ N $ TCONOR代表的非二进制对交互估计的社区成员资格，其值为$ \ MATHCAL S $的元素，其中$ N $是节点的数量和$ \ Mathcal S $是节点之间的成对交互的空间。作为信息理论基准，我们研究由非二进制随机块模型生成的数据集，并导致社区成员资格的基本信息标准作为$ n \ to \ idty $。应用程序的示例包括加权网络（$ \ mathcal s = \ mathbb r $），链接标记的网络$（\ mathcal s = \ {0,1，1，\ dots，l \} $），多路复用网络$（\ mathcal s = \ {0,1 \} ^ m $）和时间网络（$ \ mathcal s = \ {0,1 \} ^ t $）。对于时间互动，我们表明（i）即使是$ t $的少数增加也可能对社区成员的恢复产生了很大影响，（ii）即使对于非常稀疏的数据（例如\ in in inverly degress），甚至可能存在一致的恢复$ t $足够大。我们还提供了几种离线和在线的估计算法，它充分利用了观察到的数据的时间性。我们在数据稀疏性和可识别性的各种假设下分析所提出的估计算法的准确性。数值实验表明，即使是社区分配的初始估计（例如，盲目随机猜测）也会导致在少量迭代之后通过在线算法获得的高精度，并且在非常稀疏的方案中也是如此。

本文研究了聚类基质值观测值的计算和统计限制。我们提出了一个低级别的混合模型（LRMM），该模型适用于经典的高斯混合模型（GMM）来处理基质值观测值，该观测值假设人口中心矩阵的低级别。通过集成Lloyd算法和低级近似值设计了一种计算有效的聚类方法。一旦定位良好，该算法将快速收敛并达到最小值最佳的指数型聚类错误率。同时，我们表明一种基于张量的光谱方法可提供良好的初始聚类。与GMM相当，最小值最佳聚类错误率是由分离强度（即种群中心矩阵之间的最小距离）决定的。通过利用低级度，提出的算法对分离强度的要求较弱。但是，与GMM不同，LRMM的统计难度和计算难度的特征是信号强度，即最小的人口中心矩阵的非零奇异值。提供了证据表明，即使信号强度不够强，即使分离强度很强，也没有多项式时间算法是一致的。在高斯以下噪声下进一步证明了我们低级劳埃德算法的性能。讨论了LRMM下估计和聚类之间的有趣差异。通过全面的仿真实验证实了低级劳埃德算法的优点。最后，我们的方法在现实世界数据集的文献中优于其他方法。

The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i.e., assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still very limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML 2013] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to polylogarithmic factors) when the probability parameters are constant. As a byproduct, we obtain a polynomial-time algorithm with sublinear query complexity for a clustering problem with a faulty oracle, which finds all clusters of size larger than $\tilde{\Omega}({\sqrt{n}})$ even if $\Omega(n)$ small clusters co-exist in the graph. In contrast, all the previous efficient algorithms that makes sublinear number of queries cannot recover any large cluster, if there are more than $\tilde{\Omega}(n^{2/5})$ small clusters.

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

网络值时间序列是目前的网络数据的常见形式。然而，研究由网络价值随机过程产生的网络序列的总体行为相对较少。现有的大多数研究都集中在简单的设置上，其中网络在整个时间内是独立的（或有条件独立的），并且所有边缘在每个时间步骤均同步更新。在本文中，我们研究了聚集的邻接矩阵的浓度特性以及与懒惰网络值随机过程产生的网络序列相关的相应拉普拉斯矩阵，其中边缘异步不断地更新，并且每个边缘都遵循其懒惰的随机过程，以更新独立于其更新其他边缘。我们证明了这些集中度的有用性，从而证明了标准估计器在社区估计和变更点估计问题中的一致性。我们还进行了一项仿真研究，以证明懒惰参数的影响，该参数控制时间相关的程度，对社区和变化点估计的准确性。