摘 要： 主要讨论树形网络的平均节点介数，刻画了树形网络中具有最大和最小平均节点介数的网络。
关键词： 介数；无圈网；复杂网络
自从20世纪30年代Radcliffe Brown提出社会网络分析概念以来，社会网络分析已经逐步成为一种重要的社会定量研究方法[1]。近年来，随着计算机技术和互联网的飞速发展，如何利用文本挖掘、机器学习等技术面向互联网进行社会网络挖掘和分析成为了一个新的研究课题。随着数据挖掘技术的进步以及计算机处理能力的提高，研究者们分析的社会网络的规模也急剧增大。这些分析和其他现实网络分析一样，面临网络节点规模巨大的挑战。
现实生活中存在的大量复杂系统都可以通过不同的网络加以描述，网络科学已成为众多学科汇聚的交叉点。复杂网络是近几年科学研究发现的一种介于规则网络和随机网络之间的一种更接近于真实网络的网络模型，钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度（无尺度）中部分或全部性质的网络称为复杂网络[2]。随着复杂网络规模的不断扩大，对于各个节点在整个图中所起作用的研究变得迫切，各个节点的作用可以用介数来表示。介数既能刻画图中节点和边的重要性，揭示网络层次结构，又能用来构建基于点介数或边介数的聚类算法，发现图中特殊群体，因此，它一直是研究网络结构性质的一个重要量化手段。首先对于介数的概念要有一定的了解。在复杂网络研究中，研究者不仅要非常客观地关注系统内个体之间的相互作用，而且还要注视系统的整体相互作用，表达这种整体相互作用的概念是介数。介数是一个全局的变量，反映节点或边的作用和影响力，可分为节点介数（Vertex Betweenness）和边介数（Edge Betweenness）两种。节点介数定义为在网络的所有最短路径中，通过节点的最短路径条数称之为节点i的介数[3]；边的介数定义为在网络的所有最短径经过边的介数；网络平均节点介数定义为网络中所有节点介数的平均值；网络平均边介数指网络中所有边介数的平均值。节点的介数在一定程度反映的是节点在网络中的核心作用，节点的介数越大，表明节点的核心作用越强，删除这样的节点会使大量节点对之间的最短路径变长，边的介数也有同样的性质。
本文主要讨论树形网络的平均节点介数，其中节点介数是经过该节点的所有路径，网络平均节点介数是指所有节点介数的平均值。下面举一个具体的例子来分析节点介数和边介数。图1所示中各节点与边的介数可以分别表示如下。
表1中的平均节点介数为4.375，平均边介数为7.25，依据Newman[4]提出的介数新的计算机方法和Brandes算法可以更快地计算出介数。更多的介绍见参考文献[5-7]。
1 树形网络中最大平均节点介数图
随着复杂网络规模的不断增加，节点数目也在不断地增加，对于一些冗余的节点删除变得更加必要，这就需要对于节点的作用给出一个正确的评估，需要了解哪些图形具有最大的平均节点介数，网络结构可以尽可能地向这样的结构变化。本节主要介绍具有最大平均节点介数的网络。
引理1 如图2所示，N1是一棵树，N1′是经过图2的变换得到的，则等号成立当且仅当N1是一条路。
证明 有k个节点的图，如图2所示，图N1中节点A上有p个分支，有n个节点的为分支P1，有m个节点的为分支P2。图N1把分支P1添加到分支P2之后得到图的N1′分支P1+P2。则节点A上变成了P-1个分支。因为分支节点介数与分支结构和总节点个数有关，现在树形图N1和N1′的平均节点介数B（N1）和B（N1′）中，图N1和N1′中除了节点A，分支P1、P2及分支P1+P2的节点介数有变化，其他分支对应节点介数都没有改变。把其他分支节点的介数之和用M表示。
路是各个节点的度不大于2的连通的无圈图，两端的两个点的度为1，中间的各个节点的度均为2。n个节点的路中两端的两个节点为1度的叶子节点，其介数为0。假如第i个节点的介数，i的取值范围是1~n，各个节点的介数可以表示为（n-i）（i-1），其平均介数为：
证明 用归纳法证明如下。
（1）当n=4时，有4个节点的图只有两种形式，即路和星形图，路的节点平均介数为1，星形图的节点平均介数为0.75，星形图有最小平均节点介数，成立。
（2）假设当n<k时，星形图有最小的平均节点介数成立。当n=k时，在树形图中，选择一个度最大的点作为Hub节点，各个分支上选择与Hub节点直接相连的点作为分支的根节点，各个分支的变化情况不影响Hub节点的介数和其他分支上节点的介数，Hub节点的介数和分支个数与分支的节点数有关，各分支的节点数不改变，只要分支不增加或者减少，则Hub节点的介数不变，各个分支上的节点不受其他分支变化的影响。因为当n<k时，星形图有最小的节点平均介数，则各个分支都变为以分支根节点为中心的星形，各个分支有最小平均节点介数，Hub节点的介数不变。最终会有图5所示的图形，这种图形与原图相比，Hub节点的介数没有改变，各个分支节点介数变成了最小。根据引理2可知，把分支上的所有1度点添加到Hub节点上，其总的节点介数和减少，故逐渐把1度节点添加到Hub节点上，其节点介数和一直在减少，直到Hub节点上连接的都是1度点，总的节点介数和无法再减少。可知星形图具有最小的总节点介数和，成立。
综上所述，星形图具有最小的平均节点介数，证毕。
本文主要讨论了在复杂网络中树形网络的平均节点介数最大和最小的网络，对于与之相关节点介数增加和减少给出了两个引理，节点介数是通过该节点的路径数。更多的介数应用和算法分析可以参考文献[9]~[11]。
参考文献
[1] SCOT J. Social network analysis： a handbook（2nd ed）[M]. Sage Publications， 1991.
[2] 张嗣瀛.复杂系统与复杂性科学[EB/OL].http：//news.qdu.edu.cn/newx？newsid=1514，2006-05-05.
[3] 张晓林，袁莉，杨峰，等.基于Web的个性化信息服务机制[J]. 现代图书情报技术， 2001（1）：25-29.
[4] NEWMAN M E J. Scientific collaboration networks.II. shortest paths， weighted networks， and centrality[J]. Phys.Rev.E， 2001， 64（1）.
[5] LEWIS T G.网络科学原理与应用[M].陈向阳，巨修红练，译.北京：机械工业出版社， 2011.
[6] 马杰良，邢雪，安莉莉.基于科研合作网络的节点枢纽特性研究[J].东北电力大学学报，2008，28（2）：72-76.
[7] Zhang Z Z， Zhou S G， Y Qi， et al. Topologies and laplacian spectra of a deterministic uniform recursive tree[J].Eur， Phys， J.B， 2008（63）：507-513.
[8] 唐晋韬，王挺.复杂社会网络的介数性质近似计算方法研究[J].计算机工程与科学，2008，30（12）：9-14.
[9] 王小光，王锋，李森.基于介数影响矩阵的通信网络节点重要度评价方法[J].空军工程大学学报，2012，13（5）：80-84.
[10] 何宇，赵洪利，姚曜，等.介数中心性和平均最短路径长度整合近似算法[J].复杂系统与复杂性科学，2011，8（3）：44-53.
[11] 贾炜，冯登国，连一峰.基于网络中心性的计算机网络脆弱性评估方法[J].中国科学院研究生学报，2012，29（4）：529-535.