第5章〓图计算
图数据是节点和边的集合，其中节点表示实体或对象，边代表实体之间的关系或连接。图计算是一种处理图数据的计算模型，通过对节点和边进行操作和计算，发现节点间的模式和关联性等信息，解决复杂的图网络分析问题。本章将介绍图数据的统计特性、图遍历算法、图分割算法、社区发现算法以及图计算平台等相关内容。

5.1问题导入

在同一篇论文中署名的作者，即表示他们之间存在合作关系。对某一领域科研工作者之间的合作关系进行挖掘，有助于了解该领域科研团队的研究方向及进展。合作者关系数据可以使用图网络来进行建模，其过程如图51所示。为实现这一目标，需要解决以下问题： 

(1) 如何使用图网络来表示实体之间的合作关系； 

(2) 如何对图网络中的节点和边进行统计分析，以描述网络节点的属性和结构特征； 

(3) 如何对图网络进行计算，以实现图的分割和节点的聚类等任务。

围绕上述问题，本章将从图网络、图基础算法、社区发现等方面进行介绍。



图51合作者关系建模过程


5.2图网络

图网络常用于刻画社交网络、交易网络和通信网络等存在复杂网络关系的数据类型，是描述非结构化数据的一种重要方式。

5.2.1图网络表示


常用G(V,E)表示图网络，其中V是由表示实体的节点构成的集合，E是由表示节点之间关系的边构成的集合，存在边连接的两个节点vi,vj用<vi,vj>∈E表示。图网络在现实生活中是广泛存在的，可用于不同场景的数据建模与分析。

例5.1(社交网络)20世纪70年代，美国社会学家Zachary观察了一家空手道俱乐部34名成员之间的交往情况。每名成员用一个节点来表示，如果两名成员之间是交往频繁的朋友关系，那么就在两个节点之间用一条边连接，如图52所示。



图52空手道俱乐部成员的社交网络


通过构造上述图网络，可以模拟和分析现实世界中的复杂系统。但要在计算机存储或处理上述图网络，还需要借助描述图网络中各节点之间连接关系的邻接矩阵。假设G(V,E)为具有n个节点的图，其邻接矩阵A=(aij)n×n定义为


aij=
1,<vi,vj>∈E
0,<vi,vj>E(51)


例5.2如图53(a)所示的图的邻接矩阵如图53(b)所示。



图53图及其邻接矩阵


5.2.2网络结构分类

现实生活中可利用图网络表示的数据类型十分丰富。根据不同的标准，可以将图进行不同的划分。根据图网络中边是否有方向，可以将图网络分成有向图和无向图。根据图网络中边的连接方式，可以划分为01网络、加权网络、符号网络、双模网络和动态网络。根据图网络数据的表示模型，可以划分为ER随机图模型、小世界网络和无标度图网络等。

1. 基于边方向的划分

1) 无向图


边没有方向的图称为无向图。如果<vi,vj>∈E，那么同时有<vj,vi>∈E。因此，无向图的邻接矩阵是对称的。例5.1中的社交网络是一个无向图。

2) 有向图

边有方向的图称为有向图。如果从节点vi到节点vj有一条边相连，那么<vi,vj>∈E，在邻接矩阵中 aij=1。如果从节点vj到节点vi有没有边相连，那么相应的在邻接矩阵中aji=0。因此在有向图中，邻接矩阵不一定是对称的。

2. 基于边连接方式的划分

1) 01网络

01网络又称为无权网络。网络中的边仅表示相应的两个节点存在某种特殊的关系，比如两个节点是朋友关系，或者节点之间存在交易。01网络可以由邻接矩阵完全表示，矩阵中的元素取值为0或1。

2) 加权网络

加权网络不仅能够反映节点之间是否存在联系，还能反映节点之间联系的强弱。在加权网络中，可以定义权重矩阵。给定一个有n个节点的加权网络G(V,E)，其权重矩阵为W=(wij)n×n，如果节点vi到节点vj之间有边连接，则wij为连接的边的权重； 如果节点vi到节点vj之间没有边连接，那么 wij=0。

3) 符号网络

符号网络是指边具有正或负符号属性的网络，其中正号表示积极关系，用“+”标识，负号表示消极关系，用“-”标识。符号网络可以被看作一种特殊的加权网络，广泛存在于社会学、生物学和信息学等领域中。




图54双模网络示意图



4) 双模网络

双模网络是定义在两种不同类型节点上的网络，且关系仅存在于不同类型的节点之间。比如我们要使用图网络结构表示图书馆图书的借阅关系，读者和图书属于不同类型的节点。同一种类型的节点之间不会产生关系，只有不同类型的节点之间可能存在边相连，如图54所示。

5) 动态网络

动态网络中网络结构会随着时间的变化而变化，包括节点数量的变化、边的变化以及边的权重的变化等。日常生活中存在的许多网络结构数据都具有丰富的时间信息，节点之间的联系随着时间而动态演变。

3. 基于表示模型的划分

1) ER随机图

ER随机图是由著名的数学家Erdo¨s和Reˊnyi提出的随机图模型生成的随机图。在这个模型中，给定n个节点{vi,i=1,2,…,n}，每两个节点vi,vj之间以概率p连接一条无向边，而且任意两点之间存在边的概率都相互独立。

2) 小世界网络

小世界网络，就是相对于同等规模节点的随机网络，具有较短的平均路径长度和较大的聚类系数特征的网络模型。可以用来很好地建模真实网络的聚集性的特点。在现实世界的人际交往中，任意两个人只需要通过少数的几个中间人就能相互认识，具有小世界网络的特点。

3) 无标度网络

在一个包含多个节点的网络中，每个节点连接的边的数量差别很大。如果图网络中的节点的度满足幂律分布，即各节点之间的连接状况具有严重的不均匀分布性，网络中少数节点拥有极其多的连接，而大多数节点只有很少量的连接，这样的网络就称为无标度网络。幂律分布广泛地存在于物理学、计算机科学、社会科学等众多领域之中，使得无标度网络在对现实世界的建模中具有重要的意义。BA模型(BarabsiAlbert Model)是一种生成无标度网络的重要方法，其流程如下： 

(1) 初始化n0个相互连通的节点； 

(2) 增加一个节点v，这个新增加的点与已有的节点u以概率p(u,v)=deg(u)∑ideg(i)生成一条无向边，其中deg(u)表示网络中与节点u∈V有边连接的节点的数量； 

(3) 更新图网络中节点的度，不断重复步骤(2)，直到生成足够丰富的节点。

5.2.3网络描述性统计 

接下来介绍常用的网络描述性统计量。

1. 节点的度

给定一个n个节点的无向图G(V,E)，如果邻接矩阵为A，节点vi的度定义为


deg(vi)=∑nj=1aij(52)

表示与节点vi通过边相连接的节点数量。

对于邻接矩阵为A的n个节点的有向图G(V,E)，每个节点的度包括入度和出度。节点vi的入度表示从其他节点连向节点vi的数量，其定义为


deg+(vi)=∑nj=1,j≠iaji(53)

节点vi的出度表示从节点vi连向其他节点的数量，其定义为


deg-(vi)=∑nj=1,j≠iaij(54)

2. 节点的中心性

节点的中心性是衡量网络中节点重要性的指标，它反映了节点在网络结构中的地位和作用，例如社交网络中最有影响力的人，互联网或城市网络中的关键基础设施节点以及疾病的超级传播者。常见的节点中心性度量指标包括度中心度、紧密中心度、介数中心度等。

1) 度中心度

度中心度(Degree Centrality)是通过与节点有边连接的邻居节点数目来计算节点的重要性。一个节点的邻居越多，显然该节点的重要性越强。对节点的度进行归一化，可以得到度中心度的定义。给定一个包含n个节点的无向图G(V,E)，节点vi的度中心度为


Cd(vi)=deg(vi)n-1(55)

其中，0≤Cd(vi)≤1。

2) 紧密中心度

距离可以用来衡量两个非邻居节点之间的接近程度。如果节点vi与其他节点的距离都很小，那么该节点越接近图的中心。这一特性可以用紧密中心度(Closeness)来衡量。其定义如下： 


Cc(vi)=∑j≠i1d(vj,vi)(56)

其中，d(vj,vi)表示节点vi到节点vj之间的距离，可以通过迪杰斯特拉算法(Dijkstra’s Algorithm)、贝尔曼福特算法(BellmanFord Algorithm)和A*搜索算法等计算。

3) 介数中心度

在图网络中，两个非邻居节点需要通过其他节点进行连通。一个节点vi充当中介作用的次数越高，说明其扮演桥梁作用的重要性越高。假如这个节点vi消失了，那么其他节点之间的连接甚至可能断开。介数中心度(Betweenness Centrality)可以用来衡量节点在扮演桥梁作用中的重要性，其定义为


Cb(vi)=∑j,k≠iσjk(vi)σjk(57)

其中，σjk表示从节点vj到节点vk之间所有的路径的数量，σjk(vi)表示其中途径节点vi的路径数量。

3. 网络密度

在一个包含n个节点的网络G(V,E)中，最多有C2n 条边。如果节点之间都存在相连的边，那么这个上限就可以达到，此时的图网络就会显得稠密； 如果只有较少的节点之间存在连接，此时的图网络就会显得稀疏。用网络密度来衡量，其定义为


Δ=|E|C2n(58)

其中|E|表示图G(V,E)中的边数，式(59)表示在所有可能的连接中，有多大比例的边是实际存在的。在许多实际的问题中，网络的密度通常都是很低的。

例5.3(合作者网络)现在的科学研究通常需要多名研究者通力合作共同参与来完成。不同领域的合作者的规模可能会存在一定的区别。可以用图网络模型来建模科学研究合作者网络，网络中的节点代表一位学者，如果两位学者合作发表过学术论文，那么就在代表他们的节点之间连接一条边。arxiv ASTROPH(天体物理学)协作网络是基于提交到arxiv中天体物理学类别的论文建立的科学合作者网络模型，包括18772个节点和198110条边，且： 

(1) 该合作者网络的密度为0.11%，每个节点平均与21.1个节点有边连接。

(2) 可以借助Python库networkx计算该合作者网络的各节点的度等描述性统计指标。其中节点度的分布如图55所示。图中横坐标表示节点的度，纵坐标表示相应的节点数量。大多数作者的合作者都很少，只有少量的节点的度很大，与很多节点都存在连接。



图55arxiv ASTROPH合作者网络中节点度的统计


(3) 如图56展示了合作者网络节点的度与度中心度、介数中心度和紧密中心度等指标之间的相关关系。其中横坐标表示节点的度，纵坐标表示节点的其他统计特性。可见节点的度与度中心度呈现严格的线性关系。



图56arxiv ASTROPH合作者网络中节点的度与其他统计特征的散点图


5.3图基础算法

前述介绍了图的基本概念、图的表示及描述性统计，本节主要介绍图的基本算法： 图遍历和图分割。

5.3.1图遍历

图遍历(Traversing Graph)是指从图中的某一节点出发，按照某种搜索方法沿着图中的边对图中的所有节点访问一次且仅访问一次。它是图的基本运算，在求解图的连通性问题、拓扑排序、关键路径和最短路径等算法中具有重要的作用。图遍历算法包括广度优先搜索(Breadth First Search,BFS)和深度优先搜索(Depth First Search，DFS)。

1. 广度优先搜索


给定图G(V,E)和起始节点v0的情况下，广度优先搜索算法从初始点v0 开始，依次访问与其相邻的所有节点，然后由近及远，逐一访问相邻节点的相邻节点。通过广度优先搜索算法可以生成一棵根为 v0 且包括v0所有可达节点的广度优先树。

例5.4给定一个网络，如图57所示。请给出以节点1为起点的广度优先搜索结果。



图57图网络示意图


根据广度优先搜索算法思想，有： 

(1) 从节点1出发，首先搜索到它的相邻节点2和3； 

(2) 接下来搜索到节点2的相邻节点4和5； 

(3) 接下来搜索到节点3的相邻节点6和7； 

(4) 最后搜索到与节点4相邻的节点8。此时所有的节点都已搜索到，于是得到从节点1出发的基于广度优先搜索算法的路径为


1→2→3→4→5→6→7→8

2. 深度优先搜索

对于最新发现的节点v，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当以节点v为起点的所有边都已被探寻过，搜索将回溯到发现节点 v的那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个过程反复进行直到所有节点都被发现为止。

例5.5考虑例5.4中的图网络，请给出以节点1为起点的深度优先搜索结果。

根据深度优先搜索算法思想，有： 

(1) 从节点1出发，访问节点1。

(2) 访问节点1后，访问第一个与节点1相连且未被访问的节点2。之后，以节点2为新节点，继续搜索，依次访问节点4、8、5。

(3) 搜索从节点5依次溯回至节点8、4、2、1。

(4) 由于与节点1相连的节点3未被访问，访问节点3，并从节点3出发依次访问节点6、7。至此所有的节点都已被搜索，于是算法终止。最终得到从节点1出发基于深度优先搜索算法的路径为


1→2→4→8→5→3→6→7

3. Dijkstra最短路径算法


Dijkstra算法是一种基于贪心策略的路径寻优算法，主要用于求解图论中的单源最短路径问题。对给定的加权有向图G(V,E)和源点v0，将所有节点划分成S与V-S两个集合，S中存放已找到的到v0最短路径的节点(初始只包含源点v0)，V-S中存放未找到到v0最短路径的节点(初始为V-{v0})，然后计算v0到V-S中各节点最短路径的长度。若S中的节点与V-S中节点u有边相连，则v0到u的最短路径长度l(u)=minvi∈Sw(vi,u)+l(vi),其中w(vi,u)为连接节点vi与u的边的权重或长度(若vi与u不相连，则w(vi,u)=∞； 若S中的节点与u没有边相连，则l(u)=∞)。在此基础上，将v0到V-S中路径长度最短的节点加入集合S，直到所有节点都加入集合S。Dijkstra算法描述如表51所示。



表51Dijkstra算法





(1) 初始化S与V-S，其中S={v0}，V-S=V\\{v0}

(2) 计算v0到V-S中各节点最短路径的长度。将v0到V-S中路径长度最短的节点u添加到集合S中，并从V-S中删除节点u
(3) 重复步骤(2)，直到V-S集合为空


例5.6考虑如图58中的网络，请给出起点A到其他各节点的最短路径。



图58图网络示意图


根据Dijkstra算法，有： 

(1) 初始化S与V-S，令S={A(0)}，V-S={B(1),C(5),D(∞),E(∞),F(∞)}，其中B(1)表示当前起点A到节点B的最短路径长度为1，D(∞)表示当前起点A到节点D的最短路径长度为∞, 其余类似。

(2) 将起点A到V-S中路径长度最短的节点B添加到S中，更新S、V-S和节点A到V-S中各节点最短路径的长度，得S={A(0),B(1)}，V-S={C(5),D(4),E(2),F(∞)}。

(3) 将起点A到V-S中路径长度最短的节点E添加到S中，更新S、V-S和节点A到V-S中各节点最短路径的长度，得S={A(0),B(1),E(2)}，更新集合V-S={C(5),D(3),F(5)}。

(4) 将起点A到V-S中路径长度最短的节点D添加到S中，更新S、V-S和节点A到V-S中各节点最短路径的长度，得S={A(0),B(1),E(2),D(3)}，V-S={C(5),F(5)}。

(5) 由起始点到C与F的最短路径相等，可随机挑选一个加入集合S，这里以C为例，将其加入集合S，得S={A(0),B(1),E(2),D(3),C(5)}，V-S={F(5)}。

(6) 将V-S中剩余的F加入S中，得S={A(0),B(1),E(2),D(3),C(5),F(5)}，据此及算法过程可得起点A到各个节点的最短路径及长度。

5.3.2图分割

令G(V,E)表示一个加权无向图，其权重矩阵为W。图分割是将图G划分成2个规模相同的子网络G1和G2。定义一个变量


pi=
1,vi∈G1
-1,vi∈G2(59)

连接G1中的节点与G2中的节点的所有边的权重总和被称为“割”，有


cut(G1,G2)=∑vi∈G1,vj∈G2wij
=12∑ni=1∑nj=1wij(pi-pj)2
=12∑ni=1∑nj=1wij(p2i-2pipj+p2j)(510)
=12∑ni=1∑nj=1-2wijpipj+∑ni=1∑nj=12wij
=pT(D-W)p

其中,p=［p1,p2,…,pn］T，D是一个对角矩阵，对角线上的元素为dii=∑nj=1wij，也称为对角度矩阵。定义半正定对称矩阵L=D-W，称为拉普拉斯矩阵, 则图分割可以求解如下优化问题实现： 


minpTLp
s.t.p2i=1,i=1,2,…,n(511)


优化问题式(511) 是一个组合优化问题，属于NP难问题。为解决该问题，一种有效的方法是对该优化问题的约束条件进行松弛，对应的优化问题可写为


minpTLp
s.t.eTp=0(512)
  pTp=n

其中，e=［1,1,…,1］T。L的最小特征值为0，此时对应的特征向量为e，以e作为优化问题的解向量p不满足约束条件eTp=0，于是最优解应该在第二小特征值对应的特征向量p1处。根据p1的分量的正负性实现节点的划分。将特征向量分量值为正的节点划分到子图G1，特征向量分量值为负的节点划分到子图G2，从而实现网络的分割。

5.4社区发现

在许多图网络结构数据中，网络密度是很低的，节点之间存在边的连接并不是随机的。比如在银行交易网络中，亲戚朋友的银行账户之间相互转账交易是常发生的，陌生人之间的转账交易则是很偶然的。图数据分析的一个重要任务是发现网络结构中节点的聚集特性，即探索发现网络中存在的不同社区。

所谓社区，是图网络中的一个子图。社区内部的节点与节点之间的连接很紧密，而与其他社区的节点之间的连接比较稀疏。社区发现(Community Detection)是根据网络中节点之间的关系将节点划分到某一个社区之中，在本质上是一个节点聚类的问题。社区发现算法主要包括GirvanNewman算法、谱方法和Louvain算法等。

5.4.1模块度

模块度(Modularity)是用来衡量一个社区划分结果性能的定量评价指标，由Newman和Girvan于2004年首先提出来的。社区划分的结果，应该使得社区内部节点之间连接紧密，而社区之间的节点连接稀疏。模块度正是基于这一思想而定义的，它是指网络中连接社区结构内部节点的边所占的比例减去另外一个与原网络结构度数分布一致的随机网络中连接社区结构内部节点的边所占比例的期望值。其严格的数学定义如下。

定义 5.1(模块度)设图G包含n个节点和m条边，其邻接矩阵为A，ki 为节点 vi的度，给定图G的社区结构C，社区结构的模块度可通过下式计算： 


Q=12m∑i,jaij-kikj2mδ(Ci,Cj)(513)

其中，Ci 和 Cj分别表示节点 vi 和 vj所在的社区，且有


δ(Ci,Cj)=
1,Ci=Cj
0,Ci≠Cj


模块度度量了社区结构情况，值越大表明这种划分的社区结构越好，可用于评价不同社区发现算法的优劣。式(514)只计算节点 vi 和 vj属于同一个社区的情况，如果两个节点不在同一个社区则忽略不计。因此，模块度可以改写为


Q=12m∑i,jaij-kikj2mδ(Ci,Cj)
=12m∑c∈C∑vi∈c∑vj∈caij-kikj2m(514)

其中,c∈C是图G的一个社区。从式(515) 更容易理解模块度的计算思路。如果两个节点vi 和 vj之间有一条边，而且这两个节点在同一个社区内部，那么它们偏向于对模块度有积极的贡献; 反过来，如果这两个节点间没有边，而且这两个节点在同一个社区内部，无论kikj2m大小如何，它们对模块度都会有负的贡献。



图59图网络结构示意图




例5.7如图59所示，图中有6个节点，其中


m=7,k1=2,k2=2,k3=3,
k4=3,k5=2,k6=2

社区结构为 C={{1,2,3},{4,5,6}}，计算该社区结构的模块度。

根据模块度的定义，图59中社区结构的模块度为


Q1=12m∑i,jaij-kikj14δ(Ci,Cj)
=1140-k1k114+21-k1k214+21-k1k314+
0-k2k214+21-k2k314+0-k3k314+
0-k4k414+21-k4k514+21-k4k614+
0-k5k514+20-k5k614+0-k6k614
=514

为了了解不同社区结构对模块度的影响，请看下面的例5.8。




图510图网络结构示意图



例5.8考虑例5.7的图网络，使用不同的社区结构划分该网络。令其社区结构为 C={{1,2},{3,4,5,6}}，即节点1和节点2属于一个社区，节点3、4、5、6属于另一个社区，如图510所示。计算该社区结构的模块度。

根据模块度的定义，图510中社区结构的模块度为


Q2=12m∑c∈C∑i∈c∑j∈caij-kikj2m=649

通过分析例5.7和例5.8，Q2<Q1，调整节点3所属社区会导致模块度降低，从而说明社区结构{{1,2,3},{4,5,6}}比社区结构{{1,2},{3,4,5,6}}效果更好。

5.4.2GN算法

传统的社区发现算法主要基于层次聚类的思想。首先将所有的节点当作一个社区，每次使用算法将一个社区划分为两个社区，不断地迭代，实现自顶向下的方式发现图网络中的不同社区。 


GN(GirvanNewman)算法是由Girvan和Newman于2002年提出的社区发现领域的一个重要算法，具有开拓性的意义。它的基本想法是，在一个网络之中，通过社区内部的边的最短路径相对较少，而通过社区之间的边的最短路径的数目则相对较多。如果能够将连通不同社区的边删除，那么就可以很自然地将图网络划分成不同的社区。为此需要衡量边在网络中的重要性。


给定一个图网络G(V,E)，(vi,vj)∈E 的边介数(Edge Betweenness)是指网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。边介数越大，边在网络中的枢纽性越强。基于图网络的边介数，GN算法的步骤如下： 

(1) 计算图网络G中每一条边的边介数； 

(2) 删除具有最高边介数的边； 

(3) 重新计算剩余所有边的边介数； 

(4) 重复步骤(2)和步骤(3)，直到形成既定的社区数量时停止。

从而产生一种类似层次聚类的效果，形成一棵自上而下的树。GN算法在每次删除边之后都会重复计算剩余节点的边介数，从而具有较高的计算复杂度，难以在大规模图网络学习中应用。同时GN算法的终止条件缺乏一个明确的衡量目标，分裂过程可以持续进行下去直到每个节点都组成一个独立的社区。

例5.9考虑例5.1中空手道俱乐部的社交网络。

(1) 使用GN算法将该网络进行划分，当选择划分成2个社区结构时，划分结果如图511所示。可以很直观地观察到该俱乐部中存在分别以0号员工和33号员工为核心的2个小团体。



图5112个社区的社区发现可视化


(2) 模块度是衡量社区发现结果的重要评价指标。当划分的社区数量和社区结构不同时，划分结果具有不同的模块度，如图512所示。从中可见，将社区划分成4个子社区时，具有最大的模块度。



图512划分成不同社区数量的模块度


(3) 根据最大化模块度的要求，可以将该网络划分成4个社区，如图513所示。



图513模块度最大化的GN算法的社区发现结果可视化



5.4.3谱方法

在5.3.2节中，介绍了基于拉普拉斯矩阵的图分割算法，实现了将一个大规模的图划分成两个子图(社区)的目的。如果将这个过程继续进行下去，每次选择一个社区进行划分，直到满足要求为止。由于模块度能够较好地衡量社区划分的性能，因此也可以考虑使用模块度矩阵替换拉普拉斯矩阵，称为社区发现的谱方法。


把一个图G(V,E)划分成2个社区G1和G2时，根据式(510)定义的变量pi，以及模块度的定义，得到


Q=14m∑i,jaij-kikj2m(pipj+1)
=14m∑i,jaij-kikj2mpipj(515)
=14mpTBp

其中，B=(bij)称为模块度矩阵，bij=aij-kikj/2m。注意到在模块度矩阵B中，它的每一行和每一列之和都为0，所以向量e=(1,1,…,1)T为特征值0对应的特征向量。因此可以通过最大化一次划分的模块度来找到当前最优的划分，即


maxpTBp
s.t.eTp=0(516)
  pTp=1

结合矩阵计算的知识，可以得到优化问题式(517)的最优值为模块度矩阵B的最大特征值，解向量p为其对应的单位特征向量。由此得到图网络中每一个节点的划分规则： 

(1) 如果解向量p的第i个元素pi>0，那么节点vi划分为社区G1； 

(2) 如果解向量p的第i个元素pi<0，那么节点vi划分为社区G2。

图可能有多个社区，为了进一步实现更细致的社区结构，简单的做法是将每个划分出来的子社区再一分为二。但是这种做法并不合理，这是因为当划分一个子社区时，有些边可能会被删除，最终整个图的社区结构的模块度会发生变化。每次最大化模块度,最终会导致一个错误的结果。

取而代之的是，每次划分一个子社区时，仅希望最大化模块度的增量ΔQ。假设一个子社区g=Gi,i=1,2的大小为ng，希望将社区g一分为二，那么其模块度的增量ΔQ可以计算如下： 


ΔQ=12m12∑i,j∈gbij(pipj+1)-∑i,j∈gbij
=14m∑i,j∈gbijpipj-∑i,j∈gbij
=14m∑i,j∈gbij-δij∑k∈gbikpipj(517)
=14m∑i,j∈gbij-δij∑k∈gbikpipj
=14mpTB(g)p

其中，12∑i,j∈gbij(pipj+1)和∑i,j∈gbij分别表示子社区划分后和划分前模块度的大小，当i=j时δij=1，否则其值为0。因此，只有当每次社区划分导致模块度增量ΔQ>0时才进一步划分这个子社区，否则这个子社区就不会再进一步划分。因此，每次划分都会保证整个社区结构的模块度是在不断增加的。

基于模块度优化的社区发现算法思想是将社区发现问题转化为优化问题，其优化目标是最大化整个社区结构的模块度。由于社区可以是图中任意节点的组合，实践上很难通过枚举法找到模块度最大的社区划分或社区结构，因此，通常使用近似算法来获得模块度最大的社区结构。

5.5GraphScope简介


GraphScope是阿里巴巴智能实验室研发并开源的一站式大规模图计算平台，致力于解决实际生产场景中所涉及的图计算问题。它具有高效的跨引擎内存管理，在业界首次支持Gremlin分布式编译优化，同时支持算法的自动并行化和自动增量化处理动态图更新，提供了企业级场景的极致性能。目前，GraphScope已在包括风控、电商推荐、知识图谱和网络安全在内的多个互联网领域得到成功应用。接下来，本节将介绍GraphScope的系统架构、重要特性和应用场景等。

1. 系统架构

GraphScope开发的宗旨在于处理和分析海量的图结构数据。要实现以上目标，需要多种计算组件进行交互，包括集群管理软件、分布式执行引擎以及开发工具和算法库等。由于整个系统庞大且功能复杂，在此主要对其中的算法层、引擎层和存储层进行介绍。图514给出了GraphScope的系统架构。



图514GraphScope的系统架构


(1) 算法层。GraphScope构建了丰富的图分析算法，包括聚类算法、图挖掘算法和图模式匹配算法等； 此外还提供了丰富的图学习算法，包括基于图神经网络的算法与基于节点嵌入的算法。用户可以很方便地利用GraphScope提供的Python接口来调用相应的算法处理图分析任务。

(2) 引擎层。GraphScope运行时由图交互引擎、图分析引擎和图学习引擎组成，分别负责提供存储和管理图数据的能力、执行各种图算法的自动并行化能力以及执行复杂图查询的能力。

(3) 存储层。实际应用中，图数据的规模通常较大，将数据加载到不同处理阶段(不同引擎之间)并保存输出需要花费非常大的代价。为解决以上问题，GraphScope提出了分布式内存数据管理系统Vineyard，用以支持管理数据的分区和跨引擎的数据处理任务，并为上层应用提供零拷贝的数据读取。

2. 重要特性

(1) 高性能。高性能引擎支持对Gremlin查询的并行化以及图分析算法的自动并行化机制。数据管理系统Vineyard提供了高效的图存储和数据交换，实现了跨系统的数据共享。

(2) 一站式处理。提供了一个一站式环境，用于在集群中执行各种并行图操作。

(3) 云原生。支持在多个云原生环境中进行部署和扩展，便于集成云上的各种服务，使其能够充分发挥云计算的优势。

(4) 易使用。提供了丰富和灵活的统一编程模型，覆盖了多种典型的图计算任务，方便用户快速构建自己的应用。

3. 应用场景

GraphScope可以应用于多种场景，包括但不限于： 

(1) 社交网络分析。通过图算法来分析社交网络中的用户关系和社区结构。

(2) 推荐系统。基于图的推荐算法可以帮助发现用户的兴趣和推荐相关内容。

(3) 欺诈检测。分析交易图可以帮助识别潜在的欺诈行为。 

(4) 知识图谱构建和查询： 利用GraphScope来构建复杂的知识图谱，并通过图查询来检索信息。 

由于GraphScope是开源项目，它的发展受到社区贡献的推动，也意味着它在持续更新和改进中。感兴趣的用户和开发者可以从其官方GitHub仓库获取源代码，参与项目的开发和使用。

5.6案例： 基于谱聚类的图像分割

图聚类是无监督学习中的一个基本问题，在计算机科学及相关领域中有着广泛的应用。作为谱方法中的一种，谱聚类是解决图聚类问题中最易于实现的一类方法，允许对图数据和非图数据进行聚类分析，在计算机视觉、文本挖掘和语音识别等领域得到了较为广泛的应用。图像分割是指将图像划分成若干个具有独特性质的区域并提取出重要目标信息的过程。本节将通过一个案例介绍谱聚类算法在图像分割中的具体应用。

谱聚类是从图论中发展而来的，它以谱图划分作为理论基础，通过将聚类问题转化为图划分问题，实现任意形状数据的聚类。与传统的Kmeans聚类算法相比，谱聚类算法对数据分布的适应性更强，聚类性能也更优越且计算量小。其基本思想是将图像的像素点看作图的节点，用连接节点的边上权值表示样本之间的相似度，基于图像像素点之间的相似性，通过对像素点组成的图进行切分，使切图后不同子图间的边权重之和尽可能小，而子图内的边权重之和尽可能大，从而实现聚类的目的。

基于以上思想，谱聚类算法的基本步骤描述如表52所示。



表52基于谱聚类的图像分割





输入： 待分割图像，分割数k

输出： 
分割后的图像结果

(1)
对输入图像中的像素点，根据数据点之间的相似度构建相似矩阵W

(2)

根据相似模型计算相似矩阵W的度矩阵D，并构建标准化的拉普拉斯矩阵Ls=D-1/2LD-1/2，其中L=D-W表示拉普拉斯矩阵

(3)
对矩阵Ls进行特征分解，获得其前k个较小的特征值与特征向量u1,u2，…,uk

(4)

将特征向量ui组成的矩阵U按行进行归一化处理，得到归一化向量集Us，其中归一化向量为图像像素集在特征空间上的一个映射

(5)
对特征向量集Us 使用Kmeans算法进行聚类分析，得到最终聚类结果


谱聚类算法的关键代码描述如下： 



# 求解归一化的拉普拉斯矩阵并对特征向量集进行聚类分析

import scipy

import sgtl.graph

import scipy.sparse.linalg

from sklearn.cluster import Kmeans



def Clustering_eigenvectors (DatasetGraph, num_clusters, num_eigenvectors):

# 计算归一化拉普拉斯矩阵

laplacian_matrix = sgtl.graph.Graph.normalised_laplacian_matrix(DatasetGraph)

_, eigvecs = scipy.sparse.linalg.eigsh(laplacian_matrix, num_eigenvectors, which='SM')



# 对特征向量集执行K-means算法

labels = KMeans(n_clusters=num_clusters).fit_predict(eigvecs［:, :num_eigenvectors］)



# 对不同的类别进行划分

clusters = ［［］ for _ in range(num_clusters)］

for idx, label in enumerate(labels):

clusters［label］.append(idx)



return clusters






本案例测试图像来自Berkeley彩色图像数据库BSDS500，该公开数据集支持下载。该数据集常用于图像分割和物体边缘检测分析。采用谱聚类算法进行图像分割分析，图515展示了基于谱聚类算法生成的图像分割结果。通过原始图和分割后的图可以看出，谱聚类算法可以将图像中的天鹅、蝴蝶以及山等重要目标信息识别出来，且对于一些细节信息也能取得较好的分割效果，如蝴蝶的触角等。



图515基于谱聚类算法生成的图像分割结果


5.7本章小结

图计算作为人工智能中的一项重要技术，已成为支撑新兴数据驱动市场的重要引擎，在社交网络、知识图谱和计算机视觉等不同领域有着广泛的应用。本章首先介绍图网络结构数据的表示方法及其描述性统计特征，然后介绍了基于图网络的计算方法，包括图遍历和图分割算法。图遍历算法主要介绍了广度优先搜索算法和深度优先搜索算法。在不同的场景中，基于拉普拉斯矩阵的最小割是实现图分割的一种重要方法，在图像分割等领域中具有重要的应用。社区发现是图计算的一个重要的方向，可用于实现图网络中节点的聚类，本章通过一个例子介绍了GN算法等社区发现算法。最后，简要介绍了开源的图计算平台GraphScope，并通过图像分割案例讲解了谱聚类算法的应用。

习题
1. 选择题

（1） 图网络结构中的节点表示什么？（）

   

A. 数据对象
B. 数据属性
C. 数据关系
D. 数据属性值

（2） 图网络结构中，节点之间的关系是通过什么来表示的？（）

A. 节点属性
B. 边属性
C. 边的方向
D. 边的权重

（3） 图网络结构中，节点的度是指什么？ （）

A. 节点的属性数量
B. 节点的属性值数量

C. 节点与其他节点的连接数量
D. 节点与边的连接数量

（4） 以下哪种中心性指标强调节点在网络中的“桥梁”作用？（）

A. 紧密中心度
B. 介数中心度
C. 度中心度
D. 特征向量中心度

（5） 在有向图中，一个节点的介数中心度是指（）。

A. 经过的最短路径数量
B. 经过的所有路径数量

C. 经过的最短路径的比例
D. 经过的所有路径的比例

（6） Dijkstra算法适用于哪种类型的图？（）

A. 有向图
B. 无向图
C. 有向加权图
D. 以上所有

（7） 以下哪个选项是深度优先搜索的特点？（）

A. 层层遍历，每一层的所有节点都被访问完后再访问下一层

B. 先访问近邻节点，再访问远邻节点

C. 按照从顶点到叶子的顺序访问节点

D. 从起始节点开始，沿着路径一直向前探索，直到到达一个未被访问邻居的节点，然后再回溯到上一个节点继续探索

（8） 在图的最小割问题中，以下哪项描述是正确的？（）

A. 最小割是图中顶点集的一个分割，使得分割后的两个子图之间的边权重之和最小 

B. 最小割是将图中的边分割为两部分，使得两部分之间的边权重之和最大 

C. 最小割是图中顶点集的一个分割，使得分割后的子图边权重之和最大 

D. 最小割是图中顶点集的一个分割，使得分割后的子图顶点数最少

（9） 在社区发现中，哪个概念描述了节点与其社区内其他节点的连接紧密度？（）

A. 模块度
B. 网络连通性C. 节点的度
D. 紧密中心度

（10） 以下哪种算法是基于模块度的社区发现算法？（）



A. 随机游走
B. 谱聚类
C. 隐含图
GN算法

2. 简答及计算题

（1） 图网络结构中的节点表示什么？节点之间的关系是通过什么来表示的？

（2） 对于一个包含5个节点的有向图，使用Dijkstra算法计算从节点1到节点5的最短路径长度，并给出最短路径。给定的加权矩阵如下： 


03∞7∞
802∞∞
5∞01∞
2∞∞03
∞∞∞60



（3） 给定一个有10个节点和25条边的无向图，节点A的度为5。计算节点A的度中心度。

（4） 给定一个无向图，节点代表社交网络中的用户，边代表用户之间的好友关系。使用模块度计算公式来计算社区划分的模块度。假设我们有以下好友关系数据： 






假设我们已经通过社区发现算法得到了以下社区划分： 


社区1: A, B, C

社区2: D, E

使用上述模块度计算公式，计算该社区划分的模块度Q。

（5） 在社交媒体分析中，图网络社区发现是一种常用的技术，用于识别社交网络中的紧密相连的节点群体。这些社区可以帮助我们理解用户之间的互动模式，发现潜在的兴趣群体或者影响力传播网络。假设我们有以下好友关系数据： 


节点A: B,C,D

节点B: A,C,E

节点C: A,B,D,E

节点D: A,C,E,F

节点E: B,C,D,F

节点F: D,E

回答以下问题： 

① 构建网络的邻接矩阵。

② 使用社区发现算法(如GirvanNewman算法或模块度优化算法)来识别网络中的社区结构，并给出算法的主要步骤。

③ 描述算法的输出结果，包括社区的数量和每个社区的成员。

（6） 假设一个无向加权图的权重矩阵如下： 


W=012103230


计算其归一化拉普拉斯矩阵。

3. 思考题

（1） 银行用户之间通过相互交易从而产生一定的关系。把每一个银行账户看作一个节点，如果账户A向账户B汇款，那么就可以引出一条从节点A向节点B的边。如果账户B也向账户A汇款，那么也可以引出一条从节点B向节点A的边。如何将大规模的交易数据通过图网络的形式表现出来，并从中发现异常的交易模式和交易账户？

（2） GraphScope是一款开源的大规模图计算平台，能够用于解决实际生产场景中所涉及的图计算问题。试在GraphScope平台上搭建自己的社交网络分析环境，并对题3.1涉及的金融反欺诈问题进行分析。