图兰阴影方法：近团的证明和有效近似

1966−→→−−使用图兰阴影可证明和有效地近似近团：PEANUTSShweta Jain美国加州大学圣克鲁斯sjain12@ucsc.edu摘要团和近团计数是重要的图属性，在图生成、图建模、图分析、社区检测等方面具有应用。它们是稠密子图的虽然有几个不同的定义近团，他们中的大多数人都有一个属性，他们是缺少少量的边缘团。 集团计数本身被认为是一个具有挑战性的问题。 计算近团要困难得多，因为近团的搜索空间比团大几个数量级。我们给出了一个制定的近团作为一个团，是失踪的一个常数的边缘。我们利用的事实是，一个近团包含一个较小的团，并使用团抽样技术来计算近团。这种方法允许我们在具有数千万条边的图中计算具有1条或2条缺失边的据我们所知，没有已知的有效的方法来解决这个问题，我们获得了10 × 100 ×加速比现有算法计算近团。我们的主要技术是Turán Shadow采样方法的空间有效适应，最近由Jain和Seshadhri（WWW 2017）引入。这种方法构造了一个大的递归树（称为Turán Shadow），它表示图中的我们设计了一种新的算法，建立了一个估计近团，使用一个在线的，紧凑的图兰阴影的建设。CCS概念• 计算理论应用领域的理论和算法;·计算数学近似算法。关键词团，近团，近团，缺陷团，图兰阴影，采样，图ACM参考格式：Shweta Jain和C.Seshadhri 2020年。 使用图兰阴影可证明和有效地近似近团：花生。在网络会议2020（WWW '20）的会议记录，2020年4月20日至24 日 ， 台 北 ， 台 湾 。 ACM ， 美 国 纽 约 州 纽 约 市 ， 11 页 。https://doi.org/10.1145/3366423.3380264本文在知识共享署名4.0国际（CC-BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的署名传播作品的权利WWW©2020 IW 3C 2（国际万维网大会委员会），在知识共享CC-BY 4.0许可下发布。ACM ISBN 978-1-4503-7023-3/20/04。https://doi.org/10.1145/3366423.3380264C. 塞沙德里加州大学圣克鲁兹sesh@ucsc.edu1介绍子图计数是图分析中的一个重要工具，有很多名称，如模体计数，图分析和模式计数。其目的是计算一个（通常很小的）子图在一个更大的图中出现的次数在这些子图中，集团可以说是最重要的。即使是最简单的三角形，也有着丰富的算法和应用历史。最近有很多关注在大型图中计数团[5，11，14，16，19，42]。虽然团计数很重要，但团中的每条边都必须存在的要求过于严格。数据通常是嘈杂的或不完整的，并且很可能丢失甚至一两个边缘的集团是重要的。因此，重要的是还要查看非常接近集团的模式的计数。 我们将这些结构称为近团，但它们也被称为准团[23，27]和缺陷团[46]，并且具有从聚类到预测的多种应用。最近的工作已经使用了近团到k-团的分数来定义聚类系数的高阶变量[45]。在生物信息学文献中，近团（或缺陷团，因为它们是已知的）已被用于预测噪声PPI网络中错过的蛋白质-蛋白质相互作用[46]，并已被证明具有良好的预测性能。另一种看待近团的观点是将它们视为稠密子图。稠密子图的挖掘是网络分析中的一个重要问题，有着广泛的应用。[二、八、十五、二十二、三十一]计算派系已经很有挑战性了，计算近似派系带来了更多的挑战。最重要的是，近似集团不享有集团的递归结构属性-集团的子集也是集团。这排除了大多数用于团计数的递归回溯算法此外，经验证据表明，在现实世界的数据集中，近似集团的数量比集团的数量高出一个数量级，这使得计算它们的任务同样困难，如果不是更多的话。 图图1 i示出了对于4个真实世界图，3种不同类型的近团与k-团的数量（k = 5）的比率。近团的数量通常是k团数量的十倍。有几种不同的方式来定义近集团。 [38]将α-准团定义为缺失α分数边的团。 其他公式定义他们在图形属性，如度的每个顶点在近团或直径的近团。一个大小为n的集合S称为k丛，如果集合中的每个成员都连接到nk个其他成员。一个k-俱乐部是一个节点子集S，使得在由S导出的子图中，直径为k或更小。所有这些公式都有一个共同的性质，即它们代表一个缺少一些边缘的集团我们形成了近乎派系的关系，WWWShweta Jain和C.塞沙德里1967−（）下一页（）下一页（）下一页（）下一页（）下一页（）下一页（）下一页（）下一页（）（）（）下一页（）−（）下一页（）−稍微不同的方式，如缺少1或2条边的集团以这种方式定义它们的好处是，它们允许我们利用集团计数的机器。每一个这样的近似集团都有一个更小的集团包含在其中。通过对较小的团进行采样，并将其用作寻找近似团的提示，我们给出了近似团总数的估计。在第6.1节中，我们展示了这种近似集团的一个有趣应用，我们在引用网络上运行我们的算法，以发现可能应该引用其他论文但没有引用的论文。1.1问题描述一个k-团是一个由k个顶点组成的集合，使得属于该集合的所有顶点对之间存在一条边 我们在下面定义k，1-团和k，2-团。对于本文的其余部分，每当我们说近集团，我们将暗示以下3种近集团（除非另有说明）定义1.1.一个k，1-团是一个k-团，恰好有一条边丢失.对于k，2-团，有两种可能的配置-一种是缺失的边共享一个顶点，另一种是它们定义1.2.类型1k， 2-团是恰好缺失2条边的k-团，使得缺失的边共享一个顶点。定义1.3.类型2k，2-团是恰好缺失2条边的k-团，使得缺失的边不共享顶点。不同类型的近集团如图所示。二、 我们要估计G中k，1 -团和k，2 -团的个数。注意，我们所有的近团都是诱导的，并且获得非诱导近团的计数仅仅是取k团和近团的数量的线性组合的问题。 为了简洁起见，我们跳过详细的讨论。我们强调，我们没有对图进行分布假设所有的概率都超过了算法本身的内部随机性（这与实例无关1.2我们的贡献我 们 提 供 了 一 个 随 机 算 法 的 基 础 上 TuránShadow 称 为PEANUTS估计计数的k，1-团和k，2-团。此外，我们还提供了一种基于PEANUTS的启发式算法，称为Inverse-TS，它所需的时间与PEANUTS大致相同（在某些情况下，最多少10倍），但大大减少了所需的空间。 我们在商品机器上实现的Inverse-TS显示出在获得近似团的计数方面比其他方法（如颜色编码和蛮力计数）节省了大量时间，并且在算法的100次运行中显示出一致的低误差。利用集团来接近集团：数据是嘈杂的，集团是脆弱的，因此，接近集团的数量通常非常大。然而，我们根本不清楚如何在不查看每一组k个顶点的情况下计算它们的数量，这在计算上非常昂贵。PEANUTS利用了near-clique本身包含clique的事实，并利用TuránShadow来计算near-clique。存在用于通用模式计数的算法，其可用于计数近团，但是没有已知的算法致力于发现利用近团的团状结构来给出更快的估计的近团。非常快：PEANUTS是基于观察到的，每一个近集团包含一个更小的集团。因此，我们可以使用集团作为寻找近集团的线索 我们利用快速团计数算法（TuránShadow）来实现快速准确的近团计数。图1ii显示了逆TS，颜色编码（cc）和蛮力（bf）计算各种图的7，1-团的数量所花费的时间。 Inverse-TS能够在452秒内在具有400万个顶点和3400万条边的图（com-lj）中估计它们的数量，误差在2%以内，这比cc和bf快至少100倍。正如我们稍后将展示的那样，在其他近团和其他图的估计中也发现了类似的性能非常准确：与TuránShadow类似，Inverse-TS使用极值组合学的开创性结果，称为Turán 图1iii显示了使用逆TS在各种图中获得的类型2 5，2团（5，2团的特定配置）的估计值的误差。我们可以看到，所有的误差都在2%以内。此外，与颜色编码不同，Inverse-TS允许我们控制采集的样本数量，即使使用500 K样本，Inverse-TS也比颜色编码更准确，花费的时间更少（6）。对于我们实验的许多图形，蛮力算法在1天内没有终止，因此无法给我们地面真值，但在算法终止的情况下，我们看到Inverse-TS给出<了5%的错误，大部分是<2%。对于暴力算法没有终止的情况，我们查看了我们算法运行100次的输出。在所有情况下，该算法都表现出非常好的收敛性（更多细节见§6）。出色的空间效率：TuránShadow需要生成和存储整个阴影，对于具有数百万条边的图来说，这可能需要大量内存。我们的Inverse-TS的实际实现通过消除阴影构建和采样阶段的分离来解决这个问题，而是在以在线方式构建阴影时执行采样。这消除了存储整个阴影的需要，从而节省了所需空间的数量级图中的紫色条。1iv显示了Inverse-TS在任何点所需存储的最大阴影大小（瞬时阴影大小或instSS）与TuránShadow所需空间的节省系数。使用Inverse-TS至少可以节省100倍的空间。与其他算法的比较：我们通过将Inverse-TS部署在一些不同大小的真实世界图上，对它进行了彻底的分析。在大多数情况下，我们观察到Inverse-TS相当快，同时在算法的100次运行中显示出一致的低误差 我们还做了一个彻底的比较，逆TS与其他通用的模式计数算法，如颜色编码。 图1ii显示了通过不同方法计数7，1-团所需的时间。在我们所有的实验中，我们观察到，与其他算法相比，Inverse-TS在大多数图上的速度至少快10倍。使用图兰阴影可证明和有效地近似近团：PEANUTSWWW1968（5，1）（5，2）类（5，2）类网站-Stan网站-Google亚马逊BerkStan作为突击者专利soc-pokeccom-ljweb-Stan相对误差网络谷歌亚马逊伯克斯坦突击者com-ljsoc-LJ−（）下一页（）下一页（）下一页–105104103102101100k=5，近团106105104103102101100二、5二、01 .一、51 .一、00。50。01051041031021010k=7，集团时间SSinst SS10−110图(i) 比率图(ii) 定时图(iii) 误差图(iv) TS与反向TS图1：图1 i显示了四个真实世界图中不同类型的近团与k-团（k=5）的数量比。红线表示比率= 1。在大多数情况下，近团的数量至少与k团的数量具有相同的数量级，如果不是更多的话。图图1 ii显示了逆TS（inv-ts）、颜色编码（cc）和蛮力（bf）估计10个真实世界图中的7，1-团的数量所需的时间。y轴以对数刻度显示时间（以秒为单位）。红线表示86400秒（24小时）。所有运行超过24小时的实验均终止。在除了com-orkut之外的所有情况下，Inverse-TS都在几分钟内终止，加速速度在3x-100 x之间。图1 iii显示了使用逆TS获得的k = 5的类型1 k，2 -团的估计值的百分比误差。我们可以看到，误差为<2%，在大多数情况下<为1%。图1 iv显示了使用Inverse-TS（500000个样本）与使用TuránShadow（50000个样本）来估计我们实验的4个最大现实世界图中的7-团的数量时绿色条显示探索的Turán阴影百分比的因子节省（因子2-10）。紫色条显示的是图兰阴影在任何时刻所需的最大空间节省系数。（i）（7，1）（ii）第1类（ 7，2） （iii）第2（ 7，2）图2：近7-团。虚线表示缺失的边缘。蓝线标记包含的集团。所有代码和数据可用：我们使用的所有数据集都可以在[36]中公开获得此外，如果论文被接受出版，我们可以很容易地公开我们算法的1.3相关工作模式计数，也被称为graphlet计数或motif计数，已经成为图形分析的重要工具 它已被用于生物信息学[25，29，44]，社会科学[18]，垃圾邮件检测[4]，图形建模[33]等。三角形计数和最近的团计数由于其在表征现实世界图中的特殊作用而获得了很多关注[11，14，19]。团计数已被用于诸如稠密子图的发现[32，39]，网络分析的拓扑方法[35]，图聚类[45]等应用中。 更一般地，基序计数已用于聚类[40，45]，图模型的评估[33，34]，图的分类[41]等。在理论方面，存在几种基序计数算法[9，10，45]。 在更实际的方面，直到最近，才提出了计算大小为5的小图的有效方法[17，20，28，43]。其中大多数是三角形计数方法的扩展，并且不能扩展。 对于较大尺寸的图案，两种广泛使用的技术是MCMC [16，42]和[1]的颜色编码（CC）。然而，如[7]所示，基于MCMC的方法具有较差的对于相同的运行时间和大于5的模式，CC的准确性通常也相当低，正如我们将在结果中显示模体计数已经在流[6，21]和分布式设置[13]以及时间网络[26]中进行了研究。所有这些方法都是针对计数多达6个节点的任意模式，但这些方法都没有超过6个节点。此外，这些都是通用的模式计数方法，不利用类团性质的近团，以提供更有效的方法。我们的工作是第一个这样做的稠密子图算法：稠密子图作为近团的概念是由Tsourakakis等人引入的。al. 在[38]中。稠密子图有几种不同的表述，其中许多都是NP-困难的（事实上，即使是找到k个顶点上的稠密子图的问题，也被称为稠密-k- 子图[32]）。 Andersen 和Chellapilla[3]，Rossi et al. [30]和Tsourakakis et al. [38，39]提供了一些公式的实用算法。然而，他们中的大多数都集中在寻找或近似的denominator子图，而不是给全局统计。2主要思想我们的结果的出发点是TuránShadow算法估计的k-团在一个图中的数量TuránShadow基于Turán和Erdös的一个开创性定理：如果一个n顶点图的边密度大于1 1k1（Turan密度），那么这个图保证有许多（O nk−2）k-团。 这意味着如果我们从图中随机抽取一个k-顶点集，它是k-团的概率会很高。 TuránShadow利用了这一事实，将G分成（可能重叠的）Turan稠密子图，使得每个子图中特定大小的团与G中k-团的数量之间存在一一对应。G的所有这样的子图的集合称为G的Turán阴影。本质上，TuránShadow将G中k-团的搜索空间从一个大的稀疏图减少到几个稠密的子图。inv-ts（7， 1）−集团CCBF小集团类型1，（5，2）−团，k=5斯坦谷歌伯克斯坦突击者时间（秒）要素节约伯克斯坦com-ljsoc-LJ科莫尔库特WWWShweta Jain和C.塞沙德里1969→.≥Hv （）下一页（）下一页∈.∈–（）（）（）–∈−−（）∈（）−/（−）对于F=K∈CCk（G）与（P，S，S）∈SC<$（S）.因此εµkB∈k−（）∈∪ ∀ ∈ ( ) ∪更重要的是，对于任何h，TuránShadow提供了一种有效的采样u.a.r.的方法h-团从G.设Ch是G中所有h-团的集合，f：ChR+是G中所有h-团上的有界函数，则我们可以得到一个无偏估计3预赛我们设置一些符号。输入图G有n个顶点和m条边。我们假设mn。设α是图的退化度。回想一下，简并度是任何均匀采样的h-团并按h-团的总数缩放。换句话说，我们可以使用这个团采样器来获得h-团上任何有界函数的和（和均值）的无偏估计 我们利用这一事实，以获得一个估计的近团的数量。为了估计（k，1）-团的数量，我们做以下事情：观察：每个（k，1）-团恰好有两个k−1-团G中顶点的退化序。当顶点按退化度排序时，设NvG表示v的邻域，N+G表示v的外邻域我们用“u.a.r.”“作为“随机制服”的简写。我们将使用以下（重新缩放的）Buckoff界。定理3.1. [[ 12 ]中的定理1]设X1，X2，. . .，Xk 是具有期望μ的iid随机变量序列。此外，委员会认为，嵌入其中。设Ck−1是G中的（k，1）-团的集合，Ck−1设X为∈[0，B]. 对于ε < 1，Pr[|.KXi−µk|≥εµk]≤b e是G中k−1-团的集合，且∈K∈Ck−1，设f（K.）=number的（k，1）-团，团K包含在其中，则f（K）=∈k−2 exp（−2/3）。i=12 |Ck−1|.然而，由于每个（k，KC11）-集团计数两次，4主要算法估计量的方差可能相当大。我们观察到，如果（k，1）-团中的缺失边是（u，v），uv，恰好是<在TuránShadow的核心是一个叫做影子的物体我们定义一个类似的结构，称为前缀阴影。k-1-团包含u，另一个包含v。为了减少方差，我们定义f（K）=（k，1）-团的数量定义4.1. 设Ck一（G）是G中所有k-团的集合。团K包含在其中，使得uK，即，我们基于缺失边的方向打破联系。有了这个公式，f（K）=|Ck−1|.图G的k-团前缀阴影S是一个三元组{（Pi，Si，i）}其中Pi S.V.， V和 ∈N使得<$i（Pi，Si，<$i）∈S，<$c∈C<$i（Si），Pi<$c是一个uni？你..在G和KC1对于（k，2）-团，有2种可能的配置，如图所示Ck（G）与此外，如果multiset（Pi，Si，i）∈Sc∈Ci（Si）我很高兴。图二、类型1由恰好一个嵌入其中的k − 1-团组成。因此，我们设置f（K）=给定的类型1（k， 2）-团的数量{（Si，i）}是这样的，即（Si，i），ρ2（Si）>1− 1/（Si− 1）其中ρ2（Si）表示Si的边密度，则k-1-团K包含在。类型2（k， 2）-团稍微复杂一点一个2型（k， 2）-团恰好有四个k−2-团S是G的k-团前缀Turán-Shadow。它 是 容易 到 看到 的 {（v，N+，h−1）}是 H集团嵌入其中。如果边（u，v）和（w，x）缺失，则存在v前缀-G的阴影。是一个包含u，v，w和x的诱导圈，这个圈的每条边给出嵌入k，2 -团中的4个k2-团中的一个不同的k2-团.设min u，v，w，x=u，且min w，x=w。然后，对于k2-团K，设fK=k，2 -团的个数，使得u，wK.只要f是有界的，并且是一个“行为良好的函数”，即具有低方差，我们就可以使用TuránShadow作为黑盒来有效地 提高黑盒的运行时间只是提高了整个算法的运行时间。我们观察到，在TuránShadow中，大部分时间都花在构建影子上，但只有一小部分时间用于收集样本。因此，如果我们可以首先采样并确定样本位于阴影的哪些区域，我们可以通过仅显影阴影的这些部分而不是显影整个阴影来节省时间。另外，当样本的数量固定时（如图1中的情况），我们将简要回顾TuránShadow如何构建阴影。它通过退化对G的顶点进行排序，并将其转换为DAG。如[14]所示，为了计算G中的k-团，只需计算每个顶点的外邻域中的k1-团的数目因此，对于每个顶点v V，TuránShadow通过查看v的外邻域中的k 1-团的数量来计算v作为最低阶顶点的k -团的数量，并且递归地应用这个过程。 当外邻域变得足够密集时，它不再继续扩展部分团，而是将外邻域添加到阴影中，并继续下去，直到没有更多的外邻域可以添加到阴影中。算 法 PrefixedTuránShadowPickup 执 行 与 [19] 中 Shadow-Pickup完全相同的步骤，除了在每个阶段它还保持部分团P。我们算法的实际实现），我们可以交织Cl AIM4.2. 给定图 G和整数 k，发展的部分阴影与抽样的h-集团从这些部分，从而获得我们的估计F在一个在线的方式。这导致在空间和时间上的相当大的节省大纲：在§3中，我们设置了一些基本的符号。在§4中，我们展示了我们的基本框架PEANUTS和它的优化版本，称为Inverse-TS。根据我们想要计数的模式类型，我们在§5中提出并分析了不同的计数器。最后，在§6PrefixedTuránShadow返回G的k-团P refix ed-Turán-Shad ow。 其运行时间为O（|V|k+1）。ProoF. 当函数返回时，T为空，并且任何元素P，S， 只有当ρ2S>1时，S才加到S1 ℓ1 .一、如果是一个伪命题，那么它也是一个伪命题。利用文献[19]中的定理5.2，证明了多重集{（S，S？是一个shado w和hence，与最先进的技术相比这就足以证明P，S，C，P，C是唯一的。k团在G.我们将用归纳法证明这一点开始时f（K）通过获得f在一组当图的边根据我们提供了一个详细的实验研究的逆TS及其使用图兰阴影可证明和有效地近似近团：PEANUTSWWW1970′ℓ（||）S−ℓ7若ρ 2≤2或ρ2（N）>1−ρ−2S【详细】S（）下一页（）下一页（）（）−−？.（）下一页伊什−（）（/）/[客户端].′′′（）下一页.Σℓ（）（/）/我5设B=P<${c}K∈C（G）w（S）我PR2i=1XiXi1Xi（）下一页∈∈（P，S，S）∈SℓBSεsδ算法1：PrefixedTuránShadowsort（G，k）（P′，S.′，′）∈S. |S ′|- 是的设c是S中的一个群，且设K=P<$c，则K1初始化T={（k，V，k）}和S=k必为G中唯一的k-团。2当n（P，S，n）∈T使得ρ2（S）≤1−n−1Pr（K被采样）=Pr（E从D采样）n3构造退化DAG D（G |S）的4设N ~+表示D（G）的外邻域|（S））Pr（c从S采样）=Sℓw（S）1（|S|）=1w（S）.所以每S s5从T中删去P、S、N6对于每个s S1G中的k团被Sample返回的概率相同。□我们先来说说花生。本质上，它构建了+s+前缀-图兰-阴影G，样品h-团，获得f为8将（P<${s}，Ns，<$−1）加到S9否则，将（P<${s}，N+，<$−1）加到T采样h团并估计F的值。10输出S第一次迭代，P是空的，S=V和k=k，S=P，S，k和T是空的。因此，对于基本情况，该假设是平凡真实的。假设在某次迭代开始时假设为真，假设元素E=（P′，S′，S′）在开始时从T中删除这个迭代。对于s ∈ S ′，每个Es=（P′ <${s}，N+，<$′−1）是添加到S或T。 设K（E）={P ′ ∈ C |c ∈ C<$′（S ′）}表示k−团K∈ K（E），K∈sK（Es），（ii）|K |为S|K（Es）|.算法3：PEANUTSG，h，s，Func输入：G：输入图，h：团大小对于团，k =k，对于k，1 -团和类型1k， 2 -团，k= 1，对于类型2k， 2-团，k =2s：样本的预算，Func：返回f K的函数h-团K.输出：F：估计F1S=P refi xed Tu。n. do（G，h）从E.它足以证明：（i）对于任何2 令w（S）=|S|考虑k-团K=P′ <$c，c∈C<$′（S′）.让我们成为最低的根据G中的退化序对C中的顶点进行排序|S ′。然后，c\{s}是N+中的n−1-团。因此，K∈ K（Es）。额外3对于i = 1，2，.，s：4K=样品（S）我s5如果K是团，则设X′ ′=Func（G，K）c∈C′（S），在C中，向量x定义了一个partitio。不超过C′（S）。6else setXi=0每个顶点的出度最多为|V|并且递归调用的深度至多为k-1。当处理一个元素（P，S，N）时，它构造图G |It’这最多花点时间|V |2，因为它查询S中的每对顶点，|S |<|V|. 所以，时间的长短是O（|V|k+1）。□算法2：样本（S）输入：S：k−cliquePrefixed-Turán-Shadow of some graphG输出：B：k−顶点集8 设F∈=Ww（S）9返回F定理4.4. 设f是h-团上的函数，上界为B使得给定一个h-团，需要O Tf时间才能得到f的值. 设F是PEANUTS的输出，则E F =F。此外，给定任何ε>0，δ> 0和样本数s= 3 wSB ln 2 δ ε2F，则概率至少为1 δ（该概率超过PEANUTS的随机性; G上没有随机假设），|≤εF。|≤ εF.1 令w（S）=（P，S，S）∈S. |S ′|Σ设S表示G的h-团Turán阴影，且大小（S）=（S，n）∈S|S|. PEANUTS的运行时间为O（αsizee（S）+sTf+2设置概率分布D，以概率3来自D的样品a（P，S，N）在S上，使得（P，S，）∈S是|/ w（S）|/w(S)时间复杂度为O（size（S）+m + n）。ProoF. Xi都是iid随机变量，并且根据权利要求4.3中的论点，G中的每个h团都具有相同的概率是4选择u.a.r.C−tuplecfromS返回样本E[X]=.f（K）=F.设X∈6返回B[0，]。 根据第3.1条，[|.sk−E[]|≥E[]≤当ClAIM 4.3.G中任意k-团K返回的概率s=3 wSB ln 2 δ εF。TuránShadow所需的运行时间和存储直接决定了所需的|（）下一页|S′ℓ.因此，C′S′=因此，证明。s∈S′|C′−1（N+）|I. e. |K（E）|为s∈S′|K（Es）|.7W=W+X我w（S）使用图兰阴影可证明和有效地近似近团：PEANUTSWWW1971W通过调用Sample，1 .一、（S）[19]中的定理5.4唯一的区别是增加了sTf在运行时间中，这是获得s的f所需的时间ProoF.设E=（P，S，N）∈S，其中S是k-团前缀阴影 的一些 图G. 注意w（S）=样品□WWWShweta Jain和C.塞沙德里1972.[][]vv−–（/）ˆS.ΣS（）下一页（|）/vvv1N弗罗姆+N.v−[客户端]v∈.vDGvh−1v Φvv，Nv，h10让我们=|S|i=1我Φ采样av与Φ成=|，并获得h−|, and obtainthe h −ln 22ˆvvH1-N+−1的团前缀Turán-ShadowS（fδ）/εF，逆TS输出估计F，使得ˆCh−1（G|N+）/N +v. 因此，成功率g是从Ch−1（G|N+）/Φv尺寸（S）=|S|. Inverse-TS的运行时间为对于元素E=（P，S，n）∈S，其中S是k-团根据定理3.1，Pr [|SXi −µs|≥εsµ] ≤δ 当S=f（K）=f（K）=F∗4.1逆TS我们观察到，使用TuránShadow，大部分时间都花在了构建树上，只需要一小部分时间来采样。举几个例子，对于web-Stanford图，阴影的构建花费了155秒来近似7个团的数量而获取50K个样本需要0.2秒。 对于我们实验的所有其他图，都观察到类似的结果。因此，自然地，为了优化TuránShadow的性能，最大限度地减少需要构建的阴影部分将是有益的。考虑最小化建筑阴影的一个极端我们称之为一级抽样。设N+为外邻域算法4：逆TS（G，h，s，Func）1通过简并对G进行排序，并将其转换为DAGDG。2设M是映射，W=03设V上的概率分布D，其中p（v）=vΦv/Φ。4对于i = 1，2，.，s：5从D独立采样顶点v。6如果Mv 存在，设S=Mv7其他8S =预固定转弯阴影（G |N+，h − 1）在，. |N+|兰蒂昂..（+-1）}是一个9M[v]= S。 .Σvℓh-团前缀-G的阴影。如果我们用概率抽样一个v与Φv成比例，并从N+（P，S，S）∈S11设K={v}样本（S）v苏联，在N+中对特定h−1-团进行采样的概率12如果K是一个团，设X=v函数（G，K）应该是Φv/Φ1/Φv=1/Φ。如果有ChG中的h-团v然后13else setXi=0iΦv采样的h个顶点的集合是团的概率是Ch Φ（我们称之为成功率）。因此，找到h团所需的样本数为O Φ C h。 但是，与Ch相比，Φ通常非常大，因此所需的样本数量将非常大。换句话说，拾取的大多数h顶点集将不是团。TuránShadow通过首先找到Turán阴影来解决这个问题W=W+Xi15设F=WΦ16返回F此外，W=.的X. 公式E[W]=E[.SX]=然后在阴影的子图内进行采样，这些子图是密集的，因此需要较少的样本来找到k团。因此，在本发明中，.sE[X]=sF。i=1ii=1i建造阴影。1级抽样的优点是我们不需要花时间去找图兰之影我们模仿了从这个前缀阴影中采样h团的过程，但通过使用后一种方法提高了成功率我们尤其因此，E[FΦ]= E[W Φ]= F。□定理4.6. 设f是h -团上的函数，上界为B使得给定一个h-团，需要O Tf时间才能得到f的值.给定任何ε >0，δ >0且样本数s=v= .（P，S，S）∈Sv. Sℓv. 假设阴影大小，则采样h− 1-团的概率=vΦB概率至少为1 − δ，|F − F |≤ εF。让Sden.OTE 的k-团 图兰 沙德奥 的G和（S，n）∈SCG +-是的由于Φ通常比Φ小得多，成功率大大提高。如何解释O（min（sαh，αsize（S））+sTf +m+n），总存储量为我们现在正在对U.A.R.在搜索空间的大小为φv，而不是Φv，我们给每个团一个较小的权重（φv/ΦvvK（）{<$∈（）}时间复杂度为O（size（S）+m + n）。ProoF. X i都是iid随机变量，根据引理4.5中的参数，它们的ex。pectationµ=F/Φ。 假设Xi∈[0，B].图G的前缀Turán-Shadow，设E = P c，cCS表示从E得到的k-团的集合。3ΦBln（2/δ）/ε2F。i=1给我4.5. 设F是Inverse-TS返回的值。则E[F]=FProoF. 考虑一个h-团K∈Ch（G），设v是G的最低G的简并度可以在时间上线性地计算，图 [24] 。 对 于 任 何 v ， 逆 TS 中 的 映 射 Mv 存 储 N+ 的 h1- 团Prefixed-Turán-Shadow。对于在步骤5的任何v，Inverse-TS检查N+的Prefixed-Turán-Shadow是否已经构造，如果是，则使用已经构造的根据G中顶点的退化序对顶点进行排序。让E=（v，N+，h − 1）则K ∈ K（E）。v影子如果不是，则在步骤8中构造它并将其存储在M中。因此，在本发明中，在最坏的情况下，它计算N+的Prefixed-Turán-Shadow设Sve是G的h−1-团P refix ed-Turán-Shadoww|N+，让v每vEv =（P，S，N）是Sv中的元素，使得K = v <$P <$c，cC<$（S）。v即它计算G的前缀图兰阴影，根据Thm需要时间O（αsize（S））5.4从[19]。上Pr（K在步骤11中被采样）=Pr（E被采样）Pr（Ev被采样）Pr（c被采样）=0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|S|）ℓ1为|S|ΦvΦv=Φ=TuránShadow节省了所需的样品数量，3.WWWShweta Jain和C.塞沙德里1973Φv（权利要求4.2）并且它从D中采样s个这样的顶点，因此需要时间v∈VK∈K（Ev）Φ<$vΦv是O（sαh）另一方面，给定任意v，Nv的大小至多为α，因此构造H..Φv（）ΦΦvΦh−1-团Prefixed-Turán-Shadow的时间复杂度为O（α）因此，E[Xi]=K∈Ck（G）使用图兰阴影可证明和有效地近似近团：PEANUTSWWW1974（）−∈∈（）{}−（）下一页.∈ ∈（）{\displaystyle {\frac{}（图2）。因此，在本发明中，K′ CG f（K′）=F=类型1的总数ProoF. 你好。pe1（k，2）-团包含exl1k−1-团下层集团，f（K）=F=总数∈2条边缺失-（u，nbr）和（v，nbr），缺失的边具有共同的顶点（nbr），即它是1型（k，2）-团。∈∈在步骤11中采样了s个h-顶点集，并且检查采样的顶点是否形成团花费时间h2，而在给定采样集是团的情况下计算f花费时间Tf。因此，在本发明中， 的 总 时间 需 通过 逆TS 是时间复杂度为O（min（αsize（S），sαk）+sTf+m+n）.□根据我们计算的结构，我们可以找到B和Tf的适当值。请注意，在最坏的情况下，根据图的结构，Inverse-TS可能最终构建整个阴影，在这种情况下，它不会提供任何PEANUTS的节省。然而，实际上，我们观察到，在大多数情况下，使用Inverse-TS构建的阴影量显著节省。 除非另有说明，本文中的所有结果都是使用Inverse-TS得到的。5计数点击和近K-点击5.1计数（k，1）-团算法5：Func-（k，1）-Clique（G，K）1 f′=02设u和v是K的两个不同顶点3 设nbrs=Nu<$NvProoF. 根据权利要求5.2，F=G中k，1-团的总数。对于任意k，1 -团J=Knbr，其中K是其中的低阶k 1-团，或者nbrNu或nbrv或两者。因此，k，1-团的数量，其中它是低阶k 1-团是atmost 2 dmax。 另一方面，最多可以有n个nbr，因此B =min（2 dmax，n）。 查找nbrs需要O（dmax）的时间，检查nbr ∈nbrs是否与K形成（k，1）-团需要O（1）的时间。因此，Tf=O（dmax）□5.2计数类型1，（k，2）-团算法6：Func-（k，2）-Cnc-类型1（G，K）1 f′=02对于u K：3对于v K，v>u：4设nbrs是K中除u和v之外的所有顶点的顶点集5f′=f′+|NBRS|6返回f′Cl目标5.5。 设k−1-团K的f（K）表示n。我是你的兄弟4对于nbr nbr：5如果nbr连接到K中除1个顶点之外的所有顶点，则说w且nbr>w，则f′=f′+16返回f′1（k，2）-包含K的团。 则F =G中的1型（k，2）-团的总数。K′∈Ck−1（G）f（K′）=定义5.1. 设（u，v），u u，Func-（k，2）-Cnbr-Type 1找到顶点nbrs的集合，使得nbr∈nbrs，nbr连接到K中除u和v之外的所有顶点。因此，K{nbr}是一个k-团，G中的（k，1）-团。□ClAIM 5.3.对于输入k−1-团K，Func-（k， 1）-团返回f（K）。ProoF.对于任意nbr V，如果K nbr是k，1 -团，则nbr Nu或nbr Nv或两者都有。对于给定的K，Func-k，1 -Clique找到连接到K中除一个之外的每个顶点的nbr（nbrs）的集合因此，对于nbr∈nbrs，每个{nbr}K是一个（k，1）-团它被计入f′当且仅当K是一个低阶k−1-团。因此返回值，f′=f（K）。□定理5.4. 设dmax是G中任一顶点的最大度。则对于Func-（k，1）-Clique，B=min（2dmax，n），Tf =O（dmax）.因此，Func-（k，2）-Cnc-Type 1返回类型1的数目（k，2）-团，其中K是包含在，即。 返回f（K）。□定理5.7. 对于Fu