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

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

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

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

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

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

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

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

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.

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

随机奇异值分解（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的粗摘要直接估算细尺度系统的平均可控性。我们的分析表明，基本结构（例如，内建立的社区）的必要性能够准确地量化从粗体表征的网络动力学中的可控性。我们还将我们的方法与减少订单方法的方法进行比较，并突出显示了双方都可以相互表现的制度。最后，我们提供了模拟，以确认网络大小和密度不同尺度的理论结果，以及捕获粗略摘要中保留多少社区结构的参数。

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.

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

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

社区检测和正交组同步是科学和工程中各种重要应用的基本问题。在这项工作中，我们考虑了社区检测和正交组同步的联合问题，旨在恢复社区并同时执行同步。为此，我们提出了一种简单的算法，该算法由频谱分解步骤组成，然后是彼此枢转的QR分解（CPQR）。所提出的算法与数据点数线性有效且缩放。我们还利用最近开发的“休闲一淘汰”技术来建立近乎最佳保证，以确切地恢复集群成员资格，并稳定地恢复正交变换。数值实验证明了我们算法的效率和功效，并确认了我们的理论表征。

随着大型网络在重要领域的相关领域的相关性，例如对疾病传播的联系网络的研究，或社交网络对地缘政治的影响，已经有必要研究可扩展到非常大的网络的机器学习工具，通常包含数百万节点。一种主要类别可扩展算法称为网络表示学习或网络嵌入。这些算法尝试通过首次运行多个随机散步，然后使用观察到的随机步行段中的每对节点的共同数量来学习网络功能（例如〜节点）的表示，以获得一些节点的低维表示欧几里德空间。本文的目的是严格地了解两个主要算法，深途化和Node2VEC的性能，以恢复与地面真理社区的规范网络模型的社区。根据图的稀疏性，我们发现所需的随机步道段的长度，使得相应的观察到的共生窗口能够对底层社区分配的几乎精确恢复。我们证明，考虑到一些固定的共同发生窗口，使用随机散步的Node2Vec与低横向概率的随机散步可以相比，与使用简单随机散步的深度扫视相比，稀疏网络可以成功。此外，如果稀疏参数低，我们提供了证据表明这些算法几乎完全恢复可能不会成功。该分析需要开发用于对具有底层低级结构的随机网络计数的通用工具，这与独立兴趣。

网络分析一直是揭示大量对象之间关系和交互的强大工具。然而，它在准确识别重要节点节点相互作用的有效性受到快速增长的网络规模的挑战，数据以空前的粒度和规模收集。克服这种高维度的共同智慧是将节点崩溃成较小的群体，并在小组级别进行连通性分析。将努力分为两个阶段不可避免地打开了一致性的差距，并降低了效率。共识学习是通用知识发现的新常态，并具有多个可用的数据源。为此，本文以组合多个数据源来开发同时分组和连接分析的统一框架。该算法还保证了统计上最佳的估计器。

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

本文研究了一般D-均匀的HyperGraph随机块模型（D-HSBM）中精确恢复的基本限制，其中n个节点被分配到具有相对大小的k差异群落中（p1，...，pk）。具有基数d的节点的每个子集都是独立生成的，作为订单-D超边，其一定概率取决于D节点所属的地面真相群落。目标是根据观察到的超图准确地恢复K隐藏的社区。我们表明存在一个尖锐的阈值，因此可以在阈值之上实现精确的恢复，而不可能在阈值以下（除了将精确指定的小参数制度之外）。该阈值是根据我们称为社区之间普遍的Chernoff-Hellinger分歧的数量来表示的。我们对该通用模型的结果恢复了标准SBM和D-HSBM的先前结果，其中两个对称群落作为特殊情况。在证明我们的可实现结果的途径中，我们开发了一种符合阈值的多项式两阶段算法。第一阶段采用某种超图光谱聚类方法来获得社区的粗略估计，第二阶段通过局部细化步骤单独完善每个节点，以确保精确恢复。