《R语言数据挖掘》第十二章 R的网络分析初步

第十二章R的网络分析初步学习目标理论方面，掌握数据关系网络拓扑化表示的一般思路，掌握网络描述性分析的层次、角度和各种测度量的意义，适用性和应用场景。了解规则网络、小世界网络、无标度网络和随机网络的特点和联系实践方面，掌握R的复杂网络构建、分析和可视化实现、应用以及结果解读，能够正确运用复杂网络分析实际数据中的关系网络分析研究网络构成及网络成员间的相互影响，是揭示事物相关性的另一个独特视角网络分析的基本框架构建网络：网络由系统内部各成员（网络中称为节点）和成员之间的联系（网络中称为连接）构成网络的基本分析：通常按照个体层次、中间层次和全局层次，逐层递进展开。不同层次的分析服务于不同的研究目标网络的深入分析：将依据网络类型，从统计角度采用不同模型，对网络的静态特征和动态发展做进一步的分析和预测网络的定义表示及构建网络分析的基础是网络的定义及表示，通常有两种相互联系的表示方式：图论表示方式、矩阵表示方式图论表示方式：从图论角度看，网络由多个节点和节点间的连接（也称边）组成，是一种广义的图网络可记为G=(N,E)

。网络G中沿着连接在不同节点间的移动，称为游走依连接的方向性，网络分为无向网络和有向网络；依连接的类型，网络分为无权网络和加权网络。依节点类型，网络分为1-模网络和2-模网络图论表示方式：无向网络无向网络：网络中节点间的连接没有方向性涉及很多基本概念在网络G中，若存在节点沿连接“一步”游走回自身，则称网络G存在环在网络G中，若一对节点被两个以上的连接相连，则称网络G存在多边若网络G存在环或者多边，则称网络G为多重图。否则为简单图。网络的分析中，通常需将多重图简化为简单图后再研究图论表示方式：无向网络涉及很多基本概念若从网络G中的节点ni出发沿着连接游走可“抵达”节点nj，称为节点ni可达节点nj若从网络G中的任意节点ni出发沿着连接游走可达网络中其他任意节点nk，则称网络G是连通的若从网络G的某个节点开始沿着连接游走，能够返回同一节点，则称该网络G存在回路对于网络G中的一个连通子网络G’=(N’,E’)，若将G’之外的属于G的任意节点加到网络G’中，网络G’就不再具有连通性，则称G’为网络G的一个组件图论表示方式：无向网络涉及很多基本概念若网络G中任意节点ni和nk间均存在一个连接ej（直接相连），则称网络G是完备的，否则为非完备的图论表示：无向网络的R函数涉及很多R函数graph.formula(公式)graph.empty(n=N,directed=TRUE/FALSE)vcount(graph=网络类对象名)ecount(graph=网络类对象名)V(网络类对象名)E(网络类对象名)add.edges(网络类对象名,连接)k.regular.game(no.of.nodes=N,k=N－1,directed=FALSE/TRUE,multiple=FALSE/TRUE)simplify(graph=网络类对象名)plot(网络类对象名,layout=可视化方法名)is.connected(graph=网络类对象名)subcomponent(graph=网络类对象名,v=指定节点)图论表示方式：有向网络有向网络：网络中节点间的连接有方向性涉及很多基本概念互惠关系若从有向网络G中的任意节点ni出发沿有向连接ej游走，可“抵达”其他任意节点nk，则称有向网络G是强连通的若从有向网络G中的任意节点ni出发，忽略连接的方向性做无向游走，并可“抵达”其他任意节点nk，则称有向网络G是弱连通图论表示方式：有向网络涉及很多基本概念若有向网络G中存在有方向的回路，则称网络G中存在循环若有向网络G中不存在有方向的回路，无论是否存在回路，有向网络G均称为有向不循环图网络涉及很多R函数is.mutual(graph=网络类对象名)is.dag(graph=网络类对象名)图论表示：无权网络和加权网络无权网络：是在忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有相同的连接强度的无向或有向网络加权网络：是在不能忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有不同的连接强度的无向或有向网络无权网络是一种特殊的加权网络。若两节点间存在连接，权重等于1；若两节点间不存在连接，权重等于0无向加权网络分析是加权网络分析的重点R函数：is.weighted(graph=网络类对象名)图论表示：1-模网络和2-模网络模指网络中节点的类型若网络中所有节点均属于同一类型集合，该网络称为1-模网络若网络中节点分属两个不同的类型集合，该网络称为2-模网络图论表示：1-模网络和2-模网络R函数graph.full.bipartite(n1=n,n2=m,directed=TRUE/FALSE,mode=方向类型)graph.bipartite(types=节点类型逻辑向量,edges=连接,directed=TRUE/FALSE)网络的矩阵表示邻接矩阵：Y是一个N×N的方阵，反映网络中各节点间的连接情况。行号和列号为各节点的索引编码无向网络的邻接矩阵:若节点i

和节点j之间存在连接，则令矩阵中第i行第j列上的元素yij=1若节点i

和节点j之间不存在连接，则令矩阵元素yij=0有向网络的邻接矩阵：邻接矩阵Y的列号代表头节点索引编码，行号代表尾节点索引编码若节点i和节点j之间存在有向连接，则令矩阵元素yij=1若节点i和节点j之间不存在有向连接，则令矩阵元素yij=0有向图的邻接矩阵Y一般是非对称的网络的矩阵表示相关R函数get.adjacency(graph=网络类对象名,type=特征名,attr=属性名)关系矩阵表示关系矩阵也称隶属关系矩阵，用于反映2-模网络中各类节点间的连接情况设2-模网络中第一类节点个数为N1，第二类节点个数为节点N2。关系矩阵B是一个N1×N2的矩阵，通常不是方阵无向2-模网络的关系矩阵：矩阵B的行列分别为两类节点的索引编号有向2-模网络的关系矩阵：矩阵B列号代表头节点索引编码，行号代表尾节点索引编码相关R函数get.incidence(graph=网络类对象名)R建立网络对象利用邻接矩阵建立网络对象graph.adjacency(adjmatrix=邻接矩阵名,mode=网络类型名,weighted=TURE/NULL)示例利用关系矩阵建立2-模网络对象graph.incidence(incidence=关系矩阵名,directed=TRUE/FALSE,mode=方向类型,weighted=TURE/NULL)示例R建立网络对象利用连接列表建立网络对象get.data.frame(x=网络类对象名,what="edges")graph.data.frame(d=连接列表数据框,directed=TRUE/FALSE)示例R的网络可视化网络可视化的核心是以怎样的外观轮廓展示网络，尤其对较为庞大的网络更为如此合理安排网络外观轮廓的算法最小分割法：目的是最小化连接间的交叉数最小空间法：基于几何意义上的空间距离，令空间距离较近的节点摆放在相邻的位置上谱分解法：依据节点的特征向量中心度安排节点的位置树形/层次法：根据节点间的连接将节点安排成树形形状，或组织成层次图算法体现在plot函数的layout参数中网络节点重要性的测度节点重要性测度是网络基本分析的第一个层次，目的是刻画节点个体与其他节点有怎样“强度”的关系，发现网络中的重要节点节点在网络中的重要性一般表现第一，它是网络一个“局部范围”内的“中心”第二，它是一个具有强连接的“枢纽”涉及两个基本测度度测地线距离度和相关R函数节点ni的度：指节点ni有多少个与其直接连接的邻居节点无向网络：有向网络：入度、出度相关R函数degree(graph=网络类对象名,v=节点对象,mode=方向类型)graph.strength(graph=网络类对象名,vids=节点对象,mode=方向类型)测地线距离和相关R函数最短路径的距离，称为节点ni和nj间的测地线距离节点ni和nj间可能存在多条不同的最短路径有向网络需依方向游走，根据带方向的最短路径计算测地线距离可基于邻接矩阵计算得到若网络G具有连通性，网络中所有节点对测地线距离中的最大值，称为网络G的直径相关R函数：shortest.paths(graph=网络类对象名,v=起始节点对象,to=终止节点对象,mode=方向类型)diameter(graph=网络类对象名,directed=TRUE/FALSE,unconnected=TRUE/FALSE)节点“中心”作用的测度节点ni的点度中心度：为标准化度，度d(ni)与其最大可能度数之比无向网络：有向网络：点度中心度等于0：节点ni是个“孤立”点，不于其他任何节点相连，不可能是“局部范围”内的连接“中心”，重要性很低点度中心度越大说明节点ni越重要节点“中心”作用的测度节点ni的接近点度中心度接近点度中心度越大，说明节点ni与所有其他节点的测地线距离之和越小，越可能成为几何意义上的中心，节点ni越重要节点“中心”作用的测度相关R函数degree(graph=网络类对象名,v=节点对象,mode=方向类型,normalized=TRUE)closeness(graph=网络类对象名vids=节点对象,mode=方向类型,normalized=FALSE/TRUE)计算点度中心度和接近中心度的必要性探讨节点“枢纽”作用的测度中间中心度直观上，若节点ni是网络的连接“枢纽”，则一定有很多“线路”经过ni。可依“路线”的多少测度节点“枢纽”作用的高低中间中心度越大，表明必须经过节点ni的最短路径条数越多，节点ni的“枢纽”作用越强越重要标准化中间中心度：克服网络规模对中间中心度结果的影响节点“枢纽”作用的测度相关R函数betweenness(graph=网络类对象名,v=节点对象,normalized=FALSE/TRUE)edge.betweenness(graph=网络类对象名)，可计算连接的中间中心度节点重要性的其他方面结构洞一个系统（网络）中，若某个成员（节点）退出系统，使得局部系统中的其他成员（节点）间不再有任何联系（连接）。从结构上看就像局部网络中出现了一个关系断裂的“洞穴”，该成员称为一个结构洞关节点是那些若剔除网络将导致网络的组件数大大增加的节点。关节点不存在，网络将变成两个或多个互不连接的独立子网络或单个“孤立”节点。关节点在构成组件中起到了一个“中枢”作用相关R函数：articulation.points(graph=网络类对象名)节点重要性的其他方面特征向量中心度：节点重要性的测度量基本出发点是：如果节点ni较为重要，则节点ni应与其他重要节点有较多的连接相关R函数evcent(graph=网络类对象名,scale=TRUE/FALSE)节点重要性的其他方面PageRank得分是S.Brin和L.Page于1998年提出的度量网络节点重要性的测度得分，也称PageRank算法，是Google搜索算法的基础相关R函数page.rank(graph=网络类对象名,vids=网络节点,directed=TRUE,damping=0.85)网络子群构成特征研究子群分析是网络分析的第二个层次。它将研究范围从单个节点拓展到某些覆盖多个节点的局部区域。这些局部区域中节点间的关系更为密切或更特殊，成为相对独立的小群体，也称子群。子群类型二元关系，三元关系派系k-核子群分析的主要目标是基于子群类型，找到网络中包含的各种子群和数量，并借助子群特点和所体现的局部关系，细致刻画网络的结构组成特征二元关系和三元关系二元关系：通常针对有向网络而言，是有向网络中仅涉及两个节点的最小子群节点ni和nj间的二元关系有三种状态第一，yij=yji=1第二，yij=1且yji=0（或yij=0且yji=1第三，yij=yji=0网络中各种二元关系状态的数量称为二元关系普查量二元关系和三元关系三元关系：体现了关系的传递性和循环性二元关系和三元关系相关R函数dyad.census(graph=网络类对象名)triad.census(graph=网络类对象名)派系和k-核派系：若网络G中的一个组件G’是完备的，且不被其他的完备组件所包含，则称G’为网络G的一个派系派系是一个局部意义上的最大完备子网络相关R函数maximal.cliques(graph=网络类对象名,min=n1,max=n2)largest.cliques(graph=网络类对象名)派系和k-核k-核：派系若G’是网络G的一个最大连通性子图，且G’中的每个节点均至少与其他k个节点直接连接，即G’中每个节点的度均大于等于k，则称G’是网络G的一个k-核节点ni的核等于m如果它属于m-核但不属于(m＋1)-核只要节点ni不是“孤立”点，它至少是一个1-核成员，也可能属于更大的核相关R函数graph.coreness(graph=网络类对象名,mode=方向类型)社区和组件社区也称模块：是一个子网络，特点是子网络内部各结点的连接相对紧密，子网络之间的连接相对稀疏社区结构划分算法基于划分的方法模块度方法随机游走方法密度子图方法模块度相关R函数社区和组件组件作为最大连通性子网络，其凝聚程度可能低于派系等，但因“对外”没有连接而具有强独立性相关R函数clusters(graph=网络类对象名,mode=组件类型)decompose.graph(graph=网络类对象名,mode=组件类型)网络整体特征刻画网络整体特征的刻画是网络分析的最高层次，目的是从全局角度揭示网络的整体样貌。一般有两种方式：第一，利用关于网络整体特征的测度第二，通过各种分布刻画网络整体特征的测度主要有网络密度平均测地线距离网络聚类系数谱半径网络密度网络密度是网络分析中常用的一种度量全局网络特征的测度量从连接个数的角度测度网络节点间的密集程度当网络节点个数N确定后，节点之间的连接线越多，表明该图的密度越大相关R函数graph.density(graph=网络类对象名)平均测地线距离平均测地线距离也是刻画网络整体特征的常用测度从几何距离的角度测度节点连接的紧密程度，有与网络直径类似的意义，但更具稳健性平均测地线距离是各个节点测地线距离的均值该值越大表明网络整体的“覆盖”区域越大，网络节点连接的密集程度较低。反之，网络节点连接的密集程度较高相关R函数average.path.length(graph=网络类对象名,directed=TRUE/FALSE)网络聚类系数节点ni聚类系数用于测度节点ni的聚类能力网络聚类系数可定义为所有节点聚类系数的简单平均还可定义为以节点连接三方组频率为权重的节点聚类系数的加权平均相关R函数transitivity(graph=网络类对象名,type=类型名)谱半径网络的谱半径也是度量网络整体连接程度的测度量谱半径是网络邻接矩阵Y的最大非零特征值谱半径在兼顾拓扑结构的基础上测度网络的整体连接程度，更适用于不同网络间的对比谱半径越大，网络的整体连接程度越高相关R函数evcent(graph=网络类对象名,scale=TRUE/FALSE)网络特征的各种分布和度量刻画网络整体特征更细致的方式是分布，如：网络的节点度分布、点度中心度分布、中间中心度分布、测度线距离分布，等网络分析中研究最多的分布是度分布度分布特征的度量度的熵度的熵越大，度取值的平均不确定性越大，反之，度取值的平均不确定性越小网络分析中，度的熵也称为网络熵相关R函数entropy(y=频数分布,method="ML",unit="log2")主要网络类型及特点网络科学研究中，依据度分布将众多网络划分成四种类型：规则网络小世界网络无标度网络随机网络不同网络类型的主要差异在于：网络中任意两个节点ni和nj间具有连接是确定性的还是是随机性的确定性和随机性的不同程度的混合规则网络及特点规则网络是指网络中任意两个节点ni和nj间具有连接是确定性的连接的规律性导致规则网络的拓扑结构往往具有特定的“形态”k-规则网络：典型的规则网络所谓k-规则网络是指网络中的每个节点均与k（k≤N－1,N为节点个数）个节点存在直接连接的网络规则网络及特点星形网络：规则网络有N－1个节点均与剩下的一个节点ni直接相连，它们的节点度均等于1，节点ni的度等于N－1平衡2-叉树网络：规则网络除叶节点之外，每个节点都有两个子节点，共有N－1条连接。根节点的度等于2，叶节点的度等于1，其余节点的度都等于3，节点度只可能取1,2,3相关R函数graph.stargraph.tree随机网络及特点大规模随机网络的最大特点节点的度分布服从泊松分布网络熵随网络密度的增加呈非线性变化网络密度为0.5的随机网络具有最大的网络熵将包含N个节点和E条连接的随机网络看做是，包含N个节点的空网络随时间t=0,1,2,…,E推移逐步演变的结果。每个时刻t均在上个时刻t－1的基础上随机挑选一对节点并在其间增加一条连接，经过E步直到添加E条连接为止该规则是E.N.Gilbert提出的，网络称为Gilbert随机网络相关R函数erdos.renyi.game(n=节点数,p.or.m=概率或连接数,type=类型名)随机网络及特点随机网络的熵网络密度在较高水平或者较低水平时，网络熵快速下降至0。随机网络并不具有随机性，