劉元暉

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

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

中圖分類號：TP302 文獻標識碼：A 文章編號：1009-3044（2018）30-0198-03

1 引言

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

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

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

定義6：節(jié)點的社會影響力

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

3算法流程

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

算法的主要流程如下：

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

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

4 實驗驗證

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

本文采用的準確率評估指標為交互覆蓋率（Coverage）[5]和節(jié)點突出率（Highlight）。

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

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

5 總結(jié)

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

參考文獻：

[1] 房旋，陳升波，宮婧，孫知信.基于社交影響力的推薦算法[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]吳渝，馬璐璐，林茂，劉洪濤.基于用戶影響力的意見領(lǐng)袖發(fā)現(xiàn)算法[J].小型微型計算機系統(tǒng)，2015，36（03）：561-565.

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