图的度分布的可证明和实用的近似

4490使用次线性图样本对度分布进行可证明和实用的近似�†0TalyaEden计算机科学学院，特拉维夫大学特拉维夫，以色列talyaa01@gmail.com0ShwetaJain加利福尼亚大学圣克鲁兹分校圣克鲁兹，加利福尼亚州，美国sjain12@ucsc.edu0AliPinar桑迪亚国家实验室利弗莫尔，加利福尼亚州apinar@sandia.gov0DanaRon计算机科学学院，特拉维夫大学特拉维夫，以色列danaron@tau.ac.il0C.Seshadhri加利福尼亚大学圣克鲁兹分校圣克鲁兹，加利福尼亚州sesh@ucsc.edu0摘要0度分布是分析大规模图的最基本属性之一。有大量关于图采样的文献，其目标是通过小型随机样本估计大型图的属性（特别是度分布）。由于真实世界图的重尾特性和度数的大方差，估计真实世界图的度分布是一个重大挑战。我们设计了一个新算法SADDLES来解决这个问题，使用了次线性算法领域的最新数学技术。当这些指标很大时，SADDLES算法可以提供可证明的准确输出。我们定义了度分布的两个肥胖度量，称为h指数和z指数。我们证明了当这些指标很大时，SADDLES在图的规模上是次线性的。这个结果的一个推论是，对于下界为幂律的任何度分布，我们可以提供一个可证明的次线性算法。我们在各种真实数据集上部署了我们的新算法，并展示了其出色的实证行为。在所有实例中，通过观察最多1%的顶点，我们可以获得度分布中所有值的极其准确的近似值。这是对现有采样算法的重大改进，后者通常需要采样超过10%的顶点才能提供可比较的结果。我们还观察到真实图的h和z指数很大，验证了我们的理论分析。0ACM参考格式：Talya Eden，Shweta Jain，Ali Pinar，Dana Ron和C.Seshadhri。2018年。使用次线性图样本对度分布进行可证明和实用的近似。0� 该工作由Sandia LDRD计划，以色列科学基金会资助，Azrieli奖学金和NSFTRIPODS资助CCF-1740850。本工作的一部分是在算法和不确定性的Simons研究所学期上启动的。† Talya Eden和ShwetaJain对这项工作做出了相等的贡献，并共同成为本工作的第一作者。0本文根据知识共享署名4.0国际（CC BY4.0）许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861110次线性图样本。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318611101 引言0在社会科学、生物学、物理学、网络安全等领域，图被用来表示实体及其之间的关系。这导致了过去十年网络科学作为一门学科的爆炸式增长。网络科学的一个标志性特征是特定的图属性，在不同领域中是共同的，例如重尾度分布、大聚类系数和小世界行为。度分布尤其重要，因为现代网络科学的早期阶段就有了它[7, 8,21]。给定一个无向图G，度分布（或技术上称为直方图）是数字序列n(1)，n(2)，...，其中n(d)是度为d的顶点的数量。在几乎所有的真实世界场景中，平均度数很小，但方差（和更高的矩）很大。即使对于相对较大的d，n(d)仍然非零，并且n(d)通常具有平滑的非递增行为。在图1中，我们可以看到典型的度分布行为。Google网络中的平均度数小于10，但最大度数超过5000。还有许多具有所有中间度数的顶点。这被称为“重尾"分布。度分布，尤其是尾部，对于建模网络、确定其韧性、信息传播和算法学[6, 9, 13, 16, 34-37,43]具有重要意义。通过完全访问G，可以通过简单地确定每个顶点的度数来计算度分布。然而，在许多情况下，我们只能通过一些图样本来部分访问图。对度分布的天真外推可能导致有偏差的结果。Faloutsos等人的开创性研究论文声称互联网上的度分布遵循幂律分布[21]。这个度分布是通过对一组路由器进行一系列traceroute查询生成的图样本中测量幂律分布得出的。不幸的是，数学和实证证明，即使真实网络不是幂律分布，traceroute响应也可能具有幂律分布[1, 11,28,38]。通常，直接从图子样本外推度分布对于底层图是无效的。这引出了我们工作背后的主要问题。如何在不看完整图的情况下可证明地和实际地估计度分布？在统计学、数据挖掘和物理学中，有丰富的关于使用小样本估计图属性（特别是度分布）的文献[2, 3, 5, 17, 29,31, 32, 40, 45,46]。然而，对于整个度分布，没有可证明的算法，也没有对顶点数量的次线性分析。此外，大多数经验研究通常对10-30%的顶点进行采样以获得合理的估计。0研究方向：社交网络分析和Web上的图算法WWW 2018，2018年4月23日至27日，法国里昂degree distribution from a graph subsample is not valid for theunderlying graph. This leads to the primary question behind ourwork.How can we provably and practically estimate the degreedistribution without seeing the entire graph?There is a rich literature in statistics, data mining, and physicson estimating graph properties (especially the degree distribution)using a small subsample [2, 3, 5, 17, 29, 31, 32, 40, 45, 46].Nonetheless, there is no provable algorithm for the entire degreedistribution, with a formal analysis on when it is sublinear in thenumber of vertices. Furthermore, most empirical studies typicallysample 10-30% of the vertices for reasonable estimates.45001.1 问题描述0我们关注G的互补累积度直方图（通常称为累积度分布）或ccd。这是序列{N(d)}，其中N(d)=�r≥dn(r)是度至少为d的顶点的数量。ccd通常用于拟合分布，因为它平均了噪声并且是单调的[12]。我们的目标是在所有d的值上获得对G的ccdh的准确的双标准近似。0定义1.1. 如果对于任意的d，(1-ε)N((1+ε)d) ≤ �N(d) ≤(1+ε)N((1-ε)d)，那么序列{�N(d)}是ccd的(ε,ε)估计。0使用标准分布度量估计ccd比计算(ε,ε)估计要困难得多。统计度量，如KS距离、χ2、ℓp范数等，往往忽略尾部，因为（就概率质量而言）它只占分布的一小部分。(ε,ε)估计对于所有d都是准确的。查询模型：正式方法需要指定对G进行访问的查询模型。我们在理论计算机科学的属性测试和次线性算法的子领域中寻找这些模型[23,24]。考虑以下三种查询类型。•顶点查询：获取一个均匀随机的顶点v∈V。•邻居查询：给定v∈V，获取一个均匀随机的邻居u ofV。•度查询：给定v∈V，获取度数dv。算法只允许对输入进行这些查询以处理。它必须进行一些查询，并最终产生一个输出。我们讨论两种查询模型，并为两种模型给出结果。0标准模型（SM）允许所有查询：这是许多亚线性算法结果中的标准模型[19, 20,23-25]。此外，大多数关于图采样的论文隐式地使用此模型生成子样本。实际上，任何涉及从随机顶点集合爬行并收集度数的方法都属于SM。该模型是我们工作的主要设置，并允许与丰富的图采样算法进行比较。值得注意的是，在SM中，可以在O(n logn)的查询次数内确定整个度分布（额外的logn因子来自于通过均匀采样找到所有顶点的优惠券收集器界限）。因此，将算法的查询次数表示为n的一部分是有意义的。或者，查询次数基本上是算法遇到的顶点数。因此，亚线性算法进行o(n)次查询。0隐藏度模型（HDM）允许顶点和邻居查询，不允许度查询：这是一个相对较弱的模型。在许多网络安全和网络监控的情况下，算法不能查询度数，而必须间接地推断它们。可以观察到，该模型比SM要困难得多。确定所有度数需要O((m + n) logn)的时间，因为至少需要访问所有边来准确找到度数。在该模型中，我们将查询次数表示为m的一部分。0关于均匀随机顶点查询：这是一个相当强大的查询，在所有情况下可能都无法实现。事实上，Chierichetti等人明确研究了社交网络中的这个问题，并设计了（非平凡的）算法来采样均匀随机顶点[10]。在以前的工作中，Dasgupta、Kumar和Sarlos研究了仅能进行随机游走时估计平均度数的算法[14]。尽管具有这种能力，我们认为SM是理解当对图的一个小样本可以可靠地给出整体特性时的一个很好的试验平台。此外，在图采样的背景下，通常（隐式地）假设可以访问均匀随机顶点[5, 17, 29, 31, 39, 40,46]。绝大多数进行的实验经常使用均匀随机顶点。作为未来的方向，我们认为研究没有随机顶点查询的采样模型是重要的。01.2 我们的贡献0我们的主要理论结果是一种新的采样算法，称为SublinearApproximations for Degree Distributions Leveraging EdgeSamples（SADDLES）。该算法可以证明地提供ccdh的(ε,ε)-近似。我们展示了如何在SM和HDM两种模型下设计SADDLES。我们将SADDLES应用于各种真实数据集，并展示其能够通过对图的微小样本准确近似ccdh的能力。•用于估计ccdh的采样算法：我们的算法结合了随机采样中的多种技术，以获得ccdh的(ε,ε)-估计。其中一个关键组成部分是一种边缘模拟技术的应用，该技术最初由Eden等人在三角形计数的背景下设计[19,20]。这种（理论上的）技术展示了如何从独立均匀顶点中获得一组弱相关的均匀随机边。SADDLES在此方法之上采用了一种加权方案来估计ccdh。•重尾导致亚线性算法：分析SADDLES的挑战在于找到允许亚线性查询复杂度的ccdh参数。为此，我们讨论了两个度分布“尾部重度”的参数：经典的h指数和新定义的z指数。我们证明了当这些指数较大时，SADDLES的查询复杂度在两种模型下都是亚线性的。•出色的实证行为：我们在一系列大型真实世界图上部署了SADDLES的实现。在所有实例中，我们通过对图的最多1%的顶点进行采样，实现了对整个ccdh的极其准确的估计。请参考图1。观察SADDLES如何跟踪图1中所有图的ccdh的各种跳变。•与现有采样方法的比较：实际上已经提出了许多图采样方法，例如顶点采样（VS），雪球采样（OWS），森林火采样（FF），诱导图采样（IN），随机游走（RWJ），边缘采样（ES）[5, 17, 29, 31, 39,40,46]。Zhang等人最近的一项工作明确解决了这些采样方法中的偏差问题，并使用优化技术进行了修正[46]。我们与所有这些采样方法进行了直接比较，并展示了SADDLES在实际性能上明显更好。图1显示了所有这些采样方法的输出，总样本量为顶点数的1%。可以观察到，在整个度分布中，这些方法都对大部分程度的估计出现错误。对于所有方法，误差也非常大。这与以前的工作一致，其中的方法对顶点数进行了超过10%的采样。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceIn most real-world instances, the average degree d is typicallyconstant. Thus, the complexities above are strongly sublinear. Forexample, when γ = 2, we get �O(n1/2) for both models. When γ = 3,we get �O(n2/3) and �O(n3/4).Our main result is more nuanced, and holds for all degreedistributions. If the ccdh has a heavy tail, we expect N (d) tobe reasonably large even for large values of d. We describe twoformalisms of this notion, through fatness indices.4510(a) amazon0601购买网络0(b) web-Google网络0(c) cit-Patents引用网络0(d) com-orkut社交网络0图1：SADDLES在一系列网络上的输出：amazon0601（403K个顶点，4.9M条边），web-Google（870K个顶点，4.3M条边），cit-Patents（3.8M个顶点，16M条边），com-orkut社交网络（3M个顶点，117M条边）。SADDLES对图的1%的顶点进行采样，并对整个（累积）度分布给出准确的结果。为了比较，我们展示了过去工作中一些采样算法的输出，每个算法使用相同数量的样本。（由于com-Orkut的规模，涉及优化的方法[46]无法在合理的时间内产生估计值。）0边缘采样（ES）[5, 17, 29, 31, 39, 40,46]。Zhang等人最近的一项工作明确解决了这些采样方法中的偏差问题，并使用优化技术进行了修正[46]。我们与所有这些采样方法进行了直接比较，并展示了SADDLES在实际性能上明显更好。图1显示了所有这些采样方法的输出，总样本量为顶点数的1%。可以观察到，在整个度分布中，这些方法都对大部分程度的估计出现错误。对于所有方法，误差也非常大。这与以前的工作一致，其中的方法对顶点数进行了超过10%的采样。01.3 详细的理论结果0我们的主要理论结果是一种新的采样算法，称为SublinearApproximations for Degree Distributions Leveraging EdgeSamples（SADDLES）。我们首先展示了我们对幂律度分布[7, 8,21]的结果。统计拟合过程表明它们在现实世界中以某种程度存在，尽管存在很多噪声[12]。经典的幂律度分布设置为n(d) ∝ 1 / dγ，其中γ通常在[2, 3]之间。我们在此基础上建立了一个幂律下界。0定义1.2. 固定γ >2。如果ccdh满足以下性质，则度分布受到下界为幂律的限制，指数为γ。存在常数τ > 0，使得对于所有d，N(d) ≥ � τn / d γ  − 1 �。0以下是我们主要结果的一个推论。为了方便起见，我们将省略ε和logn因子对查询复杂度的依赖，使用� O(∙)表示。0定理1.3.假设G的度分布受到下界为幂律的限制，指数为γ。平均度数用d表示。对于任意ε > 0，SADDLES算法以很高的概率输出(ε,ε)-近似的ccdh，并且进行以下操作0以下是查询次数的数量。对于SM：� O(n 1 − 10γ − 1 d)。对于HDM：� O(n 1 − 10定义1.4.度分布的h指数是最大的d，使得至少有d个度至少为d的顶点。0这正是文献计量学的h指数的类比[27]。正如我们在§2.1中所示，h可以通过min d (d + N(d)) /2来近似。通过用（较小的）几何平均代替算术平均值可以得到更严格的指数。0定义1.5. 度分布的z指数是z = min d : N(d) > 00d ∙0我们的主要定理断言，大的h和z指数导致度分布估计的亚线性算法。定理1.3是通过为幂律插入指数的值直接得到的推论。0定理1.6. 对于任意ε >0，SADDLES算法输出（高概率下的）ccd的（ε，ε）-近似，并进行以下数量的查询。对于SM：O(n / h + m / z^2)。对于HDM：O(m/ z)。01.4 挑战和主要思路0真实度分布的重尾行为对于计算（ε，ε）-ccd估计构成了主要挑战。当N(d)很小时，抽样均匀随机顶点是低效的。随机顶点的随机邻居更有可能是高度顶点。这是OWS、FF、RWJ图样本保持等方法的思想[5,17,29,31,39,40,46]。但是这些方法会导致有偏样本，因为具有相同度数的顶点可能以不同的概率被选择。0Track: 社交网络分析和Web上的图算法 WWW 2018年4月23日至27日，法国里昂4520直接外推/缩放观察到的图中的度数无法提供准确的估计。我们的实验表明，现有方法总是错过头部或尾部。从数学的角度来看，绝大多数现有结果倾向于分析KS统计量或某些ℓp范数。正如我们之前提到的，这对于在所有尺度上衡量估计质量效果不好。正如我们的实验所示，这些方法都不能在少于5%的顶点下对整个ccd进行准确估计。SADDLES中的主要创新来自于最近的理论技术，通过顶点样本模拟边样本[19,20]。边的抽样分为两个阶段。在第一阶段，算法对一组r个顶点进行抽样，并建立一个在抽样顶点上的分布，使得与抽样顶点相邻的任何边都可以以均匀概率进行抽样。在第二阶段，它从该分布中抽样q条边。虽然单个边是均匀随机的，但边的集合是相关的。对于给定的d，我们定义边上的权重函数，使得总权重恰好为N(d)。SADDLES通过对生成的边样本的平均权重进行缩放来估计总权重。分析的困难在于边之间的相关性。我们的主要见解是，如果度分布具有重尾，即使对于亚线性的r和q，这种相关性也可以被控制。具体而言，这是通过将样本的平均权重的集中行为与h和z指数相关联来实现的。最终算法将这个思想与顶点抽样相结合，以获得所有d的准确估计。使用Ron和Tsur[42]的生日悖论技术处理HDM。可以使用O(√dv)邻居查询来估计度dv。但是这会给算法增加开销，特别是对于尾部的ccd估计。正如前面讨论的，我们需要偏向于更高度的方法，但这会显著增加实际估计度的查询成本。01.5 相关工作0有大量的文献关于生成一个图样本，以揭示更大的“真实”图的图属性。我们不试图对这个文献进行全面调查，只参考与我们的工作直接相关的结果。Leskovec＆Faloutsos [31]，Maiya＆Berger-Wolf[32]和Ahmed，Neville，＆Kompella[2,5]的作品提供了关于多种抽样方法的优秀调查。有许多基于随机遍历的抽样方法：森林火[31]，雪球抽样[32]和扩展抽样[31]。正如以前的工作详细说明的那样，这些方法倾向于偏向网络的某些部分，这可以用于更准确地估计各种属性[31,32,40]。Ahmed，Neville和Kompella[2-5]的一系列论文提出了结合随机顶点和边缘的替代抽样方法，以获得更好的代表性样本。所有这些结果旨在使用单个图样本捕捉图的许多属性。尽管如此，有很多以度分布为重点的先前工作。Ribiero和Towsley [40]和Stumpf和Wiuf[45]专门研究度分布。Ribiero和Towsley[40]对度分布进行了详细分析。0估计（他们也看ccd）各种这些抽样方法。他们的实证结果显示，无论是在头部还是尾部都存在显著的误差。我们注意到，几乎所有这些结果最终都会抽样到20%的图来估计度分布。张等观察到许多抽样方法的度分布是真实分布的随机线性投影[46]。他们试图反转这个（病态）线性问题，以纠正偏差。这导致估计改进，但经验研究通常需要抽样超过10%的顶点才能获得良好的估计。一些方法尝试匹配分布的形状/族群，而不是整体估计[45]。因此，统计方法可以用来估计分布的参数。但是，已经相当确定实际世界的度分布在大多数情况下很少是纯的幂律[12]。确实，拟合幂律是相当具有挑战性的，对数-对数图上的天真回归拟合是错误的，正如Clauset-Shalizi-Newman的结果所示[12]。理论计算机科学中的稀疏图的性质测试和亚线性算法子领域可以被认为是对图抽样进行性质估计的形式化。实际上，我们对主要问题的描述遵循这种语言。在这个领域有非常丰富的数学工作（参考Ron的调查[41]）。图属性测试的实际应用非常罕见，我们只知道以前有一项应用于查找路由器网络中密集核心的工作[26]。估计平均度（或总边数）的具体问题由Feige[22]和Goldreich-Ron[24]研究。Gonen等人和Eden等人专注于估计度分布的高阶矩[20,25]。我们使用的模拟边查询的主要技术之一是在Eden等人的亚线性算法结果中开发的[19,20]，用于三角形计数和度矩估计。我们强调所有这些结果都是纯理论的，它们的实用性绝非显而易见。在实践方面，Dasgupta，Kumar和Sarlos研究了实际图中的平均度估计，并开发了替代算法[14]。他们要求图具有低混合时间，并证明算法在实践中表现出色（与Feige和Goldreich-Ron算法的实现[22,24]相比）。Dasgupta等人指出，在许多情况下，无法对均匀随机顶点进行抽样，因此他们考虑了比SM或HDM弱得多的设置。Chierichetti等人专注于使用仅使用一小组种子顶点和邻居查询来抽样均匀随机顶点[10]。我们注意到，有大量关于从流中抽样图的工作[33]。这与我们的设置非常不同，因为流算法至少观察每条边一次。Simpson等人考虑了在所有尺度上估计度分布的具体问题[44]。他们观察到我们之前提到的许多挑战：准确估计尾部的困难，找到各个度量尺度的顶点，并结合头部和尾部的估计。02 预备知识0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, 2018年4月23-27日，法国里昂4530对于顶点  v ，令  Γ( v )  为  v  的邻域，  d v  为度数。如前所述，  n( d )  是度数为  d  的顶点数，  N  ( d )  = � r  ≥ d n ( r )  是  d的累积度分布函数。我们使用“u.a.r.”作为“uniform atrandom”的缩写。我们强调，所有关于概率和误差的提及都是针对采样算法的随机性而言的。输入图 G 上没有随机假设。我们使用  A∈  ( 1  ±  α ) B  表示  A  ∈  [ ( 1  −  α ) B ,  ( 1  +  α ) B]。我们将应用以下（重新缩放的）切尔诺夫界。0定理2.1. [15中的定理1] 设 X 1 ， X 2 ， . . . ， X k  是具有期望值µ  的独立同分布的随机变量序列。此外， X i  ∈  [0 ,  B ] 。• 对于  ε <  1 ，  Pr[ | � k i = 1 X i  −  µk | ≥  εµk ]  ≤  2 exp ( − ε 2 µk / 3B ) 。• 对于  t  ≥  2 eµ ，  Pr[ � k i = 1 X i  ≥  tk ]  ≤  2 − tk / B 。02.1 关于Fatness指标的更多内容0（本节中的所有证明都是相当直接的计算，因此在此版本中省略。）下面对  h -index 的特征进行了描述。由于  ( d  +  N  ( d )) / 2  ≤max ( d ,  N  ( d ))  ≤  d  +  N  ( d ) ，这证明了  min d  ( d  +  N( d )) / 2 是对  h -index 的2倍近似。0引理2.2. min d  max ( d ,  N  ( d ))  ∈ { h , h0  h -index 不会在不同尺度上测量  d  与  N  ( d )  的差异，而且大的 h -index仅确保存在足够多的高度顶点。例如，h-index不能区分两个不同分布，其累积度分布函数  N 1  和  N 2  满足 N 1 ( 100 )  =  100 且N 1 ( d )  =  0 （对于  d  >  100）以及  N 2 ( 100 ,  000 )  =  100且  N 2 ( d )  =  100 （对于所有  d  ≥  100）。这两种情况下的  h-index 都是100。  h -index 和  z -index 是相互关联的。0命题2.3. √0h  ≤  z  ≤  h0为了对这些指标有一些直观理解，我们计算幂律的  h  和  z指标。经典的幂律度分布设置为  n ( d )  ∝  1 / d γ ，其中  γ通常在 [2 ,  3] 范围内。0命题2.4. 如果度分布在下界上受到幂律的限制，那么  h  =  Ω( n 1 / ( γ  − 1 )  ) 。0指数  γ ，那么  h  =  Ω( n 1 γ  ) 且  z  =  Ω( n 102 ( γ  − 10将  γ  =  2 代入值，  h  和  z  都是  Ω( √ n ) 。将  γ=  3 代入值，  h  =  Θ( n 1 / 3 ) 且  z  =  Θ( n 1 / 4 )。2.2 模拟HDM的度查询0HDM不允许查询顶点  v  的度数  d v。然而，可以使用生日悖论的论证方法（由Ron和Tsur[42]形式化）通过对  v的u.a.r.邻居（带替换）进行采样，直到看到相同的顶点来获得  d v的准确估计。如果这发生在  t  个样本之后，  t 2 是  d v的一个常数因子近似。以下结果可以直接从[42]的定理3.1中获得（在此版本中省略了细节）。0推论2.5. 存在一个算法 DEG ，它以顶点  v作为输入，并具有以下特性：• 对于所有的  v ：以概率  >  1  −  1 /n 3 ，输出  DEG ( v )  在 ( 1  ±  ε / 10 ) d v 之间。•  DEG ( v )的期望运行时间和查询复杂度为 O ( ε − 2 √ d v  log n ) 。0我们将假设具有相同参数的DEG调用使用相同的随机位序列。或者，可以想象调用 DEG ( v )时存储输出，因此后续调用输出相同的值。为了分析方便，可以想象DEG ( v )  对所有顶点  v  只调用一次，并且这些结果被存储。0定义2.6. 输出 DEG ( v )  用 ˆ d v表示。在所有对DEG的调用中使用的随机位统称为  Λ 。（因此，  Λ完全指定了所有值  { ˆ d v  } 。）我们称  Λ是好的，如果对于所有的  v  ∈  V ，有 ˆ d v  ∈  ( 1  ±  ε / 10 ) d v0以下是条件概率的一个简单推论（在此版本中省略了证明）。0命题2.7. 考虑任意事件  A ，对于任何好的  Λ ，有 Pr[ A| Λ ]  ≥  p。那么  Pr[ A ]  ≥  p  −  1 / n 2 。0对于任何固定的  Λ ，我们将  N Λ ( d )  设置为  |{ v | ˆ d v  ≥  d }|。我们将对  SADDLES 的分析基于  � N Λ -values进行。（证明是一个直接的计算，在此版本中省略。）0命题2.8. 假设Λ是好的。对于所有的  v ，有  N Λ ( v )  ∈  [ N  (( 1+ ε / 9 ) d ) ,  N  (( 1  −  ε / 9 ) d ) ] 。03 主要结果和SADDLES0我们首先陈述关于SADDLES过程的主要结果。注意，D是一组度数，我们希望对N(d)进行近似。0定理3.1. 存在一个算法  SADDLES ，具有以下特性。设  c是一个足够大的常数。固定任意  ε  >  0 ，  δ  >  0 。假设SADDLES 的参数满足以下条件：  r  ≥  cε − 2 n / h ，  q  ≥  cε −2 m / z 2 ，  ℓ  ≥  c  log ( n / δ ) ， τ  ≥  cε − 2 。那么以概率至少 1  −  δ ，对于所有  d  ∈  D ，  SADDLES 输出  N  ( d ) 的一个  (ε , ε ) -近似。所做的查询数的期望取决于模型，并且与  D的大小无关。•  SM：  O (( n / h  +  m / z 2 )( ε − 2 log ( n / δ )))。•  HDM：  O (( m / z )( ε − 4 log 2 ( n / δ ))) 。0忽略常数因子并假设  m = O ( n ) ，随着  h  和  z指数的增加，算法的查询复杂度是次线性的。SM和HDM使用相同的算法结构，唯一的区别是在HDM中使用Corollary2.5的算法来估计度数，而在SM中度数是直接可用的。0核心理论界：中心技术界处理每个单独估计值  � N  ( d ) [ t ]的属性。0定理3.2. 假设  r  ≥  cε − 2 n / h ，  q  ≥  cε − 2 m / z 2 ，  τ  =cε − 2 。那么，对于所有  d  ∈  D ，以概率 ≥  5 / 6 ，有  N  ( d ) [t ]  ∈  [ ( 1  − ε / 2 ) N  (( 1  +  ε / 2 ) d ) ,  ( 1  +  ε / 2 ) N  (( 10该定理的证明是我们分析的主要部分，将在下一节中给出。定理3.1的误差/精度界可以通过“通过中位数提升”直接应用得到。由于空间限制，我们将错误界和查询复杂度的证明留给arxiv上更长版本的论文[18]。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, 2018年4月23-27日，法国里昂9Sample v ∼ D.10Pick u.a.r. neighbor u of v.11In HDM, call DEG(u) to get ˆdu. In SM, set ˆdu to du.12For d ∈ D:13If ˆdu ≥ d, set Yid = 1/ ˆdu. Else, set Yid = 0.14For d ∈ D:15If �i ≤r Xid ≥ τ:16�N (d)[t] = nr�i ≤r Xid.17else �N (d)[t] = nr ·ˆdRq�i ≤q Yid.18 For d ∈ D:19N ′(d) = median{ �N (d)}20 Return {N ′(d)}Λ,d (v)=v ∈V u ∈ˆdu ≥d/du=�u: ˆdudddu/ ˆdu(1)Pr(R)(R)> (ε/)(R)< 2 exp −ε2 · (cε−2n/d) · ( �NΛ(d)/2n)3 202 2NΛ(d)/d≤ 1/10Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France4540算法1：SADDLES ( D , r , q , ℓ, τ  )输入：D：要计算 N(d) 的度数集合r：顶点样本的预算 q：边样本的预算 ℓ：提升参数τ：顶点采样的截止值 输出：{ N ′ ( d ) }：估计的 {N  ( d ) }01 对于每个  t  =  1 , . . . , ℓ ：02 对于  i  =  1 , . . . , r ：03 随机选择一个顶点  v  并将其添加到多重集合  R 中。04 在HDM中，调用 DEG ( v )  来获得  ˆ d v 。在SM中，将  ˆ d v  设置为05 对于每个  d  ∈06 如果  ˆ d v  ≥  d ，则设置  X id  =07 让  R  = { v  ∈ R |  v 以概率  ˆ d v / ˆ d R 被选中}，其中  D是 R 上的分布。04 SADDLES的分析0我们现在证明定理3.2。有一些中间命题。我们将固定d ∈D和t的选择。滥用符号，我们使用� N  ( d ) 以指代� N  ( d ) [ t]。可以使用直接的Chernoff界来分析步骤16的估计值。0命题4.1.  以下命题以概率  >  9 / 10 成立。如果SADDLES ( r , q)在步骤16中为给定的d输出了一个估计值，那么� N  ( d )  ∈  ( 1  ±ε / 10 )  � N Λ ( d ) 。如果它在步骤16中没有输出，则� N Λ ( d )  <( 2 c / ε 2 )( n / r ) 。0证明.  每个X i 都是独立同分布的伯努利随机变量，成功概率恰好为� N Λ ( d ) / n。我们分为两种情况。情况1：� N Λ ( d )  ≥  ( c / 10 ε 2 )( n / r )。根据定理2.1的Chernoff界，Pr [ | � i  ≤ r X i −  r  � N Λ ( d ) / n | ≥  ( ε / 10 )( r � N Λ( d ) / n ) ]  ≤ 2 exp ( − ( ε 2 / 100 )( r � N Λ ( d ) / n )  ≤  1 / 100。情况2：� N Λ ( d)  ≤  ( c / 10 ε 2 )( n / r ) 。注意到  E [ � i  ≤ r X i ]  ≤  c / 10 ε 20≤  ( c / ε 2 ) / 2 e 。根据定理2.1的上尾界，Pr [ � i  ≤ r X i ≥ c / ε 2]  <  1 / 100。因此，至少以99 /100的概率，如果在步骤16中输出了一个估计值，� N Λ ( d )  >  ( c /10 ε 2 )( n / r ) 。根据第一种情况，以至少99 / 100的概率0至少以99 / 100的概率，� N  ( d ) 是� N Λ ( d )的 ( 1  +  ε / 10 )-估计。联合概率完成了第一部分。此外，如果� N Λ ( d )  ≥  ( 2 c / ε2 )( n / r ) ，那么至少以99 / 100的概率，� i  ≤ r X i ≥  ( 1  −  ε /10 ) r  � N Λ ( d ) / n  ≥  c / ε 2 =  τ。联合概率证明了（第二部分的反证法）。 □0我们定义有序边的权重。权重仅取决于对中的第二个成员，但可以进行更方便的分析。 � v , u �的权重是步骤13的随机变量Y i 。0定义4.2.  对于给定的Λ（DEG的随机性），有序边 � v , u �的d-权重定义如下。如果 ˆ d u  ≥  d，则将wt Λ , d  ( � v , u � )设置为1 / ˆ d u ，否则设置为0。对于顶点v，wt Λ , d  ( v )  = � u∈ Γ( v ) wt Λ , d ( � v , u � ) 。0权重定义的效用由以下命题捕捉。总权重是对� N  ( d)的近似，因此我们可以分析SADDLES对总权重的近似程度。0命题4.3.  如果Λ是良好的，则对于所有v ∈ V，wt