基于結(jié)構(gòu)熵的注意力流網(wǎng)絡(luò)異構(gòu)性研究

馬滿福，郭晨彪，李 勇，張鐘穎，張 強(qiáng)，王常青

1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，蘭州 730070

2.中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心 互聯(lián)網(wǎng)基礎(chǔ)技術(shù)開(kāi)放實(shí)驗(yàn)室，北京 100190

復(fù)雜網(wǎng)絡(luò)能夠很好地描述自然科學(xué)、社會(huì)科學(xué)、管理科學(xué)和工程技術(shù)領(lǐng)域等相互關(guān)聯(lián)的復(fù)雜模型，是研究復(fù)雜系統(tǒng)中子系統(tǒng)交互和關(guān)系的重要工具，是網(wǎng)絡(luò)科學(xué)中重要的研究方法[1]。錢(qián)學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個(gè)較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜且節(jié)點(diǎn)數(shù)目巨大，呈現(xiàn)多種不同特征，雖然各部分之間相互聯(lián)系，但在功能結(jié)構(gòu)上存在差異[2-3]。網(wǎng)絡(luò)的拓?fù)湫再|(zhì)、功能以及動(dòng)力學(xué)行為均與網(wǎng)絡(luò)的復(fù)雜性緊密相連，復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的聯(lián)系對(duì)于網(wǎng)絡(luò)復(fù)雜性刻畫(huà)十分有意義，也一直是復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)[4]。

復(fù)雜系統(tǒng)中病毒傳播[5]、社區(qū)結(jié)構(gòu)劃分[6]、節(jié)點(diǎn)重要性排序分析[7-9]、信息擴(kuò)散[10]等，都與網(wǎng)絡(luò)的異構(gòu)性不無(wú)關(guān)系[11-12]。熵是描述復(fù)雜系統(tǒng)結(jié)構(gòu)的物理量，而關(guān)系結(jié)構(gòu)的熵可以定量描述網(wǎng)絡(luò)狀態(tài)，是測(cè)度網(wǎng)絡(luò)結(jié)構(gòu)無(wú)序性的重要指標(biāo)。通過(guò)定義網(wǎng)絡(luò)結(jié)構(gòu)熵評(píng)價(jià)網(wǎng)絡(luò)異構(gòu)性，一般地，網(wǎng)絡(luò)結(jié)構(gòu)熵值越小，網(wǎng)絡(luò)越混亂，意味著網(wǎng)絡(luò)各部分間的差異越大，異構(gòu)性越強(qiáng)；反之網(wǎng)絡(luò)結(jié)構(gòu)熵越大，網(wǎng)絡(luò)越有序，意味著網(wǎng)絡(luò)結(jié)構(gòu)越趨于均衡，異構(gòu)性越弱[13-15]。目前，已有大量的研究各自從不同角度出發(fā)提出定義網(wǎng)絡(luò)結(jié)構(gòu)熵，主要有度分布熵[15]、吳結(jié)構(gòu)熵[16]、剩余度熵[15]、蔡結(jié)構(gòu)熵[17-19]等。

網(wǎng)絡(luò)結(jié)構(gòu)熵是研究復(fù)雜網(wǎng)絡(luò)的重要工具，能夠很好地度量網(wǎng)絡(luò)結(jié)構(gòu)的特征，反映了網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的異構(gòu)性。傳統(tǒng)的異構(gòu)性度量指標(biāo)度分布熵、吳結(jié)構(gòu)熵、SD結(jié)構(gòu)熵等，均從網(wǎng)絡(luò)中“點(diǎn)”或“邊”的特征來(lái)定義結(jié)構(gòu)熵。注意力流網(wǎng)絡(luò)是基于在線行為數(shù)據(jù)，通過(guò)點(diǎn)擊網(wǎng)站序列而構(gòu)建成的有向加權(quán)圖。在網(wǎng)絡(luò)中的節(jié)點(diǎn)代表Web站點(diǎn)，用戶從一個(gè)Web站點(diǎn)通過(guò)點(diǎn)擊跳轉(zhuǎn)到了另一個(gè)Web站點(diǎn)形成邊，站點(diǎn)之間的跳轉(zhuǎn)次數(shù)表示邊的權(quán)值，Web站點(diǎn)的特殊屬性就是站點(diǎn)的停留時(shí)長(zhǎng)。根據(jù)注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)熵不能準(zhǔn)確地度量注意力流網(wǎng)絡(luò)的異構(gòu)性。因此，尋找一種針對(duì)注意力流網(wǎng)絡(luò)異構(gòu)性特征的測(cè)度方法是本文研究的目的所在。本文的主要貢獻(xiàn)如下：

（1）以中國(guó)互聯(lián)網(wǎng)信息中心（CNNIC）提供的海量在線上網(wǎng)行為大數(shù)據(jù)構(gòu)建注意力流網(wǎng)絡(luò)。

（2）基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)異構(gòu)性的研究方法，結(jié)合注意力流網(wǎng)絡(luò)的站點(diǎn)及結(jié)構(gòu)特征，建立了注意力流網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)站點(diǎn)重要度的評(píng)價(jià)指標(biāo)，構(gòu)建了注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵模型，提出了注意力流網(wǎng)絡(luò)異構(gòu)性度量算法ANSE。

（3）通過(guò)實(shí)驗(yàn)分析，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵夠更好地刻畫(huà)注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，準(zhǔn)確地度量注意力流網(wǎng)絡(luò)中各站點(diǎn)的差異性，從而分析各網(wǎng)絡(luò)各站點(diǎn)的屬性特征。

1 相關(guān)工作

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

注意力流網(wǎng)絡(luò)作為網(wǎng)絡(luò)科學(xué)的一個(gè)重要分支，吸引了大量的研究人員的關(guān)注。基于加權(quán)復(fù)雜網(wǎng)絡(luò)方法研究注意力流網(wǎng)絡(luò)，研究人員在已有的研究中發(fā)現(xiàn)了多個(gè)重要的普適規(guī)律，例如：Web站點(diǎn)間注意力流演化的異速標(biāo)度律和耗散律、在注意力流網(wǎng)絡(luò)中發(fā)現(xiàn)了引力律、在注意力流中還發(fā)現(xiàn)了Heaps律等[20-23]。文獻(xiàn)[24]提出了一種在不同網(wǎng)站之間分配和流動(dòng)的幾何表示方法，根據(jù)網(wǎng)站流動(dòng)距離將大量網(wǎng)站嵌入20維歐氏空間中，發(fā)現(xiàn)20%受歡迎的網(wǎng)站吸引了75%的注意力流；文獻(xiàn)[23]基于在線集體注意力流研究網(wǎng)站的站點(diǎn)影響力，將網(wǎng)絡(luò)視為虛擬生物，根據(jù)代謝理論，網(wǎng)站必須吸收“能量”來(lái)生長(zhǎng)、繁衍和發(fā)展，將新陳代謝和用戶注意力的影響視為網(wǎng)站的能量，基于網(wǎng)絡(luò)科學(xué)理論建立注意力流網(wǎng)絡(luò)，研究了集體注意力在不同站點(diǎn)間的分布、流動(dòng)以及Web的新陳代謝規(guī)律。研究發(fā)現(xiàn)站點(diǎn)的影響力與注意力在該站點(diǎn)上的停留時(shí)間呈亞線性關(guān)系，亦即Web版的Kleiber律。然而很少有學(xué)者研究注意力流網(wǎng)絡(luò)異構(gòu)性，研究注意力流網(wǎng)絡(luò)的異構(gòu)性，分析站點(diǎn)的差異及網(wǎng)絡(luò)結(jié)構(gòu)特征具有重要的理論意義和應(yīng)用價(jià)值。

1.2 網(wǎng)絡(luò)結(jié)構(gòu)熵

網(wǎng)絡(luò)結(jié)構(gòu)熵主要基于網(wǎng)絡(luò)中節(jié)點(diǎn)、邊的特征來(lái)定義，其中網(wǎng)絡(luò)節(jié)點(diǎn)的差異性由節(jié)點(diǎn)概率分布來(lái)度量。反映網(wǎng)絡(luò)連接特征的熵有度分布熵、吳網(wǎng)絡(luò)結(jié)構(gòu)熵、蔡網(wǎng)絡(luò)結(jié)構(gòu)熵等。

（1）度分布熵[15]，以邊為研究對(duì)象，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)度概率分布，對(duì)網(wǎng)絡(luò)的異構(gòu)性進(jìn)行了測(cè)度，定義度分布網(wǎng)絡(luò)結(jié)構(gòu)熵。

（2）吳結(jié)構(gòu)熵[16]，以節(jié)點(diǎn)為主體，通過(guò)分析網(wǎng)絡(luò)節(jié)點(diǎn)所擁有的邊的條數(shù)，即各節(jié)點(diǎn)度值之間的差異來(lái)反映網(wǎng)絡(luò)的異構(gòu)性，從而提出了基于網(wǎng)絡(luò)中節(jié)點(diǎn)的特征的網(wǎng)絡(luò)結(jié)構(gòu)熵。

（3）SD結(jié)構(gòu)熵[17]，為了綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)中“點(diǎn)”或者“邊”的作用，蔡萌等綜合考慮了“點(diǎn)”和“邊”差異性，定義網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)重要性，提出了一種新的SD網(wǎng)絡(luò)結(jié)構(gòu)熵，反映網(wǎng)絡(luò)的異構(gòu)性。

文獻(xiàn)[15]指出度分布熵可以測(cè)度網(wǎng)絡(luò)異構(gòu)性，當(dāng)網(wǎng)絡(luò)中各節(jié)點(diǎn)的度值均不相同，即P(k)=1/(N-1)(?k=1,2,…,N-1)時(shí)，網(wǎng)絡(luò)的度分布熵取最大值，=ln(N-1)；相反，對(duì)于網(wǎng)絡(luò)中各節(jié)點(diǎn)的度均相同的規(guī)則網(wǎng)絡(luò)，則有，對(duì)于星型網(wǎng)絡(luò)等特殊網(wǎng)絡(luò)異構(gòu)性度量的準(zhǔn)確性不夠。文獻(xiàn)[16]吳結(jié)構(gòu)熵以節(jié)點(diǎn)為主體，通過(guò)分析網(wǎng)絡(luò)節(jié)點(diǎn)所擁有的邊的條數(shù)，即各節(jié)點(diǎn)度值之間的差異來(lái)反映網(wǎng)絡(luò)的異構(gòu)性，吳結(jié)構(gòu)熵的最小值對(duì)應(yīng)于星型網(wǎng)絡(luò)；最大值對(duì)應(yīng)于最近鄰耦合網(wǎng)絡(luò)Hmaxwu=lnN，吳結(jié)構(gòu)熵關(guān)注網(wǎng)絡(luò)連接的度分布定義節(jié)點(diǎn)重要性，忽略了節(jié)點(diǎn)本身的特性，例如在稀疏網(wǎng)絡(luò)中忽略了孤立節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響。文獻(xiàn)[17]從“點(diǎn)”差異性和“邊”差異性兩方面提出了點(diǎn)邊差異性SD結(jié)構(gòu)熵。該網(wǎng)絡(luò)結(jié)構(gòu)熵是一種有效度量網(wǎng)絡(luò)異構(gòu)性的指標(biāo)，并對(duì)稀疏網(wǎng)絡(luò)和星型網(wǎng)絡(luò)有很好的解釋，但該方法的本質(zhì)仍是以節(jié)點(diǎn)度值為基礎(chǔ)，與度分布熵和吳結(jié)構(gòu)熵等其他指標(biāo)一樣，過(guò)多強(qiáng)調(diào)網(wǎng)絡(luò)的局部特征，而忽略了特殊網(wǎng)絡(luò)的拓?fù)涮卣?。然而很少有學(xué)者研究注意力流網(wǎng)絡(luò)異構(gòu)性。

以上幾種結(jié)構(gòu)熵，均基于網(wǎng)絡(luò)中節(jié)點(diǎn)、邊的特征來(lái)定義的網(wǎng)絡(luò)結(jié)構(gòu)熵，針對(duì)注意力流網(wǎng)絡(luò)的web站點(diǎn)停留時(shí)長(zhǎng)等特殊屬性不適用，即通過(guò)傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)熵?zé)o法準(zhǔn)確地度量注意力流網(wǎng)絡(luò)Web站點(diǎn)的差異，對(duì)刻畫(huà)注意力流網(wǎng)絡(luò)異構(gòu)性不夠準(zhǔn)確。因此，本文基于注意力流網(wǎng)絡(luò)結(jié)構(gòu)及Web站點(diǎn)的特征，定義注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵，提出注意力流網(wǎng)絡(luò)異構(gòu)性算法。本文提出的注意力流網(wǎng)絡(luò)異構(gòu)性算法具有重要的理論意義與應(yīng)用價(jià)值。從理論價(jià)值來(lái)看，異構(gòu)性研究能夠很好地刻畫(huà)注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，在站點(diǎn)重要性排序分析、網(wǎng)站影響力分析、網(wǎng)站分類、社區(qū)發(fā)現(xiàn)等研究中發(fā)揮重要作用；從應(yīng)用價(jià)值來(lái)看，站點(diǎn)重要性排序等方面研究已廣泛應(yīng)用于網(wǎng)絡(luò)輿情監(jiān)控、個(gè)性化推薦、廣告精準(zhǔn)投放等方面。

2 注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵

2.1 注意力流網(wǎng)絡(luò)構(gòu)建

在線用戶行為日志數(shù)據(jù)采集中，用戶每次一開(kāi)機(jī)就會(huì)建立一個(gè)在線行為日志數(shù)據(jù)文件，該日志數(shù)據(jù)記錄每?jī)擅霗z查一次用戶計(jì)算機(jī)當(dāng)前的焦點(diǎn)窗口，如果檢查相比前兩秒發(fā)生了變化，則增加一條記錄來(lái)描述當(dāng)前焦點(diǎn)窗口信息。在保證用戶隱私的前提下，詳細(xì)記錄了開(kāi)機(jī)時(shí)間與上次關(guān)機(jī)時(shí)間、焦點(diǎn)窗口的窗口進(jìn)程名稱、URL地址、當(dāng)前標(biāo)簽頁(yè)句柄、程序名稱、程序所屬公司名稱以及用戶人口屬性等信息。表1為在線點(diǎn)擊流序列樣例。

表1 在線點(diǎn)擊流序列樣例Table 1 Example of online clickstream sequence

對(duì)于一個(gè)有N個(gè)節(jié)點(diǎn)注意力流網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)由一個(gè)加權(quán)有向圖G=(V,E,T,Z)表示，如圖1所示。其中V={v0,v1,…, }vN+1表示N+2個(gè)注意力流網(wǎng)絡(luò)的站點(diǎn)；E∈V×V為圖中的邊集；T表示集體用戶在一個(gè)站點(diǎn)上停留的總時(shí)間；Z表示邊E的權(quán)重，是一個(gè)正的自然數(shù)集，邊權(quán)值Z表示各個(gè)站點(diǎn)間轉(zhuǎn)換的強(qiáng)度，若不存在的邊其權(quán)值為0，表示用戶在網(wǎng)絡(luò)中Web節(jié)點(diǎn)的入度或出度，注意力流網(wǎng)絡(luò)示意圖如圖1所示。

圖1 注意力流網(wǎng)絡(luò)示例Fig.1 Example of attention flow network

在一個(gè)會(huì)話期間（session），一個(gè)用戶進(jìn)入一個(gè)Web站點(diǎn)后必定會(huì)在一段時(shí)間后離開(kāi)該Web站點(diǎn)，所以注意力流網(wǎng)絡(luò)是平衡的，表明每個(gè)頂點(diǎn)的總?cè)肓鳎╥nflow）與總出流（outflow）相等關(guān)系。在網(wǎng)絡(luò)中增加了兩個(gè)額外節(jié)點(diǎn)“source”節(jié)點(diǎn)（表示為節(jié)點(diǎn)0）和“sink”節(jié)點(diǎn)（表示為節(jié)點(diǎn)N+1），分別表示點(diǎn)擊流的“源”和“匯”。每個(gè)用戶從“source”節(jié)點(diǎn)開(kāi)始上網(wǎng)，當(dāng)該會(huì)話結(jié)束后進(jìn)入“sink”節(jié)點(diǎn)，用戶結(jié)束其上網(wǎng)行為。會(huì)話（session）表示用戶在一個(gè)Web站點(diǎn)上瀏覽的時(shí)間間隔，把會(huì)話時(shí)間間隔閾值定義為30分鐘是學(xué)術(shù)界針對(duì)萬(wàn)維網(wǎng)研究普遍采用的標(biāo)準(zhǔn)值[25]。

2.2 注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵模型

根據(jù)傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)熵模型，依據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)特征，通過(guò)站點(diǎn)之間跳轉(zhuǎn)的次數(shù)（即邊的權(quán)值）、停留時(shí)間等，綜合定義Web站點(diǎn)的流強(qiáng)度、站點(diǎn)之間的轉(zhuǎn)移概率、站點(diǎn)總時(shí)長(zhǎng)、站點(diǎn)吸引注意力的能力，結(jié)合Web站點(diǎn)的注意力總流量計(jì)算站點(diǎn)的綜合力，用站點(diǎn)綜合力來(lái)度量站點(diǎn)的差異性，刻畫(huà)注意力流網(wǎng)絡(luò)的異構(gòu)性，基于此基礎(chǔ)的Web站點(diǎn)重要度來(lái)定義注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵。對(duì)比傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)熵，該模型綜合考慮了Web站點(diǎn)、站點(diǎn)之間的跳轉(zhuǎn)、停留時(shí)間等，進(jìn)而全面準(zhǔn)確地度量注意力流網(wǎng)絡(luò)的異構(gòu)性。

通過(guò)網(wǎng)絡(luò)有向圖計(jì)算流矩陣，然后確定概率轉(zhuǎn)移矩陣，由站點(diǎn)總時(shí)長(zhǎng)計(jì)算對(duì)站點(diǎn)的吸引能力，最后通過(guò)站點(diǎn)耗散能力和概率轉(zhuǎn)移矩陣得到基本矩陣。由基本矩陣計(jì)算從源節(jié)點(diǎn)到目的站點(diǎn)的總流量，最終得到網(wǎng)絡(luò)站點(diǎn)的綜合力。

在一個(gè)有N節(jié)點(diǎn)的注意力流網(wǎng)絡(luò)中，網(wǎng)絡(luò)中增加了兩個(gè)額外節(jié)點(diǎn)“source”節(jié)點(diǎn)和“sink”節(jié)點(diǎn)，圖G中定義一個(gè)帶權(quán)(N+2)×(N+2)的流矩陣S(G)，流矩陣S(G)中的元素Zij=(i,j)表示從站點(diǎn)i到站點(diǎn)j的注意力流強(qiáng)度，Zij=0表示從站點(diǎn)i到站點(diǎn)j的無(wú)鏈路。圖G的流矩陣S(G)可以表示為：

由流矩陣S(G)定義一個(gè)概率轉(zhuǎn)移矩陣P(G)，P(G)表示圖G上的馬爾可夫鏈概率轉(zhuǎn)移矩陣，其中，在概率轉(zhuǎn)移矩陣P(G)中，Pij表示從站點(diǎn)i到站點(diǎn)j之間的轉(zhuǎn)移概率。圖G上的概率轉(zhuǎn)移矩陣P(G)表示為：

在注意力流網(wǎng)絡(luò)中，假設(shè)有k個(gè)用戶瀏覽了Web站點(diǎn)i，每個(gè)用戶瀏覽的時(shí)間長(zhǎng)度為tj，那么網(wǎng)絡(luò)中所有用戶在該Web節(jié)點(diǎn)的總時(shí)長(zhǎng)Ti，定義總時(shí)長(zhǎng)Ti為：

用βi表示W(wǎng)eb站點(diǎn)i對(duì)注意力流的耗散能力，來(lái)度量Web站點(diǎn)吸引注意力的能力，采用文獻(xiàn)[26]方法定義βi為：

定義矩陣D(G)為：Dij=βPij，由于β∈(0,]1，所以矩陣D(G)為去除源節(jié)點(diǎn)為(N+1)×(N+1)的矩陣。對(duì)于一個(gè)吸收馬爾可夫鏈[27]，定義基本矩陣X(G)為：

其中，I為單位矩陣。

由定義的基本矩陣計(jì)算源節(jié)點(diǎn)流到Web站點(diǎn)i的注意力總流量，用Mi來(lái)表示，Mi定義為：

根據(jù)Web站點(diǎn)i的注意力總流量來(lái)定義Web站點(diǎn)的綜合力為：

其中，Ei為Web站點(diǎn)i綜合力，xij為基本矩陣X(G)中的元素。

通過(guò)Web站點(diǎn)的綜合力的差異性來(lái)反映注意力流網(wǎng)絡(luò)的異構(gòu)性，提出基于注意力流網(wǎng)絡(luò)站點(diǎn)特征的網(wǎng)絡(luò)結(jié)構(gòu)熵。

根據(jù)網(wǎng)絡(luò)異構(gòu)性矩陣、Web站點(diǎn)流強(qiáng)度、站點(diǎn)總時(shí)長(zhǎng)、站點(diǎn)吸引注意力的能力等，結(jié)合Web站點(diǎn)的注意力總流量計(jì)算Web站點(diǎn)的綜合力，可求得Web站點(diǎn)i相對(duì)重要度Ii，其計(jì)算公式為：

若某Web站點(diǎn)的綜合力越大，可認(rèn)為該站點(diǎn)在注意力流網(wǎng)絡(luò)中的影響力越大，其Web站點(diǎn)越重要，為了衡量注意力流網(wǎng)絡(luò)在各Web站點(diǎn)重要度或者影響力的差異，結(jié)合信息論中熵的計(jì)算方法，以及基于公式（9）Web站點(diǎn)i的重要度計(jì)算方法，可得到注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵，其計(jì)算公式為：

其中，HA為注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵，Ii為站點(diǎn)的相對(duì)重要度。在注意力流網(wǎng)絡(luò)中HA的值越小，說(shuō)明網(wǎng)絡(luò)在Web站點(diǎn)綜合力尺度下的異構(gòu)性越強(qiáng)，反之網(wǎng)絡(luò)的異構(gòu)則越弱。

2.3 注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵算法ANSE

基于注意力流結(jié)構(gòu)熵模型，提出注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵算法ANSE（Attention flow Network Structural Entropy），由此得到網(wǎng)絡(luò)的流矩陣、站點(diǎn)上停留時(shí)長(zhǎng)、站點(diǎn)的綜合力等，最終通過(guò)算法輸出注意力流網(wǎng)絡(luò)的結(jié)構(gòu)熵。

算法1構(gòu)建注意力流網(wǎng)絡(luò)計(jì)算流矩陣

輸入：Si={T,P,IDi}，其中T為開(kāi)始時(shí)間，P表示為web站點(diǎn)，IDi表示用戶標(biāo)識(shí)；得到注意力流網(wǎng)絡(luò)G=(V,E,T,Z)，V表示頂點(diǎn)集，E表示圖中的邊集，T表示頂點(diǎn)權(quán)重，Z表示流強(qiáng)度

輸出：注意力流網(wǎng)絡(luò)的流矩陣S(G)

1.G=nx.DiGraph

2.G.add_node（‘source’，time=0 pages=0）

3.G.add_node（‘sink’，time=0 pages=0）

4.For i in Si:

5. G.add_node（i，time）

算法2注意力流網(wǎng)絡(luò)的基本矩陣算法

輸入：注意力流網(wǎng)絡(luò)的馬爾可夫矩陣，網(wǎng)絡(luò)Web站點(diǎn)總時(shí)長(zhǎng)。

輸出：基本矩陣X(G)

算法3注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵算法

輸入：注意力流網(wǎng)絡(luò)基本矩陣X(G)及流矩陣S(G)

輸出：注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵值

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

以中國(guó)互聯(lián)網(wǎng)信息中心（CNNIC）提供的海量在線用戶行數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，累積已達(dá)PB量級(jí)，該數(shù)據(jù)集為CNNIC目前提供的最新數(shù)據(jù)，為實(shí)驗(yàn)分析方便，本文隨機(jī)抽取該數(shù)據(jù)集中1 000名用戶1個(gè)月大約1.3億條數(shù)據(jù)記錄進(jìn)行實(shí)驗(yàn)研究，數(shù)據(jù)樣例如圖2所示。

圖2 在線行為日志數(shù)據(jù)樣例Fig.2 Example of online behavior log data

3.2 注意力流網(wǎng)絡(luò)結(jié)構(gòu)特征分析

對(duì)在線行為日志數(shù)據(jù)進(jìn)行清洗處理，使用網(wǎng)絡(luò)科學(xué)的建模方法，Web站點(diǎn)看作節(jié)點(diǎn)，用戶的站點(diǎn)轉(zhuǎn)移流動(dòng)看作邊，站點(diǎn)停留時(shí)長(zhǎng)作為節(jié)點(diǎn)權(quán)重，建立有向加權(quán)的注意力流網(wǎng)絡(luò)，通過(guò)集體用戶的數(shù)據(jù)構(gòu)建集體注意力流網(wǎng)絡(luò)圖，構(gòu)建的注意力流網(wǎng)絡(luò)中擁有20 746個(gè)節(jié)點(diǎn)和135 771條邊。注意力流網(wǎng)絡(luò)圖如圖3所示。

圖3 集體注意力流網(wǎng)絡(luò)Fig.3 Collective attention flow network

在構(gòu)造的注意力流網(wǎng)絡(luò)中，分析注意力流網(wǎng)絡(luò)出入度、站點(diǎn)的總停留時(shí)長(zhǎng)的排名以及相關(guān)網(wǎng)絡(luò)結(jié)構(gòu)的其他特征。如圖4是出度前20名的站點(diǎn)降序排名圖，然后以出度為排序的方式繪制入度的折線圖，從圖上可以看出，其網(wǎng)絡(luò)的站點(diǎn)出、入度值非常接近，而且每個(gè)站點(diǎn)出度和入度的排序基本是一致的，再次說(shuō)明注意力流網(wǎng)絡(luò)是平衡的。

圖4 站點(diǎn)度值前20降序排序圖Fig.4 Descending order of top 20 websites

表2是所有站點(diǎn)總時(shí)間排名前10的站點(diǎn)，根據(jù)站點(diǎn)分析，排名前10的站點(diǎn)均為常用的站點(diǎn)，其中排名第一的qq.com為娛樂(lè)、社交、新聞?lì)愓军c(diǎn)，第二的baidu.com為搜索引擎類網(wǎng)站，第三的taobao.com為購(gòu)物類網(wǎng)站；對(duì)比停留時(shí)間排名與站點(diǎn)以度值排名的結(jié)果有差異，單獨(dú)從站點(diǎn)度值或者總停留時(shí)長(zhǎng)等方面排名來(lái)衡量站點(diǎn)的重要度是不準(zhǔn)確的。因此需要從站點(diǎn)的度值、停留時(shí)長(zhǎng)等多個(gè)方面綜合度量站點(diǎn)差異性，以站點(diǎn)的綜合力來(lái)測(cè)度網(wǎng)絡(luò)結(jié)構(gòu)的異構(gòu)性。

表2 站點(diǎn)總停留時(shí)長(zhǎng)前10排名Table 2 Top 10 websites for total length of stay

3.3 注意力流網(wǎng)絡(luò)異構(gòu)性分析

根據(jù)注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵算法ANSE，實(shí)驗(yàn)分析注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵。在注意力流網(wǎng)絡(luò)中，基于整體網(wǎng)絡(luò)結(jié)構(gòu)異構(gòu)性的度量，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵算法ANSE綜合考慮了站點(diǎn)的度值大小、停留時(shí)間、站點(diǎn)的總流量等，以站點(diǎn)的綜合力為度量網(wǎng)絡(luò)異構(gòu)性更為準(zhǔn)確，在本文實(shí)驗(yàn)中記吳結(jié)構(gòu)熵為Wu結(jié)構(gòu)熵，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵為Ha結(jié)構(gòu)熵，度分布熵為Du度分布熵，蔡SD結(jié)構(gòu)熵為SD結(jié)構(gòu)熵。

在注意力流網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)為20 746個(gè)，不同邊值的節(jié)點(diǎn)數(shù)量為280個(gè)，按照度分布熵模型，Du度分布熵最大值5.634，隨著相同度值節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)度分布熵值也也會(huì)逐漸變小，當(dāng)20 746個(gè)節(jié)點(diǎn)全加入時(shí)，Du度分布熵達(dá)到了最小2.491。因此，依據(jù)注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，用度分布熵來(lái)度量注意力流網(wǎng)絡(luò)的異構(gòu)性是不準(zhǔn)確的。其中蔡SD結(jié)構(gòu)熵結(jié)合度分布熵和吳結(jié)構(gòu)熵，單一地考慮節(jié)點(diǎn)和邊，因此度量注意力流網(wǎng)絡(luò)中也是不準(zhǔn)確的。

分析注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，適合用吳結(jié)構(gòu)熵和注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵來(lái)度量注意力流網(wǎng)絡(luò)的異構(gòu)性。通過(guò)實(shí)驗(yàn)得到網(wǎng)絡(luò)結(jié)構(gòu)熵值如表3所示，Wu結(jié)構(gòu)熵值為7.875，Ha結(jié)構(gòu)熵值為6.579，在該注意力流網(wǎng)絡(luò)中Ha結(jié)構(gòu)熵小于Wu網(wǎng)絡(luò)結(jié)構(gòu)熵，網(wǎng)絡(luò)結(jié)構(gòu)熵值越小，注意力流網(wǎng)絡(luò)越混亂，意味著網(wǎng)絡(luò)各部分間的差異越大，異構(gòu)性越強(qiáng)。因此，從網(wǎng)絡(luò)整體結(jié)構(gòu)熵分析，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵能更好地度量網(wǎng)絡(luò)的異構(gòu)性。

表3 網(wǎng)絡(luò)結(jié)構(gòu)熵對(duì)比Table 3 Comparison of network structure entropy

3.4 站點(diǎn)差異性分析

分析發(fā)現(xiàn)，采用熵值算法計(jì)算單個(gè)站點(diǎn)的熵值，利用注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵模型，站點(diǎn)的綜合力越大站點(diǎn)熵值越大，所有站點(diǎn)的熵值如圖5所示，最大從0.135依次降低，到最后站點(diǎn)時(shí)熵值接近0；利用Wu結(jié)構(gòu)熵模型，結(jié)果如圖6所示，隨著站點(diǎn)的綜合力降低站點(diǎn)熵值也基本整體依次降低，但有個(gè)別站點(diǎn)存在前一站點(diǎn)熵值高的情況。圖7為排名前30的Ha和Wu結(jié)構(gòu)熵站點(diǎn)熵值對(duì)比。例如sogou.com的Wu熵值為0.075 5，taobao.com站點(diǎn)Wu熵值為0.047 2，按照注意力流網(wǎng)絡(luò)站點(diǎn)綜合力的比較taobao.com站點(diǎn)要比sogou.com站點(diǎn)值大，Wu結(jié)構(gòu)熵只考慮站點(diǎn)的度值的大小，說(shuō)明Wu結(jié)構(gòu)熵在刻畫(huà)注意力流網(wǎng)絡(luò)站點(diǎn)的差異性時(shí)存在不足。因此，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵能夠很好度量網(wǎng)絡(luò)站點(diǎn)的差異性。

圖5 Ha結(jié)構(gòu)熵站點(diǎn)熵值Fig.5 Entropy of Ha structure entropy websites

圖6 Wu結(jié)構(gòu)熵站點(diǎn)熵值Fig.6 Entropy of Wu structure entropy websites

圖7 Ha和Wu結(jié)構(gòu)熵站點(diǎn)熵值對(duì)比Fig.7 Comparison of entropy values of Ha and Wu structure entropy websites

表4 各種站點(diǎn)重要性算法排名前15的站點(diǎn)Table 4 Top 15 websites ranked by various website importance algorithms

以上實(shí)驗(yàn)分析得出，Web站點(diǎn)之間有著很大的差異，注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵能夠更準(zhǔn)確衡量站點(diǎn)的重要性，利用注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵進(jìn)行節(jié)點(diǎn)重要性排序分析，站點(diǎn)的Ha結(jié)構(gòu)熵值越大，說(shuō)明站點(diǎn)越重要，站點(diǎn)的影響力越大。在構(gòu)建的注意力流網(wǎng)絡(luò)中用ANSE算法和經(jīng)典的節(jié)點(diǎn)重要性算法對(duì)比分析，分別和度中心性DC、中介中心性BC、接近中心性CC、特征向量中心性EC、PageRank對(duì)比分析。

表4顯示了各種站點(diǎn)重要性算法排名前15名的站點(diǎn)。用各種算法的站點(diǎn)排名和中國(guó)的Alexa排名對(duì)比（Alexa排名是指網(wǎng)站的世界排名，是當(dāng)前較為權(quán)威的網(wǎng)站綜合排名評(píng)價(jià)指標(biāo)。），本文提出的算法和Alexa排名更加接近一致，其他傳統(tǒng)算法和Alexa排名有差異。在各種算法前15排名中，站點(diǎn)基本一致，但站點(diǎn)排名卻不同，因此，說(shuō)明本文算法的有效性和優(yōu)越性，能夠更好地度量站點(diǎn)的影響力。

實(shí)驗(yàn)得出，本文提出的注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵模型的熵更小，能夠更好地度量網(wǎng)絡(luò)異構(gòu)性；在站點(diǎn)重要性排名方面，本文提出算法排名更接近Alexa排名，ANSE算法能夠有效度量網(wǎng)絡(luò)站點(diǎn)的重要性。

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

本文利用在線點(diǎn)擊上網(wǎng)行為數(shù)據(jù)，構(gòu)建注意力流網(wǎng)絡(luò)，分析注意力流網(wǎng)絡(luò)結(jié)構(gòu)，基于網(wǎng)絡(luò)結(jié)構(gòu)熵研究注意力流網(wǎng)絡(luò)的異構(gòu)性。針對(duì)注意力流網(wǎng)絡(luò)的結(jié)構(gòu)特征，傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)熵不能定量地度量注意力流網(wǎng)絡(luò)的異構(gòu)性，本文構(gòu)建了基于注意力流網(wǎng)絡(luò)的結(jié)構(gòu)熵模型，提出了注意力流網(wǎng)絡(luò)異構(gòu)性度量算法ANSE，通過(guò)實(shí)驗(yàn)分析對(duì)比，本文提出的注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵綜合地從網(wǎng)絡(luò)的站點(diǎn)度、停留時(shí)間等因素，能夠更好地刻畫(huà)注意力流網(wǎng)絡(luò)的異構(gòu)性。實(shí)驗(yàn)表明，站點(diǎn)的注意力流網(wǎng)絡(luò)結(jié)構(gòu)熵值越大，其站點(diǎn)越重要，站點(diǎn)的影響力越大。依據(jù)注意力流結(jié)構(gòu)熵站點(diǎn)重要性排序，分別和經(jīng)典節(jié)點(diǎn)重要性算法度中心性DC、中介中心性BC、接近中心性CC、特征向量中心性EC、PageRank對(duì)比分析發(fā)現(xiàn)，結(jié)構(gòu)熵能更好地度量注意力流網(wǎng)絡(luò)中站點(diǎn)的重要性，有效地分析站點(diǎn)差異性，為站點(diǎn)影響力排名提供理論依據(jù)，該研究可應(yīng)用于社區(qū)發(fā)現(xiàn)、網(wǎng)絡(luò)輿情監(jiān)控、個(gè)性化推薦、廣告精準(zhǔn)投放等方面。