李 勇，董思秀，張 強，程方頎，王常青

（1.西北師范大學 計算機科學與工程學院，蘭州 730070；2.北京航空航天大學 計算機學院，北京 100190；3.中國互聯(lián)網(wǎng)絡信息中心互聯(lián)網(wǎng)基礎技術開放實驗室，北京 100190）

0 概述

人類社會是一個類似混沌系統(tǒng)的復雜系統(tǒng)，幾乎所有的人類社會現(xiàn)象和自然現(xiàn)象均可利用社交網(wǎng)絡、生物網(wǎng)絡等復雜網(wǎng)絡模型進行描述。復雜網(wǎng)絡內部結構錯綜復雜，存在少數(shù)關鍵核心節(jié)點，核心節(jié)點的微小擾動會引起網(wǎng)絡的系統(tǒng)性漲落，甚至導致網(wǎng)絡徹底崩潰。注意力流網(wǎng)絡［1-3］是近年來興起的一個新型的復雜網(wǎng)絡，由在線用戶在不同信息源上連續(xù)的點擊行為構成，其中，節(jié)點表示用戶點擊的信息源，邊表示用戶從一個信息源到下一個信息源的跳轉，將人類的注意力看作抽象流動的物質。在注意力流網(wǎng)絡研究領域，研究人員在前期研究中已發(fā)現(xiàn)多個演化普適模式，包括異速標度律、耗散律、引力定律和heaps律等［4-6］。LI等［2］基于在線集體注意力流，研究網(wǎng)站的影響力。WU 等［3］分析了復雜網(wǎng)絡上點擊流的分散流結構。SHI 等［7］提出一種在不同網(wǎng)站之間分配和流動集體注意力的幾何表示方法。GU 等［8］提出一種基于流的幾何嵌入及其數(shù)值近似改進算法，根據(jù)流距離定義的節(jié)點中心性對站點進行排名。

擴散模型用于度量節(jié)點的傳播影響力［9-10］并可對節(jié)點重要性進行排序，主要包括閾值模型［11］、級聯(lián)模型［12-13］、流行病模型［14-15］等模型。但是，在大型復雜網(wǎng)絡中使用擴散模型度量節(jié)點的傳播能力并對節(jié)點進行排序非常耗時。針對這一問題，近年來研究人員提出了多種節(jié)點排序的方法。這些方法主要分為結構化方法和超結構化方法，在結構化方法中節(jié)點的傳播能力僅基于拓撲位置，在超結構化方法中除了節(jié)點拓撲位置外，還考慮了個體特征、用戶興趣等因素。由于對額外信息的需求較低，并且節(jié)點的傳播能力僅基于網(wǎng)絡結構確定，因此結構化方法受到了更多的關注。根據(jù)網(wǎng)絡結構中使用的信息類型，結構化方法又分為局部、半局部、全局和混合方法。局部結構化方法僅依賴節(jié)點及其鄰居來度量其影響力，如度中心性［16］和H-index中心性［17］。半局部結構化方法除了鄰居的信息之外，還使用二階鄰居來度量節(jié)點的傳播能力，如權重度中心性和擴展權重度中心性［18］。全局結構化方法需要遍歷整個網(wǎng)絡獲取全局信息來度量節(jié)點的影響力，如緊密中心性［19］、中介中心性［20］、核數(shù)中心性［21］和K-Shell?；旌辖Y構化方法利用局部和全局信息來度量節(jié)點傳播能力，如混合度分解［22］、鄰域核數(shù)［23］、K-Shell迭代因子［24］和混合核心、度和熵［25］。除了上述結構化方法外，還有一些度量節(jié)點傳播能力的博弈論模型。文獻［26］考慮網(wǎng)絡結構，使用合作博弈論提出多種節(jié)點中心性度量方法。文獻［27］將節(jié)點傳播能力的度量問題建模為非合作博弈問題，并根據(jù)該模型度量節(jié)點的傳播能力。

網(wǎng)絡中通過連接不同子網(wǎng)絡的關鍵節(jié)點維持整個網(wǎng)絡的凝聚力，對信息流動或控制十分關鍵?，F(xiàn)有的關鍵節(jié)點識別方法多數(shù)僅關注單個或局部節(jié)點，很少從網(wǎng)絡整體性、系統(tǒng)性上探討節(jié)點影響力，而且這些方法多數(shù)是針對無向無權網(wǎng)絡，關于有向加權網(wǎng)絡節(jié)點影響力的層級性［28］研究較少。KShell［29］是網(wǎng)絡中一種度量節(jié)點影響力的算法，但不能提供有關節(jié)點拓撲位置的充足信息。近年來，已有研究針對該問題從層級角度出發(fā)提出HKS（Hierarchical K-Shell）算法［30］。HKS 算法在無向無權網(wǎng)絡中能夠準確且高效地度量節(jié)點的影響力并確定其拓撲位置，但在有向加權網(wǎng)絡中HKS 算法面臨適用性問題。為解決上述問題，本文基于中國互聯(lián)網(wǎng)絡信息中心提供的海量在線用戶行為大數(shù)據(jù)，構建集體注意力流網(wǎng)絡，定義節(jié)點的層級位置時間和位置約束，同時考慮節(jié)點的拓撲位置和時間序列，提出一種用于有向加權網(wǎng)絡的節(jié)點影響力度量及排序算法OHKS。

1 理論基礎

1.1 研究框架

本文研究框架主要包括數(shù)據(jù)預處理、數(shù)據(jù)建模、OHKS 算法及實驗分析，如圖1 所示，具體過程如下：

圖1 研究框架Fig.1 Research framework

1）數(shù)據(jù)預處理。通過分析在線用戶行為日志數(shù)據(jù)，獲取實驗所需的點擊流數(shù)據(jù)。

2）數(shù)據(jù)建模。對點擊流數(shù)據(jù)進行建模，構造注意力流網(wǎng)絡。

3）OHKS 算法。在注意力流網(wǎng)絡中，通過定義節(jié)點的層級位置時間（Hierarchical Position Time，HPT）和位置約束（P）兩項指標，同時考慮節(jié)點的拓撲位置和時間序列，使得每個節(jié)點都具有一個層級指標h，然后計算其影響力。節(jié)點的HPT 指標是從網(wǎng)絡外圍往核心分層計算，值越大，影響力越大，節(jié)點越靠近網(wǎng)絡核心。節(jié)點的P指標是從網(wǎng)絡核心往外圍分層計算，值越小，節(jié)點影響力越小，節(jié)點越接近網(wǎng)絡外圍。通過這兩個指標對每個節(jié)點的位置和影響力進行層層約束，所得出的節(jié)點影響力不僅僅單獨依賴于節(jié)點的度或節(jié)點的權重，而是更加綜合有效。

4）實驗分析。通過OHKS 算法研究了注意力流網(wǎng)絡中節(jié)點影響力的層級性，并將其實驗結果和4 種常規(guī)算法作對比實驗分析。

1.2 注意力流網(wǎng)絡

本文采用的實驗數(shù)據(jù)是中國互聯(lián)網(wǎng)絡信息中心提供的在線用戶行為日志數(shù)據(jù)，在保證用戶個人隱私的前提下，詳細記錄了海量用戶開關機時間、焦點窗口的窗口進程名和進程號、瀏覽器窗口的地址欄內容（已部分截斷）、焦點窗口對應的程序版本號、程序所屬公司名、用戶人口屬性等信息。用戶每開關機一次就會建立一個相應的日志文件。每2 秒就會掃描一次用戶電腦顯示屏最前端的焦點窗口，如果焦點窗口相比2 s 前已發(fā)生變化，則立即在日志中增加1 條記錄。為了方便分析，隨機抽取200 個用戶1 個月約800 萬條數(shù)據(jù)記錄。

注意力流網(wǎng)絡由一個加權有向圖G=（V，E，T，W）表示，如圖2 所示，其中，V表示圖的n+2 個頂點集，source 和sink 是2 個特殊節(jié)點，E表示圖的邊集，頂點權重T表示集體用戶在一個站點上注意力停留的總時間，邊的權重W表示注意力在各站點間轉換的強度（不存在的邊定義其權值為0）。

圖2 注意力流網(wǎng)絡Fig.2 Attention flow network

1.3 HKS 算法

K-Shell 是網(wǎng)絡中一種度量節(jié)點影響力的算法，但不能提供有關節(jié)點拓撲位置的充足信息。近年來，已有研究針對該問題從層級角度出發(fā)提出了HKS 算法。ZAREIE 等［30］指出圖中有3 類節(jié)點集可以影響節(jié)點νi的傳播能力：

1）在圖核心的最短路徑上訪問νi的節(jié)點集Predi。

2）在圖核心的最短路徑上νi訪問的節(jié)點集Succi。

3）在圖核心的最短路徑上νi和νj相互不訪問的節(jié)點集Sibli，其中νj是νi的鄰域節(jié)點集。

HKS 算法使用Predi、Succi、Sibli節(jié)點集指定節(jié)點位置和影響力，利用bi和fi指標指定每個節(jié)點νi的拓撲位置。bi和fi分別受Predi、Sibli、Succi節(jié)點集的影響，b和f分別決定了節(jié)點遠離外圍的程度和接近核心的程度。b實際上是節(jié)點νi被刪除的一個全局迭代計數(shù)器，計算b值的算法具體如下：1）設置Shell=1和b=1 的初始值，從圖中刪除度等于Shell 的節(jié)點，并為其分配b=1，直到圖中不再有度等于Shell 的節(jié)點；2）b增加1，Shell 增加1，度等于Shell 的節(jié)點再次從圖中被刪除，并在給定計數(shù)器b全局值的情況下將它們設置為bi；3）不斷重復該過程，直到刪除圖中所有節(jié)點。計算f值的算法具體如下：1）確定位于圖核心的節(jié)點，規(guī)定它們的f值等于被分配的b值；2）從圖的核心開始遍歷，具有最高fi值的每個節(jié)點νi在每一步中用fi-1 值來改變未刪除的鄰居f值，然后刪除節(jié)點νi；3）不斷重復該過程，直到刪除圖中所有節(jié)點。

HHKS（νi）表示節(jié)點νi的傳播影響力，計算公式如下：

其中：νj∈N（νi）表示節(jié)點νj是節(jié)點νi的鄰居節(jié)點；S（νi）表示節(jié)點νi的一階鄰域傳播影響力之和。S（νi）計算公式如下：

其中：νj∈Ni表示節(jié)點νj屬于節(jié)點νi的鄰域；dj表示節(jié)點νj的度；bj表示節(jié)點νj的b值；fj表示節(jié)點νj的f值。

2 OHKS 算法

傳統(tǒng)HKS 算法在無向無權網(wǎng)絡中能夠準確且高效地度量節(jié)點的影響力并確定其拓撲位置。然而，在有向加權網(wǎng)絡中HKS 算法面臨適用性挑戰(zhàn)。因此，本文利用OHKS 算法來研究注意力流網(wǎng)絡中節(jié)點影響力的層級性。在有向加權注意力流網(wǎng)絡中，節(jié)點表示用戶點擊過的站點，用戶在站點的停留時間表示節(jié)點的權重，邊表示集體用戶注意力從一個站點跳轉到下一個站點，跳轉次數(shù)表示節(jié)點的度，度表示邊的權重（不區(qū)分節(jié)點的出度和入度）。OHKS 算法采用凈注意力流入來度量節(jié)點的影響力，用戶瀏覽站點的先后順序表示邊的方向，根據(jù)入度計算邊的權重（區(qū)分出度和入度），再結合頂點的權重得出點入中心性。

2.1 節(jié)點層級位置時間

節(jié)點的入度平均停留時間（Average Retention Time，ART）定義為：假設站點A的入度為x，即在站點A產(chǎn)生停留時間的邊數(shù)為x，每條邊在站點A產(chǎn)生的停留時間分別為a1，a2，…，ax，那么站點A的ART計算公式如下：

根據(jù)ART與節(jié)點拓撲位置，計算層級位置時間的算法具體如下：1）設置計數(shù)器count=0和層級指標h=1，從圖中刪除ART∈［count，count+1）的節(jié)點，并使其HPT=h，不斷重復該步驟直到圖中不再有ART∈［count，count+1）的節(jié)點；2）h增加1，count增加1，再次從圖中刪除ART∈［count，count+1）的節(jié)點，根據(jù)給定的ART 全局值得出HPT；3）不斷重復該過程，直到刪除圖中所有的節(jié)點。節(jié)點的HPT 越大，影響力越大，節(jié)點越靠近圖的核心。

2.2 節(jié)點位置約束

節(jié)點的位置約束（P）表示由節(jié)點HPT 和一階鄰域同時約束。節(jié)點的P越小，節(jié)點影響力越小，節(jié)點越接近網(wǎng)絡外圍。計算位置約束的算法具體如下：1）找到具有最大HPT 的節(jié)點νi，定義將節(jié)點νi的HPT 賦給P，其余節(jié)點的P都賦值為0；3）從圖的核心開始遍歷，尋找P=Q的節(jié)點νi未刪除的鄰居節(jié)點，并給它們賦值為P-1，再刪除節(jié)點νi；4）Q自減1，不斷重復該過程，直到刪除圖中所有的節(jié)點。

若在核心節(jié)點附近存在非核心節(jié)點，非核心節(jié)點的一階鄰域會提高該節(jié)點的P值。類似于通過高度值的鄰接節(jié)點獲得間接影響力的特征向量中心性，如果一個節(jié)點的度很高，則說明該節(jié)點有較高的中心性；如果一個節(jié)點的度不是很高，它和一個有很高度值的節(jié)點鄰接，則該節(jié)點的中心性也較高。

2.3 節(jié)點影響力

OOHKS（νi）表示節(jié)點νi的影響力，計算公式如下：

3 實驗設置

3.1 數(shù)據(jù)建模

通過對在線用戶行為日志數(shù)據(jù)進行提取，可獲得用戶的點擊流數(shù)據(jù)如表1 所示。在有向加權注意力流網(wǎng)絡中，節(jié)點表示用戶在瀏覽網(wǎng)頁時所點擊的站點，邊表示用戶注意力從該站點流出進入下一站點。在數(shù)據(jù)建模過程中，需要生成站點之間邊的權重（dataew）站點的頂點的權重（datanw）、站點的入度平均停留時間，如表2～表4 所示。在表4 中，datanw1 為表datanw 中相同站點的頂點的權重累加，datanw2 為表datanw1 中相同站點的頂點的權重累加，dataew1 為dataew 中相同跳轉的邊的權重（不分出度和入度）累加，dataew2 為根據(jù)入度計算出邊的權重（分出度和入度）累加。

表1 點擊流數(shù)據(jù)Table 1 Clickstream data

表2 邊的權重Table 2 Edge weight

表3 頂點的權重Table 3 Vertex weight

表4 站點的入度平均停留時間Table 4 In-degree average retention time of site

3.2 節(jié)點影響力的層級性網(wǎng)絡構建

通過分析在線用戶行為點擊流數(shù)據(jù)，構建包含4 627個節(jié)點、58 284條邊的注意力流網(wǎng)絡，如圖3所示。

圖3 節(jié)點影響力的層級性網(wǎng)絡Fig.3 Hierarchical network of node influence

節(jié)點影響力的層級性網(wǎng)絡由一個加權有向圖G=（V，E，T，W）表示，主要以頂點的權重T和邊的權重W為依據(jù)，得出的節(jié)點影響力不僅依賴節(jié)點的度或節(jié)點的權重，而且依賴頂點的權重和邊的權重：

1）頂點的權重T。評估節(jié)點影響力的OHKS 值，由節(jié)點的層級位置時間和位置約束綜合得出。OHKS 值越大，節(jié)點影響力越大，節(jié)點越靠近網(wǎng)絡核心。對應于可視化過程中，節(jié)點半徑越大，顏色越深。

2）邊的權重W。節(jié)點之間的跳轉數(shù)，是一個累加的過程。連邊越多，節(jié)點影響力越大，節(jié)點越靠近網(wǎng)絡核心，即復雜網(wǎng)絡中的“意見領袖”思想，它強調連結度高的個體在新的意見或信息傳播中起重大作用。對應于可視化過程中，邊越粗，顏色越深。

3.3 實驗結果分析

為分析與驗證OHKS 算法得到的注意力流網(wǎng)絡中節(jié)點影響力的層級性結果，將其與度中心性、緊密中心性、K-Shell、PageRank 算法進行對比，其中，度中心性屬于局部結構化方法，緊密中心性屬于全局結構化方法，K-Shell 是一種識別關鍵節(jié)點的經(jīng)典全局結構化算法，PageRank［31-32］是一種研究節(jié)點影響力的基本算法。

3.3.1 對比算法分析

在OHKS算法中必須不斷重復從網(wǎng)絡中刪除節(jié)點，算法1 計算了每個節(jié)點的HPT，時間復雜度為O（n），其中n是網(wǎng)絡中的節(jié)點數(shù)，算法2 計算了每個節(jié)點的P，時間復雜度為O（n），節(jié)點νi的一階鄰域影響力之和S（νi）和影響力OOHKS（νi）的時間復雜度為O（n）。因此，OHKS算法的時間復雜度為O（n）。

局部結構化方法的核心思想是具有大量鄰居的高度節(jié)點更具影響力，并且具有結構簡單和時間復雜度低等優(yōu)點，但僅依賴節(jié)點及其鄰居來度量影響力，忽略了網(wǎng)絡的全局結構。度中心性衡量網(wǎng)絡中一個節(jié)點和其他節(jié)點的關聯(lián)程度，是最基本的中心性度量算法。對于一個有g個節(jié)點的無向圖，節(jié)點i的中心度是i與其他g-1 個節(jié)點的直接關聯(lián)總數(shù)，計算公式如下：

其中：CD（ni）表示節(jié)點i的中心度，將節(jié)點i在網(wǎng)絡矩陣中對應的行或列所在的單元格值累加表示節(jié)點i和g-1 個節(jié)點j的直接關聯(lián)數(shù)量；i≠j表示排除i與自身的聯(lián)系。

在全局結構化方法中需要遍歷整個網(wǎng)絡獲取全局信息來度量節(jié)點的影響力，節(jié)點影響力由網(wǎng)絡全局結構決定，因此它們具有更高的時間復雜度。緊密中心性為網(wǎng)絡中節(jié)點在最短路徑上的距離，表示節(jié)點νi和其他節(jié)點νj的最短距離之和的倒數(shù)，計算公式如下：

其中：CD（νi）表示節(jié)點νi的緊密中心度；g（νi，νj）表示νi和νj的最短路徑距離。

K-Shell 是網(wǎng)絡中一種度量節(jié)點影響力的算法，但不能提供有關節(jié)點拓撲位置的充足信息，算法具體過程如下：1）給每個節(jié)點分配一個ks指標，從圖中刪除度為1 的節(jié)點，直到不再有度為1 的節(jié)點，ks=1 被分配給已刪除的節(jié)點；2）從圖中刪除度為2 的節(jié)點，直到不再有度為2 的節(jié)點，ks=2 被分配給已刪除的節(jié)點；3）不斷重復該過程，直到從圖中刪除所有節(jié)點。

PageRank 由于遵循馬爾科夫過程和隨機游走設想，需要反復迭代獲取PR 值，其實驗數(shù)據(jù)量要求大、實驗設備性能要求高，且運行時間長。PageRank 通過網(wǎng)頁之間的鏈接結構來度量網(wǎng)頁的重要性，是類似于特征向量中心性的算法，計算公式如下：

其中：φ∈（0，1）是一個常數(shù)，被稱為阻尼系數(shù)，表示任意時刻用戶訪問到某頁面后繼續(xù)訪問下一個頁面的概率表示前一個節(jié)點j的PageRank 值；Oj表示頂點j的出度。

3.3.2 節(jié)點影響力識別方式分析

基于OHKS 算法得出的影響力前15 名的站點如表5 所示。根據(jù)度中心性、緊密中心性、K-Shell 和PageRank算法得出的影響力前15名的站點排名，如表6所示，其中K-Shell算法的站點排名不區(qū)分先后順序。

表5 基于OHKS 算法的影響力前15 名的站點排名Table 5 Ranking of the top 15 influential sites based on the OHKS algorithm

表6 基于4 種算法的影響力前15 名的站點排名Table 6 Ranking of the top 15 influential sites based on four algorithms

由表6 可以看出，OHKS 算法與度中心性、緊密中心性、K-sell、PageRank 這4 種常規(guī)算法得出的站點排名前3 名站點一致，其中，baidu.com 和sogou.com 屬于搜索引擎類站點，qq.com 屬于信息類站點。OHKS 算法結合節(jié)點的全局拓撲位置和停留時間來識別最具影響力的站點，當用戶分別訪問baidu.com、qq.com 和sogou.com 這3 個站點時，形成的多次跳轉依然是在同站內訪問，即給站點帶來了真正有效的停留時間。結合baidu.com、qq.com 等網(wǎng)站在中國的受歡迎程度，顯然會獲得高排名，且該排名與中國的Alexa 排名趨于一致。常規(guī)算法主要以跳轉為核心來識別最具影響力的站點，隨著互聯(lián)網(wǎng)的飛速發(fā)展和用戶電子設備的快速進步，訪問速度越來越快，使得用戶可以輕松、快速地在搜索引擎類站點或信息類站點中實現(xiàn)多次跳轉，因此具有大量跳轉數(shù)的網(wǎng)站排名較高。

結合表5 和表6 可以看出，前3 名以外的站點不盡相同，因為OHKS 算法從全局角度出發(fā)主要結合節(jié)點的拓撲位置和停留時間來識別最具影響力的站點。例如，sina.com 雖然屬于門戶類網(wǎng)站，但是它在OHKS 算法中的排名比在常規(guī)算法中靠前，原因在于當用戶訪問sina.com 時，除了在sina.com 中實現(xiàn)多次跳轉以外，它的微博、視頻和游戲等專欄會使得用戶長時間停留。視頻類網(wǎng)站youku.com 在OHKS 算法中的排名也比常規(guī)算法靠前，因為當用戶訪問youku.com 時，除了多次跳轉外，更多的是注意力的長時間的停留和聚焦。

3.3.3 算法適用性與性能分析

算法適用性與性能分析具體如下：

1）適用性。OHKS 算法既適用于無向無權網(wǎng)絡，又適用于有向加權網(wǎng)絡。度中心性、緊密中心性、K-Shell 和PageRank 算法僅適用于無向無權網(wǎng)絡。

2）性能。OHKS 算法結合節(jié)點的全局拓撲位置，時間復雜度低、運行效率高。度中心性算法的時間復雜度低，但忽略了網(wǎng)絡的全局結構。緊密中心性考慮了網(wǎng)絡的全局結構，但時間復雜度高。K-Shell 算法不能提供有關節(jié)點拓撲位置的充足信息。PageRank 算法實驗數(shù)據(jù)量要求大、實驗設備性能要求高，且運行周期長。

3）節(jié)點影響力識別方式。OHKS 算法從全局角度出發(fā)，主要結合節(jié)點的拓撲位置和時間序列來識別有影響力的節(jié)點。度中心性、緊密中心性、K-Shell和PageRank 算法主要以跳轉為核心來識別有影響力的節(jié)點。

4 結束語

本文以在線用戶行為點擊流大數(shù)據(jù)為研究基礎，生成點擊流模型并構建注意力流網(wǎng)絡，通過定義節(jié)點的層級位置時間和位置約束對HKS 算法進行優(yōu)化，提出一種用于有向加權網(wǎng)絡節(jié)點影響力度量及排序的算法。實驗結果表明，該算法適用于有向加權網(wǎng)絡中的節(jié)點影響力分析，能對看似吸引了大量注意力的假象節(jié)點進行甄別，準確地識別出真正有影響力的節(jié)點，從而加深對網(wǎng)絡層級結構的認識，有助于分析網(wǎng)絡中心性、節(jié)點聚類、社區(qū)結構等特征。后續(xù)將進一步劃分站點類別，并在不同類別的社區(qū)內部進行層級性或可控性算法研究，深入探索用戶行為和互聯(lián)網(wǎng)協(xié)同演化的關系。