关于图计算&图学习的基础知识概览：前置知识点学习（Paddle Graph Learning (PGL)）

欢迎fork本项目原始链接：关于图计算&图学习的基础知识概览：前置知识点学习（Paddle Graph L）https://aistudio.baidu.com/aistudio/projectdetail/4982973?contributionType=1

因为篇幅关系就只放了部分程序在第三章，如有需求可自行fork项目原始链接。

0.1图计算基本概念

首先看到百度百科定义：

图计算（Graph Processing）是将数据按照图的方式建模可以获得以往用扁平化的视角很难得到的结果。

图（Graph）是用于表示对象之间关联关系的一种抽象数据结构，使用顶点（Vertex）和边（Edge）进行描述：顶点表示对象，边表示对象之间的关系。可抽象成用图描述的数据即为图数据。图计算，便是以图作为数据模型来表达问题并予以解决的这一过程。以高效解决图计算问题为目标的系统软件称为图计算系统。

大数据时代，数据之间存在关联关系。由于图是表达事物之间复杂关联关系的组织结构，因此现实生活中的诸多应用场景都需要用到图，例如，淘宝用户好友关系图、道路图、电路图、病毒传播网、国家电网、文献网、社交网和知识图谱。

为了从这些数据之间的关联关系中获取有用信息，大量图算法层出不穷。它们通过对大型图数据的迭代处理，获得图数据中隐藏的重要信息。图计算作为下一代人工智能的核心技术，已被广泛应用于医疗、教育、军事、金融等多个领域，并备受各国政府、全球研发机构和巨头公司关注，目前已成为全球科技竞争新的战略制高点。

0.1.1图计算

• 图可以将各类数据关联起来：将不同来源、不同类型的数据融合到同一个图里进行分析，得到原本独立分析难以发现的结果；
• 图的表示可以让很多问题处理地更加高效：例如最短路径、连通分量等等，只有用图计算的方式才能予以最高效的解决。然而，图计算具有一些区别于其它类型计算任务的挑战与特点：
• 随机访问多：图计算围绕图的拓扑结构展开，计算过程会访问边以及关联的两个顶点，但由于实际图数据的稀疏性（通常只有几到几百的平均度数），不可避免地产生了大量随机访问；
• 计算不规则：实际图数据具有幂律分布的特性，即绝大多数顶点的度数很小，极少部分顶点的度数却很大（例如在线社交网络中明星用户的粉丝），这使得计算任务的划分较为困难，十分容易导致负载不均衡。

0.1.2图计算系统

随着图数据规模的不断增长，对图计算能力的要求越来越高，大量专门面向图数据处理的计算系统便是诞生在这样的背景下。

Pregel由Google研发是专用图计算系统的开山之作。Pregel提出了以顶点为中心的编程模型，将图分析过程分析为若干轮计算，每一轮各个顶点独立地执行各自的顶点程序，通过消息传递在顶点之间同步状态。Giraph是Pregel的一个开源实现，Facebook基于Giraph使用200台机器分析万亿边级别的图数据，计算一轮PageRank的用时近4分钟。

GraphLab出自于CMU的实验室，基于共享内存的机制，允许用户使用异步的方式计算以加快某些算法的收敛速度。PowerGraph在GraphLab基础上做了优化，针对实际图数据中顶点度数的幂律分布特性，提出了顶点分割的思想，可以实现更细粒度的数据划分，从而实现更好的负载均衡。其计算模型也被用在后续的图计算系统上，例如GraphX。

尽管上述的这些图计算系统相比MapReduce、Spark等在性能上已经有了显著的性能提升，但是它们的计算效率依然非常低下，甚至不如精心优化的单线程程序。

Gemini由清华大学计算机系的团队提出，针对已有系统的局限性，提出了以计算为中心的设计理念，通过降低分布式带来的开销并尽可能优化本地计算部分的实现，使得系统能够在具备扩展性的同时不失高效性 [5] 。针对图计算的各个特性，Gemini在数据压缩存储、图划分、任务调度、通信模式切换等方面都提出了对应的优化措施，比其他知名图计算系统的最快性能还要快一个数量级。ShenTu沿用并扩展了Gemini的编程和计算模型，能够利用神威·太湖之光整机上千万核的计算资源，高效处理70万亿边的超大规模图数据，入围了2018年戈登·贝尔奖的决赛名单。

除了使用向外扩展的分布式图计算系统来处理规模超出单机内存的图数据，也有一些解决方案通过在单台机器上高效地使用外存来完成大规模图计算任务，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。

0.2 图关键技术

0.2.1 图数据的组织

由于实际图的稀疏性，图计算系统通常使用稀疏矩阵的存储方法来表示图数据，其中最常用的两种是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分别按行（列）存储每行（列）非零元所在列（行），每一行则（列）对应了一个顶点的出边（入边）。

0.2.2图数据的划分

将一个大图划分为若干较小的子图，是很多图计算系统都会使用的扩展处理规模的方法；此外，图划分还能增强数据的局部性，从而降低访存的随机性，提升系统效率。
对于分布式图计算系统而言，图划分有两个目标：

1. 每个子图的规模尽可能相近，获得较为均衡的负载。
2. 不同子图之间的依赖（例如跨子图的边）尽可能少，降低机器间的通信开销。

图划分有按照顶点划分和按照边划分两种方式，它们各有优劣：

1. 顶点划分将每个顶点邻接的边都放在一台机器上，因此计算的局部性更好，但是可能由于度数的幂律分布导致负载不均衡。
2. 边划分能够最大程度地改善负载不均衡的问题，但是需要将每个顶点分成若干副本分布于不同机器上，因此会引入额外的同步/空间开销。

所有的类Pregel系统采用的均为顶点划分的方式，而PowerGraph/GraphX采用的是边划分的方式。Gemini采用了基于顶点划分的方法来避免引入过大的分布式开销；但是在计算模式上却借鉴了边划分的思想，将每个顶点的计算分布到多台机器上分别进行，并尽可能让每台机器上的计算量接近，从而消解顶点划分可能导致的负载不均衡问题。

0.2.3顶点程序的调度

在以顶点为中心的图计算模型中，每个顶点程序可以并行地予以调度。大部分图计算系统采用基于BSP模型的同步调度方式，将计算过程分为若干超步（每个超步通常对应一轮迭代），每个超步内所有顶点程序独立并行地执行，结束后进行全局同步。顶点程序可能产生发送给其它顶点的消息，而通信过程通常与计算过程分离。

同步调度容易产生的问题是：

1. 一旦发生负载不均衡，那么最慢的计算单元会拖慢整体的进度。
2. 某些算法可能在同步调度模型下不收敛。

为此，部分图计算系统提供了异步调度的选项，让各个顶点程序的执行可以更自由，例如：每个顶点程序可以设定优先级，让优先级高的顶点程序能以更高的频率执行，从而更快地收敛。
然而，异步调度在系统设计上引入了更多的复杂度，例如数据一致性的维护，消息的聚合等等，很多情况下的效率并不理想。因此，大多数图计算系统采用的还是同步的调度方式；少数支持异步计算的系统也默认使用同步方式进行调度。

0.2.4 计算与通信模式

图计算系统使用的通信模式主要分为两种，推动（Push）和拉取（Pull）：

1. 推动模式下每个顶点沿着边向邻居顶点传递消息，邻居顶点根据收到的消息更新自身的状态。所有的类Pregel系统采用的几乎都是这种计算和通信模式。
2. 拉取模式通常将顶点分为主副本和镜像副本，通信发生在每个顶点的两类副本之间而非每条边连接的两个顶点之间。GraphLab、PowerGraph、GraphX等采用的均为这种模式。

除了通信的模式有所区别，推动和拉取在计算上也有不同的权衡：

1. 推动模式可能产生数据竞争，需要使用锁或原子操作来保证状态的更新是正确的。
2. 拉取模式尽管没有竞争的问题，但是可能产生额外的数据访问。

Gemini则将两种模式融合起来，根据每一轮迭代参与计算的具体情况，自适应地选择更适合的模式。

0.3 图计算应用

0.3.1 网页排序

将网页作为顶点，网页之间的超链接作为边，整个互联网可以建模成一个非常巨大的图（十万亿级边）。搜索引擎在返回结果时，除了需要考虑网页内容与关键词的相关程度，还需要考虑网页本身的质量。

PageRank是最早Google用于对网页进行排序的算法，通过将链接看成投票来指示网页的重要程度。PageRank的计算过程并不复杂：在首轮迭代开始前，所有顶点将自己的PageRank值设为1；每轮迭代中，每个顶点向所有邻居贡献自己当前PageRank值除以出边数作为投票，然后将收到的所有来自邻居的投票累加起来作为新的PageRank值；如此往复，直到所有顶点的PageRank值在相邻两轮之间的变化达到某个阈值为止。

0.3.2 社区发现

社交网络也是一种典型的图数据：顶点表示人，边表示人际关系；更广义的社交网络可以将与人有关的实体也纳入进来，例如手机、地址、公司等。社区发现是社交网络分析的一个经典应用：将图分成若干社区，每个社区内部的顶点之间具有相比社区外部更紧密的连接关系。社区发现有非常广泛的用途，在金融风控、国家安全、公共卫生等大量场景都有相关的应用。

标签传播是一种常用的社区发现算法：每个顶点的标签即为自己的社区，初始化时设置自己的顶点编号；在随后的每一轮迭代中，每个顶点将邻居中出现最频繁的标签设置为自己新的标签；当所有顶点相邻两轮之间的标签变化少于某个阈值时则停止迭代。

0.3.3最短路径

在图上发现顶点与顶点之间的最短路径是一类很常见的图计算任务，根据起始顶点与目标顶点集合的大小，又可分为单对单（一个顶点到一个顶点）、多对多（多个顶点到多个顶点）、单源（一个顶点到所有其它顶点）、多源（多个顶点到所有其它顶点）、所有点对（所有顶点到其它所有顶点）等。对于无权图，通常使用基于BFS的算法；对于有权图，比较常见的有SPFA算法、Bellman-Ford算法等。

最短路径的用途十分广泛：在知识图谱中经常需要寻找两个实体之间的最短关联路径；基于黑名单和实体之间的关联可以发现其它顶点与黑名单之间的距离；而所有点对的最短路径可以帮助衡量各个顶点在整个图的拓扑结构所处的位置（中心程度）。

节点级别任务：金融诈骗检测中，节点是用户和商家，边是用户和商家之间的交互，利用图模型预测潜在的金融诈骗分子。在目标检测案例中，将3D点云数据中点与点之间距离作为边，通过图结构可以进行3D目标检测

边级别任务：推荐系统中，通过已有的用户-商品数据建立用户图行为关系，得到节点的向量表示，进而进行推荐任务

图级别任务：气味识别，利用图神经网络识别分子结构进而识别气味

1.图与图学习

1.1 图的基本表示方法

先简单学习一下图论的基本概念，图论的经典算法，以及近些年来图学习的发展

举个例子，一个简单的图可能是这样：

节点（node）用红色标出，通过黑色的边（edge）连接。

图可用于表示:

• 社交网络
• 网页
• 生物网络
• …

我们可以在图上执行怎样的分析？

• 研究拓扑结构和连接性

• 群体检测

• 识别中心节点

• 预测缺失的节点

• 预测缺失的边

• …

• 图 G=(V, E) 由下列要素构成：

• 一组节点（也称为 verticle）V=1,…,n

• 一组边 E⊆V×V

• 边 (i,j) ∈ E 连接了节点 i 和 j

• i 和 j 被称为相邻节点（neighbor）

• 节点的度（degree）是指相邻节点的数量

节点、边和度的示意图

• 如果一个图的所有节点都有 n-1 个相邻节点，则该图是完备的（complete）。也就是说所有节点都具备所有可能的连接方式。
• 从 i 到 j 的路径（path）是指从 i 到达 j 的边的序列。该路径的长度（length）等于所经过的边的数量。
• 图的直径（diameter）是指连接任意两个节点的所有最短路径中最长路径的长度。

举个例子，在这个案例中，我们可以计算出一些连接任意两个节点的最短路径。该图的直径为 3，因为没有任意两个节点之间的最短路径的长度超过 3。

一个直径为 3 的图

• 测地路径（geodesic path）是指两个节点之间的最短路径。
• 如果所有节点都可通过某个路径连接到彼此，则它们构成一个连通分支（connected component）。如果一个图仅有一个连通分支，则该图是连通的（connected）

举个例子，下面是一个有两个不同连通分支的图：

一个有两个连通分支的图

• 如果一个图的边是有顺序的配对，则该图是有向的（directed）。i 的入度（in-degree）是指向 i 的边的数量，出度（out-degree）是远离 i 的边的数量

有向图

• 如果可以回到一个给定节点，则该图是有环的（cyclic）。相对地，如果至少有一个节点无法回到，则该图就是无环的（acyclic）。
• 图可以被加权（weighted），即在节点或关系上施加权重。
• 如果一个图的边数量相比于节点数量较小，则该图是稀疏的（sparse）。相对地，如果节点之间的边非常多，则该图是密集的（dense）

Neo4J 的关于图算法的书给出了清晰明了的总结：

总结（来自 Neo4J Graph Book & 自尊心3大佬的贡献）

1.2 图的存储

存储图的方式有三种：相邻矩阵，邻接表，十字链表

1.2.1 相邻矩阵

有向图的相邻矩阵

无向图的相邻矩阵

• 使用邻接矩阵，这通常是在内存中加载的方式：

对于图中的每一个可能的配对，如果两个节点有边相连，则设为 1。如果该图是无向图，则 A 是对称的。

1.2.2 邻接表

对于稀疏图，可以采用邻接表存储法：

边较少，相邻矩阵就会出现大量的零元素
相邻矩阵的零元素将耗费大量的存储空间和时间

无向图的邻接表表示

无向图同一条边在邻接表中出现两次

上面的图用邻接表可表示为：

带权图的邻接表表示

有向图的邻接表（出边表）

有向图的逆邻接表（入边表）

1.2.3 十字链表 (Orthogonal List)

可以看成是邻接表和逆邻接表的结合

对应于有向图的每一条弧有一个表目，共有5个域：

• 头 headvex
• 尾 tailvex
• 下一条共尾弧 tailnextarc
• 下一条共头弧 headnextarc
• 弧权值等 info 域

顶点表目由3个域组成：

• data 域
• firstinarc 第一条以该顶点为终点的弧
• firstoutarc 第一条以该顶点为始点的弧

十字链表有两组链表组成：

• 行和列的指针序列
  每个结点都包含两个指针：

• 同一行的后继

• 同一列的后继

这三种表示方式都是等价的，我们可以根据使用场景来选择图的存储方式。

1.3 图的类型和性质简单说明

图可以根据不同标准进行分类，我们在这里主要讲一种分类方法，同构图与异构图。

同构图与异构图

1. 同构图：节点类型和边的类型只有一种的图。

2. 异构图：节点类型+边类型＞2 的图。

两个图G和H是同构图（isomorphic graphs），能够通过重新标记图G的顶点而产生图H。

如果G和H同构，那么它们的阶是相同的，它们大小是相同的，它们个顶点的度数也对应相同。

异构图是一个与同构图相对应的新概念。

传统同构图（Homogeneous Graph）数据中只存在一种节点和边，因此在构建图神经网络时所有节点共享同样的模型参数并且拥有同样维度的特征空间。

而异构图（Heterogeneous Graph）中可以存在不只一种节点和边，因此允许不同类型的节点拥有不同维度的特征或属性。

2.图算法与图分析

图分析使用基于图的方法来分析连接的数据。我们可以：查询图数据，使用基本统计信息，可视化地探索图、展示图，或者将图信息预处理后合并到机器学习任务中。图的查询通常用于局部数据分析，而图计算通常涉及整张图和迭代分析。

图算法是图分析的工具之一。图算法提供了一种最有效的分析连接数据的方法，它们描述了如何处理图以发现一些定性或者定量的结论。图算法基于图论，利用节点之间的关系来推断复杂系统的结构和变化。我们可以使用这些算法来发现隐藏的信息，验证业务假设，并对行为进行预测

2.1 路径搜索算法（Pathfinding and Search）

图搜索算法（Pathfinding and Search Algorithms）探索一个图，用于一般发现或显式搜索。这些算法通过从图中找到很多路径，但并不期望这些路径是计算最优的（例如最短的，或者拥有最小的权重和）。图搜索算法包括广度优先搜索和深度优先搜索，它们是遍历图的基础，并且通常是许多其他类型分析的第一步。

路径搜索（Pathfinding）算法建立在图搜索算法的基础上，并探索节点之间的路径。这些路径从一个节点开始，遍历关系，直到到达目的地。路径搜索算法识别最优路径，用于物流规划，最低成本呼叫或者叫IP路由问题，以及游戏模拟等。

图的遍历 (graph traversal)即给出一个图G和其中任意一个顶点V0，从V0出发系统地访问G中所有的顶点，每个顶点访问而且只访问一次

从一个顶点出发，试探性访问其余顶点，同时必须考虑到下列情况

• 从一顶点出发，可能不能到达所有其它的顶点，如：非连通图；
• 也有可能会陷入死循环，如：存在回路的图

一般情况下，可以为每个顶点保留一个 标志位 (mark bit)：

• 算法开始时，所有顶点的标志位置零

• 在遍历的过程中，当某个顶点被访问时，其标志位就被标记为已访问

2.1.1深度优先遍历&广度优先遍历|DFS & BFS

图算法中最基础的两个遍历算法：广度优先搜索（Breadth First Search，简称 BFS）和深度优先搜索（Depth First Search，简称 DFS）。BFS 从选定的节点出发，优先访问所有一度关系的节点之后再继续访问二度关系节点，以此类推。DFS 从选定的节点出发，选择任一邻居之后，尽可能的沿着边遍历下去，知道不能前进之后再回溯。

深度优先搜索（简称DFS) 类似于树的先根次序遍历，尽可能先对纵深方向进行搜索：

1. 选取一个未访问的点 v0 作为源点
2. 访问顶点 v0
3. 递归地深搜遍历 v0 邻接到的其他顶点
4. 重复上述过程直至从 v0 有路径可达的顶点都已被访问过
5. 再选取其他未访问顶点作为源点做深搜，直到图的所有顶点都被访问过

深度优先搜索的顺序是：
a->b->c->f->d->e->g

广度优先遍历（breadth-first search）

广度优先搜索 (breadth-first search，简称 BFS)。其遍历的过程是：

1. 从图中的某个顶点 v0 出发
2. 访问并标记了顶点 v0 之后
3. 一层层横向搜索 v0 的所有邻接点
4. 对这些邻接点一层层横向搜索，直至所有由 v0 有路径可达的顶点都已被访问过
5. 再选取其他未访问顶点作为源点做广搜，直到所有点都被访问过

广度优先搜索的顺序是：
a->b->d->e->f->c->g

2.1.2 最短路径

最短路径（Shortest Paths）算法计算给定的两个节点之间最短（最小权重和）的路径。算法能够实时地交互和给出结果，可以给出关系传播的度数（degree），可以快速给出两点之间的最短距离，可以计算两点之间成本最低的路线等等。例如：

• 导航：谷歌、百度、高德地图均提供了导航功能，它们就使用了最短路径算法（或者非常接近的变种）；

• 社交网络关系：当我们在 LinkedIn、人人（暴露年龄了）等社交平台上查看某人的简介时，平台会展示你们之间有多少共同好友，并列出你们之间的关系。

2.1.2.1 单源最短路径(single-source shortest paths)-------迪杰斯特拉(Dijkstra)算法

单源最短路径是给定带权图 G = <V，E>，其中每条边 (vi，vj) 上的权W[vi，vj] 是一个 非负实数 。计算从任给的一个源点 s 到所有其他各结点的最短路径

迪杰斯特拉(Dijkstra)算法

最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点，也就是 “最临近的” 节点，然后比较 起点到第二临近的节点的权重 与 最临近节点的下一个最临近节点的累计权重和 从而决定下一步该如何行走。可以想象，算法记录的累计权重和 如同地理的 “等高线” 一样，在图上以 “波” 的形式传播，直到到达目的地节点。

基本思想

把所有结点分成两组:

• 第一组 U 包括已确定最短路径的结点
• 第二组 V–U 包括尚未确定最短路径的结点

按最短路径长度递增的顺序逐个把第二组的结点加到第一组中:

• 直至从 s 出发可达结点都包括进第一组中

看懂上面的再看一下这个判断自己有没有彻底理解：

Dijkstra 算法是贪心法，不适用于负权值的情况。因为权值当作最小取进来后，不会返回去重新计算，即使不存在负的回路，也可能有在后面出现的负权值，从而导致整体计算错误

2.1.2.2 每对结点间的最短路径

Floyd算法求每对结点之间的最短路径

用相邻矩阵 adj 来表示带权有向图

基本思想

• 初始化 adj(0) 为相邻矩阵 adj
• 在矩阵 adj(0)上做 n 次迭代，递归地产生一个矩阵序列adj(1)，…，adj(k)，…，adj(n)
• 其中经过第k次迭代，adj(k)[i，j] 的值等于从结点vi 到结点 vj 路径上所经过的结点序号不大于 k 的最短路径长度

其根本思想是动态规划法

最短路径算法有两个常用的变种：A （可以念作 A Star）algorithm和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息，优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果，同时给出了最好的 K 条路径。

所有节点对最短路径（All Pairs Shortest Path）也是一个常用的最短路径算法，计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法，All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息，并且这些信息在计算中可以被重用。

2.1.3 最小生成树

最小生成树（Minimum Spanning Tree）算法从一个给定的节点开始，查找其所有可到达的节点，以及将节点与最小可能权重连接在一起，行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点，避免了循环。

最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似，所不同的是， Prim 算法每次寻找最小权重访问到下一个节点，而不是累计权重和。并且，Prim 算法允许边的权重为负。

上图是最小生成树算法的步骤分解，算法最终用最小的权重将图进行了遍历，并且在遍历的过程中，不产生环。

算法可以用于优化连接系统（如水管和电路设计）的路径。它还用于近似一些计算时间未知的问题，如旅行商问题。虽然该算法不一定总能找到绝对最优解，但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如：

• 旅行计划：尽可能降低探索一个国家的旅行成本；

• 追踪流感传播的历史：有人使用最小生成树模型对丙型肝炎病毒感染的医院暴发进行分子流行病学调查

2.1.4 随机游走

随机游走（Random Walk）算法从图上获得一条随机的路径。随机游走算法从一个节点开始，随机沿着一条边正向或者反向寻找到它的邻居，以此类推，直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛，他可能知道自己大致要去哪儿，但是路径可能极其“迂回”，毕竟，他也无法控制自己~

随机游走算法一般用于随机生成一组相关的节点数据，作为后续数据处理或者其他算法使用。例如：

• 作为 node2vec 和 graph2vec 算法的一部分，这些算法可以用于节点向量的生成，从而作为后续深度学习模型的输入；这一点对于了解 NLP （自然语言处理）的朋友来说并不难理解，词是句子的一部分，我们可以通过词的组合（语料）来训练词向量。那么，我们同样可以通过节点的组合（Random Walk）来训练节点向量。这些向量可以表征词或者节点的含义，并且能够做数值计算。这一块的应用很有意思，我们会找机会来详细介绍；

• 作为 Walktrap 和 Infomap 算法的一部分，用于社群发现。如果随机游走总是返回同一组节点，表明这些节点可能在同一个社群；

• 其他机器学习模型的一部分，用于随机产生相关联的节点数据。

2.2 中心性算法（Centrality Computation）

中心性算法（Centrality Algorithms）用于识别图中特定节点的角色及其对网络的影响。中心性算法能够帮助我们识别最重要的节点，帮助我们了解组动态，例如可信度、可访问性、事物传播的速度以及组与组之间的连接。尽管这些算法中有许多是为社会网络分析而发明的，但它们已经在许多行业和领域中得到了应用。

2.2.1 DegreeCentrality

Degree Centrality （度中心性，以度作为标准的中心性指标）可能是整篇博文最简单的 “算法” 了。Degree 统计了一个节点直接相连的边的数量，包括出度和入度。Degree 可以简单理解为一个节点的访问机会的大小。例如，在一个社交网络中，一个拥有更多 degree 的人（节点）更容易与人发生直接接触，也更容易获得流感。

一个网络的平均度（average degree），是边的数量除以节点的数量。当然，平均度很容易被一些具有极大度的节点 “带跑偏” （skewed）。所以，度的分布（degree distribution）可能是表征网络特征的更好指标。

如果你希望通过出度入度来评价节点的中心性，就可以使用 degree centrality。度中心性在关注直接连通时具有很好的效果。应用场景例如，区分在线拍卖的合法用户和欺诈者，欺诈者由于尝尝人为太高拍卖价格，拥有更高的加权中心性（weighted centrality）。

2.2.2 ClosenessCentrality

Closeness Centrality（紧密性中心性）是一种检测能够通过子图有效传播信息的节点的方法。紧密性中心性计量一个节点到所有其他节点的紧密性（距离的倒数），一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离最小值。

对于一个节点来说，紧密性中心性是节点到所有其他节点的最小距离和的倒数：

$C(u)=\frac{1}{\sum_{v=1}^{n-1} d(u, v)}$

其中 u 是我们要计算紧密性中心性的节点，n 是网络中总的节点数，d(u,v) 代表节点 u 与节点 v 的最短路径距离。更常用的公式是归一化之后的中心性，即计算节点到其他节点的平均距离的倒数，你知道如何修改上面的公式吗？对了，将分子的 1 变成 n-1 即可。

理解公式我们就会发现，如果图是一个非连通图，那么我们将无法计算紧密性中心性。那么针对非连通图，调和中心性（Harmonic Centrality）被提了出来（当然它也有归一化的版本，你猜这次n-1应该加在哪里？）：

$H(u)=\frac{1}{\sum_{v=1}^{n-1} d(u, v)}$

Wasserman and Faust 提出过另一种计算紧密性中心性的公式，专门用于包含多个子图并且子图间不相连接的非连通图：

$C_{W F}(u)=\frac{n-1}{N-1}\left(\frac{n-1}{\sum_{v=1}^{n-1} d(u, v)}\right)$

其中，N 是图中总的节点数量，n 是一个部件（component）中的节点数量。

当我们希望关注网络中传播信息最快的节点，我们就可以使用紧密性中心性。

2.2.3 BetweennessCentrality

中介中心性（Betweenness Centrality）是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于寻找连接图的两个部分的桥梁节点。因为很多时候，一个系统最重要的 “齿轮” 不是那些状态最好的，而是一些看似不起眼的 “媒介”，它们掌握着资源或者信息的流动性。

中间中心性算法首先计算连接图中每对节点之间的最短（最小权重和）路径。每个节点都会根据这些通过节点的最短路径的数量得到一个分数。节点所在的路径越短，其得分越高。计算公式：

$B(u)=\sum_{s \neq u \neq t} \frac{p(u)}{p}$

其中，p 是节点 s 与 t 之间最短路径的数量，p(u) 是其中经过节点 u 的数量。下图给出了对于节点 D 的计算过程：

当然，在一张大图上计算中介中心性是十分昂贵的。所以我们需要更快的，成本更小的，并且精度大致相同的算法来计算，例如 Randomized-Approximate Brandes。我们不会对这个算法继续深入，感兴趣的话，可以去了解一下，算法如何通过随机（Random）和度的筛选（Degree）达到近似的效果。

中介中心性在现实的网络中有广泛的应用，我们使用它来发现瓶颈、控制点和漏洞。例如，识别不同组织的影响者，他们往往是各个组织的媒介，例如寻找电网的关键点，提高整体鲁棒性。

2.2.4 PageRank

在所有的中心性算法中，PageRank 是最著名的一个。它测量节点传递影响的能力。PageRank 不但节点的直接影响，也考虑 “邻居” 的影响力。例如，一个节点拥有一个有影响力的 “邻居”，可能比拥有很多不太有影响力的 “邻居” 更有影响力。PageRank 统计到节点的传入关系的数量和质量，从而决定该节点的重要性。

PageRank 算法以谷歌联合创始人拉里·佩奇的名字命名，他创建了这个算法来对谷歌搜索结果中的网站进行排名。不同的网页之间相互引用，网页作为节点，引用关系作为边，就可以组成一个网络。被更多网页引用的网页，应该拥有更高的权重；被更高权重引用的网页，也应该拥有更高权重。原始公式：

$P R(u)=(1-d)+d\left(\frac{P R(T 1)}{C(T 1)}+\ldots+\frac{P R(T n)}{C(T n)}\right)$

其中，u 是我们想要计算 PageRank 的网页，T1 到 Tn 是引用的网页。d 被称为阻尼系数（damping factor），代表一个用户继续点击网页的概率，一般被设置为 0.85，范围 0~1。C(T) 是节点 T 的出度。

从理解上来说，PageRank 算法假设一个用户在访问网页时，用户可能随机输入一个网址，也可能通过一些网页的链接访问到别的网页。那么阻尼系数代表用户对当前网页感到无聊，随机选择一个链接访问到新的网页的概率。那么 PageRank 的数值代表这个网页通过其他网页链接过来（入度，in-degree）的可能性。那你能如何解释 PageRank 方程中的 1-d 呢？实际，1-d 代表不通过链接访问，而是随机输入网址访问到网页的概率。

PageRank 算法采用迭代方式计算，直到结果收敛或者达到迭代上限。每次迭代都会分两步更新节点权重和边的权重，详细如下图：

当然，上图的计算并没有考虑阻尼系数，那为什么一定要阻尼系数呢？除了我们定义的链接访问概率，有没有别的意义呢？从上图的过程中，我们可能会发现一个问题，如果一个节点（或者一组节点），只有边进入，却没有边出去，会怎么样呢？按照上图的迭代，节点会不断抢占 PageRank 分数。这个现象被称为 Rank Sink，如下图：

解决 Rank Sink 的方法有两个。第一个，假设这些节点有隐形的边连向了所有的节点，遍历这些隐形的边的过程称为 teleportation。第二个，使用阻尼系数，如果我们设置 d 等于 0.85，我们仍然有 0.15 的概率从这些节点再跳跃出去。

尽管阻尼系数的建议值为 0.85，我们仍然可以根据实际需要进行修改。调低阻尼系数，意味着访问网页时，更不可能不断点击链接访问下去，而是更多地随机访问别的网页。那么一个网页的 PageRank 分数会更多地分给他的直接下游网页，而不是下游的下游网页。

PageRank 算法已经不仅限于网页排名。例如：

• 寻找最重要的基因：我们要寻找的基因可能不是与生物功能联系最多的基因，而是与最重要功能有紧密联系的基因；

• who to follow service at twitter：Twitter使用个性化的 PageRank 算法（Personalized PageRank，简称 PPR）向用户推荐他们可能希望关注的其他帐户。该算法通过兴趣和其他的关系连接，为用户展示感兴趣的其他用户；

• 交通流量预测：使用 PageRank 算法计算人们在每条街道上停车或结束行程的可能性；

• 反欺诈：医疗或者保险行业存在异常或者欺诈行为，PageRank 可以作为后续机器学习算法的输入。

2.3 社群发现算法（Community Detection）

社群的形成在各种类型的网络中都很常见。识别社群对于评估群体行为或突发事件至关重要。对于一个社群来说，内部节点与内部节点的关系（边）比社群外部节点的关系更多。识别这些社群可以揭示节点的分群，找到孤立的社群，发现整体网络结构关系。社群发现算法（Community Detection Algorithms）有助于发现社群中群体行为或者偏好，寻找嵌套关系，或者成为其他分析的前序步骤。社群发现算法也常用于网络可视化。

2.3.1 MeasuringAlgorithm

三角计数（Triangle Count）和聚类系数（Clustering Coefficient）经常被一起使用。三角计数计算图中由节点组成的三角形的数量，要求任意两个节点间有边（关系）连接。聚类系数算法的目标是测量一个组的聚类紧密程度。该算法计算网络中三角形的数量，与可能的关系的比率。聚类系数为 1 表示这个组内任意两个节点之间有边相连。

有两种聚类系数：局部聚类系数（Local Clustering Coefficient）和全局聚类系数（Global Clustering Coefficient）。

局部聚类系数计算一个节点的邻居之间的紧密程度，计算时需要三角计数。计算公式：

$C C(u)=\frac{2 R_u}{k_u\left(k_u-1\right)}$

其中，u 代表我们需要计算聚类系数的节点，R(u) 代表经过节点 u 和它的邻居的三角形个数，k(u) 代表节点 u的度。下图是三三角计数聚类系数计算示意图：

全局聚类系数是局部聚类系数的归一化求和。

当需要计算一个组的稳定性或者聚类系数时，我们可以使用三角计数。三角计数在社交网络分析中有广泛的应用，通航被用来检测社区。聚类系数可以快速评估特定组或整个网络的内聚性。这些算法可以共同用于特定网络结构的寻找。例如，探索网页的主题结构，基于网页之间的相互联系，检测拥有共同主题的 “网页社群”。

2.3.2 ComponentsAlgorithm

强关联部件（Strongly Connected Components，简称 SCC）算法寻找有向图内的一组一组节点，每组节点可以通过关系 互相 访问。在 “Community Detection Algorithms” 的图中，我们可以发现，每组节点内部不需要直接相连，只要通过路径访问即可。

关联部件（Connected Components）算法，不同于 SCC，组内的节点对只需通过一个方向访问即可。

关联类算法作为图分析的早期算法，用以了解图的结构，或确定可能需要独立调查的紧密集群十分有效。对于推荐引擎等应用程序，也可以用来描述组中的类似行为等等。许多时候，算法被用于查找集群并将其折叠成单个节点，以便进一步进行集群间分析。对于我们来说，先运行以下关联类算法查看图是否连通，是一个很好的习惯。

2.3.3 LabelPropagation Algorithm

标签传播算法（Label Propagation Algorithm，简称 LPA）是一个在图中快速发现社群的算法。在 LPA 算法中，节点的标签完全由它的直接邻居决定。算法非常适合于半监督学习，你可以使用已有标签的节点来种子化传播进程。

LPA 是一个较新的算法，由 Raghavan 等人于 2007 年提出。我们可以很形象地理解算法的传播过程，当标签在紧密联系的区域，传播非常快，但到了稀疏连接的区域，传播速度就会下降。当出现一个节点属于多个社群时，算法会使用该节点邻居的标签与权重，决定最终的标签。传播结束后，拥有同样标签的节点被视为在同一群组中。

下图展示了算法的两个变种：Push 和 Pull。其中 Pull 算法更为典型，并且可以很好地并行计算：

看完上图，你应该已经理解了算法的大概过程。其实，做过图像处理的人很容易明白，所谓的标签传播算法，不过是图像分割算法的变种，Push 算法是区域生长法（Region Growing）的简化版，而 Pull 更像是分割和合并（divide-and-merge，也有人称 split-merge）算法。确实，图像（image）的像素和图（graph）的节点是十分类似的。

2.3.4 LouvainModularity Algorithm

Louvain Modularity 算法在给节点分配社群是，会比较社群的密度，而不仅仅是比较节点与社群的紧密程度。算法通过查看节点与社群内关系的密度与平均关系密度的比较，来量化地决定一个节点是否属于社群。算法不但可以发现社群，更可以给出不同尺度不同规模的社群层次，对于理解不同粒度界别的网络结构有极大的帮助。

算法在 2008 年被提出以后，迅速成为了最快的模块化算法之一。算法的细节很多，我们无法一一覆盖，下图给出了一个粗略的步骤，帮助我们理解算法如何能够多尺度地构建社群：

Louvain Modularity 算法非常适合庞大网络的社群发现，算法采用启发式方式从而能够克服传统 Modularity 类算法的局限。算法应用：

• 检测网络攻击:该算可以应用于大规模网络安全领域中的快速社群发现。一旦这些社群被发现，就可以用来预防网络攻击；

• 主题建模：从 Twitter 和 YouTube 等在线社交平台中提取主题，基于文档中共同出现的术语，作为主题建模过程的一部分。

3.算法实践（图分析、图计算）

有了前面的前置知识，来一起程序操作一下了

3.1创建一个图进行简单分析

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt

# Load the graph
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# Plot the graph
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

空手道俱乐部图

这个「空手道」图表示什么？Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员，成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间，管理员 JohnA 与教练 Mr.Hi（化名）之间出现了冲突，导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部，另一半则找了一个新教练或放弃了空手道。基于收集到的数据，除了其中一个成员，Zachary 正确分配了所有成员在分裂之后所进入的分组。

# .degree() 属性会返回该图的每个节点的度（相邻节点的数量）的列表：
n=34
print(G_karate.degree())
degree_sequence = list(G_karate.degree())

# 计算边的数量，但也计算度序列的度量：
nb_nodes = n
nb_arr = len(G_karate.edges())
avg_degree = np.mean(np.array(degree_sequence)[:,1])
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])
# 最后，打印所有信息：
print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))

# 平均而言，该图中的每个人都连接了 4.6 个人。
# 我们可以绘出这些度的直方图：
degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degree")
plt.show()

3.2图类型

3.2.1 Erdos-Rényi 模型

在 Erdos-Rényi 模型中，我们构建一个带有 n 个节点的随机图模型。这个图是通过以概率 p 独立地在节点 (i,j) 对之间画边来生成的。因此，我们有两个参数：节点数量 n 和概率 p。

Erdos-Rényi 图

在 Python 中，networkx 软件包有用于生成 Erdos-Rényi 图的内置函数。