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

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

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

1 节点重要性属性

设复杂网络 $G = (V,E)$ 是一个无向无权图，其中 $V = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ 是网络中所有节点的集合， $\left| V \right| = N$ ； $E{\rm{ = \{ }}{e_1}{\rm{,}}{e_2}{\rm{,}} \cdots {\rm{,}}{e_m}{\rm{\} }}$ 是节点间边的集合， $\left| E \right| = M$ ， $A = {a_{ij}} = 1$ ，其中 $A = {a_{ij}} = 1$ 表示节点 $i$ 和节点 $j$ 相连，否则 ${a_{ij}} = {\rm{0}}$ 。在复杂网络中，由于对节点重要性的衡量标准和角度不同，节点中心性指标的定义也各有不同^[17]，这里对所使用的几个节点重要性指标给出以下定义。

1.1 度中心性

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

$D(c) = d(v)$

(1)

式中： $v$ 为节点； $d(v)$ 称为该节点的度。在复杂社会网络中，度中心性定义表明了一个节点对其相邻节点的影响能力，数值越大，在网络中越重要^[2]。

1.2 介数中心性

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

$B(c) = \sum\limits_{} {\frac{{{S_{jk}}(i)}}{{{S_{jk}}}}} $

(2)

式中： ${S_{jk}}$ 表示源节点 $j$ 到目标节点 $k$ 的最短路径数； ${S_{jk}}(i)$ 表示节点 $j$ 和 $k$ 之间经过节点 $i$ 的最短路径数。复杂网络中介数中心性定义认为，如果一个节点是网络中其他节点对之间通信的必经之路，则其在网络中必具有重要地位^[4]。

1.3 紧密度

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

$C\left( c \right) = \frac{{N - 1}}{{\sum\limits_{j = 1}^n {{d_{ij}}} }}$

(3)

式中： ${d_{ij}}$ 表示以节点 $i$ 为起点，以 $j$ 为终点的最短路径中所含边的数量。则节点 $i$ 的紧密度中心性可以表示为网络中节点总数与该节点到其他所有节点距离之和的比值。

1.4 介数中心性

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

1.5 重要性属性权重

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

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

${{{v}}_j} = \frac{{{\sigma _j}}}{{{{\overline x}_j}}}, \quad j = 1,2, \cdots ,m $

(4)

式中： ${v_j}$ 为第 $j$ 项属性的变异系数； ${\sigma _j}$ 为第 $j$ 项属性的标准差； ${\bar x_j}$ 为第 $j$ 项属性的平均值。各项属性的权重为

${{{W}}_j} = \frac{{{v_j}}}{{\sum\limits_{j = 1}^m {{{{v}}_j}} }}$

(5)

所有权值向量 ${{{W}}_j}$ 满足：

${{W}} = ({{{W}}_1},{{{W}}_2}, \cdots ,{{{W}}_m}),\;\;\;\sum\limits_{j = 1}^m {{{{W}}_j}} = 1$

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

${p_{ij}} = \frac{{{q_{ij}}}}{{\max \left| {{q_{ij}}} \right|}}, \quad i = 1,2, \cdots ,n;j = 1,2, \cdots ,m$

(6)

式中 ${q_{ij}}$ 为第 $i$ 个节点第 $j$ 个属性重要性值。根据多属性计算的重要性量值及变异系数权重计算各节点综合重要性，即

$k\left( i \right) = \sum\limits_{j = 1}^n {{w_j}} {p_{ij}}$

(7)

2 算法流程

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

输入　网络图 $G = (V,E)$ ；多属性 ${a_i}$ ；变异系数权重 ${{{W}}_j}$ ；综合关联度 $k\left( i \right)$ ；等级划分及标准正域和正域区间；

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

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 物元建模

以网络节点 ${O_i}$ 为对象， ${c_i}$ 为节点属性特征， ${O_i}$ 关于 ${c_i}$ 的量值 ${v_i}$ 构成的有序三元组 ${M_{\rm{1}}} = (O,{c_i},{v_i})$ 作为描述节点属性量值的基本元，称为一维物元；而网络节点 $O$ 的 $n$ 个特征 ${c_1},{c_2}, \cdots ,{c_n}$ 及 $O$ 关于 ${c_i}(r = 1,2, \cdots ,n)$ 对应的量值 ${v_i}(r = 1,2, \cdots ,n)$ 所构成的阵列^[19]

${M_{\rm{1}}} = \left[ {\left. {\begin{array}{*{20}{c}} {{O_i},}&{{c_1},}&{{v_1}} \\ {}&{{c_2},}&{{v_2}} \\ {}& \vdots & \vdots \\ {}&{{c_n},}&{{v_n}} \end{array}} \right]} \right. = (O_i^{},{c_i},{v_i})$

称为n维物元。其中， ${v_r}(r = 1,2, \cdots ,n)$ 为节点 $O$ 关于重要性特征 ${c_i}(r = 1,2, \cdots ,n)$ 的量值，即各个节点关于各属性的量值。

3.3 标准正域和正域

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

${M_{\rm{2}}}\! =\! ({O_d},{c_j},{v_j}) = \left[ \!\!\!\! {\left. {\begin{array}{*{20}{c}} {{O_d},}&{{c_1},}&{{v_1}}\\ {}&{{c_2},}&{{v_2}}\\ {}& \vdots & \vdots \\ {}&{{c_n},}&{{v_n}} \end{array}}\!\!\!\! \right]} \right. \!=\! \left[\!\!\!\! {\left. {\begin{array}{*{20}{c}} {{O_d},}&{{d_1},}&{ < {a_1},{b_1} > }\\ {}&{{d_2},}&{ < {a_2},{b_2} > }\\ {}& \vdots & \vdots \\ {}&{{d_n},}&{ < {a_n},{b_n} > } \end{array}}\!\!\!\! \right]} \right.$

式中： ${O_d}$ 表示网络节点重要性； ${d_r}(r = 1,2, \cdots ,n)$ 表示对应的等级； $ < {a_{Oxr}},{b_{Oxr}} > (x = 1,2$ ； $r = 1,2,3)$ 表示节点O对于等级特征的量值范围即标准正域，对应的 $ < {a_{xr}},{b_{xr}} > (x = 1,2$ ； $r = 1,2,3)$ 即为正域。

3.4 可拓距

对于节点重要性，取实轴上的任一节点 $x$ 与实域中的任一区间 $X = < a,b > $ 的可拓距^[20]为

${\rho _m}\left( {x,{x_0},X} \right) \!=\! \bigg|x - \frac{{a + b}}{2}\bigg| - \frac{{b - a}}{2} \!=\! \left\{ \begin{array}{l} a - x,\;x \leqslant \dfrac{{a + b}}{{\rm{2}}}\\ x - b,\;x \geqslant \dfrac{{a + b}}{2} \end{array} \right.$

(8)

根据固定节点 ${x_0}$ 在区间的位置的不同，分为左侧可拓距、中点可拓距和右侧可拓距。给定区间 $X{\rm{ = }} < a,b > $ ，当 ${x_0} \in (a,\dfrac{{a + b}}{2})$ ，则 $x$ 与区间 ${X_0}$ 关于 ${x_0}$ 左侧距为

${\rho _l}(x,{x_0},X) = \left\{ \begin{array}{l} a - x,\;x \leqslant a \\ \displaystyle \frac{{b - {x_{\rm{0}}}}}{{a - {x_{\rm{0}}}}}(x - a),\;x \in \langle a,{x_0}\rangle \\ x - b,\;x \geqslant {x_o} \\ \end{array} \right.$

(9)

当 ${x_0} \in (\dfrac{{a + b}}{2},b)$ ，则 $x$ 与区间 ${X_0}$ 关于 ${x_0}$ 右侧距为

${\rho _r}(x,{x_0},X) = \left\{ \begin{array}{l} a - x,\;x \leqslant {x_{\rm{0}}} \\ \displaystyle\frac{{a - {x_{\rm{0}}}}}{{b - {x_{\rm{0}}}}}(b - x),\;x \in \langle {x_0},b\rangle \\ x - b,\;x \geqslant b \\ \end{array} \right.$

(10)

3.5 关联函数

反映各节点重要性量值与其标准正域的隶属程度的函数称为关联函数^[21]。设区间 ${X_{\rm{0}}}{\rm{ = }} < a,b > $ ， $X{\rm{ = }} < c,d > $ 且 ${X_0} \subset X$ ，则 $x$ 关于 ${x_0}$ 及区间 ${X_0}$ 和 $X$ 的关联函数^[20]为式(11)，其中， $\rho (x,{x_0},X)$ 为可拓距。

$k(x) = \left\{ \begin{array}{l} \dfrac{{\rho \left( {x,{x_0},X} \right)}}{{D(x,{x_0},{X_0},X)}},\;D(x,{x_0},{X_0},X) \ne 0{\text{且}}x \in X\\ - \rho (x,{x_0},{X_0}) + 1,\;D(x,{x_0},{X_0},X) = 0{\text{且}}x \in {X_0}\\ 0,\;D(x,{X_0},X) = 0,x \notin {X_0}{\text{且}}x \in X\\ \dfrac{{\rho \left( {x,{x_0},X} \right)}}{{D(x,{x_0},{X_0},\hat X)}},\;D(x,{x_0},X,\hat X) \ne 0{\text{且}}x \in R - X\\ - \rho (x,{x_0},\hat X) - 1,\;D(x,{x_0},X,\hat X) = 0{\text{且}}x \in R - X \end{array} \right. $

(11)

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

可拓集理论可用来描述复杂人际网络节点重要性，尝试刻画节点重要性的动态变化方向。设 $\tilde E(T) = \{ (u,y,{\rm{y'}})|u \in U,y = k(u) \in R$ ； ${T_U}u \in {T_U}U,y' = {T_k}k$ $({T_u}u \in R ) \}$ 为论域 $U$ 上的一个可拓集^[13]， $y = k(u)$ 为 $\tilde E(T)$ 的关联函数，当 $T = ({T_K},{T_U}) = (e,e)$ 时，根据关联函数值把论域分为正域、负域和零界，即： ${V_ + } = \{ u\left| {u \in } \right.U,k(u) > 0\} $ ， ${V_{\rm{ - }}} = \{ u\left| {u \in } \right.U,k(u) < 0\} $ ， ${V_{\rm{0}}} = $ $\{ u\left| {u \in } \right.U,k(u){\rm{ = }}0\} $ 。当 $T = ({T_K},{T_U}) \ne (e,e)$ 时，把论域U划分为关于变换T的正可拓、负可拓、正稳定和负稳定域，分别为

${{{V}}_{\cdot\;\; + } {}}(T) = \left\{ {\left. {u{\rm{|}}u \in U,y = k(u) \leqslant 0;{T_u}(u) \in U,y' = {T_k}k({T_u}u) > 0} \right\}} \right.$

${{{V}}_{\cdot\;\;-}}(T) = \left\{ {\left. {u{\rm{|}}u \in U,y = k(u) \geqslant 0;{T_u}(u) \in U,y' = {T_k}k({T_u}u) < 0} \right\}} \right.$

${V_ + }(T) = \left\{ {\left. {u{\rm{|}}u \in U,y = k(u) > 0;{T_u}(u) \in U,y' = {T_k}k({T_u}u) > 0} \right\}} \right.$

${V_ - }(T) = \left\{ {\left. {u{\rm{|}}u \in U,y = k(u) < 0;{T_u}(u) \in U,y' = {T_k}k({T_u}u) < 0} \right\}} \right.。$

4 实验和分析 4.1 数据集

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

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

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

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

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

4.4 关联度

对3个等级中的每个等级运用关联函数公式计算每个节点与每个等级的关联度(见式(8)~式(11))。这里以节点2为例说明计算过程，因 ${k_2}(p) = 0.{\rm{51}}$ ，有 $\begin{aligned}& {k_{{\rm{2}}{\rm{L}}}}(x) = \frac{{\rho (x,{x_0},X)}}{{D(x,{x_0},{X_0},X)}} = \frac{{0.{\rm{51}} - x}}{{\rho \left( {x,{x_0},X} \right) - \rho \left( {x,{x_0},{X_0}} \right)}}{\rm{ = }}\\ &\qquad \qquad \!\!\!\! \frac{{0.{\rm{51}} - 0.{\rm{32}}}}{{(0.{\rm{00}} - 0.{\rm{51}}) - (0.{\rm{51}} - 0.{\rm{32}})}} = - 0.{\rm{27}}\\ &{k_{{\rm{2}}{\rm{M}}}}{\rm{(x)}} = \frac{{\rho \left( {x,{x_0},X} \right)}}{{D(x,{x_0},{X_0},X)}} = \frac{{0.3{\rm{4}} - x}}{{\rho \left( {x,{x_0},X} \right) - \rho \left( {x,{x_0},{X_0}} \right){\rm{ + }}{a_{012}} - {b_{012}}}}{\rm{ = }}\\ &\qquad\qquad \!\!\!\! \frac{{0.3{\rm{4}} - 0.{\rm{51}}}}{{(0.{\rm{00}} - 0.{\rm{51}}) - (0.3{\rm{4}} - 0.{\rm{51}}){\rm{ + 0}}.{\rm{34}} - {\rm{0}}.{\rm{54}}}} = 0.31\\ &{k_{2{\rm{H}}}}(x) = \frac{{0.{\rm{55}} - 0.{\rm{51}}}}{{(0.{\rm{00}} - 0.{\rm{51}}) - (0.{\rm{55}} - 0.{\rm{51}})}}{\rm{ = }} - {\rm{0}}.{\rm{07}}\end{aligned}$ 最后列表，如表5、表6所示。

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

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

5 结束语

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