“集智百科精选”是一个长期专栏,持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目,集智百科希望打造复杂性科学领域最全面的百科全书,欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入!


本文是对集智百科中“图距离”词条的摘录,参考资料及相关词条请参阅百科词条原文。


本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!


目录


一、什么是图距离?
二、相关概念
三、寻找伪边缘点的算法
四、相关资源推荐
五、集智百科词条志愿者招募
    
图距离:https://wiki.swarma.org/index.php?title=图距离_Distance_(graph_theory)





1. 什么是图距离?




在图论 graph theory的数学领域定义中,图中两个顶点之间的距离是最短路径 shortest path(也称为图测地线 graph geodesic)中连接它们的边的数目。这也被称为测地距离 Geodesic Distance。但,两个顶点之间可能有不止一条最短路径。一般地,如果两个顶点间没有路径连接,也就是说,如果它们属于不同的连通分支 connected components,那么这两点间的距离就被定义为无穷大。

在有向图 directed graph中,顶点  和 之间的距离 被定义为从  到  之间由弧组成的最短有向路径的长度,但前提是至少存在一条这样的路径。与无向图不同,   不一定与 一致,而且可能一个是符合定义的,而另一个不符合。





2. 相关概念


一个由点集根据图中点集的距离定义的度量空间 metric space被称为图度量 Graph Metric。

当且仅当图是连接的时,(无向图的)顶点集和距离函数构成度量空间。

顶点 的”’ 离心率 eccentricity 是它与其他顶点之间最大的距离,用 表示。这可以用来判断一个节点距离图中最远节点的距离。图的”’半径 radius”’ 是任何顶点的最小离心率,用  表示。图的”’直径 diameter”’  是图中任何顶点的最大离心率。

即  是任何一对顶点之间最大的距离, 。要找到图的直径,首先要找到每对顶点之间的最短路径。

这些路径的最大长度是图的直径。在半径为 的图中,”’中心点 central vertex”’是离心率为  顶点,即距离等于半径的顶点,或者等效于一个能够满足  的顶点 。在直径为 的图中,”’边缘点 peripheral vertex”’ 是离心率为  顶点,即距离等于直径的顶点。定义,如果 , 是次要的。

伪边缘点 Pseudo-Peripheral Vertex   具有这样的属性:对于任何顶点  ,如果 距离 越远,那么 距离  越远。定义,如果一个顶点”u”对于每个顶点”v”都有 保持 ,则”u”是伪周边顶点。

依据图的顶点到给定起始顶点的距离将集合划分成多个子集称为图的层次结构 Level Structure of The Graph。

对于每对顶点,都有一条连接它们的唯一最短路径的图,则将该图称为测地图 geodetic graph。例如,所有的树状图都是测地图。



3. 寻找伪边缘点的算法


通常,外围稀疏矩阵 sparse matrix算法需要具有高离心率的起始点。边缘点会是首选,但往往难以计算。在大多数情况下,可以使用伪边缘点。通过以下算法,能轻松找到伪边缘点:

选择顶点 。
在所有尽可能远离的顶点中,让是一个最小度的顶点。
如果,那么令  并重复步骤2,否则 是一个伪边缘点。






4. 相关资源推荐


课程推荐

本课程中,我们有幸邀请了汪小帆、赵海兴、许小可、史定华、陈清华、张江、狄增如、陈关荣、樊瑛、刘宗华这十个来自六大不同高校、在网络科学领域耕耘许久的教授作为导师,依据教材框架,各有侧重地为我们共同勾勒出整个学科的美丽图景,展示这个学科的迷人魅力,指引这个学科的灿烂未来。


我们将颠覆传统老师通篇主讲的课堂模式,用一种前所未有的集智课堂形式来解惑答疑,帮助大家完成从散点思维到网络思维,直至网络科学思维的跃升。



课程推荐:巴拉巴西网络科学https://campus.swarma.org/course/1754

积分充值活动

集智的课程视频关注复杂系统和人工智能等跨学科前沿领域,在复杂系统建模、图神经网络、网络科学、计算社会科学、因果科学等领域有大量全网独家内容。
 
我们特推出积分充值活动,本次活动持续至2月11日。积分可以用于购买集智学园站内课程、参与集智俱乐部读书会。现在充值集智学园积分(∫),可获赠额外积分和复杂性科学知识卡片。
 

扫码充值
 
积分充值规则:扫描二维码充值 300 元,得 33000 ∫,赠送 2 副限量版复杂性科学知识卡充值 500 元,得 55000 ∫,赠送 4 副限量版复杂性科学知识卡充值 1000 元,得 110000 ∫,赠送 10 副限量版复杂性科学知识卡
 

复杂性科学知识卡(扑克)2.0版



5. 集智百科词条志愿者招募



作为集智百科项目团队的成员,本文内容由Ryan参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页,更多信息可以访问其集智百科个人主页。






以上内容都是我们做这项目的起点,作为来自不同学科和领域的志愿者,我们建立起一个有效的百科团队,分配有审校、翻译、编辑、宣传等工作。我们秉持:知识从我而来,问题到我为止的信念,认真负责编撰每一个词条。






在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。


如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!




集智百科报名表


来源:集智百科编辑:曾祥轩



推荐阅读什么是人工社会?| 集智百科

什么是自组织 | 集智百科

什么是元胞自动机?| 集智百科
什么是李雅普诺夫函数 | 集智百科

什么是非线性系统 | 集智百科

加入集智,一起复杂!



点击“阅读原文”,阅读图距离相关内容与文献