02-社会网络分析与算法研究35316

《02-社会网络分析与算法研究35316》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、社会网络分析与算法研究 第二章网络的表示：图论与矩阵论234图的基本概念无向图————有向图加权图————无权图无权图可以看成每条边的权值均为1的等权图567邻边：从同一个节点伸向其他不同节点的边邻点：同一条边的两个端点互称关联：一条边上的节点和该条边的关系简单图：不存在重边和自环的图复图：存在重边或自环的图完全图：所有节点对（对于有向图是指起点终点对）之间均有一条边连接的简单图N阶无向完全图有N（N－1）/2条边N阶有向完全图有N（N－1）条边8路径、简单路径、基本路径图G中的第k条路径（

2、链、途径）是指由图中的节点和边交替出现而构成的有限序列wvkn=()01122evevve−1nvn路径   wk的起点：v0路径wk的终点：vn路径   wk的内点：其余节点vini(1≤≤−1)路径   wk长：序列中边的条数由于简单图中不存在重边，所以简单图中的第k条路径可以完全由经过的节点序列表示，所以  wk可简记为wv=()vvvv9kn012−1n。92.连通性连通图：图G中任意每对vi、vj节点之间都有至少一条路径存在。非连通图：图G中至少有一对节点之间不存在路径。图G的一

3、个连通分支：若G中的任意两个节点属于且仅属于节点子集Vi时才连通，则称图G中由Vi及其连边组成的子图Gi仅是G的一个连通分支。Ω常被用于表示图G的分支数ω=1的图称为连通图ω>1的图称为非连通图对于任何图G，节点数N、边数M和分支数ω满足MNw≥−10在有向图中，图的连通性被分为三种：弱连通、单连通和强连通。有向图的底图：将有向图的所有边去除方向性所得到的无向图弱连通有向图：底图是连通图的有向图单连通有向图：在一个有向图中，任意两个节点vi、vj，若只存在vi到vj或者vj到vi路径

4、强连通有向图：若vi、vj之间存在可互达的路径从节点vi到vj的距离：从vi到vj的路径中需要经历的最少边数图G的直径：所有节点对的距离中的最大的距离11假设图G=（V，E）是一个简单图，，vV∈eE∈。割点：若去除节点v，使原来连通的图变成不连通或分支数有增加，即ω（G－v）＞ω（G）割边（桥）：若去除边e（但不去除端点）后，使图G变为不连通或使得ω（G－e）＞ω（G）块：不含割点的连通图（连通分支）图G的块：图G的不含割点的最大连通分支上述讨论的连通性、割点、割边及块的概念均与图中

5、边的方向性无关。在研究这些性质时，所有的图均看作无向图。1213图的矩阵表示 图的矩阵表示架起了图论与矩阵论之间的桥梁，通过这种表示方法就能借助于矩阵的理论和分析方法来研究图论中的问题。1.邻接矩阵邻接矩阵描述了节点与节点之间的邻接关系，通常会用一个方阵A来表示，方阵中的元素用   aij表示。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。一个无权简单图的邻接矩阵                Aa={ij}可以定义为NN×1,(,vv)∈Eija=ij0,(,vv)∉Eij1415

6、对于一个N阶简单无向图G，其邻接矩阵具有以下性质：①A是一个主对角线上的元素皆为0，其余元素为0或1的对角矩阵，且A的任何一行（列）的元素之和都等于其相应节点的度。2②若记                     CAc=={ij}，则矩阵C的主对角线上的元素为NN×NNN2caii====∑∑∑ijaaajiijijkijj==11j=1可见对角线元素    cii恰好为相应节点   vi的度    k。ik③对于任意非负整数k，  A中的第i行第j列元素表示图G中连接节点   vi和   vj的

7、长度为k的路径的数目。16对于一个N阶简单有向图G，其邻接矩阵具有以下性质：voutv①第i行元素之和为节点  i的出度ki（以节点  i为起点的邻vinv边数），其第j列元素之和为节点  i的入度ki（以节点   i为终点的邻边数）。TT②若记                        AA==C{cij}，其中    A表示矩阵A的转置矩阵，则           NN×Ncaij=∑ilajll=1表示图G中的某种节点个数，这种节点的邻边中有两条邻边分别以   vi和   vj为起点。N

8、T③若记                     AAF=={fij}NN×，则              faij=∑lilja表示图G中的某种节点l=1个数，这种节点的邻边中有两条邻边分别以   vi和   vj为终点。17一个加权简单图的邻接矩阵            Aa={ij}可以定义为NN×ωij,(,)vvij∈Ea=ij0(或∞∉,vv,)Eij其中，  ωij表示边          evij=(,)ivj上的权值（即边权），在相似权含