1.2　图

本节将介绍图的经典算法——用于解决社交网络中的问题，以及图的结构分析方法——以供读者从结构的角度分析社交图。最后，介绍几种特殊的图，以及这些图在社交网络场景中的应用。

1.2.1　图的经典算法

1. 深度优先搜索（DFS）和广度优先搜索（BFS）算法

如果想查找社交网络中的某个参与者，则可以搜索社交图，若能够搜索到对应的顶点，那么社交网络中存在此参与者，否则，不存在此参与者。如果想知道社交网络中是否存在参与者1到达参与者2的途径，则可以在社交图中搜索参与者1对应的顶点，若从此顶点出发能够搜索到到达参与者2对应顶点的路径，则认为社交网络中存在此途径。

最常见的两种图搜索算式是深度优先搜索（Depth First Search，DFS）和广度优先搜索（Breadth First Search，BFS）。

DFS算法有“不撞南墙不回头”的特点，其在搜索过程中沿着与当前顶点关联的边向下搜索，如果当前顶点的所有邻接顶点都已经被搜索过，那么回溯到上一个被搜索的顶点。重复此操作，直至找到搜索目标。DFS算法的每一次搜索都尽可能地在回溯到上个顶点之前在每个分支上搜索得更深入，因此得名“深度优先搜索”。

BFS算法的思路则是逐个搜索与当前顶点邻接的所有顶点，直到所有邻接顶点都被查询过后，才认为当前的顶点已经被搜索完毕，再继续下个顶点的搜索。

算法1-1　BFS算法

输入：图G，起始顶点u，搜索目标顶点t

输出：BFS结果

1： // S为待搜索顶点队列，R为已搜索顶点集

2：while do

3：  取S中的第一个顶点v进行搜索，将v所有不属于的邻接顶点添加到S中；

4：  将S中的v删除，加入R中；

5：end

2. Kosaraju算法

定义9：图，如果对于任意的都存在一条路径P(u,v)，则称图G是连通的，否则，称G是非连通的。如果G中存在路径P(u,v)，则称u连通到v。

定义10：有向图，如果对于任意的都同时存在路径P(u,v)和路径P(v,u)，则称图G是强连通的。

如果社交图是连通的，那么可以理解为社交图对应的社交网络中的任何两个参与者之间都存在直接或间接认识的途径。

定义11：如果图H满足，且H中边的顶点的分配方式和G一样，那么称H是G的子图。

定义12：有向图G最大的强连通的子图被称为图G的强连通分量。

社交图的强连通分量内任意两者之间都存在相互到达的途径，因此此分量内的人群连接紧密，他们可能拥有共同的兴趣、相似的价值观和类似的成长背景等，因而可以用寻找社交图的强连通分量来发掘社交网络中连接紧密的小团体。

Kosaraju算法需要进行两次DFS，第一次得到有向图的拓扑结构，第二次得到有向图的强连通分量。

算法1-2　Kosaraju算法

输入：有向图G，记录顶点搜索顺序的数组t={}

输出：G的所有连通分量

1：对G进行DFS，在t中记录顶点的搜索顺序；

2：对G进行取反操作（顶点不变，边的方向取反）得到G′；

3：while do

4：  按照t中搜索顺序的逆序对G′进行DFS，把搜索过的顶点从G′和t中删除，直到搜索无法继续进行；// 所有被删除的顶点以及它们之间关联的边组成了G的一个连通分量

5：end

3. 入度表（Kahn）算法

通过寻找有向图的拓扑排序可以确定社交图上是否存在回路。

定义13：拓扑排序是有向无环图的顶点集V的线性序列，满足对于G的每一条有向边，在拓扑排序中，u的顺序都在v之前。

如果能找到有向图对应的拓扑排序，就表示此图中没有环；反之，如果有向图不存在拓扑排序，那么此图中就一定存在回路。通常利用入度表（Kahn）算法来寻找有向图的拓扑排序。

算法1-3　Kahn算法

输入：有向图G，记录拓扑排序的数组S={}

输出：S（图G的拓扑排序）

1：while do //为以v为终点的边数

2：  把不存在任何指向其的边的顶点都加入S中；

3：  从G中删除在步骤2中加入S的顶点，并把从此顶点出发的边也从G中删除；

4：end

4. Dijkstra算法

图上还有很多其他经典算法，如Dijkstra算法、Prim算法、Kruskal算法。虽然这些算法多应用于路径规划、计算机网络时延计算、路由选择、资源优化等场景，但社交网络中的某些问题也可以用这些算法来解决，比如寻找某社交网络中与其他参与者之间关系最淡薄的参与者。

社交网络中参与者之间关系的深浅主要体现在其对其他参与者的影响力大小，也就是说，参与者对其他参与者的影响力越大，其与其他参与者之间的关系越亲密，反之则越淡薄。想要寻找社交网络中与其他参与者关系最淡薄的人，就等价于寻找社交网络中影响力最小的顶点。由此，把社交网络转换成一张有权社交图，边的权值表示社交网络中对应顶点之间连接的边的数量。通常，将所有P(u,v)中权值之和最小的路径称为最短P(u,v)，将此权值称为u到v的最短距离。那么，可以将社交网络中某顶点的影响力表示为其到其他所有顶点的最短距离之和。这样，一个社交网络上的问题就被转化成了计算最短距离的问题，可以用图的Dijkstra算法来求解。

Dijkstra算法是由荷兰计算机科学家Edsger W.Dijkstra于1959年提出的算法。该算法基于一个显而易见的事实：假设v是P(u,z)中的一点，那么最短P(u,z)中，u到v的部分必定是最短的P(u,v)。因此，Dijkstra算法按照路径长度递增次序产生起点到其他所有顶点的最短路径。

算法1-4　Dijkstra算法

输入：有非负权值的图，起始顶点为u，边xy的权值记为，如果边
　　　xy不存在，那么，顶点集

输出：起始顶点u到其他所有顶点的最短距离

1：对于，计算；

2：while do

3：  选择，把对应的添加至S中；

4：  用更新中顶点的dist值；

5：end

5. Prim算法

定义14：如果H满足，且H中边的顶点的分配方式和G一样，那么称H为G的生成子图。

定义15：树是不含有环的连通图。

定义16：如果树T是连通图G的生成子图，那么称T是G的生成树。

定义17：如果生成树T是加权连通图G的各边的权值之和最小的生成树，那么称T是G的最小生成树。

Prim算法和Kruskal算法常用于搜索图的最小生成树。这两种算法都采用了贪心算法，即：求解问题时，总是做出在当前看来最好的选择。换言之，贪心算法解决问题不从整体最优的角度出发，而是把问题拆分成若干个子问题，先对每个子问题寻求最优解，再将若干局部最优解组合成原问题的最优解。

算法1-5　Prim算法

输入：  加权图，最小生成树，其中，（x为起始顶点），

输出：最小生成树H

1：while do

2：  在E中选取权值最小的边uv，其中，；// 如果存在多条边满足前述条件，即有多条相同权值的边，则可任意选取其中之一

3：  将v加入中，uv加入中；

4：end

6. Kruskal算法

Kruskal算法的思路是从具有最小权值的边开始不断扩张树H，直至生成最小生成树。

算法1-6　Kruskal算法

输入：加权图，最小生成树

输出：最小生成树H

1：按照边的权值从小到大测试所有边，如果把当前边加入最小生成树H的边集中，不会使得H中出现环，则把这条测试边加入当前的最小生成树中；否则，将边舍弃；直到H中所有顶点互相连通

1.2.2　图的结构分析

每个社交网络都与社交图一一对应，通过发掘图的结构特征，就可以得到对应的社交网络的结构特点。因此，分析图的结构是社交网络分析的重要手段之一。

1. 社交图顶点的结构分析

度指的是与图上顶点关联的边数。在有向图中，由于边存在方向，因此顶点的度分为出度和入度：顶点的出度等于由此顶点出发的边数，入度则等于指向此顶点的边数。度是最简单的表示顶点与其他顶点的关联程度的变量。一个顶点的度越大，这个顶点与其他顶点的关联越紧密，在社交网络中，此顶点对其他顶点的影响越大，在网络中的地位越重要。这种表示方式虽然简单有效，但是仅仅考虑了顶点间的直接关联，而忽略了整个社交图的结构特征。顶点的度也被称为绝对中心度，为

　　（1-5）

为弥补绝对中心度的局限性，1979年Freeman提出了相对中心度的概念。相对中心度为顶点的绝对中心度与可能的最大绝对中心度的比值。对于一幅有着个顶点的无环无向社交图，其可能的最大绝对中心度为。无向社交图的相对中心度为

　　（1-6）

通常，研究者把有一个度为的顶点和个度为1的顶点的图称为星图，或称为星形耦合网络。图1-4是一个有6个顶点的星图。此星图中，顶点a具有最大绝对中心度。

对于无圈的有向图，其可能的最大绝对中心度为，因此有向社交图的相对中心度为

　　（1-7）

绝对中心度与相对中心度都只考虑了顶点与其他顶点的直接联系，而忽略了间接联系。因此，Sabidussi提出了接近中心度的概念。他认为：顶点的重要性应该由其对其他顶点的依赖性来决定。一个顶点越重要，它越容易与其他顶点进行交互；一个顶点越不重要，它与其他顶点的交互越困难，换言之，它与其他顶点的最短距离之和越大。因此，社交图的接近中心度为

　　（1-8）

其中，表示G的顶点v和顶点t之间的最短距离。

对顶点v到其他所有顶点的最短距离进行平均，得到顶点v的平均最短路径：

　　（1-9）

其中，N表示社交图G的顶点总数。

顶点v的平均最短路径只对连通图G有意义，因为如果顶点v与顶点u不连通，那么最短P(u,v)的值为∞。为了得到非连通图的平均最短路径，对进行取倒数处理，得到顶点v的全局效率：

　　（1-10）

越小，顶点v与其他顶点间的信息传播越慢，社交互动越困难。类似于全局效率，可以定义顶点v在社交图的区域H上的局部效率：

　　（1-11）

其中，表示社交图的子图H中的顶点数。

在地铁线路中，不同线路交会的车站被称为交通枢纽站，比如：西直门站是北京地铁2号线、4号线和13号线的交通枢纽站。仿照这个思路，可以用某顶点承载的最短路径数来表示此顶点在社交网络中的重要程度。通常将经过顶点的最短路径数称为顶点v的介数（Betweenness）。

2. 社交图整体的结构分析

上述分析都是基于顶点的社交图结构分析，然而，很多时候，人们关注的重点并不是图上的某个顶点，而是整幅社交图。通常用度分布来刻画社交图的顶点的绝对中心度的分布。度分布可以揭示网络的类型及性质，是网络的重要几何性质。

　　（1-12）

其中，表示图G中度为k的顶点数，N表示图G的顶点总数。

对于一个顶点数有限的完全随机网络，其度分布符合泊松分布。泊松分布的形状以峰值为中心，峰值两侧以指数速度衰减。在这样的网络中，度值比平均值高许多或低许多的顶点，都十分罕见。

科学家们一直想当然地认为现实中的网络都是完全随机的，但1999年无标度网络的提出打破了这种构想：现实世界中的大多数复杂网络（如因特网、万维网和生物新陈代谢网络等）的度分布明显偏离了泊松分布，它们的顶点度分布更符合幂律（Power Law）分布的特征。

幂律分布的曲线有一条长长的尾巴，因此，幂律分布又被称为长尾分布。符合幂律分布的图中，顶点的度往往相差悬殊，极少数顶点的度很大，而绝大多数顶点的度很小，其度范围往往可以跨越几个数量级。比如：在社交网络中，往往少部分人掌握着大多数的社交关系，而其他人的社交关系相当有限。

通常将度分布服从幂律分布的复杂网络称为无标度网络（Scale-Free Network）。与随机网络相反，它是一种高度集中的网络，在这种网络中，度值极大的几个顶点被称为“集散顶点”，它们对整个网络的结构及特性有着很重要的影响。

社交网络的度中心势C用于衡量社交网络的绝对中心度的趋势，其公式为

　　（1-13）

其分子的含义是社交图G中所有顶点的绝对中心度与最大中心度之差的总和，其分母的含义是所有顶点的绝对中心度与最大中心度之差的总和的最大可能值。在具有N个顶点的星图中，中心顶点的绝对中心度为，其他顶点的度为1，因此，所有顶点的绝对中心度与最大中心度之差的总和为，这也是该总和的最大可能值。所以式（1-13）可以转换为

　　（1-14）

1998年，美国康奈尔大学的博士生Duncan Watts和他的导师Steven Strogatz共同发表了一篇名为Collective dynamics of 'small-world' networks的论文。他们认为，复杂网络可以按照两个独立的结构特性进行分类——集聚系数和顶点间的平均路径长度^[6]。集聚系数反映了顶点的邻接顶点间结构的紧密程度，集聚系数越大，此顶点的邻接区域中的顶点连接越亲密，的定义如下：

　　（1-15）

其中，表示社交图上与顶点v邻接的顶点数，表示社交图上与顶点v邻接的顶点之间的边数。

的含义是个顶点之间最大的可能边数。由此，顶点v的集聚系数可以被理解为顶点v的邻接顶点间的实际边数与最大可能边数的比值。集聚系数是能够描述图或网络中的顶点集结成团的程度的系数。显然，的范围介于0～1之间。越接近1，表示这个顶点附近的点越有“抱团”的趋势。

平均路径长度指的是一个网络中两个顶点之间最短距离的平均值，定义顶点到自身的最短距离为0，则社交图的平均路径长度定义为

　　（1-16）

如果去除每个顶点到自身的距离，那么平均路径长度可以被定义为

　　（1-17）

社交网络的密度（Density）则从边数角度衡量社交网络的结构紧密程度，其公式为

　　（1-18）

其中，表示社交图的边数。

一般情况下，关系网中边数越多，顶点间的关系越紧密，信息的传播越快速。

此外，社交网络的大小指社交图中顶点的个数。社交网络的直径指的是社交图中任意两个顶点u和v之间的最短距离。对于非连通图，其直径显然是∞。该值反映了社交网络联系的紧密程度。

3. 社交图层次的结构分析

具有严格组织结构的社交图，如表示公司管理关系的图，往往具有明确的层次性。公司管理制度的存在，使得此类社交网络上信息的传递具有严格的方向，因而社交图呈现出强烈的层次特征。因此，可以用层次度（Hierarchy）来评价社交图的层次性。

社交图的层次度H定义为

　　（1-19）

其中，表示社交图中双向连通的顶点对的数量。

社交图的结构层次性越强，社交关系的方向越明确，双向连通的顶点对越少，层次度H更接近1。

1.2.3　特殊的图

1. k部图

现在的人乐于使用各种社交软件，一个人可能会在多个社交软件上都注册有账号。现有社交图G，G中的顶点表示某人在某社交软件上的账号，比如某人的微信号或某人的豆瓣账号。为了打破各个社交软件间的壁垒，可以把同一个人在不同软件上的账号用边关联起来，比如把表示某人的微信号的顶点与表示其豆瓣账号的顶点相关联。此时，社交图G可以被划分成k个独立集，每个独立集代表一种社交软件。

定义17：如果图G可以被划分为k个互不相交的非空子集，使得每个子集内不存在任何互为邻居的顶点，则这样的图G被称为k部图。如果，那么图G为二部图，如图1-5所示。

除了表示社交关系，k部图也常用于表示资源的分配方式。比如：图G的顶点表示学校的教师或学生，如果老师给某位学生讲过课，则将该老师与该学生相关联。此时，图G为二部图。

2. 同质图、异质图

社交图中每个顶点的特征类型往往相同。但是，在某些情况下，图的顶点并不全是同类型的，顶点需要不同的特征来表达，通常分别用同质图和异质图来表示。

定义18：同质图（Homogeneity）是图中的顶点类型和关系类型都仅有一种的图。异质图（Heterogeneity）是图中的顶点类型或关系类型多于一种的图。

图的另一个概念——同构，与同质名字相似，但需要注意的是，这是两个完全不同的概念。“同构”这一概念只适用于一组图，单独说某张图是同构的是没有任何意义的。

定义19：对于图和图，如果存在一个双射f将映射到，使得对于任何都有对应的，那么图G与图H是同构的。

由于顶点位置的选择不同，不同的人根据同一个邻接矩阵可能画出表面上截然不同的图，但实际上，这些图是同构的。

在有机化学中，分子式相同、结构不同的化合物互为同分异构体，如因碳架不同产生的碳架异构体。由于化学键的能量存在差异，同分异构体之间的化学性质具有明显的差异。然而，在图论中，图的结构决定了图的本质特征，因此，同构的图之间有类似的性质。同构关系是一种等价关系，具有自反、对称和传递的属性。等价关系可以把一个集合划分成一些等价类。相应地，图的同构关系也可以把图集合划分成几个同构类。

3. 超图

在学者合作关系网络中，普通的图虽然能表示作者之间是否存在合作关系，但是不能表示是否有3个及以上的学者同时参与了一次合作，即使关联多个学者的顶点也仅代表两两之间有过合作而非有过共同的合作关系。

为了解决普通的图无法完全刻画真实世界的网络特征的问题，数学家Claude Berge于20世纪60年代提出了一种新的图理论——超图（Hypergraph）理论。在超图中，边被推广为广义的边，即可以和任意个数的顶点相连的超边。下面给出超图的数学定义。

定义20：超图，V是顶点集，E是V的一组非空子集，其元素被称为边或超边。

4. 树

定义21：所有连通分量都是树的非连通图被称为森林。

定义22：树上每一个顶点的子树的个数为这个顶点的度；树上度为0的顶点被称为该树的叶。

图1-6中，薛公的度是1，薛蝌、薛宝琴、薛蟠和薛宝钗是该树的叶。

树是图论中最简单的图，也是图的骨架^[7]。除了上述表示人物关系的应用，树还有很多其他应用，如表示文件的目录结构。