一種基于歷史交互行為的關(guān)鍵節(jié)點(diǎn)選取算法

劉元暉

摘要：在包含大量不對(duì)等關(guān)系的實(shí)體網(wǎng)絡(luò)中，通常存在一個(gè)或多個(gè)在交互行為中起主導(dǎo)作用的節(jié)點(diǎn)，即“關(guān)鍵節(jié)點(diǎn)”。本算法參考了衡量網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的PageRank經(jīng)典算法，提出了一種基于歷史交互行為的改進(jìn)算法，并對(duì)相關(guān)的參數(shù)和公式做了定義和論述，同時(shí)對(duì)算法流程做了詳細(xì)的說(shuō)明。該算法采用節(jié)點(diǎn)交互覆蓋率作為評(píng)估指標(biāo)，計(jì)算節(jié)點(diǎn)社會(huì)影響力值，從而獲得實(shí)體網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。與傳統(tǒng)PageRank算法進(jìn)行對(duì)比，該算法具有更高的準(zhǔn)確性。

關(guān)鍵詞：關(guān)鍵節(jié)點(diǎn)； 交互行為

中圖分類(lèi)號(hào)：TP302 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）30-0198-03

1 引言

物聯(lián)網(wǎng)的核心在于實(shí)現(xiàn)物與物之間主觀能動(dòng)的信息交換和數(shù)據(jù)通信，將物體的信息通過(guò)網(wǎng)絡(luò)傳輸?shù)侥硞€(gè)信息處理中心，實(shí)現(xiàn)各種信息服務(wù)和應(yīng)用，即物物互聯(lián)。確定物聯(lián)實(shí)體間的信息交互關(guān)系，同時(shí)根據(jù)參與的交互對(duì)象的關(guān)系，自主確定信息交互的方式，進(jìn)而確定需要交互的信息，有助于提升物聯(lián)實(shí)體間的信息交互的智慧性，實(shí)現(xiàn)物聯(lián)網(wǎng)的智慧互聯(lián)。

在物聯(lián)網(wǎng)的交互關(guān)系網(wǎng)絡(luò)中，根據(jù)交互關(guān)系的方向性和信息反饋差可將交互關(guān)系分為對(duì)等關(guān)系和不對(duì)等關(guān)系。

在實(shí)體交互網(wǎng)絡(luò)中，不對(duì)等關(guān)系通常占據(jù)明顯地位，且存在于眾多設(shè)備間[1-2]。因此，不對(duì)等關(guān)系是智慧物聯(lián)網(wǎng)交互關(guān)系網(wǎng)絡(luò)研究的重點(diǎn)，而在包含大量不對(duì)等關(guān)系的實(shí)體網(wǎng)絡(luò)中，通常存在一個(gè)或多個(gè)在交互行為中起主導(dǎo)作用的節(jié)點(diǎn)，即“關(guān)鍵節(jié)點(diǎn)”[3]。在分析物聯(lián)交互關(guān)系網(wǎng)絡(luò)時(shí)，找到其中的“關(guān)鍵節(jié)點(diǎn)”，可迅速通過(guò)該節(jié)點(diǎn)找到與之相關(guān)聯(lián)的全部節(jié)點(diǎn)，繼而掌握整個(gè)網(wǎng)絡(luò)的交互關(guān)系組成。因此，研究提取關(guān)鍵節(jié)點(diǎn)的算法對(duì)于識(shí)別不對(duì)等關(guān)系有明顯的研究意義。

本文參考衡量網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的PageRank算法[4]，提出一種針對(duì)不對(duì)等關(guān)系中關(guān)鍵節(jié)點(diǎn)的選取算法，該算法通過(guò)對(duì)實(shí)體間交互歷史數(shù)據(jù)的分析，選取不對(duì)等關(guān)系中的關(guān)鍵節(jié)點(diǎn)。

2 相關(guān)定義

交互度是交互關(guān)系中控制節(jié)點(diǎn)與被控制節(jié)點(diǎn)間的交互程度，基于節(jié)點(diǎn)間的交互信息量，節(jié)點(diǎn)間的交互度定義如下：

節(jié)點(diǎn)p進(jìn)入網(wǎng)絡(luò)時(shí)，會(huì)選擇與自己擁有相同連接關(guān)系的多個(gè)節(jié)點(diǎn)，如p1，p2，p3并與之有進(jìn)一步的交互，當(dāng)節(jié)點(diǎn)p1與節(jié)點(diǎn)p進(jìn)行單向交互時(shí)，就說(shuō)明p與p1之間存在不對(duì)等交互關(guān)系，即p將自己的交互度以一定的比例分配給了p1節(jié)點(diǎn)。節(jié)點(diǎn)間的交互度分配比例定義如下：

定義4：節(jié)點(diǎn)間的交互度分配比例

定義5：時(shí)間函數(shù)

在t時(shí)刻，完成交互請(qǐng)求的累計(jì)函數(shù)為[yt]，單位時(shí)間內(nèi)完成交互請(qǐng)求的函數(shù)為[y，t]。

當(dāng)[t=0]時(shí)，[yt=0]，代表此時(shí)無(wú)交互行為進(jìn)行；當(dāng)[t>0]時(shí)，[yt]會(huì)隨著時(shí)間的增大而逐漸增大，為單調(diào)遞增函數(shù)，[y，t>0]。

SNRank算法通過(guò)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響程度來(lái)判斷關(guān)鍵節(jié)點(diǎn)，因此，定義節(jié)點(diǎn)的社會(huì)影響力如下：

定義6：節(jié)點(diǎn)的社會(huì)影響力

其中，SNR（q）、SNR（p）分別表示實(shí)體節(jié)點(diǎn)q、p的影響力值；E表示所有與節(jié)點(diǎn)q進(jìn)行交互的節(jié)點(diǎn)的集合；[p]表示節(jié)點(diǎn)p進(jìn)行單向交互的所有節(jié)點(diǎn)總和；[y，t]為t時(shí)刻時(shí)，單位時(shí)間完成交互請(qǐng)求的數(shù)量；C為用于函數(shù)收斂的阻尼系數(shù)，是一個(gè)常數(shù)，表示節(jié)點(diǎn)q收到請(qǐng)求信息并響應(yīng)后，繼續(xù)與它的下級(jí)節(jié)點(diǎn)進(jìn)行交互的概率，本文參考PageRank算法中的阻尼系數(shù)取值，在所提出的SNRank算法中，C的取值同樣為0.85。

3算法流程

算法的目的是計(jì)算出節(jié)點(diǎn)的社會(huì)影響力值，對(duì)所有節(jié)點(diǎn)的社會(huì)影響力值進(jìn)行排序，社會(huì)影響力值排序靠前的一個(gè)或多個(gè)節(jié)點(diǎn)即為所要找的“關(guān)鍵節(jié)點(diǎn)”。

算法的主要流程如下：

首先對(duì)所用到的數(shù)據(jù)集進(jìn)行初處理，將各個(gè)節(jié)點(diǎn)對(duì)應(yīng)的不同交互行為進(jìn)行分類(lèi)、累加，從而求得節(jié)點(diǎn)的全部信息量[Sq]和節(jié)點(diǎn)間的交互信息量[Np，q]，繼而求出節(jié)點(diǎn)間的交互度[Ip，q]。通過(guò)分析目標(biāo)節(jié)點(diǎn)與其他與之有交互關(guān)系的節(jié)點(diǎn)間的交互情況，可以計(jì)算該節(jié)點(diǎn)與其他節(jié)點(diǎn)間的交互度分配比例。最后，利用SNRank算法進(jìn)行不斷迭代計(jì)算，由于阻尼系數(shù)的存在，每個(gè)實(shí)體的SNRank值最終會(huì)趨于一個(gè)穩(wěn)定值，當(dāng)前后兩次計(jì)算的SNRank值的偏差足夠小時(shí)，可以認(rèn)為該值已經(jīng)保持穩(wěn)定；當(dāng)每個(gè)節(jié)點(diǎn)的SNRank值均處于穩(wěn)定時(shí)，計(jì)算結(jié)束。

該算法的流程圖如圖1所示：

4 實(shí)驗(yàn)驗(yàn)證

本文選取麻省理工學(xué)院人體動(dòng)力學(xué)實(shí)驗(yàn)室采集的Reality Mining項(xiàng)目中所收集的數(shù)據(jù)作為測(cè)試用例，來(lái)構(gòu)建實(shí)體間信息交互原始關(guān)系網(wǎng)絡(luò)。該數(shù)據(jù)集中包含了100名志愿者在一年內(nèi)彼此之間的全部通信行為記錄，包括通話記錄、短信記錄、郵件記錄、手機(jī)藍(lán)牙連接記錄、WIFI熱點(diǎn)連接記錄等物聯(lián)網(wǎng)中常見(jiàn)的數(shù)據(jù)類(lèi)型。

本文采用的準(zhǔn)確率評(píng)估指標(biāo)為交互覆蓋率（Coverage）[5]和節(jié)點(diǎn)突出率（Highlight）。

交互覆蓋率分析如圖2（上）所示，從圖中可發(fā)現(xiàn)，SNRank算法在交互覆蓋率的結(jié)果上，與PageRank算法的結(jié)果近似，說(shuō)明找到的“關(guān)鍵節(jié)點(diǎn)”都是能夠起到作為“關(guān)鍵節(jié)點(diǎn)”作用的，表明所得結(jié)果是正確的，且SNRank算法與PageRank算法的結(jié)果中的差異體現(xiàn)在交互覆蓋率上，說(shuō)明SNRank算法所提取的“關(guān)鍵節(jié)點(diǎn)”準(zhǔn)確性更高。

節(jié)點(diǎn)突出率分析如圖2（下）所示：從圖中可發(fā)現(xiàn)，SNRank算法在節(jié)點(diǎn)突出率的結(jié)果上，優(yōu)于PageRank算法，說(shuō)明了SNRank算法能夠從“非關(guān)鍵節(jié)點(diǎn)”中高效地識(shí)別出所需的“關(guān)鍵節(jié)點(diǎn)”，且提取出的“關(guān)鍵節(jié)點(diǎn)”更加突出、更有識(shí)別度。

5 總結(jié)

本文提出了一種基于歷史交互數(shù)據(jù)分析的關(guān)系識(shí)別算法。該算法結(jié)合物聯(lián)網(wǎng)內(nèi)交互數(shù)據(jù)的特性，針對(duì)數(shù)據(jù)的時(shí)空相關(guān)性進(jìn)行了分析和處理，使用了麻省理工學(xué)院人體動(dòng)力學(xué)實(shí)驗(yàn)室的Social Evolution數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，并與PageRank算法進(jìn)行了對(duì)比實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)結(jié)果，利用準(zhǔn)確性評(píng)估指標(biāo)，驗(yàn)證了所提出算法的準(zhǔn)確性和有效性。

參考文獻(xiàn)：

[1] 房旋，陳升波，宮婧，孫知信.基于社交影響力的推薦算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016，26（06）：31-36.

[2] Sergey Brin，Lawrence Page. Reprint of： The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks，2012，56（18）.

[3]Feng Li，Timon C. Du. Who is talking？ An ontology-based opinion leader identification framework for word-of-mouth marketing in online social blogs[J]. Decision Support Systems，2010，51（1）.

[4]Pavel Zakharov. Diffusion approach for community discovering within the complex networks： LiveJournal study[J]. Physica A： Statistical Mechanics and its Applications，2006，378（2）.

[5]吳渝，馬璐璐，林茂，劉洪濤.基于用戶影響力的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（03）：561-565.

【通聯(lián)編輯：代影】