毕业设计（论文）文献综述：基于电阻距离对节点重要度的评判

毕业设计（论文）--文献综述综述题目基于电阻距离对节点重要度的评判专业信息与计算科学姓名学号指导教师基于电阻距离对节点重要度的评判摘要在自然界和人类社会中，复杂网络与复杂系统广泛存在，如蛋白质交互网络、人际关系网、科学家协作网络、交通网络、因特网等。复杂网络往往规模大，数量多，范围广，并且还处于动态演化中，这促使不同领域的学者们去研究它们，其理论研究和应用研究都非常富有吸引力和挑战性，亦有着广阔的应用前景。如今复杂网络的研究成果已经非常丰富了，科学家们还在不断地开发出新的研究方向和应用领域。本论文对网络节点进行重要性评估快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题,现有的节点重要度评估方法对于大型网络而言,计算速度较慢基于电阻距离提出一种快速实用的节点重要度评估方法。关键词：复杂网络；电阻距离；基尔霍夫指数；节点重要度TheresistancedistanceevaluationofnodeimportanceJinglong.Wang(SchoolofMathematicsandPhysics,AnhuiJianzhuUniversity,Hefei230601)AbstractInnatureandhumansociety,widelyexistsincomplexsystemsandcomplexnetworks,suchasproteininteractionnetwork,interpersonalrelationshipnetwork,scientistscooperationnetwork,trafficnetwork.Internetandothercomplexnetworksareoftenlargeinsize,number,range,andalsointhedynamicevolution,whichprompteddifferentscholarstostudythemandthetheoreticalresearchandappliedresearchareveryattractiveandchallenging,butalsohasbroadapplicationprospects.Nowthestudyoncomplexnetworkshasbeenveryrich,scientistscontinuetodevelopnewareasofresearchandapplication.ThispaperonnetworknodesimportanceevaluationquicklyExploretheimportanceofnodespeedhasbecomeoneofthebasicproblemsindatamining,complexnetworks,nodeimportanceevaluationmethodforexistinglargenetworks,andslowcomputationspeedafastandpracticalmethodofnodeimportanceevaluationisputforwardbasedontheresistancedistance.KeywordsComplexnetwork;Resistancedistance;Kirchhoffindex;Rodeimportance

1引言复杂网络发展了那么多年，如今研究复杂网络的理论和方法已经有很多种了。学者们从各种不同的角度对复杂网络进行描述和论证，努力发掘复杂网络的新现象和新性质。于是，复杂网络的新理论和新方法也层出不穷，不甚枚举。目前，已经有相当一部分国内外专家学者发现了一般的网络与电路网络有一定的相似性，具有某种内在的联系，在理论研究上可以相互转化和替代。现在电气技术的发展十分迅速，更新换代也相当快速，电路变得越来越复杂，大型的电路早已呈现出网络形状。学者们逐渐利用电网络的理论及方法来研究一般的网络图和复杂网络，探讨一般的普通网络和电网络之间的对应关系。根据他们先前的工作，一个普通的连通网络可以被表示成为一个相应的电网络。经过不懈的努力，他们得到了电阻距离(resistancedistance)这么一个很有意义的概念。尽管电阻距离是通过电网络而得到的，但它也能很好地应用于一般的普通网络中。电阻距离可以被当作网络上的一个距离度量，同时也是网络的一个很重要的不变量。如同最短路径长度一样，电阻距离也可以在一定的程度上对网络进行刻画。利用电网络和电阻距离，可以更方便地对其他可以类比的网络进行研究，这是一个非常特殊也非常有用的理论工具。到目前为止，关于电阻距离的研究已经有了一定的积累，散见于各类文献中，但主要还是数学和化学方面的学者在研究电阻距离，也并没有形成一个综合性的总结。2基本概念2.1电网络图为了简化描述，又不失一般性，让无向带权图来表示普通的无向连通网络。如果一个网络中的每条边由一个有效的不变电阻代替，电阻的阻值等于边的权值，那么这个网络就被转化为相应的电网络，让无向带权图表示普通的无向连通网络。如果一个网络中每条边都用一个有效且不变的电阻代替，电阻值等于边的权值，那么此网络就可以转化成相应的电网络。2.2电阻距离通过基尔霍夫定律，在一个纯电阻网络里，仍以两节点之间的有效电阻等于这两个节点之间施加一个电压后网络电路中的总电压和总电流的比值。根据欧姆定律，可以得到电阻网络中任意两个节点之间的电阻值，这就是所谓的电阻距离，这是一个新的距离度量。2.3基尔霍夫指数在化学领域，电阻距离被更广泛地研究。如果让节点表示原子，边表示原子间的化学键，那么，就形成了化学领域中的分子网络图。从原子及其之间化学键的关系来，分子网络图大多是含有回路的图，特别是有机化合物的分子图，这种带环的特点使得电阻距离非常适合用于分子网络图结构的数值化描述。因此，电阻距离研究中最著名的成果也首先出现在化学领域，这就是作为化学分子图中结构化描述符的Kirchhoff指数，用来反映化合物的结构特征。Kirchhoff指直接产生于分子结构图，是分子结构数值化表示的一种方式，与化合物的许多性质相关。除此之外，Kirchhoff指数还可以被用来定义高分子的拓扑半径。很显然，Kirchhoff指数的主要研究对象也是含回路的网络图。Kirchhoff指数被定义为网络中任意两点之间的电阻距离之和。2.4节点重要度作为距离度量指标，电阻距离与网络中其他的距离度量有点不太一样，那就是连通网络中任何两个节点之间一定会存在一个确定的电阻距离的值，而不是像权重那样的度量指标只有直接相连的两个节点之间才会有一个数值，这给我们对每个节点进行全面地评估带来了极大的方便。根据第二章中性质所阐述的内涵，如果网络中任意一个节点到其他节点之间的电阻距离越小，则表明它和那个节点之间的路径也就越多，这也说明了它们之间的联系也就越紧密，这也符合欧姆定律的含义。如果把某一个节点到其他所有节点之间的电阻距离进行叠加，这个叠加后的数值越小，则表明了这个节点总体上与其他节点之间的联系也越紧密。这种情况也暗示了相比较而言这个节点处于网络中的地位也就越重要了。如果类比人类社会，人类也与蚂蚁、蜜蜂等一样是社会性群体动物，个体不可能脱离群体而能完全单独地存在。在一个社会圈子里某个社会成员和其他所有人都有紧密联系，说明他/她很受欢迎，很有人缘，大家都喜欢他/她，甚至他/她能做到振臂一呼应者云集，由此也反映出他/她在其所在的社会圈子里的声望很高，也就说他的的重要度比其他社会成员要高。反之，如果一个人与周围许多人都搞不好关系，矛盾重重，冲突不断，给身边的人带来了困扰甚至痛苦，周围的人理所当然会他/她疏远关系，敬而远之，保持一定的距离，这个人自然在其生活圈子里没什么声望，人微言轻，没有号召力、影响力，没有存在感，其的重要度当然就很低了。于是，我们可以说，一个节点到网络中其他所有节点之间的电阻距离之和越小，则它在网络中越重要。如果从相似性度量的角度来说，这也暗示了它与其他所有节点都具有很大的相似性，自然它的的重要度也比其他节点大。电阻距离的重要度评价一个节点的重要程度是通过考虑所有的路径而实现的，不仅仅是只考虑最短路径，这一点从电阻距离的概念本身就能看得出来。这可以算作是电阻距离的重要度的物理意义了，它能体现出信息流在所有路径上流动时节点对信息流的控制能力，也能反映出一个网络的全局和局部属性。4总结对网络节点进行重要性评估快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题,现有的节点重要度评估方法对于大型网络而言,计算速度较慢基于电阻网络提出一种快速实用的节点重要度评估方法,该方法利用节点对网络电能消耗的影响来评估节点的重要度,如果由于一个节点的存在而导致网络平均电能消耗减少则该节点就越重要,反之则该节点重要度就低。节点重要度评估是网络分析的一个基础问题。电力网络中,哪些节点对网络的连通性起到至关重要的作用`病毒和疾病免疫控制过程中,哪些节点的感染会对整个网络造成巨大威胁在线社会网络中谁是网络中最有影响的人物谁是恐怖主义组织的关键人物这些都是极具现实意义的问题当前的主要方法都是基于图论的相关理论和方法来进行节点重要评估。参考文献[1]鲁斌，几类复杂网络度量性质和拓扑性质的研究[D]，华南理工大学，2013.[2]杨玉军，图的电阻距离法则和Kirchhoff指标研究[D]，兰州，兰州大学，2009.[3]李鹏翔，任玉晴，席酉民.网络节点（集）重要性的一种度量指标[J]，系统工程，2004,22（4）：13-20.[4]赫南，李德毅，淦文燕，等.复杂网络中重要性节点发掘综述[J]，计算机科学，2007,34（12）：1-5.[5]王林，张婧婧.复杂网络的中心化[J].复杂系统与复杂性科学，2006,3（1）：13-20.[6]晋建志

复杂网络基于节点重要度的社团探测及社团演化模型研究[D].华中师范大学.2014.[7]陈关荣.复杂网络及其新近研究进展简介[J].力学进展.2008(06):1-10.[8]吕金虎.复杂网络的同步：理论、方法、应用与展望[J].力学进展.2008(06):25-35.[9]蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学.2008(07):55-72.[10]沈华伟,程学旗,陈海强,刘悦.基于信息瓶颈的社区发现[J].计算机学报.2008(04):158-165.[11]李婷婷.组合化学中树的拓扑指数逆问题研究[D].山东大学.2005.[12]侯远.连通图的Wiener指数和度距离的若干性质[D].福州大学.2006.[13]张芩.基于Cayley图与小世界现象的网络拓扑结构研究[D].华南理工大学.2013.[14]吕金虎.复杂网络的同步：理论、方法、