杂网络中重要性节点发掘综述.pdf

计算机科学2007V01．34No．12 复杂网络中重要性节点发掘综述* 赫南1李德毅2淦文燕3朱熙1 (北京航空航天大学计算机系 北京100083)1(电子系统工程研究所北京100039)2 (清华大学计算机系 北京100084)3 摘要发掘网络中重要性1节点(边)一直是图论领域的一个基本问题。随着近年来复杂网络研究热潮的兴起，特 别是很多实际网络所抽象出来的复杂网络，表现出了与以往图理论不同的特性，如小世界特性、无尺度特性等。如何 在复杂网络环境下，发掘重要性节点已经成为复杂网络研究的一个基本问题。本文简要介绍了复杂网络的基本概念， 详细总结、分析了在复杂网络环境下几个领域中发掘重要性节点的方法，最后提出了这一领域内几个有待深入研究的 问题和可能的应用方向。 关键词复杂网络，节点重要性，图，相对重要性 VitalNodesin Networks Mining Complex HENanlLI De-Yi2GANWen-Yan3ZHUXiI of ofAeronauticsand (DepartmentComputerScience，BeijingUniversity 100083)1 Astronautics。Beijing ofElectronic (Institute System 100039)2 Engineering，Beijing of Science8L (DepartmentComputer Technology．TsinghuaUniversity．Beijing100084)3 Abstract vital has beenabasic in the of Net— Miningnodes／edgesalways problemGraphTheory．AsstudyComplex workshasbecomemoreandmore thattherearelotsofreal-worldnetworksthatcanbemodeledas hot，especially Networks，whichalsohave differentfromthoseinthetraditional Complex manyimportantproperties GraphTheory。 tO 己唇small-world minevitalnodesin Networkshasbecomeanew- property，scale_freeproperty，etc．HOW Complex bom reviewssomebasic of Networks．summariesand problem．Thispaper