网络数据分析中的基本技术挑战是社区的自动发现 - 紧密连接或具有相似功能或角色的节点组。在本评论中，我们回顾了过去20年的该领域的进度。

社区检测是网络科学中最重要的方法领域之一，在过去的几十年里引起了大量关注的方法之一。该区域处理网络的自动部门到基础构建块中，目的是提供其大规模结构的概要。尽管它的重要性和广泛的采用普及，所谓的最先进和实际在各种领域实际使用的方法之间存在明显的差距。在这里，我们试图通过根据是否具有“描述性”或“推论”目标来划分现有方法来解决这种差异。虽然描述性方法在基于社区结构的直观概念的网络中找到模式的模式，但是推理方法阐述了精确的生成模型，并尝试将其符合数据。通过这种方式，他们能够为网络形成机制提供见解，并以统计证据支持的方式与随机性的单独结构。我们审查如何使用推论目标采用描述性方法被陷入困境和误导性答案，因此应该一般而言。我们认为推理方法更通常与更清晰的科学问题一致，产生更强大的结果，并且应该是一般的首选。我们试图消除一些神话和半真半假在实践中使用社区检测时，努力改善这些方法的使用以及对结果的解释。

网络慷慨地，相似节点的趋势和传递性，连接两个节点的趋势如果它们共享公共邻居，则在网络分析中被混为特性，因为一个机制可以驱动另一个机制。在这里，我们提出了一种能够区分两个机制的生成模型和相应的推理过程。我们的方法基于随机块模型（SBM）的变化，增加了三合一封闭边缘，其推断可以识别负责网络中每个边缘存在的最合理的机制，以及基础社区结构本身。我们展示该方法如何避免通过网络中的三角形形成的单独引起的虚假社区的检测，以及它在与没有三合会的纯版本的纯版本相比，如何提高边缘预测的性能。

Stochastic blockmodels have been proposed as a tool for detecting community structure in networks as well as for generating synthetic networks for use as benchmarks. Most blockmodels, however, ignore variation in vertex degree, making them unsuitable for applications to real-world networks, which typically display broad degree distributions that can significantly distort the results.Here we demonstrate how the generalization of blockmodels to incorporate this missing element leads to an improved objective function for community detection in complex networks. We also propose a heuristic algorithm for community detection using this objective function or its non-degree-corrected counterpart and show that the degree-corrected version dramatically outperforms the uncorrected one in both real-world and synthetic networks.

网络表示学习（NRL）方法在过去几年中受到了重大关注，因此由于它们在几个图形分析问题中的成功，包括节点分类，链路预测和聚类。这种方法旨在以一种保留网络的结构信息的方式将网络的每个顶点映射到低维空间中。特别感兴趣的是基于随机行走的方法;这些方法将网络转换为节点序列的集合，旨在通过预测序列内每个节点的上下文来学习节点表示。在本文中，我们介绍了一种通用框架，以增强通过基于主题信息的随机行走方法获取的节点的嵌入。类似于自然语言处理中局部单词嵌入的概念，所提出的模型首先将每个节点分配给潜在社区，并有利于各种统计图模型和社区检测方法，然后了解增强的主题感知表示。我们在两个下游任务中评估我们的方法：节点分类和链路预测。实验结果表明，通过纳入节点和社区嵌入，我们能够以广泛的广泛的基线NRL模型表明。

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.

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

隐藏的社区是最近提出的一个有用的概念，用于社交网络分析。为了处理网络规模的快速增长，在这项工作中，我们从本地角度探讨了隐藏社区的检测，并提出了一种在从原始网络采样的子程目上迭代地检测和提升每个层的新方法。我们首先将根据我们修改的本地频谱方法从单个种子节点展开种子集，并检测初始占主导地位的本地社区。然后，我们暂时删除该社区的成员以及它们与其他节点的连接，并检测剩余子图中的所有邻居社区，包括一些“破坏社区”，该部分仅包含原始网络中的一部分成员。当地社区和邻里社区形成了一个主导层，通过减少这些社区内的边缘权重，我们削弱了这一层的结构来揭示隐藏的层。最终，我们重复整个过程，并且可以迭代地检测并升级包含种子节点的所有社区。理论上我们展示了我们的方法可以避免破碎的社区和当地社区被认为是子图中的一个社区的某些情况，导致对全球隐藏的社区检测方法可能引起的检测不准确。广泛的实验表明，我们的方法可以显着优于为全球隐藏社区检测或多个本地社区检测设计的最先进的基线。

社区检测和层级提取通常被认为是网络上的单独推理任务。考虑到研究真实数据时只有其中一个可以是一种过度简化。在这项工作中，我们提出了一种基于社区和分层结构之间的相互作用的生成模型。它假设每个节点在交互机制中的偏好和具有相同偏好的节点更有可能相互作用，而仍然允许异构交互。算法实现是有效的，因为它利用网络数据集的稀疏性。我们展示了我们对综合和实世界数据的方法，并比较了与社区检测和排名提取的两个标准方法的性能。我们发现该算法在不同场景中准确地检索每个节点的偏好，我们表明它可以区分表现出与大多数不同的节点的小子集。结果，该模型可以识别网络是否具有整体优选的交互机制。这在没有明确的“先验”信息的情况下是相关的，关于结构良好地解释了观察到的网络数据集。我们的模型允许从业者自动从数据中学习。

最近有一项激烈的活动在嵌入非常高维和非线性数据结构的嵌入中，其中大部分在数据科学和机器学习文献中。我们分四部分调查这项活动。在第一部分中，我们涵盖了非线性方法，例如主曲线，多维缩放，局部线性方法，ISOMAP，基于图形的方法和扩散映射，基于内核的方法和随机投影。第二部分与拓扑嵌入方法有关，特别是将拓扑特性映射到持久图和映射器算法中。具有巨大增长的另一种类型的数据集是非常高维网络数据。第三部分中考虑的任务是如何将此类数据嵌入中等维度的向量空间中，以使数据适合传统技术，例如群集和分类技术。可以说，这是算法机器学习方法与统计建模（所谓的随机块建模）之间的对比度。在论文中，我们讨论了两种方法的利弊。调查的最后一部分涉及嵌入$ \ mathbb {r}^ 2 $，即可视化中。提出了三种方法：基于第一部分，第二和第三部分中的方法，$ t $ -sne，UMAP和大节。在两个模拟数据集上进行了说明和比较。一个由嘈杂的ranunculoid曲线组成的三胞胎，另一个由随机块模型和两种类型的节点产生的复杂性的网络组成。

图形嵌入是图形节点到一组向量的转换。良好的嵌入应捕获图形拓扑，节点与节点的关系以及有关图，其子图和节点的其他相关信息。如果实现了这些目标，则嵌入是网络中有意义的，可理解的，可理解的压缩表示形式，可用于其他机器学习工具，例如节点分类，社区检测或链接预测。主要的挑战是，需要确保嵌入很好地描述图形的属性。结果，选择最佳嵌入是一项具有挑战性的任务，并且通常需要领域专家。在本文中，我们在现实世界网络和人为生成的网络上进行了一系列广泛的实验，并使用选定的图嵌入算法进行了一系列的实验。根据这些实验，我们制定了两个一般结论。首先，如果需要在运行实验之前选择一种嵌入算法，则Node2Vec是最佳选择，因为它在我们的测试中表现最好。话虽如此，在所有测试中都没有单一的赢家，此外，大多数嵌入算法都具有应该调整并随机分配的超参数。因此，如果可能的话，我们对从业者的主要建议是生成几个问题的嵌入，然后使用一个通用框架，该框架为无监督的图形嵌入比较提供了工具。该框架（最近在文献中引入并在GitHub存储库中很容易获得）将分歧分数分配给嵌入，以帮助区分好的分数和不良的分数。

图形嵌入是将网络的节点转换为一组向量。良好的嵌入应捕获底层图形拓扑和结构，节点到节点关系以及图形，其子图和节点的其他相关信息。如果实现了这些目标，则嵌入是网络的有意义，可以理解的，通常是压缩的。不幸的是，选择最好的嵌入是一个具有挑战性的任务，并且通常需要域名专家。在本文中，我们扩展了评估作者最近引入的图形嵌入的框架。现在，该框架为每个嵌入的嵌入分配两个分数，本地和全局，测量评估嵌入的嵌入的质量，以便分别需要良好地表示网络的全局属性。如果需要，最好的嵌入可以以无监督的方式选择，或者框架可以识别一些值得进一步调查的少数嵌入。该框架灵活，可扩展，可以处理无向/定向，加权/未加权图。

我们研究了流行群体质量指标的潜在偏见，例如电导或模块化。我们提出了一种方法，该方法使用随机和优先附加块模型构造来生成具有预设社区结构的网络，将应用质量指标。这些模型还允许我们生成不同强度的多级结构，这将显示指标是否有利于较大或更少数量的群集。另外，我们提出了另一种质量指标，密度比。我们观察到，即使它们的相对内部和外部连接是相同的，大多数研究的指标也倾向于倾向于倾向于将分区分成较少数量的大集群。发现偏置的度量较少是模块化和密度比。

我们对跨越各个领域的多种域的275个经验网络的随机块模型（SBM）的拟合质量和尺寸幅度的订单进行系统分析。我们采用后预测模型检查作为评估拟合质量的标准，这涉及根据一组网络描述符比较由经验网络的推断模型生成的网络。我们观察到SBM能够为大多数网络提供准确的描述，但缺乏所有建模要求。特别地，具有大直径和慢速混合随机步道的网络往往由SBM非常赘言。然而，与经常假设的相反，在许多情况下，SBM可以很好地描述具有高丰度三角形的网络。我们证明，简单的网络描述符可用于评估SBM是否可以提供足够准确的表示，可能指向可以系统地提高这类模型的表现力的可能模型扩展。

我们介绍了一个新型的多层加权网络模型，该模型除了本地信号外，还考虑了全局噪声。该模型类似于多层随机块模型（SBM），但关键区别在于，跨层之间的块之间的相互作用在整个系统中是常见的，我们称之为环境噪声。单个块还以这些固定的环境参数为特征，以表示不属于其他任何地方的成员。这种方法允许将块同时聚类和类型化到信号或噪声中，以便更好地理解其在整个系统中的作用，而现有块模型未考虑。我们采用了分层变异推断的新颖应用来共同检测和区分块类型。我们称此模型为多层加权网络称为随机块（具有）环境噪声模型（SBANM），并开发了相关的社区检测算法。我们将此方法应用于费城神经发育队列中的受试者，以发现与精神病有关的具有共同心理病理学的受试者社区。

Machine learning on graphs is an important and ubiquitous task with applications ranging from drug design to friendship recommendation in social networks. The primary challenge in this domain is finding a way to represent, or encode, graph structure so that it can be easily exploited by machine learning models. Traditionally, machine learning approaches relied on user-defined heuristics to extract features encoding structural information about a graph (e.g., degree statistics or kernel functions). However, recent years have seen a surge in approaches that automatically learn to encode graph structure into low-dimensional embeddings, using techniques based on deep learning and nonlinear dimensionality reduction. Here we provide a conceptual review of key advancements in this area of representation learning on graphs, including matrix factorization-based methods, random-walk based algorithms, and graph neural networks. We review methods to embed individual nodes as well as approaches to embed entire (sub)graphs. In doing so, we develop a unified framework to describe these recent approaches, and we highlight a number of important applications and directions for future work.

We consider an approach for community detection in time-varying networks. At its core, this approach maintains a small sketch graph to capture the essential community structure found in each snapshot of the full network. We demonstrate how the sketch can be used to explicitly identify six key community events which typically occur during network evolution: growth, shrinkage, merging, splitting, birth and death. Based on these detection techniques, we formulate a community detection algorithm which can process a network concurrently exhibiting all processes. One advantage afforded by the sketch-based algorithm is the efficient handling of large networks. Whereas detecting events in the full graph may be computationally expensive, the small size of the sketch allows changes to be quickly assessed. A second advantage occurs in networks containing clusters of disproportionate size. The sketch is constructed such that there is equal representation of each cluster, thus reducing the possibility that the small clusters are lost in the estimate. We present a new standardized benchmark based on the stochastic block model which models the addition and deletion of nodes, as well as the birth and death of communities. When coupled with existing benchmarks, this new benchmark provides a comprehensive suite of tests encompassing all six community events. We provide analysis and a set of numerical results demonstrating the advantages of our approach both in run time and in the handling of small clusters.

Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.

许多复杂网络的结构包括其拓扑顶部的边缘方向性和权重。可以无缝考虑这些属性组合的网络分析是可取的。在本文中，我们研究了两个重要的这样的网络分析技术，即中心和聚类。采用信息流基于集群的模型，该模型本身就是在计算中心的信息定理措施时构建。我们的主要捐款包括马尔可夫熵中心的广义模型，灵活地调整节点度，边缘权重和方向的重要性，具有闭合形式的渐近分析。它导致一种新颖的两级图形聚类算法。中心分析有助于推理我们对给定图形的方法的适用性，并确定探索当地社区结构的“查询”节点，从而导致群集聚类机制。熵中心计算由我们的聚类算法摊销，使其计算得高效：与使用马尔可夫熵中心为聚类的先前方法相比，我们的实验表明了多个速度的速度。我们的聚类算法自然地继承了适应边缘方向性的灵活性，以及​​边缘权重和节点度之间的不同解释和相互作用。总的来说，本文不仅具有显着的理论和概念贡献，还转化为实际相关性的文物，产生新的，有效和可扩展的中心计算和图形聚类算法，其有效通过广泛的基准测试进行了验证。

通常，使用网络编码在物理，生物，社会和信息科学中应用程序中复杂系统中实体之间的交互体系结构。为了研究复杂系统的大规模行为，研究网络中的中尺度结构是影响这种行为的构件。我们提出了一种新方法来描述网络中的低率中尺度结构，并使用多种合成网络模型和经验友谊，协作和蛋白质 - 蛋白质相互作用（PPI）网络说明了我们的方法。我们发现，这些网络拥有相对较少的“潜在主题”，可以成功地近似固定的中尺度上网络的大多数子图。我们使用一种称为“网络词典学习”（NDL）的算法，该算法结合了网络采样方法和非负矩阵分解，以学习给定网络的潜在主题。使用一组潜在主题对网络进行编码的能力具有多种应用于网络分析任务的应用程序，例如比较，降解和边缘推理。此外，使用我们的新网络去核和重建（NDR）算法，我们演示了如何通过仅使用直接从损坏的网络中学习的潜在主题来贬低损坏的网络。