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

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

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

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

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

网络可能具有弱信号和严重程度的异质性，并且可能在一次出现时非常稀疏，但在另一个发生中非常致密。得分（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家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

随机奇异值分解（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的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

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

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

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

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

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

我们在非均匀超图随机块模型（HSBM）下的稀疏随机超图中的社区检测问题，是社区结构的随机网络的一般模型和高阶交互。当随机超图具有界定的预期度时，我们提供了一种频谱算法，该频谱算法输出分区，其中至少有$ \ gamma $分数正确分类，其中$ \ gamma \ in（0.5,1）$取决于信号 - 模型的噪声比（SNR）。当SNR随着顶点的数量转到无限的时，SNR慢慢地增长，我们的算法达到了弱的一致性，这改善了Ghoshdastidar和Dukkipati（2017）的上一个结果，用于非均匀的HSBMS。我们的谱算法由三个主要步骤组成：（1）HIFFEGE选择：选择某些尺寸的超高率，为诱导的子图像提供最大信噪比; （2）光谱分区：构造正则化邻接矩阵，并基于奇异向量获得近似分区; （3）纠正和合并：将超代表信息从邻接张于升级升级错误率保证。我们的算法的理论分析依赖于稀疏非均匀随机超图的邻接矩阵的浓度和正则化，这可以是独立的兴趣。

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.

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

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

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

我们在一般随机块模型下研究现实网络中的社区层次结构，其中连接概率在二叉树中构造。在这种模型中，标准递归双分区算法基于非通知图拉普拉斯的Fiedler向量将网络分成两个社区，并重复分割，直到停止规则指示不进一步的社区结构。我们在广泛的模型参数下证明了这种方法的强大一致性，它包括稀疏网络，节点度为$ O（\ log n）$。此外，与大多数现有工作不同，我们的理论涵盖了多尺度网络，其中连接概率可能因数量级而异，这包括一类实际相关但技术上挑战处理的重要阶段。最后，我们展示了我们对综合性数据和实际示例算法的表现。

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