跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂479网络图扩展摘要*瓦莱里娅·菲昂达意大利卡拉布里亚大学DeMaCSfionda@mat.unical.it朱塞佩·皮罗ICAR-CNR意大利pirro@icar.cnr.it克劳迪奥·古铁雷斯智利大学DCCcgutierr@dcc.uchile.cl摘要研究了基于类图信息的知识地图构建问题。我们生活在数字时代，与地球类似，网络太大，其相互关系太复杂，任何人都无法通过直接观察掌握其中的大部分因此，将制图学原理应用于数字景观的问题是耐人寻味的。我们介绍了一个数学形式主义，捕捉的一般概念的地图的一个图形，并使其开发和操作中的一个半自动化的方式。我们描述了我们的形式主义的Web上的关联数据图的实现，并讨论了算法，有效地生成和组合（通过代数）区域和地图。最后，我们讨论了知识地图的例子与工具实现我们的框架。ACM参考格式：瓦莱里娅·菲昂达朱塞佩·皮罗克劳迪奥·古铁雷斯2018年。 建立网络图的知识地图：扩展摘要. 在WWW '18伴侣：2018年网络会议伴侣，2018年4月23日至 27 日 ， 法 国 里 昂 。 ACM ， New York ， NY ， USA ， 4 页 。https://doi.org/10.1145/3184558.31862371引言Web是一个巨大的互联信息空间，用户通常通过浏览器启用的导航来访问然而，网络实在是太大了，它的相互关系太复杂了，任何人都无法仅仅通过直接观察来掌握。例如，考虑使用GoogleScholar导航引文网络的任务。一个典型地从种子纸开始然后，通过点击被引用链接，她/他导航到引用了种子论文的论文，选择感兴趣的论文（例如， 通过将它们加书签）并继续。过了一段时间，就很难根据感兴趣的论文和它们之间的联系来重建引文网络。而且，整个过程都是手动的。具有识别感兴趣的引用网络的部分的自动方式（即，论文及其连接）和某种形式的抽象表示，其中只有突出的论文（例如，在标题中包含某些关键词的论文）和它们之间的链接，将是对导航的非常有用的支持为了处理Web上大量的互联信息，我们从制图学中获得灵感，并引入了一个框架来构建Web地图在物理*Aneextendedversionappear edinArtificialIntelligence[7]本文在知识共享署名4.0国际（CC BY 4.0）许可下发布作者保留在其个人和公司网站上以适当的归属方式传播作品的权利。WWW©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.3186237空间，地图制作的过程可以概括为两个主要步骤，即选择和抽象[10]。选择使人们能够只关注将服务于地图目的的特定信息片段;具体地说，在这个阶段中，要绘制的区域被选择。在我们先前关于导航引用网络的示例中，区域将包括节点（即，论文），并通过导航期间访问的链接引用抽象性是地图的基本属性，即地图总是小于它所描绘的区域。 抽象我们的引用网络可以通过仅考虑具有某些属性的节点来完成（例如，在一些特定会议上发表的论文）以及它们之间的链接。Web技术和语言的最新进展源于语义Web建议，以及资源描述框架（RDF）标准数据格式中的结构化信息在计划规模上的可用性，为Web地图的自动化构建提供了新的 一方面，在RDF谓词中编码的数据项之间的相互链接具有精确的语义含义，从而允许精确表征可达性的性质，这在提取Web区域中至关重要。 另一方面，地图可以被赋予RDF表示，然后不仅由人类通过视觉解释来处理，而且由于RDF的机器可处理性质，还可以由机器来处理。这将促进地图的交流、合并和再利用。我们相信，Web地图的可用性可以帮助用户处理Web区域的复杂性，就像地理地图帮助用户处理大型物理区域的复杂性有许多工具（部分）触及这些方面。 最传统和最流行的是书签：一个URL列表，有时按标签分类。该想法已经被增强以结合例如社交特征（共享、排名、标记书签）和/或不同类型的数据的注释（例如，不仅是URL，还有文档）。Delicious和Diigo是两个流行的书签系统。 其他方法超越了书签，并且能够组织URL以突出显示它们之间的连接。 结果以图形地图的形式进行分组和呈现。一些示例是像Tag Galaxy的搜索引擎、导航历史工具（例如，[3]）、可视化HTML站点地图（供用户使用）和Web地图集[2]）。最近的方法集中于提供特定领域的视觉表示，诸如出版物或新闻（例如，[11]）。现有的方法不符合我们设想的地图的想法。首先，他们没有建立地图的制图意义，因为他们错过了抽象阶段。其次，它们仅为人类可视化而设计。第三，它们不能实现区域的声明性规范（例如，Web的感兴趣部分）进行映射。第四，它们缺乏正式的数学模型。跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂480⊆昆汀Tarantinoe2约翰福特士丹利伍迪·艾伦地图2马丁·昆廷斯科塞斯·塔伦蒂诺约翰福特木本艾伦e1士丹利库布里克地图1蒂姆伯顿特里Gilliam大卫林奇格雷格哈里森影响控制器之间士丹利库布里克奥森威尔斯木本艾伦Lars von特里尔约翰福特马丁斯科塞斯昆汀Tarantino彼得杰克逊保罗·T.安德森尼古拉斯伦夫大卫芬奇图1：取自维基百科的Web区域举个例子图1示出了取自维基百科的Web区域，其中用户Syd已经标记了他最喜欢的导演，即J。Ford，S. Kubrick，W.Allen和Q.塔伦蒂诺除了这些节点之外的区域还包含其他节点（较亮的节点）。一个问题出现了：一个好的希德最喜欢的导演的地图应该是什么样子的？图2显示了两种可能的地图。贴图1包含的节点和边比贴图2多Map 2采用特定的简洁策略：它最小化节点和边的数量以保持成对的区分节点之间的连通性（即，Syd节点M.不包括Scorsese，因为它不是可区分节点，而是J.Ford和Q.Tarantino（两个区分节点）仍然经由直接边e2来维持。图1中的边el不包括在图2中，因为J.Ford和W.Allen仍然通过S进行维护 Kubrick和没有路径在该地区从J。福特W。艾伦没有经过显著节点。图2：图2中的区域的两个可能的地图1.一、区域地图的概念本质上是以简洁的方式反映区域中的信息，即不同节点之间的连通但是，地图中必须包含多少原始区域作者J。L. 博尔赫斯在谈到“埃姆皮尔地图”时，嘲笑完全准确的地图... 与之完全吻合 在另一个极端，最小映射是仅包括没有关于其连接性的信息的节点的那些（例如，书签）。在它们之间存在除了区分的节点之外还提供关于它们的连通性的信息的地图（例如，图1和图2）。灵活的映射框架应考虑不同类型的映射。在下文中，我们给出了Web映射的基本原理（第2节），描述了如何在当前的Web基础设施中映射这个框架（第3节），然后得出结论（第4节）。2网上的正式地图制作地图的研究被称为制图学[10]。制图学依赖于人类大脑阅读地图中所表示的复杂信息的能力。在下文中，我们提供了图的映射的形式和一般定义，其中节点表示对象（例如，人）和边缘关系（例如，友谊，其中。正如我们将展示的，“对象”映射的数学表征带来了新的挑战和机遇。一方面，我们不得不面对这样的研究问题：什么是好的地图？如何有效地计算地图？另一方面，地图可以被赋予在RDF中）表示，然后可以共享、交换、重用和组合。2.1作为数学对象的地图我们将Web空间建模为有向图。 设Γ =（VΓ，ΕΓ）是网络区域，其中VΓ和ΕΓ分别是节点和有向边的集合。在地图构建的过程中，我们忽略边缘标签（如果存在），因为我们对捕获节点之间的可达性感兴趣图1是Web区域的示例 在本文的其余部分，我们使用以下符号：u → v表示边（u，v）∈ EΓ且u v是Γ中从u到v的路.定义1（MAP）。Γ =（V Γ，E Γ）的映射M=（VM，EM）是图s.t. VM VΓ且每一条边（x，y）∈ EM在Γ中蕴涵x y。映射的思想本质上是表示成对的区分节点之间的可达性（即，VM中的节点），以简洁的方式。这种定义捕获了在Web上定义的一些基本形式的地图，例如书签。对于书签，可分辨节点集是Web图中已被标记为感兴趣的页面集然而，这种概念的地图不考虑可达性信息之间的区别节点。定义2（完全MA p）。Γ =（V Γ，E Γ）的映射M=（VM，EM）是完备的当且仅当，对所有x，y∈VM，Γ中的x y蕴涵M中的xy。完整的地图解决问题的可达性之间distinguished节点。一个可能的完整地图的区域图。图1中的Map1中显示了1。二、 它包括一些直接边，例如J之间的边。Ford和S.库布里克虽然最初并不存在于该地区。然而，有时完整性不足以通过地图总结信息J.Ford和S. 库布里克是有用的，因为它表明S。库布里克可以从J.Ford通过节点（O. 不属于地图（见图）。①的人。现在考虑图1中的图1中的边e1。2、J.Ford和W.艾伦与前面的情况相比，该边缘不用于相同的事实上，J.Ford和W.Allen仍然通过S进行维护。库布里克和没有其他路径在该地区从J。福特W。Allen仅传递非区分节点。因此，e1是冗余的。避免冗余对于最小化保持区分的通信设备对之间的连接性所需的信息量结我们需要完善地图的概念。设Γ=（VΓ，EΓ）是Web区域，并且N VΓ是节点的集合。我们写uNv当且仅当Γ中有一条从u到v的路不经过N中的任何中间节点。跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂481∈→ R∈MM›→→×P定义3（良好M A p）。Γ=（V Γ，Ε Γ）的映射M =（VΜ，ΕΜ）是好的，如果对于每对节点x，y VΜ，以下两个性质成立：(1) 在Γ中的xVMy蕴涵在M中的x →y;(2) 在M中的x→ y蕴涵在Γ中的x VMy。一张好的地图也是一张完整的地图。图2 2显示了图1中的区域的良好地图。1.一、好地图的概念背后的想法是，给出一个经济的代表性之间的可达性对显着的节点。此外，好的映射有一个重要的性质，如下面的定理所报告的。定理4. 设Γ=（VΓ，EΓ）是腹板区域。给定NVΓ，存在Γ上唯一的好映射M，其中VM=N。正如引言中所讨论的，灵活的地图框架应该考虑不同类型的地图。准确的地图是该地区本身。 好的地图是包括连接信息的最小地图的示例。然而，在一些情况下，除了区分节点之外，还需要包括更多节点我们现在介绍k-映射，一个良好的映射家族，它考虑区域中的节点具有一些属性。为此，令f： Vr是在区域的节点上定义的实值函数。函数f可以是例如节点的中心性的度量（例如，PageRank）或流行度度量（例如，入射边缘的数量）。定义5（k-mA ps）。 设Γ=（V，E）是网区域，并且地图可以（部分）避免。接下来的结果显示了这种可能性。对于给定的Web区域Γ=（VΓ，EΓ）和SVΓ，我们用SΓ*表示Γ上S的传递闭包，即图（S，{（x，y）：xSyinΓ}）。我的建议是8号。设M1=（VM1，EM1），M2=（VM2，EM2）是Γ上的好映射.（1）M1M2=（VM1∩VM2）M*1∪（VM1∩VM2）M*2（2）EM1M2EM1∪EM2∪ {（x，y）∈EΓ：x∈VM1，y∈VM2} ∪∪ {（y，x）∈EΓ：x∈VM1，y∈VM2} ∪∪ {xVM1∪VM2y，x∈VM1，y ∈VM2} ∪∪ {yVM1∪VM2x，x ∈VM1，y ∈VM2}第9章. 图M1M2可以仅基于在图M1、M2和时间O中可用的信息来计算（|VM1 ∩VM2|×（|VM1|+的|EM1|+的|VM2|+的|EM2|））。此外，近似M1M2（模冗余）的计算不能比从头开始计算VM1 ∪VM2上的好映射更有效。3Web区域的声明规范我们简要地讨论了如何声明性地指定Web区域，并保持节点之间的连接信息的问题这个需要被编码在下面的一般问题中：给定图G =（VG，EG）和一组节点N VG，构造一个子图（aregion）R=（V′，E′）使得NV′.ΓIfaloutsosel al. [4]解决这个问题的一个变体：给定一个f：VΓ→ R是实值函数。Γ的k-映射是由可区别节点集{v ∈VΓ：f（v）≥ k}生成的好映射。计算好的地图。 地图捕获给定一组可区分节点的区域中的信息。我们有以下结果。定理6. 设Γ=（VΓ，EΓ）是腹板区域。给定VMVΓ，Γ的唯一好映射M =（VM，EM）可以在时间上计算：(1) O（|VM|×（|VΓ\VM|+的|EΓ|）），如果Γ是一般图。(2) C（|VM|×个|VΓ\VM|）+|EΓ|）如果Γ是DAG。2.2映射代数在本节中，我们研究映射的代数性质并定义其上的下面的定理说明了映射族的性质。定理7. 设Γ=（VΓ，EΓ）是一个Web区域，M（Γ）是Γ上所有映射的集合.此外，设Mi=（VMi，EMi）（Γ）是映射.(1) M（Γ）上的二元关系，定义为M1 M2iffVM1 VM2是M（Γ）上的偏序。(2) 阶导出一个布尔代数（M（Γ），Γ，），其中：M1 M2是Γ在VM1∪ VM2上的唯一好映射; M1 M2是Γ在VM1∩ VM2上的唯一好映射。(3) 从（P（V），∪，∩，V，）出发（ （Γ）， 、，Γ， ），由N给出MN （N在Γ上的唯一好映射）。在地图上具有良好定义的操作使得能够从其他地图获得新地图问题是如果重新计算一个边加权无向图，两个顶点s，t和一个整数k，找到一个包含s，t的大小为k的连通子图H，它使给定的优度函数最大化。已经提出了其他方法来发现人群（例如，[1]）或简化网络（例如，[12]）。然而，这些方法不提供代数来操纵所产生的对象此外，它们还假设整个G是局部可用的;这阻碍了它们对诸如Web图的分布式图的适用性。为了正式指定和获取Web区域，我们利用图形导航语言导航语言是V G子图（G）（V G）形式的一组函数（许多导航语言（例如，XPath，nSPARQL [9]）能够查找由一系列边标签连接的节点对，这些边标签与通过边标签字母表上的正则表达式表达的某种模式（或导航表达式）相 这对我们的目标来说是不够的;我们的框架可以与任何导航语言一起工作，其语义能够输出子图而不是节点对的集合（例如NautiLOD [5，6，8]）。3.1实施的制度构建关联数据网络地图的框架已在MA Ge工具1中以Java实现，并使用NautiLOD来指定和构建Web区域。我们现在讨论一个真实世界的例子2。1，其可在地址http://mapsforweb.wordpress.com处下载22016年的数据跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂482M1好地图∩访问S.Kubrick好地图T. BernersLee访问T. Berners Lee好地图S. 库布里M1第60节-第六章S. 库布里M1M2第15节-地图T. Berners LeeM2M1M2结束节点起始节点其他节点图3：S的影响图Kubrick和T.伯纳斯·李只考虑距离6的科学家实施例10. （影响网络和代数图）指定两个区域，其中包含影响或受到斯坦利·库布里克（SK）或蒂姆·伯纳斯-李（TBL）影响的人，距离为6。区域中的结束节点必须是科学家。计算地图并使用地图的代数。与SK的影响网络相关联的区域包含2981个节点和7893条边。 与SK（109个节点; 2629条边）相关联的良好地图概括了该区域，然后提供了对结束节点之间的连接性的洞察（即， 已经或已经影响SK的科学家）和SK。 我们通过计算该区域的60-map（M1）（120个节点; 3627个边缘）。与TBL相关的区域较小（149个节点; 236个边缘）。例如，相关的好图（18个节点; 43条边）告诉我们，存在从TBL到G的影响路径。皮亚诺通过P。道的普通当放大这条路径时，通过计算该区域（23个节点; 43条边）的15-map（M 2），我们发现无尾节点B罗素也在路上。图图3还显示了地图代数的例子它显示了M1和M2的交点。结果是通过对区域进行合并然后从一组可分辨节点计算出良好的地图而获得的良好地图（见定义3）由VM 1 VM 2给出。然而，使用代数的优点是避免从头开始计算好的地图，并且在不查看区域的情况下获得它作为一个例子，在M1和M2的交集中我们有节点G.Peano和A. Tarski，这意味着两者都属于SK和TBL的影响力网络M1和M2的并集的映射使得能够将来自两个映射的信息放在一起这使得能够发现在两个映射中不存在的节点对 在该具体示例中，SK和TBL之间不存在路径，SK和TBL之间也不存在路径。M1也不在M2中。然而，使得能够发现TBL和SK之间的连接的k -映射的并集（即，TBL→P.出口→B。F. Skinner←SK）.4总结发言由于人的I/O能力的限制，在Web规模的信息管理要求自动机制，从而机器可处理的信息。 在本文中，我们已经表明，地图，帮助人类在信息空间中导航的关键设备，是有意义的Web空间。 我们认为，这里提出的正式模型是一个起点，进一步发展的网络上的地图。引用[1] J. Adibi，H. Chalupsky，E. Melz，A. Valente等人KOJAK集团搜索器：通过集成的基于知识和统计推理连接点。在AAAI，第800-807页，2004中。[2] M.道奇和R. Kitchin 网络空间地图集。艾迪生-韦斯利《大不列颠人》，2001年。[3] P. Doemel WebMap：一个图形化的超文本导航工具。计算机网络和ISDN系统，28（1）：85 -97，1995。[4] C. Faloutsos，K.S. McCurley，和A.汤姆金斯快速发现连接子图。在KDD中，第118-127页。ACM，2004年。[5] V. Fionda，C. Gutierrez和G. Pirro.从图导航中提取相关子图。在ISWC（海报演示），卷914中。CEUR-WS.org，2012年。[6] 诉菲翁达角Gutierrez和G.Pirro. 数据网络上的语义导航：路径、网络片段和动作的在WWW中，第281ACM，2012年。[7] 诉菲翁达角Gutierrez和G.Pirro. 构建网络图的知识地图第内特尔，239：143[8] 诉菲翁达湾Pirrò和C.古铁雷斯Nautilod：一种数据图网络的形式化语言TWEB，9（1）：5：1[9] J. Pérez，M. Arenas和C.古铁雷斯nSPARQL：RDF的导航语言。JWS，8（4），2010.[10] A. H. 罗宾逊，J。Morrison，O.C. Muehrcke，A.J.Kimerling和S.C. 古普蒂尔制图的要素。Wiley，1995年。[11] D. 沙哈夫角Guestrin和E.霍维茨思维列车：生成信息地图。在WWW中，第899-908页。ACM，2012年。[12] F. Zhou，S.Malher和H.托伊沃宁以最小的连通性损失简化网络在ICDM，第659-668页中。IEEE，2010。
