可拓聚类的科教人际网络节点重要性动态分析方法

严家萌，许立波，李兴森，庞超逸，董瑞辰

（1. 浙江大学 工程师学院，浙江 杭州 310015; 2. 浙江大学 宁波理工学院 计算机与数据工程学院，浙江 宁波315100; 3. 广东工业大学 可拓学与创新方法研究所，广东 广州 510006; 4. 北京邮电大学 国际学院，北京100876）

随着技术的进步，交流的频繁，人们的社会活动日益网络化，各种各样的复杂网络随之充斥着我们的生活。复杂网络[1]具有结构复杂、网络进化、连接复杂、节点多样和动力学复杂性等特征，以及小世界、集群和幂律(power law)等现象。复杂网络拓扑图上各节点的复杂性，也决定了网络中每个节点的重要性程度存在差异，寻找出这些网络中的关键节点，有针对性地分析其性质并进行有效利用有着重要意义[2]。例如：对社交网络中热点问题的挖掘，科研合作网中影响力因子认定，交通网络拥堵路段识别，电力网络用电高峰管理，信息传播机制的发现，舆论倾向性的研究，犯罪网络的侦察等都离不开节点重要性这个基本问题。发现重要的节点，有助于参透舆论热点和预测信息传播规律，以及把握扩散方向和对关键的认定，趋利避害为人们所利用。

在复杂网络中，对节点影响力重要性的评估得到了广泛而深入的研究，这些研究从不同角度对节点的重要性刻画给出了可行性分析与探索。目前，经典的关键节点中心性测量指标可被用来对节点的传播影响力进行评估，包括度中心性(degree centrality)[3]、介数中心性(betweenness centrality)[4]、紧密度指标 (closeness centrality)[5]、KShell (KS指标)[6]等，总之，这些都是基于属性和网络位置的方法。文献[7]利用度中心性来测量最有影响力的节点，在符合幂律的非均匀网络中度数较大的节点的传播影响力相对较大。文献[8]利用介数中心性来评价社会网络影响力，以其经过某个节点的最短路径的数目来刻画节点的重要性。文献[9-10]利用紧密度指标刻画某个节点到其他节点的难易程度。文献[11-12]提出通过KShell (KS)分解来确定最具有影响力的单源节点。总体看来，这些评估方法虽然可行有效，但大都是静态地刻画和测量复杂网络节点重要性，而对其动态变化趋势和演化效果却极少提及。

可拓学[13]是通过定性和定量相结合的手段去智能化处理矛盾问题的新兴学科，近几年来在模式识别[14]、决策分析[15-16]、问题求解等研究领域有着广泛的应用。其中可拓集理论是研究事物动态性和可变性的有力工具，据此本文提出一种基于可拓聚类的复杂人际网络节点重要性分析方法，尝试从动态上对网络节点影响力变化趋势做出判断。

1 节点重要性属性

1.1 度中心性

在静态网络中，节点度是指与其直接连接的节点个数。度中心性用于描述节点在整个网络中所产生的影响力，用D(c)表示为，即

1.2 介数中心性

介数中心性刻画了网络中节点对于信息流动的影响力[18]，反映了相应的节点在整个网络中的作用，介数中心性的值越高, 则该节点的影响力越大, 相应地也就越重要。节点介数定义为网络中任意两个节点间最短路径总数与最短路径中经过该节点的路径的数目的比例的倒数，节点的介数定义为

1.3 紧密度

在一个社会网络中，紧密度[9]用于刻画节点到达其他节点的难易程度，其值越大，表明到达其他节点越容易，节点越居于网络中心位置，相应地也就越重要，具体用表示，即

1.4 介数中心性

K-Shell是图论里一个经典的概念，是一种粗粒化的节点重要性分类方法。操作上K-Shell相当于剥去最外面一层壳，首先去除网络中度数小于的所有节点及其连边；如果在剩下的节点中仍有度值小于的节点，那么就继续去除这些节点，直至网络中剩下的节点的度值不小于。依次取=1, 2, ···, n，就得到了该网络的 K-Shell分解[18]，依此类推，直到复杂社会网络中所有的节点都被赋予K-Shell值。

1.5 重要性属性权重

节点多属性不同指标从不同的角度探讨了节点在复杂网络中的重要程度，但由于实际的网络尤为复杂，仅依赖于单一指标来判断某个节点在网络中的影响力具有很大的片面性[2]。而如果将某些单一指标简单叠加或者平均，并不能保证取得良好的效果，因为各个指标在度量节点重要性时权重有所不同，侧重点各异。这就需要进行多属性关联考虑，将多个重要性评价指标作为该节点的属性，通过计算各个属性的权重比例，最后得到该节点的综合重要性量值。

权系数反映了单个样本对整体结果的重要程度，在复杂社会网络中，动态分析节点重要性变化时，会出现影响力量值整体同方向变化情况，此时便会影响对结果的判断。因此，根据网络节点重要性量值的变化程度来设置各自的权值，比等权值、主观赋权值等更加合理。变异系数法是直接利用各属性所包含的信息通过计算得到的，为了消除各属性值的不同影响，需要用各项属性值的变异系数来衡量各项属性取值的差异程度。各项属性值的变异系数公式为

根据多属性量值的计算，将每个节点在对应的属性上的取值规范化，即

2 算法流程

算法 人际网络可拓聚类动态算法

输出 各节点重要性等级，关联度变化。

1)根据原始数据构建人际关系网络图，每个个体人作为网络节点，人与人熟识与否决定是否有边；

2)根据式(1)～(3)包括度中心性、介数中心性、紧密度、K-Shell值计算每个节点的各重要性属性值；

3)根据节点的各重要性属性值，按式(4)、式(5)采用变异系数法计算各重要性属性权重；

4)根据式(7)计算每个节点的每个重要性属性值与权重的乘积，得到该节点的综合重要性度量值；

5)划分等级(L、M、H)，根据实际需要取每个等级的标准正域和正域区间；

6)计算每个节点重要性值关于每个等级的关联度，关联度值最大的等级为该节点的重要性等级；

7)在第二时间点上，对变化后的节点网络，重复 3)～6)。

8)比较两个时点每个节点重要性等级变化，并给出变化论域。

3 可拓模型构建

3.1 建模机制

可拓聚类模型首先将根据多属性计算各节点重要性，结合变异系数权重值求得综合重要性，之后根据实际需要划分等级个数，统计每个等级节点重要性的取值范围构成标准正域区间，而在全体数据中的取值范围为正域区间。然后通过关联函数计算每个节点与每个等级的关联度，取关联度值最大的等级为该节点等级。最后得到各节点不同时间点的关联度，进而从动态的角度来分析节点重要性变化情况。

3.2 物元建模

3.3 标准正域和正域

根据需要划分节点重要性为高、中、低3个等级(L、M、H)，分别统计出各等级取值范围作为标准正域区间，全局取值范围作为正域区间。

3.4 可拓距

3.5 关联函数

反映各节点重要性量值与其标准正域的隶属程度的函数称为关联函数[21]。设区间，的关联函数[20]为式(11)，其中，为可拓距。

3.6 节点重要性变化可拓学解释

可拓集理论可用来描述复杂人际网络节点重要性，尝试刻画节点重要性的动态变化方向。设为论域上的一个可拓集[13]，为的关联函数，当时，根据关联函数值把论域分为正域、负域和零界，即：U划分为关于变换T的正可拓、负可拓、正稳定和负稳定域，分别为

4 实验和分析

4.1 数据集

实验数据来自Freeman观测的由美国国家科学基金会赞助的计算机会议参加者构成的社会网络，该网络呈现出复杂网络的基本特征。会议的参加者都是社会网络研究领域从事新兴学科的研究者，在利用图这一数据结构抽象时，通过熟识与否来定义网络的边取值，选取其中32个人构成的网络数据作为实验数据，并在两个时间点上进行了测量其网络变化，两个时间点间距9个月。

4.2 节点重要性及权重系数计算

根据前文选取多属性测量节点重要性的分析，分别计算度中心性(式(1))、介数中心性(式(2))、紧密度(式(3))以及K-shell分解的重要性量值，并标准化(式(6))，再根据式(4)、式(5)计算各个属性变异系数权重，最后根据式(7)取其值为该节点的综合重要性量值，如表1所示。表2为第二个时间节点的各属性重要性量值及综合重要性量值。

表1 第一时间节点重要性及变异系数Table 1 First time node importance and variation coefficient

表2 第二时间节点重要性及变异系数Table 2 Second time node importance and variation coefficient

4.3 等级划分及标准正域与正域

为探究节点重要性变化情况，在分析节点重要性时分为3个等级(高(High)、中(Middle)、低(Low))。根据多属性和变异系数权重计算每个节点综合重要性量值，取其最低20%为低影响力节点，最高20%为高影响力节点，中间60%为中间节点。在每个等级量值中取标准正域区间，在全局量值上取正域区间，结果见表3、4。

表3 第一时间节点影响力等级划分及(标准)正域Table 3 First time node importance level and (standard)positive domain

表4 第二时间节点影响力等级划分及(标准)正域Table 4 Second time node importance level and (standard)positive domain

4.4 关联度

对3个等级中的每个等级运用关联函数公式计算每个节点与每个等级的关联度(见式(8)～式(11))。这里以节点2为例说明计算过程，因

最后列表，如表5、表6所示。

表5 第一时间点各等级上的关联度Table 5 Relevance at each level of the first time

表6 第二时间点各等级上的关联度Table 6 Relevance at each level of the second time

4.5 节点重要性动态变动结果

根据以上计算结果，每个节点最大关联度值对应等级即为该节点所属等级，列表见表7(T1为第一时间点，T2为第二时间点)。从表7中能直观地看出每个节点的等级变化情况，这里根据可拓集理论，给出了每个节点的可拓论域变化类型。表7中，“稳定”表示节点影响力重要性等级不变，“可拓”表示其等级有所改变，“负”表示节点重要性下降，“正”表示上升。例如，对于n2节点，在第一时间点高等级关联度只有-0.07，而到第二时间点为0.04，所以其由中间等级M(middle)变为高等级H(high)，即为可拓域，关联度由负变为正，所以称之为正可拓域，亦即说明在人际网络中经过一段时间后其节点重要性提高了，影响力变大。

表7 节点重要性变化情况Table 7 Change in node importance

5 结束语

人际网络可以采用图这一数据结构抽象，然后计算每个节点在多个重要性属性上的值，根据变异系数权重法取得该节点的综合重要性，此方法克服了单一属性的片面性。而可拓聚类方法，首先通过聚类分析划分节点集合若干等级，构造标准正域和正域区间，根据关联函数计算每个节点与每个等级集合的关联度，关联度值最大的等级即为该节点所属重要性等级，最后在两个时间点上比较等级变化情况，给出可拓论域解释。利用可拓聚类方法尝试对节点重要性变化的动态把握，使网络节点及各指标均能以形式化的模型更直观地展现。接下来工作将会在更大数据集和更复杂类型网络进一步验证可拓聚类方法的有效性，以及对其方法本身进行改进等。