郑州网络营销外包顾问,咸阳seo培训,举报网站制度建设方面,北京网站搭建服务论文笔记整理#xff1a;毕祯#xff0c;浙江大学硕士#xff0c;研究方向#xff1a;知识图谱、自然语言处理。链接#xff1a;https://arxiv.org/abs/2006.07060动机图已被用作对人或物体之间的成对关系建模的强大工具。而超图是更广泛概念的一种特殊类型#xff0c;其… 论文笔记整理毕祯浙江大学硕士研究方向知识图谱、自然语言处理。链接https://arxiv.org/abs/2006.07060动机图已被用作对人或物体之间的成对关系建模的强大工具。而超图是更广泛概念的一种特殊类型其中每个超边可以由任意数量的节点组成而不是仅由两个组成。大量的现实世界数据集都是这种形式的。比如电子邮件的收件人列表参与讨论主题的用户或在线问题中标记的主题标签等。由于这些情况表示形式复杂且缺少适当的工具因此在研究中很少会去关注探索这些问题的建模与算法。本篇论文根据经验研究了多个跨领域的真实世界超图数据集。为了进行深入研究引入了多级分解方法该方法通过一组成对图表示每个超图。每个成对图称为k级分解图捕获了k个节点的子集对之间的交互。通过经验的总结在每个分解级别所研究的超图都遵循五个结构特性或者指标。这些属性用作评估超图的逼真度的标准并为超图生成问题奠定基础。文章最后提出了一种超图生成器采取了非常简单的思路但是能够满足这些评估指标。与此相比的是其他对比模型则很难达到同样的效果。背景图1 超图的例子超图是图的一般化其中边可以连接任意数量的顶点。相反在普通图中一条边正好连接两个顶点。在图1中假设顶点代表文章每条边代表两个顶点享有同一个作者。如果使用简单的图结构来表示就会丢失“同一作者发表多篇文章”这样集合的信息。实际生活中存在着大量类似的图结构而超图是相对合适的表示方法。多级分解方法定义其中图2 超图的多级分解利用分解图具有几个优点1子集交互分解后的图揭示了节点子集之间的子集交互。2成对图表示分解后的图可以使用成对图的现有度量进行分析。3没有信息丢失原始的超图可以从分解后的图中恢复。观测指标论文证明了下列的结构模式在真实超图的分解图的每个级别中均有效。P1Giant connected component巨型连接分量此属性意味着存在一个包含大量节点的连接分量并且该比例显着大于第二大连接分量至少大70倍。网络中的大多数节点都相互连接。此属性用作其他属性的基础。P2Heavy-tailed degree distribution重尾度分布 节点的度数定义为其邻居数。此属性意味着度分布是重尾的即以比指数分布慢的速率衰减。这可以用“rich gets richer”来部分解释高级节点更有可能形成新的链接。P3Small effective diameter有效直径小 分解的图通常不完全连接论文采用的定义其中有效直径是最小距离d使得所有连接对中的大约90可以通过最长d的路径到达。此属性意味着实际数据集中的有效直径相对较小并且大多数连接对可以以较小的距离到达。需要注意的是空模型也具有此特征并且在这方面比较实际数据集和相应的空模型不会产生一致的结果。P4High clustering coefficient高聚类系数 利用聚类系数C定义为所有节点的局部聚类系数的平均值。每个节点v的局部聚类系数Cv定义为此属性意味着实际数据集中的统计量明显大于相应的空模型中的统计量。由于邻居结构产生大量三角形因此此属性表示网络中存在许多邻居结构。P5Skewed singular values偏斜奇异值 此属性意味着奇异值分布通常是重尾分布并且以与模式P2相同的方式进行验证。HpyerPA生成器生成器HyperPA反复向超图引入新节点并形成新的超边缘。添加节点后HyperPA会创建k个新的超边缘其中从预定分布NP中采样了k个。对于此新节点引入的每个新超边缘其大小s是从预定分布S中采样的。当选择其他节点填充此新超边缘时它将考虑包含s-1个节点的所有组。在所有此类群体中每个群体被选中的机会与其程度成正比。每个组的程度定义为包含该组的超边缘的数量。评测方法P1如果在该级别的分解图生成的超图保留一个巨大的连通分量给出1分。P2生成的度分布与实际分布之间的相似性由Kolmogorov-Smirnov D统计量度其中FF是累积度分布 相应的实图和生成的分解图。对D统计量小于0.2的生成器给予1分。P3我们希望生成的有效直径d接近实际值d。由于P3为“有效直径较小”因此d不应太大。论文采用验收范围为2d/34d/3的启发式方法。如果d在接受范围内则给出1分。P4论文将接受范围试探为(2c/3, min(4c/3, 1))如果c′在接受范围内则给出1分。P5与P2相似真实数据集和生成的数据集的奇异值分布之间的相似性由Kolmogorov-Smirnov D统计量度。对D统计量小于0.2的生成器给予1分。实验结果及结论生成器的结果在表中进行了数字比较。HyperPANaivePA和子集采样这两个表的总分分别为64、49和57。其中论文提出的模型HyperPA得分最高。如果不考虑子集交互变量S、NP和n不足以重现pattern因为即使使用S、NP和nNaivePA和子集采样也无法做到。论文工作的贡献是三方面的多级分解首先提出多级分解作为研究超图的有效手段。多级分解有几个好处1它捕获超图内的组交互2其图形表示为利用现有工具提供了便利3它代表了原始超图而没有信息丢失。实际超图中的模式pattern论文介绍在13个现实世界超图中持有的一组常见模式。具体来说在不同的分解级别是巨型连通分量、重尾度分布、小有效直径、高聚类系数和偏斜奇异点的价值分布。有效仿真的超图生成器最后引入HyperPA这是一种超图生成器它很简单但是能够在不同分解级别上再现真实世界超图的模式。通过保持超图中节点的子集交互的连通性HyperPA在重现模式方面表现出比其他基准模型更好的性能。 OpenKG开放知识图谱简称 OpenKG旨在促进中文知识图谱数据的开放与互联促进知识图谱和语义技术的普及和广泛应用。点击阅读原文进入 OpenKG 博客。
