中心度算法演示PPT课件

中心度算法示例两个简单的例子用网络图表示三个计算过程度数中心性、中介中心性和接近中心性,1,-,例子一：,2,-,例子一,度数中心性原理：各个节点直接相连节点数节点计算1（直接连接了节点2、3、4）共32（直接连接了节点1、3）共23（直接连接了节点1、2）共24（直接连接了节点1）共1,试验结果,3,-,例子一,中介中心性原理：找到节点作为连接其他节点所在最短路径，计算有多少条，并用总和除以2.（去除双向重复）节点1：不包括节点1本身与其他点的直接相连。节点1在2到4、4到2的最短路径上，在3到4、4到3的最短路径上。共四条最短路径。(1+1+1+1)/2=2.节点2等：它不能起到连接其他节点最短距离作用，如3到4的最短路径、4到3的最短路径等，都不必须经过节点2.所以节点2的中介中心性为0。节点3、4同理。,试验结果,4,-,例子一,接近中心性原理：某节点到其他节点的最短距离和节点1到节点2、3、4的最短距离都是1，所以总和为1+1+1=3。节点2到1、3的最短距离都是1，到节点4的最短距离是2，所以总和为1+1+2=4。节点3与2对称，所以同理可得。节点4到节点1距离为1，到节点2、3距离都是2，所以总和为2+2+1=5,试验结果,5,-,例子二：,6,-,例子二,度数中心性原理：各个节点直接相连节点数节点计算1（直接连接了节点2、3）共22（直接连接了节点1、4）共23（直接连接了节点1、4）共24（直接连接了节点2、3、5）共35（直接连接了节点4）共1,试验结果,7,-,例子二：中介中心性,原理：找到节点作为连接其他节点所在最短路径，计算有多少条，并用总和除以2.（去除双向重复）。节点1在2到3的最短路径上，在3到2的最短路径上，共2条最短路径。但由于节点1不是2到3,或者3到2之间的最短路径的唯一连接点（节点4可以取代1），所以总数还要除以2.计算：(1+1)/2/2=0.5.节点2在1到4、4到1、5到1、1到5最短路径上。共四条最短路径。但由于节点2不是1到4,或者1到1、1到5、5到1之间的最短路径的唯一连接点（节点3可以取代2），所以总数还要除以2.计算：4/2/2=1.（4代表4条最短路径，除以第一个2去是掉双向，再除以2是考虑节点2不是唯一连接点。）节点3与2对称同理，所以节点3的中介中心性也是1。节点4在2到5、5到2、5到3、3到5、1到5、5到1、2到3、3到2的最短路径上。共8条最短路径。节点4是2-5,3-5，1-5之间的最短路径的唯一连接点。但由于节点4不是2、3之间的最短路径的唯一连接点（节点1可以取代4），所以连接2-3之间这部分要减半，变成计为1.总数是（6+1）/2=3.5。,试验结果,8,-,例子二,接近中心性原理：某节点到其他节点的最短距离和节点1到节点2、3的最短距离都是1，节点1到节点4、5的距离分别是2和3，所以总和为1+1+2+3=7。节点2到1、4的最短距离都是1，到节点3、5的最短距离都是2，所以总和为1+1+2+2=6。节点3与2对称，同理可得。节点4到节点2、3、5的最短距离都为1，到节点1距离都是2，所以总和为1+1+1+2=5节点