1、复杂网络节点重要性评价研究复杂网络节点重要性评价研究 答辩人：何建军 导 师：曾庆光、李仁发 教授提纲o 一、研究内容o 二、研究意义o 三、主要工作o 四、学术论文一、研究内容o 本文主要研究复杂网络节点重要性评价方法n 基于节点相似度贡献的节点重要性评价算法n 基于场论模型的节点重要性评价算法n 基于节点重要性的网络演化模型o 目的:更有效准确地发掘网络中重要的节点。二、研究意义o 政治领域：政治领域：恐怖分子，迅速定位犯罪团伙网络的头目，捉拿逮捕其关键人物。o 社会领域：社会领域：传染病（如艾滋病、非典、禽流 感，甲型流感等），有针对性地先治疗、隔离病源，从而有效地防止疾病的传播，将损失
2、降到最低限度。o 信息技术领域：信息技术领域：搜索引擎（百度&谷歌）三、主要工作基于相似度贡献的节点重要性评价算法基于场论模型的节点重要性评价算法基于Sim-NodeRank网络演化模型基于FieldTheory-NodeRank网络演化模型第三章第三章第四章第四章第五章第五章应用应用基于相似度贡献的节点重要性评价算法Pagerank算法：PR(1)=(1/5)*PR(2)PR(2)=PR(1)+(1/2)*PR(3)+(1/2)*PR(4)+(1/3)*PR(5)PR(3)=(1/4)*PR(2)+(1/2)*PR(6)ijjNjPRiDiPR)()()1()()(TNeNeD1 1,1,1
3、,)(算法步骤(Sim-NodeRank)节点相似度矩阵构造 o 如果节点a的邻接节点b和节点c相似，那么节点a也与节点c相似。文献Vertex similarity in networks vijvjivijSASEASS1AES为节点相似度矩阵是单位矩阵，SE概率转移矩阵构造 o 对节点相似度矩阵进行归一化处理得到概率转移矩阵。（前图）NodeRank值计算o 采用Floyd-warshall算法求取中心度)()1(11nntranClosenessSumClosenessNodeRankMNodeRank实验结果及分析o 选择三个常用的网络数据：真核细胞新陈代谢网络 艾滋病患者性关系网络
4、 空手道俱乐部网络真核细胞新陈代谢网络 艾滋病患者性关系网络 空手道俱乐部网络 基于场论模型的节点重要性评价算法重新构造概率转移矩阵：节点之间相互作用力越大，跳转的概率也就越大；相互作用力越小，跳转的概率也就越小节点间的距离：节点间的相似度质量：节点度 rMrMKFabba3算法步骤(FieldTheory-NodeRank)真核细胞新陈代谢网络 艾滋病患者性关系网络 空手道俱乐部网络 基于节点重要性的网络演化模型BA网络演化模型（增长+优先连接）优先连接：采用“度”来衡量网络中存在的节点被新加入节点选中的概率:jjiikk基于节点重要性的网络演化模型分别采用Sim-NodeRank和Fiel
5、dTheory-NodeRank节点重要性评价方法来代替度衡量方法，改写节点连接机制公式。网络中存在的节点被新加入节点选中的概率:代替代替jijNodeRankiNodeRank)()(jjiikk实验结果及分析比较的物理动力学特性：节点度概率分布节点度概率分布:P(k)一个随机选定的节点的度恰好为k的概率平均路径长度平均路径长度:任意两个节点之间距离的平均值 聚类系数聚类系数:你的两个朋友很可能彼此也是朋友；一个节点有K个邻 居节点，这K个节点之间最多有K(K-1)/2条边，实际 存在的边数为E，则这个节点的聚类系数值等于E和 K(K-1)/2之比。网络平均度网络平均度:网络所有节点度的平均值度分布(BA Model;N=1000,m=m0=2,4,6 8)度分布(Sim-NodeRank)度分布(FieldTheory-NodeRank)平均路径长度(m=m0=7)平均路径长度(m=m0=7)聚类系数(m=m0=7)聚类系数(m=m0=7)网络平均度(m=m0=7)网络平均度(m=m0=7)三、学术论文o 何建军，李仁发.一种改进的基于随机游走模型的排序方法.计算机工程与应用Thats AllThanks
