开放科学（资源服务）标志码（OSID）：

0 概述

人类社会是一个类似混沌系统的复杂系统，几乎所有的人类社会现象和自然现象均可利用社交网络、生物网络等复杂网络模型进行描述。复杂网络内部结构错综复杂，存在少数关键核心节点，核心节点的微小扰动会引起网络的系统性涨落，甚至导致网络彻底崩溃。注意力流网络^[1-3]是近年来兴起的一个新型的复杂网络，由在线用户在不同信息源上连续的点击行为构成，其中，节点表示用户点击的信息源，边表示用户从一个信息源到下一个信息源的跳转，将人类的注意力看作抽象流动的物质。在注意力流网络研究领域，研究人员在前期研究中已发现多个演化普适模式，包括异速标度律、耗散律、引力定律和heaps律等^[4-6]。LI等^[2]基于在线集体注意力流，研究网站的影响力。WU等^[3]分析了复杂网络上点击流的分散流结构。SHI等^[7]提出一种在不同网站之间分配和流动集体注意力的几何表示方法。GU等^[8]提出一种基于流的几何嵌入及其数值近似改进算法，根据流距离定义的节点中心性对站点进行排名。

扩散模型用于度量节点的传播影响力^[9-10]并可对节点重要性进行排序，主要包括阈值模型^[11]、级联模型^[12-13]、流行病模型^[14-15]等模型。但是，在大型复杂网络中使用扩散模型度量节点的传播能力并对节点进行排序非常耗时。针对这一问题，近年来研究人员提出了多种节点排序的方法。这些方法主要分为结构化方法和超结构化方法，在结构化方法中节点的传播能力仅基于拓扑位置，在超结构化方法中除了节点拓扑位置外，还考虑了个体特征、用户兴趣等因素。由于对额外信息的需求较低，并且节点的传播能力仅基于网络结构确定，因此结构化方法受到了更多的关注。根据网络结构中使用的信息类型，结构化方法又分为局部、半局部、全局和混合方法。局部结构化方法仅依赖节点及其邻居来度量其影响力，如度中心性^[16]和H-index中心性^[17]。半局部结构化方法除了邻居的信息之外，还使用二阶邻居来度量节点的传播能力，如权重度中心性和扩展权重度中心性^[18]。全局结构化方法需要遍历整个网络获取全局信息来度量节点的影响力，如紧密中心性^[19]、中介中心性^[20]、核数中心性^[21]和K-Shell。混合结构化方法利用局部和全局信息来度量节点传播能力，如混合度分解^[22]、邻域核数^[23]、K-Shell迭代因子^[24]和混合核心、度和熵^[25]。除了上述结构化方法外，还有一些度量节点传播能力的博弈论模型。文献[26]考虑网络结构，使用合作博弈论提出多种节点中心性度量方法。文献[27]将节点传播能力的度量问题建模为非合作博弈问题，并根据该模型度量节点的传播能力。

网络中通过连接不同子网络的关键节点维持整个网络的凝聚力，对信息流动或控制十分关键。现有的关键节点识别方法多数仅关注单个或局部节点，很少从网络整体性、系统性上探讨节点影响力，而且这些方法多数是针对无向无权网络，关于有向加权网络节点影响力的层级性^[28]研究较少。K-Shell^[29]是网络中一种度量节点影响力的算法，但不能提供有关节点拓扑位置的充足信息。近年来，已有研究针对该问题从层级角度出发提出HKS（Hierarchical K-Shell）算法^[30]。HKS算法在无向无权网络中能够准确且高效地度量节点的影响力并确定其拓扑位置，但在有向加权网络中HKS算法面临适用性问题。为解决上述问题，本文基于中国互联网络信息中心提供的海量在线用户行为大数据，构建集体注意力流网络，定义节点的层级位置时间和位置约束，同时考虑节点的拓扑位置和时间序列，提出一种用于有向加权网络的节点影响力度量及排序算法OHKS。

1 理论基础 1.1 研究框架

本文研究框架主要包括数据预处理、数据建模、OHKS算法及实验分析，如图 1所示，具体过程如下：

1）数据预处理。通过分析在线用户行为日志数据，获取实验所需的点击流数据。

2）数据建模。对点击流数据进行建模，构造注意力流网络。

3）OHKS算法。在注意力流网络中，通过定义节点的层级位置时间（Hierarchical Position Time，HPT）和位置约束（P）两项指标，同时考虑节点的拓扑位置和时间序列，使得每个节点都具有一个层级指标h，然后计算其影响力。节点的HPT指标是从网络外围往核心分层计算，值越大，影响力越大，节点越靠近网络核心。节点的P指标是从网络核心往外围分层计算，值越小，节点影响力越小，节点越接近网络外围。通过这两个指标对每个节点的位置和影响力进行层层约束，所得出的节点影响力不仅仅单独依赖于节点的度或节点的权重，而是更加综合有效。

4）实验分析。通过OHKS算法研究了注意力流网络中节点影响力的层级性，并将其实验结果和4种常规算法作对比实验分析。

1.2 注意力流网络

本文采用的实验数据是中国互联网络信息中心提供的在线用户行为日志数据，在保证用户个人隐私的前提下，详细记录了海量用户开关机时间、焦点窗口的窗口进程名和进程号、浏览器窗口的地址栏内容（已部分截断）、焦点窗口对应的程序版本号、程序所属公司名、用户人口属性等信息。用户每开关机一次就会建立一个相应的日志文件。每2秒就会扫描一次用户电脑显示屏最前端的焦点窗口，如果焦点窗口相比2 s前已发生变化，则立即在日志中增加1条记录。为了方便分析，随机抽取200个用户1个月约800万条数据记录。

注意力流网络由一个加权有向图G=（V，E，T，W）表示，如图 2所示，其中，V表示图的n+2个顶点集，source和sink是2个特殊节点，E表示图的边集，顶点权重T表示集体用户在一个站点上注意力停留的总时间，边的权重W表示注意力在各站点间转换的强度（不存在的边定义其权值为0）。

1.3 HKS算法

K-Shell是网络中一种度量节点影响力的算法，但不能提供有关节点拓扑位置的充足信息。近年来，已有研究针对该问题从层级角度出发提出了HKS算法。ZAREIE等^[30]指出图中有3类节点集可以影响节点v_i的传播能力：

1）在图核心的最短路径上访问v_i的节点集Pred_i。

2）在图核心的最短路径上v_i访问的节点集Succ_i。

3）在图核心的最短路径上v_i和v_j相互不访问的节点集Sibl_i，其中v_j是v_i的邻域节点集。

HKS算法使用Pred_i、Succ_i、Sibl_i节点集指定节点位置和影响力，利用b_i和f_i指标指定每个节点v_i的拓扑位置。b_i和f_i分别受Pred_i、Sibl_i、Succ_i节点集的影响，b和f分别决定了节点远离外围的程度和接近核心的程度。b实际上是节点v_i被删除的一个全局迭代计数器，计算b值的算法具体如下：1）设置Shell=1和b=1的初始值，从图中删除度等于Shell的节点，并为其分配b=1，直到图中不再有度等于Shell的节点；2）b增加1，Shell增加1，度等于Shell的节点再次从图中被删除，并在给定计数器b全局值的情况下将它们设置为b_i；3）不断重复该过程，直到删除图中所有节点。计算f值的算法具体如下：1）确定位于图核心的节点，规定它们的f值等于被分配的b值；2）从图的核心开始遍历，具有最高f_i值的每个节点v_i在每一步中用f_i-1值来改变未删除的邻居f值，然后删除节点v_i；3）不断重复该过程，直到删除图中所有节点。

H_HKS（v_i）表示节点v_i的传播影响力，计算公式如下：

$ {H}_{\mathrm{H}\mathrm{K}\mathrm{S}}\left({v}_{i}\right)=\sum\limits_{{v}_{j}\in N\left({v}_{i}\right)}S\left({v}_{j}\right) $

(1)

其中：v_j∈N（v_i）表示节点v_j是节点v_i的邻居节点；S（v_i）表示节点v_i的一阶邻域传播影响力之和。S（v_i）计算公式如下：

$ S\left({v}_{i}\right)=\sum\limits_{{v}_{j}\in {N}_{i}}{d}_{j}({b}_{j}+{f}_{j}) $

(2)

其中：v_j∈N_i表示节点v_j属于节点v_i的邻域；d_j表示节点v_j的度；b_j表示节点v_j的b值；f_j表示节点v_j的f值。

2 OHKS算法

传统HKS算法在无向无权网络中能够准确且高效地度量节点的影响力并确定其拓扑位置。然而，在有向加权网络中HKS算法面临适用性挑战。因此，本文利用OHKS算法来研究注意力流网络中节点影响力的层级性。在有向加权注意力流网络中，节点表示用户点击过的站点，用户在站点的停留时间表示节点的权重，边表示集体用户注意力从一个站点跳转到下一个站点，跳转次数表示节点的度，度表示边的权重（不区分节点的出度和入度）。OHKS算法采用净注意力流入来度量节点的影响力，用户浏览站点的先后顺序表示边的方向，根据入度计算边的权重（区分出度和入度），再结合顶点的权重得出点入中心性。

2.1 节点层级位置时间

节点的入度平均停留时间（Average Retention Time，ART）定义为：假设站点A的入度为x，即在站点A产生停留时间的边数为x，每条边在站点A产生的停留时间分别为a₁，a₂，…，a_x，那么站点A的ART计算公式如下：

$ {{A}_{\mathrm{A}\mathrm{R}\mathrm{T}}}_{A}=\frac{\sum\limits_{n=1}^{x}{a}_{x}}{x} $

(3)

根据ART与节点拓扑位置，计算层级位置时间的算法具体如下：1）设置计数器count=0和层级指标h=1，从图中删除ART∈[count，count+1）的节点，并使其HPT=h，不断重复该步骤直到图中不再有ART∈[count，count+1）的节点；2）h增加1，count增加1，再次从图中删除ART∈[count，count+1）的节点，根据给定的ART全局值得出HPT；3）不断重复该过程，直到删除图中所有的节点。节点的HPT越大，影响力越大，节点越靠近图的核心。

算法1  每个节点的HPT（T₁，T₂）计算算法

输入  节点的邻接表T₁、节点的ART表T₂

输出  节点的HPT表T₃

//建立空图G（V，E，ART），将T₁中的节点和边添加到图

//G，将T₂中的ART添加到相应节点

1.设置count = 0

2.设置h = 1

3.for each（V！= Ø）

4.for each（v_i ∈ V）

5.设置flag = false

6.if（count < h and $ \mathrm{A}\mathrm{R}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $ ∈ [count，count+1））

7.$ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $ = h

8.flag = true

9.end if

10.end for

11.if（flag = true）

12.for each（v_i ∈ V）

13.if（$ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $ = h）

14.从V中删除节点v_i

15.end for

16.count++

17.else

18.h++

19.end if

20.end for

2.2 节点位置约束

节点的位置约束（P）表示由节点HPT和一阶邻域同时约束。节点的P越小，节点影响力越小，节点越接近网络外围。计算位置约束的算法具体如下：1）找到具有最大HPT的节点v_i，定义Q=max（$ HP{T}_{{v}_{i}} $）；2）将节点v_i的HPT赋给P，其余节点的P都赋值为0；3）从图的核心开始遍历，寻找P=Q的节点v_i未删除的邻居节点，并给它们赋值为P-1，再删除节点v_i；4）Q自减1，不断重复该过程，直到删除图中所有的节点。

若在核心节点附近存在非核心节点，非核心节点的一阶邻域会提高该节点的P值。类似于通过高度值的邻接节点获得间接影响力的特征向量中心性，如果一个节点的度很高，则说明该节点有较高的中心性；如果一个节点的度不是很高，它和一个有很高度值的节点邻接，则该节点的中心性也较高。

算法2  每个节点的P（T₁，T₃）计算算法

输入  节点的邻接表T₁、节点的HPT表T₃

输出  节点的P表T₄

//建立空图G（V，E，HPT），将T₁中的节点和边添加到

//图G，将T₃中的HPT添加到相应节点

1.设置Q = max（$ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $）

2.for each（v_i ∈ V）

3.if（∄ v_j ∈ N_i where $ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{j}}} $ > $ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $）

4.$ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{i}}} $ = $ \mathrm{H}\mathrm{P}{\mathrm{T}}_{{\mathrm{v}}_{\mathrm{i}}} $

5.else

6.$ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{i}}} $ = 0

7.end for

8.for each（V！= Ø）

9.for each（v_i ∈ V）

10.if（$ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{i}}} $ == Q）

11.for each（v_j ∈ N_i）

12.if（$ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{i}}} $-1 > P _vj）

13.$ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{j}}} $ = $ {\mathrm{P}}_{{\mathrm{v}}_{\mathrm{i}}} $-1

14.end if

15.end for

16.end if

17.end for

18.从V中删除节点v_i

19.Q = Q-1

20.end for

2.3 节点影响力

O_OHKS（v_i）表示节点v_i的影响力，计算公式如下：

$ {O}_{\mathrm{O}\mathrm{H}\mathrm{K}\mathrm{S}}\left({v}_{i}\right)=\sum\limits_{{v}_{j}\in N\left({v}_{i}\right)}S\left({v}_{j}\right) $

(4)

S（v_i）计算公式如下：

$ S\left({v}_{i}\right)=\sum\limits_{{v}_{j}\in {N}_{i}}{d}_{{v}_{j}}({H}_{\mathrm{H}\mathrm{P}{\mathrm{T}}_{{v}_{j}}}+{P}_{{v}_{j}}) $

(5)

其中：$ {H}_{\mathrm{H}\mathrm{P}{\mathrm{T}}_{{v}_{j}}} $表示节点v_j的HPT值；$ {P}_{{v}_{j}} $表示节点v_j的P值。

3 实验设置 3.1 数据建模

通过对在线用户行为日志数据进行提取，可获得用户的点击流数据如表 1所示。在有向加权注意力流网络中，节点表示用户在浏览网页时所点击的站点，边表示用户注意力从该站点流出进入下一站点。在数据建模过程中，需要生成站点之间边的权重（dataew）站点的顶点的权重（datanw）、站点的入度平均停留时间，如表 2~表 4所示。在表 4中，datanw1为表datanw中相同站点的顶点的权重累加，datanw2为表datanw1中相同站点的顶点的权重累加，dataew1为dataew中相同跳转的边的权重（不分出度和入度）累加，dataew2为根据入度计算出边的权重（分出度和入度）累加。

3.2 节点影响力的层级性网络构建

通过分析在线用户行为点击流数据，构建包含4 627个节点、58 284条边的注意力流网络，如图 3所示。

节点影响力的层级性网络由一个加权有向图G=（V，E，T，W）表示，主要以顶点的权重T和边的权重W为依据，得出的节点影响力不仅依赖节点的度或节点的权重，而且依赖顶点的权重和边的权重：

1）顶点的权重T。评估节点影响力的OHKS值，由节点的层级位置时间和位置约束综合得出。OHKS值越大，节点影响力越大，节点越靠近网络核心。对应于可视化过程中，节点半径越大，颜色越深。

2）边的权重W。节点之间的跳转数，是一个累加的过程。连边越多，节点影响力越大，节点越靠近网络核心，即复杂网络中的“意见领袖”思想，它强调连结度高的个体在新的意见或信息传播中起重大作用。对应于可视化过程中，边越粗，颜色越深。

3.3 实验结果分析

为分析与验证OHKS算法得到的注意力流网络中节点影响力的层级性结果，将其与度中心性、紧密中心性、K-Shell、PageRank算法进行对比，其中，度中心性属于局部结构化方法，紧密中心性属于全局结构化方法，K-Shell是一种识别关键节点的经典全局结构化算法，PageRank^[31-32]是一种研究节点影响力的基本算法。

3.3.1 对比算法分析

在OHKS算法中必须不断重复从网络中删除节点，算法1计算了每个节点的HPT，时间复杂度为O（n），其中n是网络中的节点数，算法2计算了每个节点的P，时间复杂度为O（n），节点v_i的一阶邻域影响力之和S（v_i）和影响力O_OHKS（v_i）的时间复杂度为O（n）。因此，OHKS算法的时间复杂度为O（n）。

局部结构化方法的核心思想是具有大量邻居的高度节点更具影响力，并且具有结构简单和时间复杂度低等优点，但仅依赖节点及其邻居来度量影响力，忽略了网络的全局结构。度中心性衡量网络中一个节点和其他节点的关联程度，是最基本的中心性度量算法。对于一个有g个节点的无向图，节点i的中心度是i与其他g-1个节点的直接关联总数，计算公式如下：

$ {C}_{\mathrm{D}}\left({n}_{i}\right)=\sum\limits_{j=1}^{g}{x}_{ij} $

(6)

其中：C_D（n_i）表示节点i的中心度，将节点i在网络矩阵中对应的行或列所在的单元格值累加；$ \sum\limits_{j=1}^{g}{x}_{ij}(i\ne j) $表示节点i和g-1个节点j的直接关联数量；i≠j表示排除i与自身的联系。

在全局结构化方法中需要遍历整个网络获取全局信息来度量节点的影响力，节点影响力由网络全局结构决定，因此它们具有更高的时间复杂度。紧密中心性为网络中节点在最短路径上的距离，表示节点v_i和其他节点v_j的最短距离之和的倒数，计算公式如下：

$ {C}_{\mathrm{D}}\left({v}_{i}\right)=\frac{n-1}{\sum\limits_{j\ne i}^{n}g({v}_{i}, {v}_{j})} $

(7)

其中：C_D（v_i）表示节点v_i的紧密中心度；g（v_i，v_j）表示v_i和v_j的最短路径距离。

K-Shell是网络中一种度量节点影响力的算法，但不能提供有关节点拓扑位置的充足信息，算法具体过程如下：1）给每个节点分配一个k_s指标，从图中删除度为1的节点，直到不再有度为1的节点，k_s=1被分配给已删除的节点；2）从图中删除度为2的节点，直到不再有度为2的节点，k_s=2被分配给已删除的节点；3）不断重复该过程，直到从图中删除所有节点。

PageRank由于遵循马尔科夫过程和随机游走设想，需要反复迭代获取PR值，其实验数据量要求大、实验设备性能要求高，且运行时间长。PageRank通过网页之间的链接结构来度量网页的重要性，是类似于特征向量中心性的算法，计算公式如下：

$ {P}_{\mathrm{P}{\mathrm{R}}_{i}}=\varphi \sum\limits_{j}\frac{{P}_{\mathrm{P}{\mathrm{R}}_{j}}}{{Q}_{j}}+(1-\varphi ) $

(8)

其中：$ \varphi $∈（0，1）是一个常数，被称为阻尼系数，表示任意时刻用户访问到某页面后继续访问下一个页面的概率；$ {P}_{\mathrm{P}{\mathrm{R}}_{i}} $表示前一个节点j的PageRank值；O_j表示顶点j的出度。

3.3.2 节点影响力识别方式分析

基于OHKS算法得出的影响力前15名的站点如表 5所示。根据度中心性、紧密中心性、K-Shell和PageRank算法得出的影响力前15名的站点排名，如表 6所示，其中K-Shell算法的站点排名不区分先后顺序。

由表 6可以看出，OHKS算法与度中心性、紧密中心性、K-sell、PageRank这4种常规算法得出的站点排名前3名站点一致，其中，baidu.com和sogou.com属于搜索引擎类站点，qq.com属于信息类站点。OHKS算法结合节点的全局拓扑位置和停留时间来识别最具影响力的站点，当用户分别访问baidu.com、qq.com和sogou.com这3个站点时，形成的多次跳转依然是在同站内访问，即给站点带来了真正有效的停留时间。结合baidu.com、qq.com等网站在中国的受欢迎程度，显然会获得高排名，且该排名与中国的Alexa排名趋于一致。常规算法主要以跳转为核心来识别最具影响力的站点，随着互联网的飞速发展和用户电子设备的快速进步，访问速度越来越快，使得用户可以轻松、快速地在搜索引擎类站点或信息类站点中实现多次跳转，因此具有大量跳转数的网站排名较高。

结合表 5和表 6可以看出，前3名以外的站点不尽相同，因为OHKS算法从全局角度出发主要结合节点的拓扑位置和停留时间来识别最具影响力的站点。例如，sina.com虽然属于门户类网站，但是它在OHKS算法中的排名比在常规算法中靠前，原因在于当用户访问sina.com时，除了在sina.com中实现多次跳转以外，它的微博、视频和游戏等专栏会使得用户长时间停留。视频类网站youku.com在OHKS算法中的排名也比常规算法靠前，因为当用户访问youku.com时，除了多次跳转外，更多的是注意力的长时间的停留和聚焦。

3.3.3 算法适用性与性能分析

算法适用性与性能分析具体如下：

1）适用性。OHKS算法既适用于无向无权网络，又适用于有向加权网络。度中心性、紧密中心性、K-Shell和PageRank算法仅适用于无向无权网络。

2）性能。OHKS算法结合节点的全局拓扑位置，时间复杂度低、运行效率高。度中心性算法的时间复杂度低，但忽略了网络的全局结构。紧密中心性考虑了网络的全局结构，但时间复杂度高。K-Shell算法不能提供有关节点拓扑位置的充足信息。PageRank算法实验数据量要求大、实验设备性能要求高，且运行周期长。

3）节点影响力识别方式。OHKS算法从全局角度出发，主要结合节点的拓扑位置和时间序列来识别有影响力的节点。度中心性、紧密中心性、K-Shell和PageRank算法主要以跳转为核心来识别有影响力的节点。

4 结束语

本文以在线用户行为点击流大数据为研究基础，生成点击流模型并构建注意力流网络，通过定义节点的层级位置时间和位置约束对HKS算法进行优化，提出一种用于有向加权网络节点影响力度量及排序的算法。实验结果表明，该算法适用于有向加权网络中的节点影响力分析，能对看似吸引了大量注意力的假象节点进行甄别，准确地识别出真正有影响力的节点，从而加深对网络层级结构的认识，有助于分析网络中心性、节点聚类、社区结构等特征。后续将进一步划分站点类别，并在不同类别的社区内部进行层级性或可控性算法研究，深入探索用户行为和互联网协同演化的关系。