复杂网络分析初步R语言数据挖掘方法及应用课件

R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用案例说明广义上讲，任何事物都处在一个有形或无形的网络当广义上讲，任何事物都处在一个有形或无形的网络当中，与网络中的其他事物形成一种相互依存或竞争关中，与网络中的其他事物形成一种相互依存或竞争关系系多个国家之间构成具有进出口贸易往来关系的贸易网络；多个国家之间构成具有进出口贸易往来关系的贸易网络；企业内部多个部门之间构成具有协同合作关系的协同网络；企业内部多个部门之间构成具有协同合作关系的协同网络；互联网社区中多个个体之间构成具有信息共享交换、舆论互联网社区中多个个体之间构成具有信息共享交换、舆论传播互动关系的社交网络；多名学者之间构成具有成果引传播互动关系的社交网络；多名学者之间构成具有成果引用和被引用关系的合作研究网络；多只股票之间构成具有用和被引用关系的合作研究网络；多只股票之间构成具有价格波动影响关系的收益联动网络；多种商品之间构成的价格波动影响关系的收益联动网络；多种商品之间构成的具有连带销售关系的交叉购买网络；多部电影、多个影星、具有连带销售关系的交叉购买网络；多部电影、多个影星、众多影迷之间构成具有参演和不参演、喜爱和不喜爱等多众多影迷之间构成具有参演和不参演、喜爱和不喜爱等多种关系的娱乐网络，等等种关系的娱乐网络，等等案例说明广义上讲，任何事物都处在一个有形或无形的网络当中，与R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络分析n研究网络构成及网络成员间的相互影响，是揭示事物研究网络构成及网络成员间的相互影响，是揭示事物相关性的另一个独特视角相关性的另一个独特视角n网络分析的基本框架网络分析的基本框架n构建网络：网络由系统内部各成员（网络中称为节构建网络：网络由系统内部各成员（网络中称为节点）和成员之间的联系（网络中称为连接）构成点）和成员之间的联系（网络中称为连接）构成n网络的基本分析：通常按照个体层次、中间层次和网络的基本分析：通常按照个体层次、中间层次和全局层次，逐层递进展开。不同层次的分析服务于全局层次，逐层递进展开。不同层次的分析服务于不同的研究目标不同的研究目标n网络的深入分析：将依据网络类型，从统计角度采网络的深入分析：将依据网络类型，从统计角度采用不同模型，对网络的静态特征和动态发展做进一用不同模型，对网络的静态特征和动态发展做进一步的分析和预测步的分析和预测网络分析研究网络构成及网络成员间的相互影响，是揭示事物相关性R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的定义表示及构建n网络分析的基础是网络的定义及表示，通常有两种相网络分析的基础是网络的定义及表示，通常有两种相互联系的表示方式：图论表示方式、矩阵表示方式互联系的表示方式：图论表示方式、矩阵表示方式n图论表示方式：从图论角度看，网络由多个节点和节图论表示方式：从图论角度看，网络由多个节点和节点间的连接（也称边）组成，是一种广义的图点间的连接（也称边）组成，是一种广义的图n网络可记为网络可记为G=(N,E)。网络。网络G中沿着连接在不同节中沿着连接在不同节点间的移动，称为游走点间的移动，称为游走n依连接的方向性，网络分为无向网络和有向网络；依连接的方向性，网络分为无向网络和有向网络；依连接的类型，网络分为无权网络和加权网络。依依连接的类型，网络分为无权网络和加权网络。依节点类型，网络分为节点类型，网络分为1-1-模网络和模网络和2-2-模网络模网络网络的定义表示及构建网络分析的基础是网络的定义及表示，通常有R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：无向网络n无向网络：网络中节点间的连接没有方向性无向网络：网络中节点间的连接没有方向性n涉及很多基本概念涉及很多基本概念n在网络在网络G G中，若存在节点沿连接中，若存在节点沿连接“一步一步”游走回自游走回自身，则称网络身，则称网络G G存在环存在环n在网络在网络G G中，若一对节点被两个以上的连接相连，中，若一对节点被两个以上的连接相连，则称网络则称网络G G存在多边存在多边n若网络若网络G G存在环或者多边，则称网络存在环或者多边，则称网络G G为多重图。否为多重图。否则为简单图。网络的分析中，通常需将多重图简化则为简单图。网络的分析中，通常需将多重图简化为简单图后再研究为简单图后再研究图论表示方式：无向网络无向网络：网络中节点间的连接没有方向性R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：无向网络n涉及很多基本概念涉及很多基本概念n若从网络若从网络G中的节点中的节点ni出发沿着连接游走可出发沿着连接游走可“抵达抵达”节点节点nj，称为节点，称为节点ni可达节点可达节点njn若从网络若从网络G中的任意节点中的任意节点ni出发沿着连接游走可达出发沿着连接游走可达网络中其他任意节点网络中其他任意节点nk，则称网络，则称网络G 是连通的是连通的n若从网络若从网络G的某个节点开始沿着连接游走，能够返的某个节点开始沿着连接游走，能够返回同一节点，则称该网络回同一节点，则称该网络G存在回路存在回路n对于网络对于网络G中的一个连通子网络中的一个连通子网络G=(N,E)，若将若将G之外的属于之外的属于G的任意节点加到网络的任意节点加到网络G中，网络中，网络G就不再具有连通性，则称就不再具有连通性，则称G为网络为网络G的一个组件的一个组件图论表示方式：无向网络涉及很多基本概念R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：无向网络n涉及很多基本概念涉及很多基本概念n若网络若网络G中任意节点中任意节点ni和和nk间均存在一个连接间均存在一个连接ej（直（直接相连），则称网络接相连），则称网络G是完备的，否则为非完备的是完备的，否则为非完备的图论表示方式：无向网络涉及很多基本概念R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：无向网络的R函数n涉及很多涉及很多R R函数函数ngraph.formula(graph.formula(公式公式)ngraph.empty(n=N,directegraph.empty(n=N,directed=TRUE/FALSE)d=TRUE/FALSE)nvcount(graph=vcount(graph=网络类对象网络类对象名名)necount(graph=ecount(graph=网络类对象网络类对象名名)nV(V(网络类对象名网络类对象名)nE(E(网络类对象名网络类对象名)nadd.edges(add.edges(网络类对象名网络类对象名,连接连接)nk.regular.game(no.of.nodek.regular.game(no.of.nodes=N,k=Ns=N,k=N1,directed=FALSE/TRUE,mul1,directed=FALSE/TRUE,multiple=FALSE/TRUE)tiple=FALSE/TRUE)nsimplify(graph=simplify(graph=网络类对象网络类对象名名)nplot(plot(网络类对象名网络类对象名,layout=,layout=可视化方法名可视化方法名)nis.connected(graph=is.connected(graph=网络网络类对象名类对象名)nsubcomponent(graph=subcomponent(graph=网络类网络类对象名对象名,v=,v=指定节点指定节点)图论表示：无向网络的R函数涉及很多R函数k.regular.R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：有向网络n有向网络：网络中节点间的连接有方向性有向网络：网络中节点间的连接有方向性n涉及很多基本概念涉及很多基本概念n互惠关系互惠关系n若从有向网络若从有向网络G中的任意节点中的任意节点ni出发沿有向连接出发沿有向连接ej游游走，可走，可“抵达抵达”其他任意节点其他任意节点nk，则称有向网络，则称有向网络G是强连通的是强连通的n若从有向网络若从有向网络G中的任意节点中的任意节点ni出发，忽略连接的出发，忽略连接的方向性做无向游走，并可方向性做无向游走，并可“抵达抵达”其他任意节点其他任意节点nk，则称有向网络，则称有向网络G是弱连通是弱连通图论表示方式：有向网络有向网络：网络中节点间的连接有方向性R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：有向网络n涉及很多基本概念涉及很多基本概念n若有向网络若有向网络G中存在有方向的回路，则称网络中存在有方向的回路，则称网络G中存在循环中存在循环n若有向网络若有向网络G中不存在有方向的回路，无论是否存在回路，中不存在有方向的回路，无论是否存在回路，有向网络有向网络G均称为有向不循环图网络均称为有向不循环图网络n涉及很多涉及很多R R函数函数nis.mutual(graph=is.mutual(graph=网络类对象网络类对象名名)nis.dag(graph=is.dag(graph=网络类对象名网络类对象名)图论表示方式：有向网络涉及很多基本概念涉及很多R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：无权网络和加权网络n无权网络：是在忽略网络中不同节点间关系强弱差异无权网络：是在忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有相同的连接强度的无向或性的前提下，各节点连接有相同的连接强度的无向或有向网络有向网络n加权网络：是在不能忽略网络中不同节点间关系强弱加权网络：是在不能忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有不同的连接强度的无差异性的前提下，各节点连接有不同的连接强度的无向或有向网络向或有向网络n无权网络是一种特殊的加权网络。若两节点间存在连无权网络是一种特殊的加权网络。若两节点间存在连接，权重等于接，权重等于1 1；若两节点间不存在连接，权重等于；若两节点间不存在连接，权重等于0 0n无向加权网络分析是加权网络分析的重点无向加权网络分析是加权网络分析的重点nR R函数：函数：is.weighted(graph=is.weighted(graph=网络类对象名网络类对象名)图论表示：无权网络和加权网络无权网络：是在忽略网络中不同节点R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：1-模网络和2-模网络nR R函数函数ngraph.full.bipartite(n1=n,n2=m,directed=TRUEgraph.full.bipartite(n1=n,n2=m,directed=TRUE/FALSE,mode=/FALSE,mode=方向类型方向类型)ngraph.bipartite(types=graph.bipartite(types=节点类型逻辑向量节点类型逻辑向量,edges=edges=连接连接,directed=TRUE/FALSE),directed=TRUE/FALSE)图论表示：1-模网络和2-模网络R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：1-模网络和2-模网络n模指网络中节点的类型模指网络中节点的类型n若网络中所有节点均属于同一类型集合，该网络称若网络中所有节点均属于同一类型集合，该网络称为为1-1-模网络模网络n若网络中节点分属两个不同的类型集合，该网络称若网络中节点分属两个不同的类型集合，该网络称为为2-2-模网络模网络图论表示：1-模网络和2-模网络模指网络中节点的类型R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的矩阵表示n邻接矩阵：邻接矩阵：Y Y是一个是一个N NN N的方阵，反映网络中各节点的方阵，反映网络中各节点间的连接情况。行号和列号为各节点的索引编码间的连接情况。行号和列号为各节点的索引编码n无向网络的邻接矩阵无向网络的邻接矩阵:n若节点若节点i 和节点和节点j之间存在连接，则令矩阵中第之间存在连接，则令矩阵中第i行第行第j列上的列上的元素元素yij=1n若节点若节点i 和节点和节点j之间不存在连接，则令矩阵元素之间不存在连接，则令矩阵元素yij=0n有向网络的邻接矩阵：邻接矩阵有向网络的邻接矩阵：邻接矩阵Y Y的列号代表头节点的列号代表头节点索引编码，行号代表尾节点索引编码索引编码，行号代表尾节点索引编码n若节点若节点i和节点和节点j之间存在有向连接，则令矩阵元素之间存在有向连接，则令矩阵元素yij=1n若节点若节点i和节点和节点j之间不存在有向连接，则令矩阵元素之间不存在有向连接，则令矩阵元素yij=0n有向图的邻接矩阵有向图的邻接矩阵Y Y一般是非对称的一般是非对称的网络的矩阵表示邻接矩阵：Y是一个NN的方阵，反映网络中各节R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的矩阵表示n相关相关R R函数函数nget.adjacency(graph=get.adjacency(graph=网络类对象名网络类对象名,type=,type=特征名特征名,attr=,attr=属性名属性名)网络的矩阵表示相关R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用关系矩阵表示n关系矩阵也称隶属关系矩阵，用于反映关系矩阵也称隶属关系矩阵，用于反映2-2-模网络中各模网络中各类节点间的连接情况类节点间的连接情况n设设2-模网络中第一类节点个数为模网络中第一类节点个数为N1，第二类节点个数为节点，第二类节点个数为节点N2。关系矩阵。关系矩阵B是一个是一个N1N2的矩阵，通常不是方阵的矩阵，通常不是方阵n无向无向2-2-模网络的关系矩阵：矩阵模网络的关系矩阵：矩阵B的的行列分别为两类行列分别为两类节点的索引编号节点的索引编号n有向有向2-2-模网络的关系矩阵：矩阵模网络的关系矩阵：矩阵B B列号代表头节点索列号代表头节点索引编码，行号代表尾节点索引编码引编码，行号代表尾节点索引编码n相关相关R R函数函数nget.incidence(graph=get.incidence(graph=网络类对象名网络类对象名)关系矩阵表示关系矩阵也称隶属关系矩阵，用于反映2-模网络中各R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R建立网络对象n利用邻接矩阵建立网络对象利用邻接矩阵建立网络对象ngraph.adjacency(adjmatrix=graph.adjacency(adjmatrix=邻接矩阵名邻接矩阵名,mode=,mode=网络类型网络类型名名,weighted=TURE/NULL),weighted=TURE/NULL)n示例示例n利用关系矩阵建立利用关系矩阵建立2-2-模网络对象模网络对象ngraph.incidence(incidence=graph.incidence(incidence=关系矩阵名关系矩阵名,directed=TRUE/FALSE,mode=,directed=TRUE/FALSE,mode=方向类型方向类型,weighted=TURE/NULL),weighted=TURE/NULL)n示例示例R建立网络对象利用邻接矩阵建立网络对象R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R建立网络对象n利用连接列表建立网络对象利用连接列表建立网络对象nget.data.frame(x=get.data.frame(x=网络类对象名网络类对象名,what=edges),what=edges)ngraph.data.frame(d=graph.data.frame(d=连接列表数据框连接列表数据框,directed=TRUE/FALSE)directed=TRUE/FALSE)n示例示例R建立网络对象利用连接列表建立网络对象R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R的网络可视化n网络可视化的核心是以怎样的外观轮廓展示网络，尤网络可视化的核心是以怎样的外观轮廓展示网络，尤其对较为庞大的网络更为如此其对较为庞大的网络更为如此n合理安排网络外观轮廓的算法合理安排网络外观轮廓的算法n最小分割法：目的是最小化连接间的交叉数最小分割法：目的是最小化连接间的交叉数n最小空间法：基于几何意义上的空间距离，令空间距离较最小空间法：基于几何意义上的空间距离，令空间距离较近的节点摆放在相邻的位置上近的节点摆放在相邻的位置上n谱分解法：依据节点的特征向量中心度安排节点的位置谱分解法：依据节点的特征向量中心度安排节点的位置n树形树形/层次法：根据节点间的连接将节点安排成树形形状，层次法：根据节点间的连接将节点安排成树形形状，或组织成层次图或组织成层次图n算法体现在算法体现在plotplot函数的函数的layoutlayout参数中参数中R的网络可视化网络可视化的核心是以怎样的外观轮廓展示网络，尤R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络节点重要性的测度n节点重要性测度是网络基本分析的第一个层次，目的节点重要性测度是网络基本分析的第一个层次，目的是刻画节点个体与其他节点有怎样是刻画节点个体与其他节点有怎样“强度强度”的关系，的关系，发现网络中的重要节点发现网络中的重要节点n节点在网络中的重要性一般表现节点在网络中的重要性一般表现n第一，它是网络一个第一，它是网络一个“局部范围局部范围”内的内的“中心中心”n第二，它是一个具有强连接的第二，它是一个具有强连接的“枢纽枢纽”n涉及两个基本测度涉及两个基本测度n度度n测地线距离测地线距离网络节点重要性的测度节点重要性测度是网络基本分析的第一个层次R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用度和相关R函数n节点节点ni的度：指节点的度：指节点ni有多少个与其直接连接的邻居有多少个与其直接连接的邻居节点节点n无向网络：无向网络：n有向网络：入度、出度有向网络：入度、出度n相关相关R R函数函数ndegree(graph=degree(graph=网络类对象名网络类对象名,v=,v=节点对象节点对象,mode=,mode=方向类方向类型型)ngraph.strength(graph=graph.strength(graph=网络类对象名网络类对象名,vids=,vids=节点对象节点对象,mode=mode=方向类型方向类型)度和相关R函数节点ni的度：指节点ni有多少个与其直接连接的R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用测地线距离和相关R函数n最短路径的距离，称为节点最短路径的距离，称为节点ni和和nj间的测地线距离间的测地线距离n节点节点ni和和nj间可能存在多条不同的最短路径间可能存在多条不同的最短路径n有向网络需依方向游走，根据带方向的最短路径计算有向网络需依方向游走，根据带方向的最短路径计算n测地线距离可基于邻接矩阵计算得到测地线距离可基于邻接矩阵计算得到n若网络若网络G G具有连通性，网络中所有节点对测地线距离具有连通性，网络中所有节点对测地线距离中的最大值，称为网络中的最大值，称为网络G G的直径的直径n相关相关R R函数：函数：nshortest.paths(graph=shortest.paths(graph=网络类对象名网络类对象名,v=,v=起始节点对象起始节点对象,to=to=终止节点对象终止节点对象,mode=,mode=方向类型方向类型)ndiameter(graph=diameter(graph=网络类对象名网络类对象名,directed=TRUE/FALSE,unconnected=TRUE/FALSE),directed=TRUE/FALSE,unconnected=TRUE/FALSE)测地线距离和相关R函数最短路径的距离，称为节点ni和nj间的R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n节点节点ni的点度中心度：为标准化度，度的点度中心度：为标准化度，度d(ni)与其最大与其最大可能度数之比可能度数之比n无向网络：无向网络：n有向网络：有向网络：n点度中心度等于点度中心度等于0 0：节点：节点ni是个是个“孤立孤立”点，不于点，不于其他任何节点相连，不可能是其他任何节点相连，不可能是“局部范围局部范围”内的连内的连接接“中心中心”，重要性很低，重要性很低n点度中心度越大说明节点点度中心度越大说明节点ni越重要越重要节点“中心”作用的测度节点ni的点度中心度：为标准化度，度dR R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n节点节点ni的接近点度中心度的接近点度中心度n接近点度中心度越大，说明节点接近点度中心度越大，说明节点ni与所有其他节点的与所有其他节点的测地线距离之和越小，越可能成为几何意义上的中心，测地线距离之和越小，越可能成为几何意义上的中心，节点节点ni越重要越重要节点“中心”作用的测度节点ni的接近点度中心度R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n相关相关R R函数函数ndegree(graph=degree(graph=网络类对象名网络类对象名,v=,v=节点对象节点对象,mode=,mode=方向类方向类型型,normalized=TRUE),normalized=TRUE)ncloseness(graph=closeness(graph=网络类对象名网络类对象名vids=vids=节点对象节点对象,mode=,mode=方方向类型向类型,normalized=FALSE/TRUE),normalized=FALSE/TRUE)n计算点度中心度和接近中心度的必要性探讨计算点度中心度和接近中心度的必要性探讨节点“中心”作用的测度相关R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“枢纽”作用的测度n中间中心度中间中心度n直观上，若节点直观上，若节点ni是网络的连接是网络的连接“枢纽枢纽”，则一定有很多，则一定有很多“线路线路”经过经过ni。可依。可依“路线路线”的多少测度节点的多少测度节点“枢纽枢纽”作用作用的高低的高低n中间中心度越大，表明必须经过节点中间中心度越大，表明必须经过节点ni的最短路径条数的最短路径条数越多，节点越多，节点ni的的“枢纽枢纽”作用越强越重要作用越强越重要n标准化中间中心度：克服网络规模对中间中心度结果的标准化中间中心度：克服网络规模对中间中心度结果的影响影响节点“枢纽”作用的测度中间中心度R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“枢纽”作用的测度n相关相关R R函数函数nbetweenness(graph=betweenness(graph=网络类对象名网络类对象名,v=,v=节点对象节点对象,normalized=FALSE/TRUE)normalized=FALSE/TRUE)nedge.betweenness(graph=edge.betweenness(graph=网络类对象名网络类对象名)，可计算连接的，可计算连接的中间中心度中间中心度节点“枢纽”作用的测度相关R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面n结构洞结构洞n一个系统（网络）中，若某个成员（节点）退出系统，使一个系统（网络）中，若某个成员（节点）退出系统，使得局部系统中的其他成员（节点）间不再有任何联系（连得局部系统中的其他成员（节点）间不再有任何联系（连接）。从结构上看就像局部网络中出现了一个关系断裂的接）。从结构上看就像局部网络中出现了一个关系断裂的“洞穴洞穴”，该成员称为一个结构洞，该成员称为一个结构洞n关节点关节点n是那些若剔除网络将导致网络的组件数大大增加的节点。是那些若剔除网络将导致网络的组件数大大增加的节点。关节点不存在，网络将变成两个或多个互不连接的独立子关节点不存在，网络将变成两个或多个互不连接的独立子网络或单个网络或单个“孤立孤立”节点。关节点在构成组件中起到了一节点。关节点在构成组件中起到了一个个“中枢中枢”作用作用n相关相关R R函数：函数：articulation.points(graph=articulation.points(graph=网络类对象名网络类对象名)节点重要性的其他方面结构洞R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面n特征向量中心度：节点重要性的测度量特征向量中心度：节点重要性的测度量n基本出发点是：如果节点基本出发点是：如果节点ni较为重要，则节点较为重要，则节点ni应应与其他重要节点有较多的连接与其他重要节点有较多的连接n相关相关R R函数函数nevcent(graph=evcent(graph=网络类对象名网络类对象名,scale=TRUE/FALSE),scale=TRUE/FALSE)节点重要性的其他方面特征向量中心度：节点重要性的测度量R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面nPageRankPageRank得分得分n是是S.BrinS.Brin和和L.PageL.Page于于19981998年提出的度量网络节点年提出的度量网络节点重要性的测度得分，也称重要性的测度得分，也称PageRankPageRank算法，是算法，是GoogleGoogle搜索算法的基础搜索算法的基础n相关相关R R函数函数npage.rank(graph=page.rank(graph=网络类对象名网络类对象名,vids=,vids=网络节点网络节点,directed=TRUE,damping=0.85)directed=TRUE,damping=0.85)节点重要性的其他方面PageRank得分R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络子群构成特征研究n子群分析是网络分析的第二个层次。它将研究范围从子群分析是网络分析的第二个层次。它将研究范围从单个节点拓展到某些覆盖多个节点的局部区域。这些单个节点拓展到某些覆盖多个节点的局部区域。这些局部区域中节点间的关系更为密切或更特殊，成为相局部区域中节点间的关系更为密切或更特殊，成为相对独立的小群体，也称子群。子群类型对独立的小群体，也称子群。子群类型n二元关系，三元关系二元关系，三元关系n派系派系nk-k-核核n子群分析的主要目标是基于子群类型，找到网络中包子群分析的主要目标是基于子群类型，找到网络中包含的各种子群和数量，并借助子群特点和所体现的局含的各种子群和数量，并借助子群特点和所体现的局部关系，细致刻画网络的结构组成特征部关系，细致刻画网络的结构组成特征网络子群构成特征研究子群分析是网络分析的第二个层次。它将研究R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用二元关系和三元关系n二元关系：通常针对有向网络而言，是有向网络中仅二元关系：通常针对有向网络而言，是有向网络中仅涉及两个节点的最小子群涉及两个节点的最小子群n节点节点ni和和nj间的二元关系有三种状态间的二元关系有三种状态n第一，第一，yij=yji=1n第二，第二，yij=1且且yji=0（或或yij=0且且yji=1n第三第三，yij=yji=0n网络中各种二元关系状态的数量称为二元关系网络中各种二元关系状态的数量称为二元关系普查量普查量二元关系和三元关系二元关系：通常针对有向网络而言，是有向网络R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用二元关系和三元关系n三元关系：体现了关系的传递性和循环性三元关系：体现了关系的传递性和循环性二元关系和三元关系三元关系：体现了关系的传递性和循环性R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用二元关系和三元关系n相关相关R R函数函数ndyad.census(graph=dyad.census(graph=网络类对象名网络类对象名)ntriad.census(graph=triad.census(graph=网络类对象名网络类对象名)二元关系和三元关系相关R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用派系和k-核n派系：若网络派系：若网络G中的一个组件中的一个组件G是完备的，且不被其是完备的，且不被其他的完备组件所包含，则称他的完备组件所包含，则称G为网络为网络G的一个派系的一个派系n派系是一个局部意义上的最大完备子网络派系是一个局部意义上的最大完备子网络n相关相关R R函数函数nmaximal.cliques(graph=maximal.cliques(graph=网络类对象名网络类对象名,min=n1,max=,min=n1,max=n2)n2)nlargest.cliques(graph=largest.cliques(graph=网络类对象名网络类对象名)派系和k-核派系：若网络G中的一个组件G是完备的，且不被其R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用派系和k-核nk-核：派系若核：派系若G是网络是网络G的一个最大连通性子图的一个最大连通性子图，且且G中的每个节点均至少与其他中的每个节点均至少与其他k个节点直接连接，即个节点直接连接，即G中每个节点的度均大于等于中每个节点的度均大于等于k，则称则称G是网络是网络G的一的一个个k-核核n节点节点ni的核等于的核等于m如果它属于如果它属于m-核但不属于核但不属于(m1)-核核n只要节点只要节点ni不是不是“孤立孤立”点，它至少是一个点，它至少是一个1-核成员，核成员，也可能属于更大的核也可能属于更大的核n相关相关R R函数函数ngraph.coreness(graph=graph.coreness(graph=网络类对象名网络类对象名,mode=,mode=方向类型方向类型)派系和k-核k-核：派系若G是网络G的一个最大连通性子图，R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用社区和组件n社区也称模块：是一个子网络，特点是子网络内部各社区也称模块：是一个子网络，特点是子网络内部各结点的连接相对紧密，子网络之间的连接相对稀疏结点的连接相对紧密，子网络之间的连接相对稀疏n社区结构划分算法社区结构划分算法n基于划分的方法基于划分的方法n模块度方法模块度方法n随机游走方法随机游走方法n密度子图方法密度子图方法n模块度模块度n相关相关R R函数函数社区和组件社区也称模块：是一个子网络，特点是子网络内部各结点R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用社区和组件n组件作为最大连通性子网络，其凝聚程度可能低于派组件作为最大连通性子网络，其凝聚程度可能低于派系等，但因系等，但因“对外对外”没有连接而具有强独立性没有连接而具有强独立性n相关相关R R函数函数nclusters(graph=clusters(graph=网络类对象名网络类对象名,mode=,mode=组件类型组件类型)ndecompose.graph(graph=decompose.graph(graph=网络类对象名网络类对象名,mode=,mode=组件类型组件类型)社区和组件组件作为最大连通性子网络，其凝聚程度可能低于派系等R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络整体特征刻画n网络整体特征的刻画是网络分析的最高层次，目的是网络整体特征的刻画是网络分析的最高层次，目的是从全局角度揭示网络的整体样貌。一般有两种方式：从全局角度揭示网络的整体样貌。一般有两种方式：n第一，利用关于网络整体特征的测度第一，利用关于网络整体特征的测度n第二，通过各种分布刻画第二，通过各种分布刻画n网络整体特征的测度主要有网络整体特征的测度主要有n网络密度网络密度n平均测地线距离平均测地线距离n网络聚类系数网络聚类系数n谱半径谱半径网络整体特征刻画网络整体特征的刻画是网络分析的最高层次，目的R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络密度n网络密度是网络分析中常用的一种度量全局网络特征网络密度是网络分析中常用的一种度量全局网络特征的测度量的测度量n从连接个数的角度测度网络节点间的密集程度从连接个数的角度测度网络节点间的密集程度n当网络节点个数当网络节点个数N N确定后，节点之间的连接线越多，确定后，节点之间的连接线越多，表明该图的密度越大表明该图的密度越大n相关相关R R函数函数ngraph.density(graph=graph.density(graph=网络类对象名网络类对象名)网络密度网络密度是网络分析中常用的一种度量全局网络特征的测度R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用平均测地线距离n平均测地线距离也是刻画网络整体特征的常用测度平均测地线距离也是刻画网络整体特征的常用测度n从几何距离的角度测度节点连接的紧密程度，有与从几何距离的角度测度节点连接的紧密程度，有与网络直径类似的意义，但更具稳健性网络直径类似的意义，但更具稳健性n平均测地线距离是各个节点测地线距离的均值平均测地线距离是各个节点测地线距离的均值n该值越大表明网络整体的该值越大表明网络整体的“覆盖覆盖”区域越大，网络区域越大，网络节点连接的密集程度较低。反之，网络节点连接的节点连接的密集程度较低。反之，网络节点连接的密集程度较高密集程度较高n相关相关R R函数函数naverage.path.length(graph=average.path.length(graph=网络类对象名网络类对象名,directed=TRUE/FALSE),directed=TRUE/FALSE)平均测地线距离平均测地线距离也是刻画网络整体特征的常用测度R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络聚类系数n节点节点ni聚类系数用于测度节点聚类系数用于测度节点ni的聚类能力的聚类能力n网络聚类系数网络聚类系数n可定义为所有节点聚类系数的简单平均可定义为所有节点聚类系数的简单平均n还可定义为以节点连接三方组频率为权重的节点聚还可定义为以节点连接三方组频率为权重的节点聚类系数的加权平均类系数的加权平均n相关相关R R函数函数ntransitivity(graph=transitivity(graph=网络类对象名网络类对象名,type=,type=类型名类型名)网络聚类系数节点ni聚类系数用于测度节点ni的聚类能力R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用谱半径n网络的谱半径也是度量网络整体连接程度的测度量网络的谱半径也是度量网络整体连接程度的测度量n谱半径是网络邻接矩阵谱半径是网络邻接矩阵Y Y的最大非零特征值的最大非零特征值n谱半径在兼顾拓扑结构的基础上测度网络的整体连谱半径在兼顾拓扑结构的基础上测度网络的整体连接程度，更适用于不同网络间的对比接程度，更适用于不同网络间的对比n谱半径越大，网络的整体连接程度越高谱半径越大，网络的整体连接程度越高n相关相关R R函数函数nevcent(graph=evcent(graph=网络类对象名网络类对象名,scale=TRUE/FALSE),scale=TRUE/FALSE)谱半径网络的谱半径也是度量网络整体连接程度的测度量R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络特征的各种分布和度量n刻画网络整体特征更细致的方式是分布，如：刻画网络整体特征更细致的方式是分布，如：n网络的节点度分布、点度中心度分布、中间中心度分布、网络的节点度分布、点度中心度分布、中间中心度分布、测度线距离分布，等测度线距离分布，等n网络分析中研究最多的分布是度分布网络分析中研究最多的分布是度分布n度分布特征的度量度分布特征的度量n度的熵度的熵n度的熵越大，度取值的平均不确定性越大，反之，度取值度的熵越大，度取值的平均不确定性越大，反之，度取值的平均不确定性越小的平均不确定性越小n网络分析中，度的熵也称为网络熵网络分析中，度的熵也称为网络熵n相关相关R R函数函数nentropy(y=entropy(y=频数分布频数分布,method=ML,unit=log2),method=ML,unit=log2)网络特征的各种分布和度量刻画网络整体特征更细致的方式是分布，R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用主要网络类型及特点n网络科学研究中，依据度分布将众多网络划分成四种网络科学研究中，依据度分布将众多网络划分成四种类型：类型：n规则网络规则网络n小世界网络小世界网络n无标度网络无标度网络n随机网络随机网络n不同网络类型的主要差异在于：不同网络类型的主要差异在于：n网络中任意两个节点网络中任意两个节点ni和和nj间具有连接是确定性的间具有连接是确定性的还是是随机性的还是是随机性的n确定性和随机性的不同程度的混合确定性和随机性的不同程度的混合主要网络类型及特点网络科学研究中，依据度分布将众多网络划分成R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用规则网络及特点n规则网络是指网络中任意两个节点规则网络是指网络中任意两个节点ni和和nj间间n具有连接是确定性的具有连接是确定性的n连接的规律性导致规则网络的连接的规律性导致规则网络的拓扑结构往往具有特定的拓扑结构往往具有特定的“形形态态”nk-k-规则网络：典型的规则网络规则网络：典型的规则网络n所谓所谓k-规则网络是指网络中的规则网络是指网络中的每个节点均与每个节点均与k（kN1,N为为节点个数）个节点存在直接连节点个数）个节点存在直接连接的网络接的网络规则网络及特点规则网络是指网络中任意两个节点ni和nj间R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用规则网络及特点n星形网络：规则网络星形网络：规则网络n有有N1个节点均与剩下的一个节点个节点均与剩下的一个节点ni直接相连，它直接相连，它们的节点度均等于们的节点度均等于1，节点节点ni的度等于的度等于N1n平衡平衡2-2-叉树网络：规则网络叉树网络：规则网络n除叶节点之外，每个节点都有两个子节点，共有除叶节点之外，每个节点都有两个子节点，共有N1条连接。根节点的度等于条连接。根节点的度等于2，叶节点的度等于，叶节点的度等于1，其余节点的度都等于其余节点的度都等于3，节点度只可能取，节点度只可能取1,2,3n相关相关R R函数函数ngraph.stargraph.starngraph.treegraph.tree规则网络及特点星形网络：规则网络R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用随机网络及特点n大规模随机网络的最大特点大规模随机网络的最大特点n节点的度分布服从泊松分布节点的度分布服从泊松分布n网络熵随网络密度的增加呈非线性变化网络熵随网络密度的增加呈非线性变化n网络密度为网络密度为0.50.5的随机网络具有最大的网络熵的随机网络具有最大的网络熵n将包含将包含N个节点和个节点和E条连接的随机网络看做是，包含条连接的随机网络看做是，包含N个节点的个节点的空网络随时间空网络随时间t=0,1,2,E推移逐步演变的结果。每个时刻推移逐步演变的结果。每个时刻t均在均在上个时刻上个时刻t1的基础上随机挑选一对节点并在其间增加一条连的基础上随机挑选一对节点并在其间增加一条连接，经过接，经过E步直到添加步直到添加E E条连接为止条连接为止n该规则是该规则是E.N.GilbertE.N.Gilbert提出的，网络称为提出的，网络称为GilbertGilbert随机网络随机网络n相关相关R R函数函数nerdos.renyi.game(n=erdos.renyi.game(n=节点数节点数,p.or.m=,p.or.m=概率或连接数概率或连接数,type=type=类型名类型名)随机网络及特点大规模随机网络的最大特点R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用随机网络及特点n随机网络的熵随机网络的熵n网络密度在较高水平或者网络密度在较高水平或者较低水平时，网络熵快速较低水平时，网络熵快速下降至下降至0 0。随机网络并不具。随机网络并不具有随机性，其度分布与泊有随机性，其度分布与泊松分布相距较大松分布相距较大n网络密度在网络密度在0.50.5时，网络熵时，网络熵到达最大，网络的随机性到达最大，网络的随机性最高最高n随着网络密度偏离随着网络密度偏离0.50.5，随，随机网络就不再那么随机机网络就不再那么随机随机网络及特点随机网络的熵R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用小世界网络及特点n小世界网络是介于规则网络和随机网络之间的一种网小世界网络是介于规则网络和随机网络之间的一种网络，一般具有大部分的确定性和少部分的随机性络，一般具有大部分的确定性和少部分的随机性n生成生成WSWS网络网络n起步于一个规则网络，如起步于一个规则网络，如k-规则网络规则网络n对规则网络中的每条连接，以重连概率对规则网络中的每条连接，以重连概率p，将连接，将连接的一端重新连接到随机挑选的节点上的一端重新连接到随机挑选的节点上n最终有最终有Ep条连接进行过重连，余下的条连接进行过重连，余下的(1p)E条连条连接保持不变接保持不变nWSWS小世界网络的随机性体现在小世界网络的随机性体现在Ep条随机化的连接中。条随机化的连接中。其随机性取决于重连概率其随机性取决于重连概率p小世界网络及特点小世界网络是介于规则网络和随机网络之间的一种R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用小世界网络及特点n相关相关R R函数函数nwatts.strogatz.game(dim=watts.strogatz.game(dim=维数维数,size=,size=节点个数节点个数,nei=,nei=邻域邻域半径半径,p=,p=重连概率重连概率)n随着网络重连概率随着网络重连概率p p的增大，网络熵逐渐增大，网络的增大，网络熵逐渐增大，网络的平均测地线长度将呈指数下降。的平均测地线长度将呈指数下降。WSWS小世界网络的度小世界网络的度分布较陡，且随重连概率分布较陡，且随重连概率p p的增加而逐渐趋于平缓，的增加而逐渐趋于平缓，是个类泊松分布是个类泊松分布小世界网络及特点相关R函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用无标度网络及特点n无标度网络是介于规则网络和随机网络之间的一种网无标度网络是介于规则网络和随机网络之间的一种网络，一般具有大部分的随机性和少部分的规则性络，一般具有大部分的随机性和少部分的规则性n典型的无标度网络是典型的无标度网络是BABA网络网络nBABA规则的思路：规则的思路：n从一个很小的完备网络开始，每步向现有网络中添加一个从一个很小的完备网络开始，每步向现有网络中添加一个节点节点v和和m条连接条连接n头节点的选择依据当前网络中的节点度，构造一个关于节头节点的选择依据当前网络中的节点度，构造一个关于节点度的线性或非线性函数。哪个节点的度越高，函数值越点度的线性或非线性函数。哪个节点的度越高，函数值越大，成为头节点的概率就越高大，成为头节点的概率就越高n每添加一个节点后，重新计算各节点的度每添加一个节点后，重新计算各节点的度n该步骤重复多次，直到网络到达指定的节点规模为止该步骤重复多次，直到网络到达指定的节点规模为止无标度网络及特点无标度网络是介于规则网络和随机网络之间的一种R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用无标度网络及特点n相关相关R R函数函数nbarabasi.game(n=barabasi.game(n=节点个数节点个数,m=,m=每个节点添加的连接数每个节点添加的连接数)npower.law.fit(x=power.law.fit(x=节点度向量节点度向量)nstatic.power.law.game(no.of.nodes=static.power.law.game(no.of.nodes=网络节点数网络节点数,no.of.edges=,no.of.edges=网络连接数网络连接数,exponent.out=,exponent.out=参数参数)n度数较低的节点个数较多，度数较低的节点个数较多，hubhub节点因度数较高数量节点因度数较高数量极少极少nBABA网络的熵与网络密度有关。随着网络的熵与网络密度有关。随着BABA规则中参数规则中参数m的的不断增大，网络密度将不断增加，也使网络熵出现非不断增大，网络密度将不断增加，也使网络熵出现非线性的变化线性的变化无标度网络及特点相关R函数