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

1、R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用案例说明 广义上讲，任何事物都处在一个有形或无形的网络当广义上讲，任何事物都处在一个有形或无形的网络当中，与网络中的其他事物形成一种相互依存或竞争关中，与网络中的其他事物形成一种相互依存或竞争关系系 多个国家之间构成具有进出口贸易往来关系的贸易网络；多个国家之间构成具有进出口贸易往来关系的贸易网络；企业内部多个部门之间构成具有协同合作关系的协同网络企业内部多个部门之间构成具有协同合作关系的协同网络；互联网社区中多个个体之间构成具有信息共享交换、舆；互联网社区中多个个体之间构成具有信息共享交换、舆

2、论传播互动关系的社交网络；多名学者之间构成具有成果论传播互动关系的社交网络；多名学者之间构成具有成果引用和被引用关系的合作研究网络；多只股票之间构成具引用和被引用关系的合作研究网络；多只股票之间构成具有价格波动影响关系的收益联动网络；多种商品之间构成有价格波动影响关系的收益联动网络；多种商品之间构成的具有连带销售关系的交叉购买网络；多部电影、多个影的具有连带销售关系的交叉购买网络；多部电影、多个影星、众多影迷之间构成具有参演和不参演、喜爱和不喜爱星、众多影迷之间构成具有参演和不参演、喜爱和不喜爱等多种关系的娱乐网络，等等等多种关系的娱乐网络，等等R R语言数据挖掘方法及应用语言数据挖掘方法及应

3、用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络分析n 研究网络构成及网络成员间的相互影响，是揭示事物研究网络构成及网络成员间的相互影响，是揭示事物相关性的另一个独特视角相关性的另一个独特视角n 网络分析的基本框架网络分析的基本框架n 构建网络：网络由系统内部各成员（网络中称为节构建网络：网络由系统内部各成员（网络中称为节点）和成员之间的联系（网络中称为连接）构成点）和成员之间的联系（网络中称为连接）构成n 网络的基本分析：通常按照个体层次、中间层次和网络的基本分析：通常按照个体层次、中间层次和全局层次，逐层递进展开。不同层次的分析服务于全局层次，逐层递进展开。不同层次的分析服务于不同

4、的研究目标不同的研究目标n 网络的深入分析：将依据网络类型，从统计角度采网络的深入分析：将依据网络类型，从统计角度采用不同模型，对网络的静态特征和动态发展做进一用不同模型，对网络的静态特征和动态发展做进一步的分析和预测步的分析和预测R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的定义表示及构建n 网络分析的基础是网络的定义及表示，通常有两种相网络分析的基础是网络的定义及表示，通常有两种相互联系的表示方式：图论表示方式、矩阵表示方式互联系的表示方式：图论表示方式、矩阵表示方式n 图论表示方式：从图论角度看，网络由多个节点和节图论表示方式：

5、从图论角度看，网络由多个节点和节点间的连接（也称边）组成，是一种广义的图点间的连接（也称边）组成，是一种广义的图n 网络可记为网络可记为G=(N,E) 。网络。网络G中沿着连接在不同节中沿着连接在不同节点间的移动，称为游走点间的移动，称为游走n 依连接的方向性，网络分为无向网络和有向网络；依连接的方向性，网络分为无向网络和有向网络；依连接的类型，网络分为无权网络和加权网络。依依连接的类型，网络分为无权网络和加权网络。依节点类型，网络分为节点类型，网络分为1-1-模网络和模网络和2-2-模网络模网络R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应

6、用图论表示方式：无向网络n 无向网络：网络中节点间的连接没有方向性无向网络：网络中节点间的连接没有方向性n 涉及很多基本概念涉及很多基本概念n 在网络在网络G G中，若存在节点沿连接中，若存在节点沿连接“一步一步”游走回自游走回自身，则称网络身，则称网络G G存在环存在环n 在网络在网络G G中，若一对节点被两个以上的连接相连，中，若一对节点被两个以上的连接相连，则称网络则称网络G G存在多边存在多边n 若网络若网络G G存在环或者多边，则称网络存在环或者多边，则称网络G G为多重图。否为多重图。否则为简单图。网络的分析中，通常需将多重图简化则为简单图。网络的分析中，通常需将多重图简化为简单图

7、后再研究为简单图后再研究R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：无向网络n 涉及很多基本概念涉及很多基本概念n 若从网络若从网络G中的节点中的节点ni出发沿着连接游走可出发沿着连接游走可“抵达抵达”节点节点nj，称为节点，称为节点ni可达节点可达节点njn 若从网络若从网络G中的任意节点中的任意节点ni出发沿着连接游走可达出发沿着连接游走可达网络中其他任意节点网络中其他任意节点nk，则称网络，则称网络G 是连通的是连通的n 若从网络若从网络G的某个节点开始沿着连接游走，能够返的某个节点开始沿着连接游走，能够返回同一节点，

8、则称该网络回同一节点，则称该网络G存在回路存在回路n 对于网络对于网络G中的一个连通子网络中的一个连通子网络G=(N,E)，若将若将G之外的属于之外的属于G的任意节点加到网络的任意节点加到网络G中，网络中，网络G就不再具有连通性，则称就不再具有连通性，则称G为网络为网络G的一个组件的一个组件R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：无向网络n 涉及很多基本概念涉及很多基本概念n 若网络若网络G中任意节点中任意节点ni和和nk间均存在一个连接间均存在一个连接ej（直（直接相连），则称网络接相连），则称网络G是完备的，否则为非

9、完备的是完备的，否则为非完备的R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：无向网络的R函数n 涉及很多涉及很多R R函数函数n graph.formula(graph.formula(公式公式) )n graph.empty(n=N,directegraph.empty(n=N,directed=TRUE/FALSE)d=TRUE/FALSE)n vcount(graph=vcount(graph=网络类对象网络类对象名名) )n ecount(graph=ecount(graph=网络类对象网络类对象名名) )n V(V(网络

10、类对象名网络类对象名) )n E(E(网络类对象名网络类对象名) )n add.edges (add.edges (网络类对象名网络类对象名, ,连接连接) )n k.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)n simplify(graph=simplify(graph=网络类对象网络类对象名名) )n plot(plot(网络类对象名网络类

11、对象名,layout=,layout=可视化方法名可视化方法名) )n is.connected (graph=is.connected (graph=网络网络类对象名类对象名) )n subcomponent(graph=subcomponent(graph=网络类网络类对象名对象名, v=, v=指定节点指定节点) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：有向网络n 有向网络：网络中节点间的连接有方向性有向网络：网络中节点间的连接有方向性n 涉及很多基本概念涉及很多基本概念n 互惠关系互惠关系n 若从有向网络若从有

12、向网络G中的任意节点中的任意节点ni出发沿有向连接出发沿有向连接ej游走，可游走，可“抵达抵达”其他任意节点其他任意节点nk，则称有向网络，则称有向网络G是强连通的是强连通的n 若从有向网络若从有向网络G中的任意节点中的任意节点ni出发，忽略连接的出发，忽略连接的方向性做无向游走，并可方向性做无向游走，并可“抵达抵达”其他任意节点其他任意节点nk，则称有向网络则称有向网络G是弱连通是弱连通R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示方式：有向网络n 涉及很多基本概念涉及很多基本概念n 若有向网络若有向网络G中存在有方向的回路，则称

13、网络中存在有方向的回路，则称网络G中存在循环中存在循环n 若有向网络若有向网络G中不存在有方向的回路，无论是否存在回路，中不存在有方向的回路，无论是否存在回路，有向网络有向网络G均称为有向不循环图网络均称为有向不循环图网络n 涉及很多涉及很多R R函数函数n is.mutual (graph=is.mutual (graph=网络类对象网络类对象名名) )n is.dag (graph=is.dag (graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示：无权网络和加权网络n 无权网络：是在忽略网

14、络中不同节点间关系强弱差异无权网络：是在忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有相同的连接强度的无向或性的前提下，各节点连接有相同的连接强度的无向或有向网络有向网络n 加权网络：是在不能忽略网络中不同节点间关系强弱加权网络：是在不能忽略网络中不同节点间关系强弱差异性的前提下，各节点连接有不同的连接强度的无差异性的前提下，各节点连接有不同的连接强度的无向或有向网络向或有向网络n 无权网络是一种特殊的加权网络。若两节点间存在连无权网络是一种特殊的加权网络。若两节点间存在连接，权重等于接，权重等于1 1；若两节点间不存在连接，权重等于；若两节点间不存在连接，权重等于0 0n 无向加权

15、网络分析是加权网络分析的重点无向加权网络分析是加权网络分析的重点n R R函数：函数：is.weighted (graph=is.weighted (graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示： 1-模网络和2-模网络n R R函数函数n graph.full.bipartite(n1=n,n2=m,directed=TRUgraph.full.bipartite(n1=n,n2=m,directed=TRUE/FALSE,mode=E/FALSE,mode=方向类型方向类型) )n g

16、raph.bipartite(types=graph.bipartite(types=节点类型逻辑向量节点类型逻辑向量, , edges=edges=连接连接,directed=TRUE/FALSE),directed=TRUE/FALSE)R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用图论表示： 1-模网络和2-模网络n 模指网络中节点的类型模指网络中节点的类型n 若网络中所有节点均属于同一类型集合，该网络称若网络中所有节点均属于同一类型集合，该网络称为为1-1-模网络模网络n 若网络中节点分属两个不同的类型集合，该网络称若网络中节点分属

17、两个不同的类型集合，该网络称为为2-2-模网络模网络R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的矩阵表示n 邻接矩阵：邻接矩阵：Y Y是一个是一个N NN N的方阵，反映网络中各节点的方阵，反映网络中各节点间的连接情况。行号和列号为各节点的索引编码间的连接情况。行号和列号为各节点的索引编码n 无向网络的邻接矩阵无向网络的邻接矩阵: :n 若节点若节点i 和节点和节点j之间存在连接，则令矩阵中第之间存在连接，则令矩阵中第i行第行第j列上的列上的元素元素yij=1n 若节点若节点i 和节点和节点j之间不存在连接，则令矩阵元素之间不存在连

18、接，则令矩阵元素yij=0n 有向网络的邻接矩阵：邻接矩阵有向网络的邻接矩阵：邻接矩阵Y Y的列号代表头节点的列号代表头节点索引编码，行号代表尾节点索引编码索引编码，行号代表尾节点索引编码n 若节点若节点i和节点和节点j之间存在有向连接，则令矩阵元素之间存在有向连接，则令矩阵元素yij=1n 若节点若节点i和节点和节点j之间不存在有向连接，则令矩阵元素之间不存在有向连接，则令矩阵元素yij=0n 有向图的邻接矩阵有向图的邻接矩阵Y Y一般是非对称的一般是非对称的R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络的矩阵表示n 相关相关R R函

19、数函数n get. adjacency(graph=get. adjacency(graph=网络类对象名网络类对象名,type=,type=特征名特征名,attr=,attr=属性名属性名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用关系矩阵表示n 关系矩阵也称隶属关系矩阵，用于反映关系矩阵也称隶属关系矩阵，用于反映2-2-模网络中各模网络中各类节点间的连接情况类节点间的连接情况n 设设2-模网络中第一类节点个数为模网络中第一类节点个数为N1，第二类节点个数为节，第二类节点个数为节点点N2。关系矩阵。关系矩阵B是一个是一个N1N2的

20、矩阵，通常不是方阵的矩阵，通常不是方阵n 无向无向2-2-模网络的关系矩阵：矩阵模网络的关系矩阵：矩阵B的的行列分别为两类行列分别为两类节点的索引编号节点的索引编号n 有向有向2-2-模网络的关系矩阵：矩阵模网络的关系矩阵：矩阵B B列号代表头节点索列号代表头节点索引编码，行号代表尾节点索引编码引编码，行号代表尾节点索引编码n 相关相关R R函数函数n get. incidence(graph=get. incidence(graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R建立网络对象n 利用邻接矩阵

21、建立网络对象利用邻接矩阵建立网络对象n graph.adjacency(adjmatrix=graph.adjacency(adjmatrix=邻接矩阵名邻接矩阵名,mode=,mode=网络类型网络类型名名,weighted=TURE/NULL),weighted=TURE/NULL)n 示例示例n 利用关系矩阵建立利用关系矩阵建立2-2-模网络对象模网络对象n graph.incidence(incidence=graph.incidence(incidence=关系矩阵关系矩阵名名,directed=TRUE/FALSE,mode=,directed=TRUE/FALSE,mode=方向

22、类方向类型型,weighted=TURE/NULL),weighted=TURE/NULL)n 示例示例R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R建立网络对象n 利用连接列表建立网络对象利用连接列表建立网络对象n get.data.frame(x=get.data.frame(x=网络类对象名网络类对象名, what=edges), what=edges)n graph.data.frame(d=graph.data.frame(d=连接列表数据框连接列表数据框, , directed=TRUE/FALSE)directed=TRUE

23、/FALSE)n 示例示例R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用R的网络可视化n 网络可视化的核心是以怎样的外观轮廓展示网络，尤网络可视化的核心是以怎样的外观轮廓展示网络，尤其对较为庞大的网络更为如此其对较为庞大的网络更为如此n 合理安排网络外观轮廓的算法合理安排网络外观轮廓的算法n 最小分割法：目的是最小化连接间的交叉数最小分割法：目的是最小化连接间的交叉数n 最小空间法：基于几何意义上的空间距离，令空间距离较最小空间法：基于几何意义上的空间距离，令空间距离较近的节点摆放在相邻的位置上近的节点摆放在相邻的位置上n 谱分解法：依据节

24、点的特征向量中心度安排节点的位置谱分解法：依据节点的特征向量中心度安排节点的位置n 树形树形/ /层次法：根据节点间的连接将节点安排成树形形状，层次法：根据节点间的连接将节点安排成树形形状，或组织成层次图或组织成层次图n 算法体现在算法体现在plotplot函数的函数的layoutlayout参数中参数中R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络节点重要性的测度n 节点重要性测度是网络基本分析的第一个层次，目的节点重要性测度是网络基本分析的第一个层次，目的是刻画节点个体与其他节点有怎样是刻画节点个体与其他节点有怎样“强度强度”的关系

25、，的关系，发现网络中的重要节点发现网络中的重要节点n 节点在网络中的重要性一般表现节点在网络中的重要性一般表现n 第一，它是网络一个第一，它是网络一个“局部范围局部范围”内的内的“中心中心”n 第二，它是一个具有强连接的第二，它是一个具有强连接的“枢纽枢纽”n 涉及两个基本测度涉及两个基本测度n 度度n 测地线距离测地线距离R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用度和相关R函数n 节点节点ni的度：指节点的度：指节点ni有多少个与其直接连接的邻居有多少个与其直接连接的邻居节点节点n 无向网络：无向网络：n 有向网络：入度、出度有向网络

26、：入度、出度n 相关相关R R函数函数n degree(graph=degree(graph=网络类对象名网络类对象名, v=, v=节点对象节点对象, mode =, mode =方向类方向类型型) )n graph.strength (graph=graph.strength (graph=网络类对象名网络类对象名, vids =, vids =节点对象节点对象, , mode =mode =方向类型方向类型) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用测地线距离和相关R函数n 最短路径的距离，称为节点最短路径的距离，称为节点ni

27、和和nj间的测地线距离间的测地线距离n 节点节点ni和和nj间可能存在多条不同的最短路径间可能存在多条不同的最短路径n 有向网络需依方向游走，根据带方向的最短路径计算有向网络需依方向游走，根据带方向的最短路径计算n 测地线距离可基于邻接矩阵计算得到测地线距离可基于邻接矩阵计算得到n 若网络若网络G G具有连通性，网络中所有节点对测地线距离具有连通性，网络中所有节点对测地线距离中的最大值，称为网络中的最大值，称为网络G G的直径的直径n 相关相关R R函数：函数：n shortest.paths(graph=shortest.paths(graph=网络类对象名网络类对象名, v=, v=起始节

28、点对象起始节点对象, , to=to=终止节点对象终止节点对象,mode=,mode=方向类型方向类型) )n diameter(graph=diameter(graph=网络类对象网络类对象名名,directed=TRUE/FALSE,unconnected=TRUE/FALSE),directed=TRUE/FALSE,unconnected=TRUE/FALSE)R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n 节点节点ni的点度中心度：为标准化度，度的点度中心度：为标准化度，度d(ni)与其最大与其最大可能度数

29、之比可能度数之比n 无向网络：无向网络：n 有向网络：有向网络：n 点度中心度等于点度中心度等于0 0：节点：节点ni是个是个“孤立孤立”点，不于点，不于其他任何节点相连，不可能是其他任何节点相连，不可能是“局部范围局部范围”内的连内的连接接“中心中心”，重要性很低，重要性很低n 点度中心度越大说明节点点度中心度越大说明节点ni越重要越重要R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n 节点节点ni的接近点度中心度的接近点度中心度n 接近点度中心度越大，说明节点接近点度中心度越大，说明节点ni与所有其他节点的与所有其

30、他节点的测地线距离之和越小，越可能成为几何意义上的中心，测地线距离之和越小，越可能成为几何意义上的中心，节点节点ni越重要越重要R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“中心”作用的测度n 相关相关R R函数函数n degree(graph=degree(graph=网络类对象名网络类对象名, v=, v=节点对象节点对象, mode =, mode =方向类方向类型型,normalized = TRUE),normalized = TRUE)n closeness(graph=closeness(graph=网络类对象名网络类对

31、象名vids=vids=节点对象节点对象, mode =, mode =方方向类型向类型,normalized = FALSE/TRUE),normalized = FALSE/TRUE)n 计算点度中心度和接近中心度的必要性探讨计算点度中心度和接近中心度的必要性探讨R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“枢纽”作用的测度n 中间中心度中间中心度n 直观上，若节点直观上，若节点ni是网络的连接是网络的连接“枢纽枢纽”，则一定有很多，则一定有很多“线路线路”经过经过ni。可依。可依“路线路线”的多少测度节点的多少测度节点“枢纽枢纽

32、”作用的高低作用的高低n 中间中心度越大，表明必须经过节点中间中心度越大，表明必须经过节点ni的最短路径条数的最短路径条数越多，节点越多，节点ni的的“枢纽枢纽”作用越强越重要作用越强越重要n 标准化中间中心度：克服网络规模对中间中心度结果的标准化中间中心度：克服网络规模对中间中心度结果的影响影响R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点“枢纽”作用的测度n 相关相关R R函数函数n betweenness(graph=betweenness(graph=网络类对象名网络类对象名, v=, v=节点对象节点对象, , normali

33、zed = FALSE/TRUE)normalized = FALSE/TRUE)n edge.betweenness(graph=edge.betweenness(graph=网络类对象名网络类对象名) )，可计算连接的，可计算连接的中间中心度中间中心度R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面n 结构洞结构洞n 一个系统（网络）中，若某个成员（节点）退出系统，使一个系统（网络）中，若某个成员（节点）退出系统，使得局部系统中的其他成员（节点）间不再有任何联系（连得局部系统中的其他成员（节点）间不再有任何联系（连接）

34、。从结构上看就像局部网络中出现了一个关系断裂的接）。从结构上看就像局部网络中出现了一个关系断裂的“洞穴洞穴”，该成员称为一个结构洞，该成员称为一个结构洞n 关节点关节点n 是那些若剔除网络将导致网络的组件数大大增加的节点。是那些若剔除网络将导致网络的组件数大大增加的节点。关节点不存在，网络将变成两个或多个互不连接的独立子关节点不存在，网络将变成两个或多个互不连接的独立子网络或单个网络或单个“孤立孤立”节点。关节点在构成组件中起到了一节点。关节点在构成组件中起到了一个个“中枢中枢”作用作用n 相关相关R R函数：函数： articulation.points(graph= articulatio

35、n.points(graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面n 特征向量中心度：节点重要性的测度量特征向量中心度：节点重要性的测度量n 基本出发点是：如果节点基本出发点是：如果节点ni较为重要，则节点较为重要，则节点ni应应与其他重要节点有较多的连接与其他重要节点有较多的连接n 相关相关R R函数函数n evcent (graph=evcent (graph=网络类对象名网络类对象名, scale = TRUE/FALSE), scale = TRUE/FALSE)R R语言

36、数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用节点重要性的其他方面n PageRankPageRank得分得分n 是是S. BrinS. Brin和和L. PageL. Page于于19981998年提出的度量网络节年提出的度量网络节点重要性的测度得分，也称点重要性的测度得分，也称PageRankPageRank算法，是算法，是GoogleGoogle搜索算法的基础搜索算法的基础n 相关相关R R函数函数n page.rank (graph=page.rank (graph=网络类对象名网络类对象名, vids =, vids =网络节点网络节点,

37、, directed = TRUE, damping=0.85) directed = TRUE, damping=0.85) R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络子群构成特征研究n 子群分析是网络分析的第二个层次。它将研究范围从子群分析是网络分析的第二个层次。它将研究范围从单个节点拓展到某些覆盖多个节点的局部区域。这些单个节点拓展到某些覆盖多个节点的局部区域。这些局部区域中节点间的关系更为密切或更特殊，成为相局部区域中节点间的关系更为密切或更特殊，成为相对独立的小群体，也称子群。子群类型对独立的小群体，也称子群。子群类型n

38、二元关系，三元关系二元关系，三元关系n 派系派系n k-k-核核n 子群分析的主要目标是基于子群类型，找到网络中包子群分析的主要目标是基于子群类型，找到网络中包含的各种子群和数量，并借助子群特点和所体现的局含的各种子群和数量，并借助子群特点和所体现的局部关系，细致刻画网络的结构组成特征部关系，细致刻画网络的结构组成特征R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用二元关系和三元关系n 二元关系：通常针对有向网络而言，是有向网络中仅二元关系：通常针对有向网络而言，是有向网络中仅涉及两个节点的最小子群涉及两个节点的最小子群n 节点节点ni和和n

39、j间的二元关系有三种状态间的二元关系有三种状态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 相关相

40、关R R函数函数n dyad.census(graph=dyad.census(graph=网络类对象名网络类对象名) )n triad.census(graph=triad.census(graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用派系和k-核n 派系：若网络派系：若网络G中的一个组件中的一个组件G是完备的，且不被其是完备的，且不被其他的完备组件所包含，则称他的完备组件所包含，则称G为网络为网络G的一个派系的一个派系n 派系是一个局部意义上的最大完备子网络派系是一个局部意义上的最大完备子网络n

41、相关相关R R函数函数n maximal.cliques(graph=maximal.cliques(graph=网络类对象名网络类对象名, min=n1, max= n2), min=n1, max= n2)n largest.cliques(graph=largest.cliques(graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用派系和k-核n k-核：派系若核：派系若G是网络是网络G的一个最大连通性子图的一个最大连通性子图，且且G中的每个节点均至少与其他中的每个节点均至少与其他k个节点直接连接

42、，即个节点直接连接，即G中每个节点的度均大于等于中每个节点的度均大于等于k，则称则称G是网络是网络G的的一个一个k-核核n 节点节点ni的核等于的核等于m如果它属于如果它属于m-核但不属于核但不属于(m1)-核核n 只要节点只要节点ni不是不是“孤立孤立”点，它至少是一个点，它至少是一个1-核成员，核成员，也可能属于更大的核也可能属于更大的核n 相关相关R R函数函数n graph.coreness(graph=graph.coreness(graph=网络类对象名网络类对象名,mode=,mode=方向类型方向类型) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法

43、及应用语言数据挖掘方法及应用社区和组件n 社区也称模块：是一个子网络，特点是子网络内部各社区也称模块：是一个子网络，特点是子网络内部各结点的连接相对紧密，子网络之间的连接相对稀疏结点的连接相对紧密，子网络之间的连接相对稀疏n 社区结构划分算法社区结构划分算法n 基于划分的方法基于划分的方法n 模块度方法模块度方法n 随机游走方法随机游走方法n 密度子图方法密度子图方法n 模块度模块度n 相关相关R R函数函数R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用社区和组件n 组件作为最大连通性子网络，其凝聚程度可能低于派组件作为最大连通性子网络，其

44、凝聚程度可能低于派系等，但因系等，但因“对外对外”没有连接而具有强独立性没有连接而具有强独立性n 相关相关R R函数函数n clusters(graph=clusters(graph=网络类对象名网络类对象名, mode=, mode=组件类型组件类型) )n decompose.graph(graph=decompose.graph(graph=网络类对象名网络类对象名, mode=, mode=组件类型组件类型) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络整体特征刻画n 网络整体特征的刻画是网络分析的最高层次，目的是网络整体特

45、征的刻画是网络分析的最高层次，目的是从全局角度揭示网络的整体样貌。一般有两种方式：从全局角度揭示网络的整体样貌。一般有两种方式：n 第一，利用关于网络整体特征的测度第一，利用关于网络整体特征的测度n 第二，通过各种分布刻画第二，通过各种分布刻画n 网络整体特征的测度主要有网络整体特征的测度主要有n 网络密度网络密度n 平均测地线距离平均测地线距离n 网络聚类系数网络聚类系数n 谱半径谱半径R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络密度n 网络密度是网络分析中常用的一种度量全局网络特征网络密度是网络分析中常用的一种度量全局网络特征的测

46、度量的测度量n 从连接个数的角度测度网络节点间的密集程度从连接个数的角度测度网络节点间的密集程度n 当网络节点个数当网络节点个数N N确定后，节点之间的连接线越多，确定后，节点之间的连接线越多，表明该图的密度越大表明该图的密度越大n 相关相关R R函数函数n graph.density(graph=graph.density(graph=网络类对象名网络类对象名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用平均测地线距离n 平均测地线距离也是刻画网络整体特征的常用测度平均测地线距离也是刻画网络整体特征的常用测度n 从几何距离的角度测度

47、节点连接的紧密程度，有与从几何距离的角度测度节点连接的紧密程度，有与网络直径类似的意义，但更具稳健性网络直径类似的意义，但更具稳健性n 平均测地线距离是各个节点测地线距离的均值平均测地线距离是各个节点测地线距离的均值n 该值越大表明网络整体的该值越大表明网络整体的“覆盖覆盖”区域越大，网络区域越大，网络节点连接的密集程度较低。反之，网络节点连接的节点连接的密集程度较低。反之，网络节点连接的密集程度较高密集程度较高n 相关相关R R函数函数n average.path.length (graph=average.path.length (graph=网络类对象网络类对象名名,directed=T

48、RUE/FALSE),directed=TRUE/FALSE)R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络聚类系数n 节点节点ni聚类系数用于测度节点聚类系数用于测度节点ni的聚类能力的聚类能力n 网络聚类系数网络聚类系数n 可定义为所有节点聚类系数的简单平均可定义为所有节点聚类系数的简单平均n 还可定义为以节点连接三方组频率为权重的节点聚还可定义为以节点连接三方组频率为权重的节点聚类系数的加权平均类系数的加权平均n 相关相关R R函数函数n transitivity(graph=transitivity(graph=网络类对象名网络

49、类对象名, type=, type=类型名类型名) )R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用谱半径n 网络的谱半径也是度量网络整体连接程度的测度量网络的谱半径也是度量网络整体连接程度的测度量n 谱半径是网络邻接矩阵谱半径是网络邻接矩阵Y Y的最大非零特征值的最大非零特征值n 谱半径在兼顾拓扑结构的基础上测度网络的整体连谱半径在兼顾拓扑结构的基础上测度网络的整体连接程度，更适用于不同网络间的对比接程度，更适用于不同网络间的对比n 谱半径越大，网络的整体连接程度越高谱半径越大，网络的整体连接程度越高n 相关相关R R函数函数n evce

50、nt (graph=evcent (graph=网络类对象名网络类对象名, scale = TRUE/FALSE), scale = TRUE/FALSE)R R语言数据挖掘方法及应用语言数据挖掘方法及应用R R语言数据挖掘方法及应用语言数据挖掘方法及应用网络特征的各种分布和度量n 刻画网络整体特征更细致的方式是分布，如：刻画网络整体特征更细致的方式是分布，如：n 网络的节点度分布、点度中心度分布、中间中心度分布、网络的节点度分布、点度中心度分布、中间中心度分布、测度线距离分布，等测度线距离分布，等n 网络分析中研究最多的分布是度分布网络分析中研究最多的分布是度分布n 度分布特征的度量度分布特