《R语言数据挖掘(第2版)》教学课件—第十二章R的网络分析初步.pptx
- 文档编号:671935
- 上传时间:2023-04-29
- 格式:PPTX
- 页数:53
- 大小:410.23KB
《R语言数据挖掘(第2版)》教学课件—第十二章R的网络分析初步.pptx
《《R语言数据挖掘(第2版)》教学课件—第十二章R的网络分析初步.pptx》由会员分享,可在线阅读,更多相关《《R语言数据挖掘(第2版)》教学课件—第十二章R的网络分析初步.pptx(53页珍藏版)》请在冰点文库上搜索。
第十二章,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=N1,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是一个NN的方阵,反映网络中各节点间的连接情况。
行号和列号为各节点的索引编码无向网络的邻接矩阵:
若节点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是一个N1N2的矩阵,通常不是方阵无向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-核但不属于(m1)-核,只要节点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(kN1,N为节点个数)个节点存在直接连接的网络,规则网络及特点,星形网络:
规则网络有N1个节点均与剩下的一个节点ni直接相连,它们的节点度均等于1,节点ni的度等于N1平衡2-叉树网络:
规则网络除叶节点之外,每个节点都有两个子节点,共有N1条连接。
根节点的度等于2,叶节点的度等于1,其余节点的度都等于3,节点度只可能取1,2,3相关R函数graph.stargraph.tree,随机网络及特点,大规模随机网络的最大特点节点的度分布服从泊松分布网络熵随网络密度的增加呈非线性变化网络密度为0.5的随机网络具有最大的网络熵将包含N个节点和E条连接的随机网络看做是,包含N个节点的空网络随时间t=0,1,2,E推移逐步演变的结果。
每个时刻t均在上个时刻t1的基础上随机挑选一对节点并在其间增加一条连接,经过E步直到添加E条连接为止该规则是E.N.Gilbert提出的,网络称为Gilbert随机网络相关R函数erdos.renyi.game(n=节点数,p.or.m=概率或连接数,type=类型名),随机网络及特点,随机网络的熵网络密度在较高水平或者较低水平时,网络熵快速下降至0。
随机网络并不具有随机性,其度分布与泊松分布相距较大网络密度在0.5时,网络熵到达最大,网络的随机性最高随着网络密度偏离0.5,随机网络就不再那么随机,小世界网络及特点,小世界网络是介于规则网络和随机网络之间的一种网络,一般具有大部分的确定性和少部分的随机性生成WS网络起步于一个规则网络,如k-规则网络对规则网络中的每条连接,以重连概率p,将连接的一端重新连接到随机挑选的节点上最终有Ep条连接进行过重连,余下的(1p)E条连接保持不变WS小世界网络的随机性体现在Ep条随机化的连接中。
其随机性取决于重连概率p,小世界网络及特点,相关R函数watts.strogatz.game(dim=维数,size=节点个数,nei=邻域半径,p=重连概率)随着网络重连概率p的增大,网络熵逐渐增大,网络的平均测地线长度将呈指数下降。
WS小世界网络的度分布较陡,且随重连概率p的增加而逐渐趋于平缓,是个类泊松分布,无标度网络及特点,无标度网络是介于规则网络和随机网络之间的一种网络,一般具有大部分的随机性和少部分的规则性典型的无标度网络是BA网络BA规则的思路:
从一个很小的完备网络开始,每步向现有网络中添加一个节点v和m条连接头节点的选择依据当前网络中的节点度,构造一个关于节点度的线性或非线性函数。
哪个节点的度越高,函数值越大,成为头节点的概率就越高每添加一个节点后,重新计算各节点的度该步骤重复多次,直到网络到达指定的节点规模为止,无标度网络及特点,相关R函数barabasi.game(n=节点个数,m=每个节点添加的连接数)power.law.fit(x=节点度向量)static.power.law.game(no.of.nodes=网络节点数,no.of.edges=网络连接数,exponent.out=参数)度数较低的节点个数较多,hub节点因度数较高数量极少BA网络的熵与网络密度有关。
随着BA规则中参数m的不断增大,网络密度将不断增加,也使网络熵出现非线性的变化,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- R语言数据挖掘第2版 语言 数据 挖掘 教学 课件 第十二 网络分析 初步