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

李 勇，董思秀，張 強(qiáng)，程方頎，王常青

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

0 概述

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

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

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

1 理論基礎(chǔ)

1.1 研究框架

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

圖1 研究框架Fig.1 Research framework

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

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

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

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

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

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

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

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

1.3 HKS 算法

K-Shell 是網(wǎng)絡(luò)中一種度量節(jié)點(diǎn)影響力的算法，但不能提供有關(guān)節(jié)點(diǎn)拓?fù)湮恢玫某渥阈畔ⅰ＝陙?lái)，已有研究針對(duì)該問(wèn)題從層級(jí)角度出發(fā)提出了HKS 算法。ZAREIE 等［30］指出圖中有3 類節(jié)點(diǎn)集可以影響節(jié)點(diǎn)νi的傳播能力：

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

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

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

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

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

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

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

2 OHKS 算法

傳統(tǒng)HKS 算法在無(wú)向無(wú)權(quán)網(wǎng)絡(luò)中能夠準(zhǔn)確且高效地度量節(jié)點(diǎn)的影響力并確定其拓?fù)湮恢谩Ｈ欢谟邢蚣訖?quán)網(wǎng)絡(luò)中HKS 算法面臨適用性挑戰(zhàn)。因此，本文利用OHKS 算法來(lái)研究注意力流網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的層級(jí)性。在有向加權(quán)注意力流網(wǎng)絡(luò)中，節(jié)點(diǎn)表示用戶點(diǎn)擊過(guò)的站點(diǎn)，用戶在站點(diǎn)的停留時(shí)間表示節(jié)點(diǎn)的權(quán)重，邊表示集體用戶注意力從一個(gè)站點(diǎn)跳轉(zhuǎn)到下一個(gè)站點(diǎn)，跳轉(zhuǎn)次數(shù)表示節(jié)點(diǎn)的度，度表示邊的權(quán)重（不區(qū)分節(jié)點(diǎn)的出度和入度）。OHKS 算法采用凈注意力流入來(lái)度量節(jié)點(diǎn)的影響力，用戶瀏覽站點(diǎn)的先后順序表示邊的方向，根據(jù)入度計(jì)算邊的權(quán)重（區(qū)分出度和入度），再結(jié)合頂點(diǎn)的權(quán)重得出點(diǎn)入中心性。

2.1 節(jié)點(diǎn)層級(jí)位置時(shí)間

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

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

2.2 節(jié)點(diǎn)位置約束

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

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

2.3 節(jié)點(diǎn)影響力

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

3 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

表4 站點(diǎn)的入度平均停留時(shí)間Table 4 In-degree average retention time of site

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

3.3.1 對(duì)比算法分析

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

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

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

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

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

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

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

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

3.3.2 節(jié)點(diǎn)影響力識(shí)別方式分析

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

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

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

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

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

3.3.3 算法適用性與性能分析

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

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

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

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

4 結(jié)束語(yǔ)

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