论文部分内容阅读
摘 要：发现网络的重要性一直是图论领域的一个基本问题。随着近年来复杂网络研究的兴起，特别是由许多实际网络提取的复杂网络，它们表现出与以往图论不同的特征，如世界特征小，无标度特征。如何在复杂的网络环境中发现重要节点已成为复杂网络研究中的基本问题。本文简要介绍了复杂网络的基本概念，详细总结、分析了在复杂网络环境下几个领域中发掘重要性节点的方法，最后提出了这一领域内几个有待深入研究的问题和可能的应用方向。
关键词：复杂网络；重要节点
1.复杂网络的概念
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述，网络由许多节点和连接节点之间的边缘组成。其中，节点代表真实系统中的不同个体，而边缘代表这些个体之间的连接。通常，当两个节点之间存在某种关系时，连接一个边缘，如果不存在，则边缘连接的两个节点在网络中被视为相邻。当数学研究网络时，它只关心节点之间是否有任何连接边缘。至于节点的位置和边缘的形状，没有必要在意。近年来复杂网络理论的研究越来越热，也开创了很多其他的相关分支，但是一些基本问题仍然值得我们去深入地研究。可视化技术的应用，能够定性地表示出小型网络的层次化结构特征，可以直观地显示哪些节点是相连接的。同样，网络属性的定量映射也是非常重要的，尤其是当网络的规模和复杂性是非常大的，这是非常困难的分析用图形表示的问题。在各种复杂的网络，它是在复杂网络研究的一个基本问题，以找出一个非常大规模的网络，该网络节点（边缘）是最重要的，还是相对于其他节点或节点一个节点的重要性。
2.对社会网络的分析法
社会网络分析的研究在20世纪40年代末就开始了，其中各种主流的方法都有这样一个假设，也就是说，节点的重要性等同于与其他节点的节点的连接，从而使指数的研究不破坏网络的完整性（连接），一般不会考虑节点集的重要性。这些方法中的一个重要的基本思想是，在网络中的不同节点之间重要性差由网络在分析了一些有用的信息而获得，如节点的度，最短路径，节点的重量和边缘。通过对这些基本属性的统计、计算，能相对定量地反映出节点在网络中的位置特性，将网络节点的显著性进行”放大”来定义节点的重要性。其中，已提出的发现重要节点的指标主要分为核心性和声望两大类，度量的方法主要包括节点的度、接近度、介数、信息、特征向量和累计提名等，现简单介绍一下其中几种常见的方法。将网络中的节点按照其度的大小进行排序，可以一定程度上反映节点的重要性。节点的度值越高，则这个节点就越重要，这种方法比较的简单且符合大众心理，但是其缺点也同样明显，仅仅从节点度的大小并不能准确表达网络中节点的重要程度。例如，一个节点的度值虽然很高，但是连接它的其他节点并不重要，则这个节点并不一定非常重要，反之，若一个节点的度值并不是非常高，但是连接它的节点多数都非常重要，则这个节点在网络中可能是个非常重要的节点。例如有些名人的微博写得并不是很好，像记流水账，但是他们的微博在排行榜中却名列前茅，这与他们拥有大量粉丝很有关系。
3.对系统科学的分析法
系统的科学研究方法是利用网络的连通性来反映系统某些功能的完整性，并通过测量节点对网络连接的破坏程度来反映网络节点（集合）的重要性，也就是说，“破坏性等同于重要性，系统科学方法的主要研究成果是系统的”核与核“理论。系统的“核”定义为节点或节点的集合。在系统功能中具有重要或主导作用，并且如果被破坏则导致完全损失或重大损失，“核”的计算由点切集和连接分支的数量来定义。节点（集合）的重要性源于图论中的点切集概念，即定义删除节点（集合）后网络连接损坏的重要性。对网络连接的损害越大，由于维护网络连接取决于它们的存在，因此删除节点（集合）越重要。但该理论的主要目的是了解具有不同连通性的类似连接问题。另外，对于切点中每个节点的重要性，也不能给出明确的等级，不同点割集中节点的重要性也无法横向比较，因为它们的删除都会使系统不再连通。系统中节点（集）的删除除了对系统连通性可能具有破坏，还会影响到系统的一些其他指标，也可以通过计算这些指标的性能变化来度量节点的重要性。类似地，他们也考虑了寻找最短路径上k个最重要的节点的问题，并且给出了一个指数级复杂度的寻找算法。对于k=1的情况，需要O（mn+n2logn）的时间复杂度和O（m）的空间复杂度，其中m和n分别表示系统中边和节点的数量。此外，国外的物理学家和数学家们也提出了一种基于最小生成树的指标，即节点的重要性决定于该节点被删除后系统中最小生成树数量的变化情况，去掉节点以及相关联的边后，所得到的图对应的生成树数量越少，则表明该节点越重要。
4.对信息搜索领域的分析法
互联网可以被看作是一个巨大的图，其中节点代表网页，（有向）边代表网页之间的超链接。在互联网搜索领域，计算机科学家也提出了很多算法来判断网页节点的重要程度，其中近几年来两个最著名、最有代表性的算法是国外科学家Brin和Page在1998年提出的PageRank算法和Kleinberg在同一年提出的HITS算法。此后，互联网的搜索领域也随着Google的成功，越来越受到人们的关注，不断有新的算法和变种提出。Lempel和Moran在2000年提出了SALSA算法，它是HITS算法的一個变种，考虑了用户回退浏览不同页面的情况。其他一些学者也相继提出了另外的算法，如PHITS，Bayesian，Reputation等算法，这些算法实际上都显式或隐式地对网页节点的重要性进行了计算、排序，在实际的应用中极大地提高了检索结果的质量，在发掘网络节点上显得尤为重要。
5.总结
本文介绍了在复杂网络环境下，对复杂网络中节点重要性发掘的几个领域，并对其中重要的方法进行了讨论和分析。主要集中在传统的社会网络、系统科学和源于互联网的信息搜索等领域中的一些算法和思想，指出了其各自的优缺点。另外，相对于全局地评估节点的重要性方法，在最后也介绍了复杂网络中节点的相对重要性分析。总的来说，社会网络分析方法的核心思想是”重要性等价于显著性”，对网络中重要节点的发掘不以破坏网络的整体性为基础。分析网络中节点的重要性，对于网络的安全防护等应用具有非常重要的意义。特别是现实世界中很多网络都具有复杂网络的特性，如小世界、无尺度、幂律分布等特性，在复杂网络的环境中，发掘网络中节点的重要性显得更加重要。
作者简介：
钱宇锋（1986.2--），男，汉族，湖北武汉人，讲师，博士，主要从事复杂系统与复杂网络，应用数学研究
（作者单位：湖北工业大学理学院）
关键词：复杂网络；重要节点
1.复杂网络的概念
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述，网络由许多节点和连接节点之间的边缘组成。其中，节点代表真实系统中的不同个体，而边缘代表这些个体之间的连接。通常，当两个节点之间存在某种关系时，连接一个边缘，如果不存在，则边缘连接的两个节点在网络中被视为相邻。当数学研究网络时，它只关心节点之间是否有任何连接边缘。至于节点的位置和边缘的形状，没有必要在意。近年来复杂网络理论的研究越来越热，也开创了很多其他的相关分支，但是一些基本问题仍然值得我们去深入地研究。可视化技术的应用，能够定性地表示出小型网络的层次化结构特征，可以直观地显示哪些节点是相连接的。同样，网络属性的定量映射也是非常重要的，尤其是当网络的规模和复杂性是非常大的，这是非常困难的分析用图形表示的问题。在各种复杂的网络，它是在复杂网络研究的一个基本问题，以找出一个非常大规模的网络，该网络节点（边缘）是最重要的，还是相对于其他节点或节点一个节点的重要性。
2.对社会网络的分析法
社会网络分析的研究在20世纪40年代末就开始了，其中各种主流的方法都有这样一个假设，也就是说，节点的重要性等同于与其他节点的节点的连接，从而使指数的研究不破坏网络的完整性（连接），一般不会考虑节点集的重要性。这些方法中的一个重要的基本思想是，在网络中的不同节点之间重要性差由网络在分析了一些有用的信息而获得，如节点的度，最短路径，节点的重量和边缘。通过对这些基本属性的统计、计算，能相对定量地反映出节点在网络中的位置特性，将网络节点的显著性进行”放大”来定义节点的重要性。其中，已提出的发现重要节点的指标主要分为核心性和声望两大类，度量的方法主要包括节点的度、接近度、介数、信息、特征向量和累计提名等，现简单介绍一下其中几种常见的方法。将网络中的节点按照其度的大小进行排序，可以一定程度上反映节点的重要性。节点的度值越高，则这个节点就越重要，这种方法比较的简单且符合大众心理，但是其缺点也同样明显，仅仅从节点度的大小并不能准确表达网络中节点的重要程度。例如，一个节点的度值虽然很高，但是连接它的其他节点并不重要，则这个节点并不一定非常重要，反之，若一个节点的度值并不是非常高，但是连接它的节点多数都非常重要，则这个节点在网络中可能是个非常重要的节点。例如有些名人的微博写得并不是很好，像记流水账，但是他们的微博在排行榜中却名列前茅，这与他们拥有大量粉丝很有关系。
3.对系统科学的分析法
系统的科学研究方法是利用网络的连通性来反映系统某些功能的完整性，并通过测量节点对网络连接的破坏程度来反映网络节点（集合）的重要性，也就是说，“破坏性等同于重要性，系统科学方法的主要研究成果是系统的”核与核“理论。系统的“核”定义为节点或节点的集合。在系统功能中具有重要或主导作用，并且如果被破坏则导致完全损失或重大损失，“核”的计算由点切集和连接分支的数量来定义。节点（集合）的重要性源于图论中的点切集概念，即定义删除节点（集合）后网络连接损坏的重要性。对网络连接的损害越大，由于维护网络连接取决于它们的存在，因此删除节点（集合）越重要。但该理论的主要目的是了解具有不同连通性的类似连接问题。另外，对于切点中每个节点的重要性，也不能给出明确的等级，不同点割集中节点的重要性也无法横向比较，因为它们的删除都会使系统不再连通。系统中节点（集）的删除除了对系统连通性可能具有破坏，还会影响到系统的一些其他指标，也可以通过计算这些指标的性能变化来度量节点的重要性。类似地，他们也考虑了寻找最短路径上k个最重要的节点的问题，并且给出了一个指数级复杂度的寻找算法。对于k=1的情况，需要O（mn+n2logn）的时间复杂度和O（m）的空间复杂度，其中m和n分别表示系统中边和节点的数量。此外，国外的物理学家和数学家们也提出了一种基于最小生成树的指标，即节点的重要性决定于该节点被删除后系统中最小生成树数量的变化情况，去掉节点以及相关联的边后，所得到的图对应的生成树数量越少，则表明该节点越重要。
4.对信息搜索领域的分析法
互联网可以被看作是一个巨大的图，其中节点代表网页，（有向）边代表网页之间的超链接。在互联网搜索领域，计算机科学家也提出了很多算法来判断网页节点的重要程度，其中近几年来两个最著名、最有代表性的算法是国外科学家Brin和Page在1998年提出的PageRank算法和Kleinberg在同一年提出的HITS算法。此后，互联网的搜索领域也随着Google的成功，越来越受到人们的关注，不断有新的算法和变种提出。Lempel和Moran在2000年提出了SALSA算法，它是HITS算法的一個变种，考虑了用户回退浏览不同页面的情况。其他一些学者也相继提出了另外的算法，如PHITS，Bayesian，Reputation等算法，这些算法实际上都显式或隐式地对网页节点的重要性进行了计算、排序，在实际的应用中极大地提高了检索结果的质量，在发掘网络节点上显得尤为重要。
5.总结
本文介绍了在复杂网络环境下，对复杂网络中节点重要性发掘的几个领域，并对其中重要的方法进行了讨论和分析。主要集中在传统的社会网络、系统科学和源于互联网的信息搜索等领域中的一些算法和思想，指出了其各自的优缺点。另外，相对于全局地评估节点的重要性方法，在最后也介绍了复杂网络中节点的相对重要性分析。总的来说，社会网络分析方法的核心思想是”重要性等价于显著性”，对网络中重要节点的发掘不以破坏网络的整体性为基础。分析网络中节点的重要性，对于网络的安全防护等应用具有非常重要的意义。特别是现实世界中很多网络都具有复杂网络的特性，如小世界、无尺度、幂律分布等特性，在复杂网络的环境中，发掘网络中节点的重要性显得更加重要。
作者简介：
钱宇锋（1986.2--），男，汉族，湖北武汉人，讲师，博士，主要从事复杂系统与复杂网络，应用数学研究
（作者单位：湖北工业大学理学院）