注意力流網絡中節點影響力的層級性研究

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

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

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］研究較少。KShell［29］是網絡中一種度量節點影響力的算法，但不能提供有關節點拓撲位置的充足信息。近年來，已有研究針對該問題從層級角度出發提出HKS（Hierarchical K-Shell）算法［30］。HKS 算法在無向無權網絡中能夠準確且高效地度量節點的影響力并確定其拓撲位置，但在有向加權網絡中HKS 算法面臨適用性問題。為解決上述問題，本文基于中國互聯網絡信息中心提供的海量在線用戶行為大數據，構建集體注意力流網絡，定義節點的層級位置時間和位置約束，同時考慮節點的拓撲位置和時間序列，提出一種用于有向加權網絡的節點影響力度量及排序算法OHKS。

1 理論基礎

1.1 研究框架

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

圖1 研究框架Fig.1 Research framework

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）。

圖2 注意力流網絡Fig.2 Attention flow network

1.3 HKS 算法

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

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

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

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

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

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

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

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

2 OHKS 算法

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

2.1 節點層級位置時間

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

根據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 越大，影響力越大，節點越靠近圖的核心。

2.2 節點位置約束

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

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

2.3 節點影響力

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

3 實驗設置

3.1 數據建模

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

表1 點擊流數據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 節點影響力的層級性網絡構建

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

圖3 節點影響力的層級性網絡Fig.3 Hierarchical network of node influence

節點影響力的層級性網絡由一個加權有向圖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），節點νi的一階鄰域影響力之和S（νi）和影響力OOHKS（νi）的時間復雜度為O（n）。因此，OHKS算法的時間復雜度為O（n）。

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

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

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

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

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

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

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

3.3.2 節點影響力識別方式分析

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

表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 種常規算法得出的站點排名前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 算法進行優化，提出一種用于有向加權網絡節點影響力度量及排序的算法。實驗結果表明，該算法適用于有向加權網絡中的節點影響力分析，能對看似吸引了大量注意力的假象節點進行甄別，準確地識別出真正有影響力的節點，從而加深對網絡層級結構的認識，有助于分析網絡中心性、節點聚類、社區結構等特征。后續將進一步劃分站點類別，并在不同類別的社區內部進行層級性或可控性算法研究，深入探索用戶行為和互聯網協同演化的關系。