2.2 网络的基本特征

2.2.1 节点

所有的图都由一些基本的模块组成，其中一个主要的组成部分是节点集。在一个表示朋友关系的图中，节点表示人，任何两个相互连接的人表示他们之间为朋友关系。根据应用场景，这些节点可以成为顶点或角色。例如。在一个网络图中，节点表示网站，节点之间的边表示网站之间的网络链接。在社交场合，这些节点被称为角色。节点集的数学表示是

式中， V是节点集， v_i（1≤i≤n）是一个节点，=n表示节点集的大小。

2.2.2 边

图的另一个重要元素是边集。边连接节点。在社交场合，节点表示如人这样的社会实体，边表示节点之间的关系，因此边被认为是关系或（社会）联系。边集通常用E表示：

式中， e_i（1≤i≤m）表示一条边，边集的大小通常用=m表示。

边也可以用其两个端点（节点）表示，此时e（v₁ ， v₂ ）或（v₁ ， v₂ ）定义了节点v₁和v₂之间的边e。边可以有方向，即一个节点连接到另一个节点，但并不能表示另一个节点也连接到此节点。当边无方向时，节点之间是相互连接的。在图2.11（b）中，由于节点之间的连接没有方向性，所以e（v₁ ， v₂ ）和e（v₂ ， v₁ ）是同一条边。称该图中的边为无向边，该图为无向图。相反，若边有方向性，则e（v₁ ， v₂ ）和e（v₂ ， v₁ ）不是同一条边。图 2.11（a）是一个包含有向边的有向图，有向边用箭头表示。在有向图中，边e（v_i， v _j）用从v_i到v _j的箭头表示。边可以从某一节点出发并指向该节点本身，这样的边称为环（Loop）或自连接（Self-link），用e（v_i， v_i）表示。对于无向图中的任何一个节点v_i，通过边与其相连的节点集称为节点v_i的邻居节点，用N （v_i）表示。在有向图中，节点v_i有入度邻居N_in （v_i） （连接到v_i的节点）和出度邻居N_out （v_i） （ v_i连接到的节点）。在图 2.11（a）中， N_in （v₂ ）={v₃}， N_out（v₂）={v₁，v₃}。

2.2.3 度和度的分布

与一个节点相连的边的数量称为节点的度，节点v_i的度通常用d _i表示。在有向边的情况下，节点有入度（指向该节点的边）和出度（从该节点指出的边）之分，这两个值分别用和表示。在社会媒体中，度表示一个给定用户的朋友数量。例如，在Facebook上，度表示该用户的朋友数量；在Twitter上，入度和出度分别表示粉丝数和关注数。在无向图中，所有节点的度数之和等于图中边的数量的两倍。

定理2.1 在无向图中，所有节点的度数之和等于图中边的数量的两倍：

引理2.1.1 在无向图中，度数为奇数的节点有偶数个。

引理2.1.2 在有向图中，所有节点的入度之和等于所有节点的出度之和：

在规模非常大的图中，节点度数的分布（度的分布）是一个需要考虑的重要属性。度的分布在描述网络时有重要作用。每种分布均可通过其基本组成元素来描述。就该问题来说，组成元素是图中全部节点的度。度的分布p_d表示一个随机选择的节点v的度数为d的概率。p_d是一个概率分布，满足=1。在有n个节点的图中， p_d的定义如下：

式中， n_d是度为d的节点数量。一个较为常用且重要的表示方法是绘制分布的直方图，图中x轴表示度数d， y轴表示度数为n_d的节点数量或者度数为p_d的节点的比例。

2.2.4 图的表示

前面展示了图这种直观的表示方法。这种表示方法对人来说很清晰，但是不能被计算机有效利用，也不能用数学工具来处理。因此，需要找到可以存储节点集和边集的另一种表示，使之满足：（1）不丢失信息；（2）易于被计算机使用；（3）可以方便地被数学工具使用。

1.邻接矩阵

一种简单的图表示方案是使用邻接矩阵。图2.12中显示了一个图及其对应的邻接矩阵。在邻接矩阵中，1 表示节点v_i和节点v _j之间有边相连，0 表示两个节点之间没有边相连。广义上讲，在邻接矩阵中可以用任何实数表示节点之间的关联紧密程度。邻接矩阵给出了图的更自然的数学表达。值得注意的是，在社交网络中，由于对全部节点来说，交互关系（边）的数量相对较少，所以邻接矩阵中有很多元素为 0。这样就形成了一个庞大的稀疏矩阵（在数值分析中，稀疏矩阵是指大多数元素为0的矩阵）。

在邻接矩阵中，对角线上的元素代表环或自连接。邻接矩阵通常可以表示为

2.邻接表

邻接表（Adjacency List）表示每个节点和与其相连接的节点列表。节点列表通常根据节点的编号或者其他原则排序。对于图 2.12（a）中的图，相应的邻接表如表2.1所示。

3.边列表

另一个简单且常用的存储大规模图的方法是存储图中所有的边。这种表示称为边列表（Edge List）。对于图2.12（a）中的图，有如下的边列表表示形式：

(v₁,v₂),(v₂,v₃),(v₂,v₄),(v₃,v₄),(v₄,v₅),(v₄,v₆)

在这种表示形式中，每个元素是一条边，用（v_i， v _j）表示，意指节点v_i连接到节点v_j。由于社会媒体网络的稀疏性，邻接表和边列表这两种表示形式都能有效地节省大量空间。这是因为在邻接矩阵中，很多0元素都需要被记录下来，但是在邻接表和边列表表示中都不需要存储。

2.2.5 图的类型

通常来讲，图有多种基本类型。本节中简单介绍几种基本类型。

1.零图

零图（Null Graph）是节点集为空集（没有节点）的图。显而易见，既然零图中不包含节点，那么自然也不包含边。相应地，零图可以表示为

2.空图

空图（Empty Graph）或无边图（Edgeless Graph）是边集为空集的图：

注意，其中节点集可以不为空集。零图是空图，反之不一定成立。

3.有向图、无向图、混合图

如前所述，只包含有向边的图称为有向图，只包含无向边的图称为无向图。顾名思义，混合图（Mixed Graph）包含有向边和无向边。在有向图中，节点i和节点 j之间可以有两条边（一条从节点i到节点 j，另一条从节点 j到节点i），但在无向图中节点之间只存在一条边。因此，有向图的邻接矩阵一般不是对称矩阵（节点i连接到节点 j并不等价于节点 j连接到节点i），但是无向图的邻接矩阵是对称矩阵（ A=AT）。

在社会媒体中，存在很多有向网络和无向网络。例如，Facebook 是一个无向网络，其中Jon 是Mary的朋友，于是Mary也是Jon的朋友。Twitter是一个有向网络，其中的关注关系不是双向的（一个方向称为关注者，另一个方向称为被关注者）。

4.简单图和多重图

在之前给出的图中，任何两个节点之间只能存在一条边，这样的图称为简单图（Simple Graph）。两个节点之间可以有多条边的图是多重图（Multi Graph）。在多重图的邻接矩阵中，元素可以含有比 1 大的数值，用以表明节点间有多条边。由于两个人之间经常有多重关系，所以多重图在社会媒体中较为常见。两个人之间可以是朋友，同时也可以是同事、同一个社团的成员或者其他关系。对于这样的每种关系，两个人之间可以增加一条新的边，如此就构成一个多重图。

5.带权图

带权图（Weighted Graph）是对图上的边赋予相应的权重值的图。例如，图可以表示地图，其中节点代表城市，边代表城市之间的路线，每条边上的权重代表城市之间的距离。带权图形式化地表示为G（V， E，W），其中W 代表每条边对应的权重，并且。在邻接矩阵的表示中，可用权重值代替 1/0 值。假设v_i和v _j之间有边（当且仅当W_ij≠0时），于是可将E和W 合二为一，放在一个邻接矩阵A中，从而节省存储空间。根据情况需要，权重值也可表示为w_ij或w（i， j）。

网络图是带权图的一个例子。网络图是表示互联网网站之间的链接关系的图。一般而言，网络图是有向图，节点代表网站，边被赋予的权重代表网站之间的链接数量。两个网站之间可以有多条链接指向对方，并且独立的网站中可以有环（指向自己的链接）。

带权图的一个特例是边上的权重用二值（0/1 或+/-）表示。这样的边通常称为标号边（Signed Edge），这样的带权图称为标号图（Signed Graph）。标号边可以用来表示矛盾的行为，如表示朋友和仇敌关系。两个节点之间正面（+）的边表示朋友关系，负面（-）的边表示敌对关系。当边是有向边时，一个端点是另一个端点的朋友或敌人，反之不成立；当边是无向边时，两个端点互为朋友或敌人关系。在另一种应用场景中，正面（+）的边可以表示较高的社会地位，而负面（-）的边可以表示较低的社会地位。社会地位是每个人在社会中位置的排序。例如，在校园环境中，因为校长被视为具有比学生更高的社会地位，所以校长和学生之间通过指向校长的正面（+）的边相连接。图 2.13 中显示了包含节点和节点之间标号边的标号图。

2.2.6 图的连通性

在图中，连通性（Connectivity）定义了节点之间是如何通过一系列的边相连的。在定义图的连通性之前，需要先解释一些基本概念。

（1）相邻节点（Adjacent Node）和相邻边（Adjacent Edge）。在图G（V， E）中，若节点v_i和节点v _j通过一条边连接，则称v_i和v _j是相邻节点；若两条边e₁ ， e₂具有相同的一个端点（即通过一个节点相连），则称它们为相邻边。

（2）通路（Walk）和环路（Circuit）。通路是依次遍历相邻边产生的边序列。若通路的起始节点和终止节点不是同一个节点（即v₁≠v_n+1），则称这种通路为开通路（Open Walk）；若通路的起始节点和终止节点是同一个节点（即v₁=v_n+1），则称这种通路为闭通路（Closed Walk），通路的长度是在通路中遍历的边的数量。简单通路是每条边只被遍历一次的通路，因此通路中的每条边都是不同的。一个闭合的简单通路（起始节点和终止节点相同）称为环路。

（3）路径（Path）和回路（Cycle）。若通路经过的节点与边均没有出现重复，则称之为路径。闭合的路径称为回路。路径和回路的长度用其遍历的边的数量表示。在有向图中，由于边的遍历只能沿着边的方向进行，所以称为有向路径。在图 2.14 中， v₄，v₃，v₆，v₄，v₂是一条通路， v₄，v₃是一条路径， v₄，v₃，v₆，v₄，v₂是一条简单通路，v₄，v₃，v₆，v₄既是环路又是回路。

（4）连通性。若节点v_i和节点v _j相邻或者v_i和v _j之间有路径相连，则称节点v_i与节点v _j连接。若图中的任何两个节点之间都有一条路径，则称该图是连通图。在有向图中，在不考虑沿着边的方向的情况下（即用无向边代替有向边），若任何两个节点之间都有路径，则称该有向图为弱连通图；在考虑沿着边的方向的情况下，若任何两个节点之间均存在有向路径，则称该有向图为强连通图。图2.15中给出了连通图、不连通图、强连通图和弱连通图的例子。

（5）连通分支。在无向图中，若子图中的任何两个节点之间都有一条路径，则称该子图为连通分支。在有向图中，若对连通分支内的任何两个节点v和u，既存在从v到u的有向路径，又存在从u到v的有向路径，则称该连通分支为强连通分支。若将有向边替换成无向边之后，形成了一个连通分支，则称该连通分支为弱连通分支。