下载掌阅APP，畅读海量书库
立即打开
我们将用本节来介绍图论领域中一些有用的概念。这些术语用来描述图数据之间的连通性。让我们来可视化样本数据中前三个人的图数据。
图2-4中展示的数据将用来阐释本节接下来的部分引入的基本概念。这些数据包含三个人的信息：Michael、Maria和Rashika。Michael和Maria共享一个账户，如图2-4所示。在我们的例子里，Rashika不和其他任何人共享数据。
图2-4：图数据一览，我们将用它来介绍本章中新的图术语
最先需要介绍的概念是图、图数据及其定义中用到的最基本元素。这些术语广泛应用在图领域的所有成员中，作为图的基本元素为人所知。
图
图是数据的一种呈现方式，有两种不同的元素：顶点和边。
顶点
顶点表示数据中的一个概念或实体。
边
边表示顶点之间的关系或链接。
你可能已经见过我们讨论的基本元素了，从图2-4中的金融数据包含四个概念实体：客户、账户、信用卡和贷款。这些实体自然地在图中被画成顶点。
我们在本书中避免使用节点（node）一词，因为我们关注分布式图，而节点在分布式系统、图论和计算机科学中有不同的含义。
接下来，我们用边来连接顶点。这些联系表示了不同数据块之间存在关系。在图数据中，一条边连接两个顶点，作为两个对象之间关联的抽象表示。
对于这份数据，我们用边表示一个人和他的金融数据之间的联系。我们把数据建模来表明；客户拥有（own）账户，客户借有（owe）贷款或者客户使用（use）信用卡。这些边在图数据库中变成了“拥有”“借有”和“使用”。
结合上述，数据中所有的这些顶点和边可以呈现整张图。
虽然图论中有很多概念值得深究，让我们从邻接（adjacency）这个术语开始。你会发现在图论中讨论数据如何连接时离不开这个词。本质上，邻接是个数学术语，用来描述顶点之间如何相连。正式的定义如下：
邻接
如果两个顶点之间有一条边相连，则两个顶点称为邻接。
在图2-4中，Maria和acct_14邻接。同样地，我们可以看到Michael和Maria都和acct_14邻接，因为他们都拥有这个账户。当你能够用不同的方式看到实体和它们之间的关系的时候，在应用中使用图数据的优势立马显现出来。
邻接的概念会贯穿整本书，你会在各种不同的话题中和它不期而遇，从数据的连通性到磁盘上不同的存储格式。目前为止，你只需要知道这个热词代表了顶点之间如何连接。
互相连接的数据形成社区。在图论中，这些社区被称为邻接点（neighborhood）。
邻接点
对于顶点v，所有和v邻接的顶点都是v的邻接点，写作N（v）。所有的邻接点都是v的邻居。
图2-5向我们展示了图邻接点中的概念，从customer_0 Michael开始。在样本数据中，顶点cc_17、loan_32和acct_14都和Michael直接相连或邻接。我们称之为customer_0的一级邻接点。
你可以从初始顶点开始带着这个概念继续前进。二级邻接点包含从Michael开始相距两条边的顶点；Maria就是Michael的二级邻接点。反之同理，Michael是Maria的二级邻接点。从单个起始点开始，如此往复就可以遍历整张图的所有顶点。
邻接点的概念引出了距离。谈论这个样本数据的连接性的另一种方式就是，从一个顶点走到另一个顶点需要多少步。讨论Michael的一级或者二级邻接点，和找到从Michael开始距离为1和2的顶点是一样的。
图2-5：一个可视化例子：从customer_0开始的图邻接点
距离
在图数据中，距离是指从一个顶点到另外一个顶点之间需要走过的边的数量。
在图2-5中，我们选择了顶点Michael作为起始点。顶点cc_17、loan_32和acct_14是Michale的一级邻接点，和与Michael距离为1等价。
在数学表达中，它经常被写作dist（Michael，cc_17）=1。这也意味着从起始点开始的所有二级邻接点都有两条边的距离，以此类推——具体写作dist（Michael，Maria）=2。
邻接、邻接点和距离的概念帮助我们理解两份数据之间是否连通。对很多应用来说，了解一份数据和它邻居之间的连通性如何是非常有用的。
是否连通，以及连通性是否良好之间的区别引出了一个数学界的新术语：度（degree）。
度
一个顶点的度是与其相关（即相连）的边的数量。
换句话说，我们讨论顶点的度数是指与该顶点接触的边数。
当我们展示接下来的例子时，回想一下图2-4。在那张图中，我们看到有三条边分别将Michael连到cc_17、loan_32和acct_14。可以说Michael的度是3，也可以表示为deg（Michael）=3。
在这份数据中，有两个顶点的度是2。具体来说就是acct_14邻接Michael和Maria，所以它的度是2。在图的右侧，我们看到Rashika也只有两条边，也就是说Rashika的度是2。
我们的样例数据中一共有5个度数为1的顶点。它们分别是loan_32、cc_17、Maria、cc_32和acct_5。
在图论中，只有一度的顶点被称为叶（leaf）。
我们也把一个顶点的度分为两类，按照这条边是从某个顶点开始还是结束。让我们引入两个新的术语分别来描述它们。
入度
一个顶点的入度是指所有和该顶点相关（或相触）的且进入该顶点的边的总量。
出度
一个顶点的出度是指所有和该顶点相关（或相触）的向外延伸的边的总量。
让我们把这些定义应用在刚才提到过的例子上。
Michael的三条边都是从Michael开始、结束于其他顶点：cc_17、loan_32和acct_14。因此，我们说Michael的出度为3，因为三条边都是向外的。
acct_14的入度是2，因为它有两条进入的边，分别来自Michael和Maria。Rashika的两条边都是向外的，所以我们说Rashika的出度为2。
cc_17的入度是1，因为连接它的边是进来的，对loan_32、cc_32和acct_5也同理。Maria的出度是1，因为它一条连出去的边到acct_14。
顶点的度的含义
数据科学家和图论学者使用顶点的度来理解图数据中连接的类型。一个可以开始的地方是在图中找到连接度最高的顶点。
根据应用程序的不同，高度数的顶点可以被认为是枢纽或具有高度影响力的实体。
找到这些高度连接的顶点是很有用的，因为当在图数据库里存储或查询它们时会对性能产生影响。对图数据库实践者来说，度数极端高的顶点（超过10万条边）被称之为超级节点（supernode）。
对于本节的目的，我们希望阐明如何在你的应用程序里运用和解释图结构。对于高度连接的顶点的性能问题，我们将在第9章详细说明，也会正式定义超级节点，解释它们对你的数据库的影响，并逐步说明应对策略。
回想本章开始时我们提出的三个问题。目前为止我们提到过的概念都只对应了其中前两个问题。接下来会引入一个工具来教会你如何通过把可视图表转化为代码来建模图结构。让我们开始。