网络中节点重要性评价ppt课件.ppt

网络中节点重要性评价,zdh4.9,方法,社会网络分析：点度中心度（度）中间中心度（介数）网络流中心性接近中心度（紧密度）特征向量中心度子图中心性,复杂网络：随机行走介数聚集性节点删除法节点融合法节点孤立法节点收缩法Pagerank法和HITS法,社会网络分析,点度中心度（Degree Centrality） 1.定义 指的是该点的度数，即与该点直接相连的点的个数。在无向图中是点的度数，在有向图中是点入度和点出度之和。 2.意义 分析节点直接影响力，即考察此人的直接社会关系。,社会网络分析,3.计算设网络具有 n个节点，k为节点度，则节点i的度数中心度为：,社会网络分析,中间中心度（Betweenness Centrality ）1.定义一个点Y 相对于一个点对X 和Z 的中间中心度指的是该点处于此点对的捷径上的能力。经过点Y 并且连接这两点的捷径占这两点之间的捷径总数之比。 2.意义分析该节点对网络信息流动的影响，即考察此人的社交能力或对于社会网络中信息流动的影响力。,社会网络分析,3.计算用gst,i 表示节点对s和 t最短路径经过i点的路径数，nst表示节点s和节点t之间存在所有最短路径的路径数，则节点i的中间中心度：,复杂网络,网络流中心性（Flow Centrality)1.定义是按照节点在网络流中起到的作用来衡量节点的重要性，他只强调节点的参与程度，而不要求一定是最优化，因此他只是中间中心性方法的一种推广，把节点对其他非最短路策略下的参与也计算在内。,复杂网络,2.意义与中间中心度相同3.计算g (st)表示网络中节点对(s，t)之间的所有路径数，不包含回路,gi (st)表示节点对(s，t)之间经过节点i的路径数。,社会网络分析,接近中心度（Closeness Centrality） 1.定义是指该点与图中所有其它点的捷径距离之和。2.意义分析节点通过社会网络对其它节点的间接影响力，即考察此人的间接社会关系。,社会网络分析,3.计算,社会网络分析,特征向量中心度（Eigenvector centrality ）1.定义节点的中心化测试值由周围所有连接的节点决定，即一个节点的中心化指标应该等于其相邻节点的中心化指标之线性叠加。2.意义分析这种通过与具有高度值的相邻节点所获得的间接影响力,社会网络分析,3.计算在Ucinet中，执行NetworkCentralityEigenvetor。,社会网络分析,子图(subgraph centrality)1.定义是对节点度中心性的改进，基于节点对所在网络局部子图的参与程度来确定节点的重要性。 2.计算,复杂网络,复杂网络是近几年科学研究发现的一种介于规则网络和随机网络之间的一种更接近于真实网络的一种网络模型。复杂网络最典型的特征是小世界现象和无标度特征。小世界现象说明了规模很大的网络的任意两个节点之间存在最短路径；无标度特征则揭示了真实网络的结构符合幂率分布的事实。,复杂网络,引文网络是复杂网络复杂网络中许多发现重要节点的方法可以用到引文网络中发现重要文献,复杂网络,随机行走中心性（Random Walk Centrality）1.定义随机行走模型的提出基于一个多数网络的事实，网络节点对网络的整体特性是未知的，这样就使得对整体网络选择最优不可能,复杂网络,2.计算(a)构建关系矩阵L=D-A其中，A为目标网络的邻接矩阵，D为节点度组成的对角矩阵(b)变换矩阵，把L矩阵去掉最后一行和最后一列，变成可逆矩阵(c)求L矩阵的逆矩阵L-1。，在L 基础上添加元素全为0的一行一列，构成新矩阵T,复杂网络,复杂网络,节点删除法：利用网络的连通性来反映系统某种功能的完整性。通过度量节点(集)被删除后对网络连通的破坏程度来定义其重要性的。即“破坏性等价于重要性”。对网络连通的破坏程度越大，被删除的节点(集)越重要。,复杂网络,系统中节点(集)的删除还会影响到系统的一些其他指标，也可以通过计算这些指标的性能变化来度量节点的重要性。如 Chen等人提出了一种基于最小生成树的指标，即节点的重要性决定于该节点被删除后系统中最小生成树数量的变化情况。去掉节点以及相关联的边后，所得到的图对应的生成树数量越少，则表明该节点越重要。,复杂网络,节点融合法（节点收缩法）将节点的平均路径和节点个数乘积的倒数定义为网络凝聚度，用每个节点融合后的网络凝聚度来评价节点重要性。网络凝聚度越大，重要性越高。,复杂网络,节点孤立法当某个节点在被破坏或是失效时，该节点无法与其他节点连通，但是不能像其他节点融合法或是节点删除法那样，忽略它对网络的影响。因为其他节点仍然尝试与该节点连通，会增加一定的网络负担，使得网络通信的总路径增加。,复杂网络,信息搜索领域、互联网PageRank算法HITS算法,