注意力流網(wǎng)絡(luò)中節(jié)點影響力的層級性研究

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

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

0 概述

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

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

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

1 理論基礎(chǔ)

1.1 研究框架

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

圖1 研究框架Fig.1 Research framework

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

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

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

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

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

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

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

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

1.3 HKS 算法

K-Shell 是網(wǎng)絡(luò)中一種度量節(jié)點影響力的算法，但不能提供有關(guān)節(jié)點拓?fù)湮恢玫某渥阈畔?。近年來，已有研究針對該問題從層級角度出發(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指標(biāo)指定每個節(jié)點νi的拓?fù)湮恢谩i和fi分別受Predi、Sibli、Succi節(jié)點集的影響，b和f分別決定了節(jié)點遠(yuǎn)離外圍的程度和接近核心的程度。b實際上是節(jié)點νi被刪除的一個全局迭代計數(shù)器，計算b值的算法具體如下：1）設(shè)置Shell=1和b=1 的初始值，從圖中刪除度等于Shell 的節(jié)點，并為其分配b=1，直到圖中不再有度等于Shell 的節(jié)點；2）b增加1，Shell 增加1，度等于Shell 的節(jié)點再次從圖中被刪除，并在給定計數(shù)器b全局值的情況下將它們設(shè)置為bi；3）不斷重復(fù)該過程，直到刪除圖中所有節(jié)點。計算f值的算法具體如下：1）確定位于圖核心的節(jié)點，規(guī)定它們的f值等于被分配的b值；2）從圖的核心開始遍歷，具有最高fi值的每個節(jié)點νi在每一步中用fi-1 值來改變未刪除的鄰居f值，然后刪除節(jié)點νi；3）不斷重復(fù)該過程，直到刪除圖中所有節(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 算法在無向無權(quán)網(wǎng)絡(luò)中能夠準(zhǔn)確且高效地度量節(jié)點的影響力并確定其拓?fù)湮恢谩Ｈ欢?，在有向加?quán)網(wǎng)絡(luò)中HKS 算法面臨適用性挑戰(zhàn)。因此，本文利用OHKS 算法來研究注意力流網(wǎng)絡(luò)中節(jié)點影響力的層級性。在有向加權(quán)注意力流網(wǎng)絡(luò)中，節(jié)點表示用戶點擊過的站點，用戶在站點的停留時間表示節(jié)點的權(quán)重，邊表示集體用戶注意力從一個站點跳轉(zhuǎn)到下一個站點，跳轉(zhuǎn)次數(shù)表示節(jié)點的度，度表示邊的權(quán)重（不區(qū)分節(jié)點的出度和入度）。OHKS 算法采用凈注意力流入來度量節(jié)點的影響力，用戶瀏覽站點的先后順序表示邊的方向，根據(jù)入度計算邊的權(quán)重（區(qū)分出度和入度），再結(jié)合頂點的權(quán)重得出點入中心性。

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

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

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

2.2 節(jié)點位置約束

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

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

2.3 節(jié)點影響力

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

3 實驗設(shè)置

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

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

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

表2 邊的權(quán)重Table 2 Edge weight

表3 頂點的權(quán)重Table 3 Vertex weight

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

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

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

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

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

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

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

3.3 實驗結(jié)果分析

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

3.3.1 對比算法分析

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

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

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

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

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

K-Shell 是網(wǎng)絡(luò)中一種度量節(jié)點影響力的算法，但不能提供有關(guān)節(jié)點拓?fù)湮恢玫某渥阈畔?，算法具體過程如下：1）給每個節(jié)點分配一個ks指標(biāo)，從圖中刪除度為1 的節(jié)點，直到不再有度為1 的節(jié)點，ks=1 被分配給已刪除的節(jié)點；2）從圖中刪除度為2 的節(jié)點，直到不再有度為2 的節(jié)點，ks=2 被分配給已刪除的節(jié)點；3）不斷重復(fù)該過程，直到從圖中刪除所有節(jié)點。

PageRank 由于遵循馬爾科夫過程和隨機游走設(shè)想，需要反復(fù)迭代獲取PR 值，其實驗數(shù)據(jù)量要求大、實驗設(shè)備性能要求高，且運行時間長。PageRank 通過網(wǎng)頁之間的鏈接結(jié)構(gòu)來度量網(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é)合節(jié)點的全局拓?fù)湮恢煤屯Ａ魰r間來識別最具影響力的站點，當(dāng)用戶分別訪問baidu.com、qq.com 和sogou.com 這3 個站點時，形成的多次跳轉(zhuǎn)依然是在同站內(nèi)訪問，即給站點帶來了真正有效的停留時間。結(jié)合baidu.com、qq.com 等網(wǎng)站在中國的受歡迎程度，顯然會獲得高排名，且該排名與中國的Alexa 排名趨于一致。常規(guī)算法主要以跳轉(zhuǎn)為核心來識別最具影響力的站點，隨著互聯(lián)網(wǎng)的飛速發(fā)展和用戶電子設(shè)備的快速進(jìn)步，訪問速度越來越快，使得用戶可以輕松、快速地在搜索引擎類站點或信息類站點中實現(xiàn)多次跳轉(zhuǎn)，因此具有大量跳轉(zhuǎn)數(shù)的網(wǎng)站排名較高。

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

3.3.3 算法適用性與性能分析

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

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

2）性能。OHKS 算法結(jié)合節(jié)點的全局拓?fù)湮恢茫瑫r間復(fù)雜度低、運行效率高。度中心性算法的時間復(fù)雜度低，但忽略了網(wǎng)絡(luò)的全局結(jié)構(gòu)。緊密中心性考慮了網(wǎng)絡(luò)的全局結(jié)構(gòu)，但時間復(fù)雜度高。K-Shell 算法不能提供有關(guān)節(jié)點拓?fù)湮恢玫某渥阈畔ⅰageRank 算法實驗數(shù)據(jù)量要求大、實驗設(shè)備性能要求高，且運行周期長。

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

4 結(jié)束語

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