标题： 局部三元系数的高效自适应估计 显示英文标题

标题： Efficient and Adaptive Estimation of Local Triadic Coefficients

摘要： 表征图属性是分析和理解现实世界网络系统的基础。局部聚类系数，以及最近引入的局部闭合系数，捕获了在大量应用中至关重要的强大属性，从图嵌入到图划分。这些系数捕捉每个节点邻域的局部密度，考虑了三元结构和长度为二的路径。因此，我们将这些系数统称为局部三元系数。在本工作中，我们考虑了一个新颖的问题，即高效计算输入图中节点被划分为一组不相交的桶时的局部三元系数的平均值。每个桶中节点的平均局部三元系数提供了对图结构和与每个桶相关的节点属性之间相互作用的更好洞察。不幸的是，精确计算需要列出图中的所有三角形，在大型网络中是不可行的。因此，我们专注于获得高度准确的概率估计。我们开发了Triad，一种基于采样的自适应算法，可用于估计将节点划分为桶时的平均局部三元系数。Triad基于一类新的无偏估计器，以及对其样本复杂度的非平凡界限，使得可以高效地计算高度准确的估计。最后，我们展示了Triad如何在实践中高效地用于大型网络，并展示了一个案例研究，表明平均局部三元系数可以捕捉合作网络上的高阶模式。 显示英文摘要

摘要： Characterizing graph properties is fundamental to the analysis and to our understanding of real-world networked systems. The local clustering coefficient, and the more recently introduced, local closure coefficient, capture powerful properties that are essential in a large number of applications, ranging from graph embeddings to graph partitioning. Such coefficients capture the local density of the neighborhood of each node, considering incident triadic structures and paths of length two. For this reason, we refer to these coefficients collectively as local triadic coefficients. In this work, we consider the novel problem of computing efficiently the average of local triadic coefficients, over a given partition of the nodes of the input graph into a set of disjoint buckets. The average local triadic coefficients of the nodes in each bucket provide a better insight into the interplay of graph structure and the properties of the nodes associated to each bucket. Unfortunately, exact computation, which requires listing all triangles in a graph, is infeasible for large networks. Hence, we focus on obtaining highly-accurate probabilistic estimates. We develop Triad, an adaptive algorithm based on sampling, which can be used to estimate the average local triadic coefficients for a partition of the nodes into buckets. Triad is based on a new class of unbiased estimators, and non-trivial bounds on its sample complexity, enabling the efficient computation of highly accurate estimates. Finally, we show how Triad can be efficiently used in practice on large networks, and we present a case study showing that average local triadic coefficients can capture high-order patterns over collaboration networks.