第2章 社交网络分析理论基础

2.1 图论

图研究的是数据元素之间的多对多关系。在图中，任意两个元素之间可能存在关系，即节点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入社交网络、生物网络等。

2.1.1 哥尼斯堡七桥问题

18 世纪的哥尼斯堡（Konigsberg）是一座美丽的城市，布勒格尔河从这里流过，并且横贯城区。这条河有两条支流在城中交汇，汇合处有两座小岛，人们在这里建了一座公园，公园中的七座桥把河两岸和小岛连接起来。当时，那里的居民热衷于一个有趣的数学游戏：游人怎样才能一次走完七座桥，每座桥只经过一次，最后又回到出发点呢？哥尼斯堡七桥分布情况如图2.1所示。

有趣的七桥和迷人的景色吸引了众多的游客，有人在游览时提出这样的问题：能否从某个地方出发，穿过所有桥各一次后再回到出发点？这个问题在街头流传着，但没有人能回答它，这就是著名的哥尼斯堡七桥问题。这个问题看起来似乎不难，但人们始终没有找到答案，最后问题到了当时世界上最有名的大数学家欧拉那里。

瑞士数学家欧拉思考和解决这个问题的方法如下：既然问题是要找一条不重复地经过7座桥的路线，而4块陆地都是桥梁的连接点，那么不妨把图中的4块陆地（岸和岛）抽象为4个点（见图2.2），把7座桥抽象为7条线段。这样，就把七桥问题简化为能否一笔画出这7条线段和4个交点组成的几何图形的问题，也就是一笔画问题，即图论。

欧拉的这一考虑非常重要、非常巧妙，体现了数学家处理实际问题的独特之处——首先把一个实际问题抽象成为适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点却是解决难题的关键。

欧拉在研究一笔画问题的基础上，得出了如下重要结论。

（1）凡是由偶点组成的连通图，一定可以一笔画成。画时可将任意一个偶点作为起点，最后一定能以这个点为终点画完此图。

（2）凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须将一个奇点作为起点，将另一个奇点作为终点。

（3）其他情况的图都不能一笔画出。

2.1.2 图的基本概念

图是一个用线或边连接在一起的顶点或节点的集合。严格地说，图是有限顶点集V 和边集E的有序对，用G=（V， E）表示，其中V 是顶点（Vertex）的非空有限集合，记为V （G）；E是无序集＜v， w＞的一个子集，记为E（G）；元素是图的弧（Arc）。将顶点集合为空的图称为空图。图G的形式定义为

式中， p（v， w）表示从顶点v到顶点w有一条直接通路；弧表示两个顶点v和w之间存在一个关系，用顶点偶对＜v， w＞表示。通常根据图的顶点偶对将图分为有向图和无向图。

1.有向图

若在图G的关系集合E（G）中，顶点偶对＜v， w＞的v和w之间是有序的，则称图 G 是有向图（Digraph）。在有向图中，若＜v， w＞∈E（G），则表示从顶点v到顶点w有一条弧，其中v称为弧尾或始点， w称为弧头或终点，如图 2.3（a）所示。

2.无向图

若在图G的关系集合E（G）中，顶点偶对＜v， w＞的v和w之间是无序的，则称图 G 是无向图（Un-Digraph）。在无向图中，若＜v， w＞∈E（G），则有＜w，v＞∈E（G），即E（G）是对称的，此时用无序对（v，w）表示v和w之间的一条边，因此（v， w）和（w， v）代表的是同一条边，如图2.3（b）所示。

2.1.3 图的存储结构

图的存储结构比较复杂，其复杂性主要表现如下。

（1）任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。

（2）图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元；反之，按每个顶点自己的度设计不同的结构又会影响操作。

图的常用存储结构有邻接矩阵、邻接链表、十字链表、邻接多重表和边表，其中邻接矩阵定义为

2.1.4 图的连通性

连通图是任意两个顶点都有路相连的图，其连通程度有高有低。例如，图 2.4中所示的图都是连通图。对于图 G₁，删除一条边或一个顶点可使其变得不连通；对于图 G₂，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G₃，要破坏其连通性，至少需要删除三条边或三个顶点。

1.割点与割边

定义2.1 设v∈V （G），若w（G-v）＞w（G），则称v为图G的一个割点。

例如，图2.5中的u， v两点是其割点。

定义2.2 设e∈E（G），若w（G-e）＞w（G），则称e为G的一条割边。

例如，图2.6中的边uv和wu都是其割边。

2.连通度和边连通度

定义 2.3 对图 G，若 V（G）的子集V′使得w（G-V′）＞w（G），则称V′为图 G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。

注：（1）割点是1-顶点割集。

（2）完全图没有顶点割集。

定义 2.4 图G的连通度定义为κ（G）=min{V′是连通图 G 的顶点割集}。特别地，完全图的连通度定义为κ（K_v）=v-1，空图的连通度定义为 0，不连通图的连通度定义为0。

注：（1）若图G是平凡图，则κ（G）=0。

（2）使得V′=κ（G）的顶点割集V′称为G的最小割集。

（3）若κ（G）≥k，则称图G为k连通的。

定义2.5 对图G，若E（G）的子集E′使得w（G-E′）＞w（G），则称E′为图G的一个边割集。含有k条边的边割集称为k-边割集。

注：（1）对非平凡图G，若E′是一个边割集，则G\E′不连通。

（2）一条割边构成一个1-边割集。

（3）设S⊂V（G）， S′⊂V（G）， S，S′≠∅，记号[S，S′]表示一端在S中而另一端在S′中的所有边的集合。对图G的每个边割集E′，必定存在非空的S⊂V （G），使得[S， S]是 G 的一个边割集，其中S=V\S。

定义 2.6 图 G 的边连通度定义为κ′（G）=min{|E′| E′是连通图 G 的边割集}。完全图的边度定义为κ′（K_v）=v-1，空图的边连通度定义为0，不连通图的边连通度定义为0。

3.2连通图的性质

无割点的连通图称为一个块（Block）。设 G 是一个图，H 是 G 的一个子图，若H本身是一个块并且它是G中具有此性质的极大子图，则称H是图G的一个块。图2.7中显示了块和图中的块。

v≥3的图 G 是 2-连通图（块）当且仅当 G 中的任意两个顶点共圈。对∀w∈V （G），任取u， v∈V （G-w）。由条件， u， v在 G 中共圈 C。当d （u， v）=k时，设P₀=u... wv是长为k的一条（u， v）路，则d （u， w）=k-1。由归纳法假设， u， w在同一圈上，故在u， w间有两条无公共内部顶点的路P和Q。

2.1.5 图的匹配理论

设M是图G=（V， E）的一个匹配， v_i∈V。若v_i与M中的边相关联，则称v_i是M饱和点，否则称v_i为M非饱和点。若G中的每个顶点都是M饱和点，则称M为G的完美匹配。设M是G的一个匹配，P是G的一条链。若P的边交替地一条是 M 中的边、一条不是 M 中的边，则称 P 为 M 交错链。类似地，可以定义 G 的交错圈。易知，G 的交错圈一定是偶圈。一条连接两个不同的 M 非饱和点的 M 交错链称为 M 增广链。两个集合 S₁与 S₂的“异或”操作S₁⊕S₂是集合S₁⊕S₂=（S₁∩S₂ ）-（S₁∪S₂ ）。容易看出，若设M是G的匹配，P是G中的M增广链，则M⊕P也是G的匹配，而且G中的匹配M是最大匹配当且仅当G中没有M增广链。

1.匹配与最大匹配

设G是一个图， M ⊆E（G），对∀e_i，e_j∈M，e_i与e_j在G中不相邻，则称M是 G 的一个匹配。对匹配 M 中的每条边e=uv，两端点u和v称为被匹配 M 所匹配， u和v都称为M饱和的。若G中无匹配M′使得，则称M是G的一个最大匹配；若 G 中的每个点都是 M 饱和的，则称 M 是 G 的完美匹配。显然，完美匹配必然是最大匹配。在图 2.8（a）中，边集{e₁}、{e₁ ， e₂}、{e₁ ， e₂ ， e₃}都构成匹配，{e₁ ， e₂ ， e₃}是图 2.8（a）的一个最大匹配。在图 2.8（b）中，边集{e₁，e₂，e₃，e₄}是一个完美匹配，也是一个最大匹配。

2.完美匹配

若在一个图的某个匹配中，所有顶点都是匹配点，则它是一个完美匹配。图G 的奇分支是 G 中含有奇数个顶点的连通分支，用O（G）表示 G 的奇分支的个数。图G有完美匹配的充要条件是对∀S⊂V （G）， O（G\S）≤。

图 G 有完美匹配M，对∀S⊂V （G），若G\S无奇点，则O（G\S）=0，否则G₁，G₂，...，G_k是G\S的所有奇分点，每个G_i中至少有一个顶点u_i在M下与S中的某个顶点v_i配对（i=1，2，...，k），所以O（G\S）=k=。图的完美匹配如图2.9所示。

2.1.6 支配集、点独立集、点覆盖集

1.支配集

支配集的定义如下：假设D⊆V （G），若对∀u∈V （G），要么u∈D，要么u与D中的某些顶点相邻，则称 D 为图 G 的一个支配集；若一个支配集的任何真子集都不是支配集，则称它为极小支配集。图 G 的含顶点最少的支配集称为最小支配集，最小支配集的顶点个数称为G的支配数，记为γ（G）。

在图 2.10 中， D₀={v₀}， D₁={v₁ ， v₄ ， v₇}， D₂={v₁ ， v₃ ， v₅ ， v₆}都是 G 的支配集，前两个是极小支配集， D₀是最小支配集，γ（G）=1。

图的支配集是内容非常丰富的一个研究专题，在许多科学领域有着重要的应用，是目前研究的一个热点方向。

2.点独立集

点独立集的定义如下：假设I⊆V （G），若I中任意两个顶点均不相邻，则称I为图G的一个独立点集；若对∀u∈V （G）\I， I∪{u}不再是G的独立集，则称独立集I为图G的一个极大点独立集。G的所含点数最多的点独立集称为最大点独立集，它所含的点数称为G的独立数，记为α（G）。

在图 2.10 中， I₀={v₀}， I₁={v₁，v₄，v₇}， I₂={v₁，v₃，v₅，v₆}都是 G 的独立集，且都是极大独立集，其中I₂是最大独立集，α（G）=4。独立集和支配集的关系是，图G的极大独立集必定是图G的极小支配集，反之不成立。

3.点覆盖集

点覆盖集的定义如下：假设F⊂V （G），若G的每条边至少有一个端点属于F，则称 F 是 G 的一个点覆盖；若对任给的v∈F，F-{v}不再是 G 点覆盖集，则称点覆盖集 F 是一个极小点覆盖。图 G 的含点数最少的点覆盖称为最小点覆盖，其点数称为G的点覆盖数，记为β（G）。

在图 2.10 中，{v₀，v₁，v₃，v₅，v₇}和{v₁，v₂，v₃，v₄，v₅，v₆，v₇，v₈}都是图 G 的点覆盖，且都是极小点覆盖，前一个点覆盖是最小点覆盖，β（G）=4。点覆盖集和支配集是容易混淆的两个概念，它们的本质区别是，点覆盖集用点覆盖边，而支配集用点支配点。在连通图中，点覆盖集必定是支配集，但支配集未必是覆盖集。例如，图2.10中的{v₀}及{v₁ ， v₄ ， v₇}都是G的支配集，但不是覆盖集。