共享局部算法的數據分析

崔鵬宇

摘要：本文針對單一關系的數據挖掘方案不能精準的發現網絡中隱藏的問題，通過提出異構網絡數據挖掘的算法達到網絡節點的初步劃分目標的實并且能夠初步此得到各數據子集。

關鍵詞：異構網絡；數據挖掘；共享局部結構

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9416（2018）01-0138-02

隨著社會網絡分析的進一步發展，人們逐漸發現單一的關系網絡并不能很好的刻畫出實體間的真實結構[1]。在現實的社會網絡中，實體之間往往是多種關系交織在一起的[2]。每種關系對應一個關系圖，僅僅利用一種關系圖分析網絡結構有可能會造成重要信息的缺失，從而不能精準地挖掘其隱含的數據結構[3-4]。將含有多種關系的網絡稱之為“異質網絡”或者多關系網絡[5]。以信息共享為代表的各種異構網絡應用蓬勃發展，使得人們與互聯網間的聯系更加緊密與多向，由簡單單項的信息檢索轉變為以用戶為主導的信息的創建與傳播。隨著用戶之間的互交越來越密切與深入，異構網絡下的數據挖掘研究逐漸成為復雜網絡分析的一大熱點[6]。

本文提出一種基于共享局部結構的異質網絡數據挖掘算法，該模型利用各維關系網絡間的共性信息，根據各關系圖的初始聚類結果，找出那些在多個關系網中都同屬于一個類型的節點簇，即數據子集，并對其中的節點進行標記，然后根據某種劃分原則依次將剩余未標記的節點并入相應的數據子集中，從而完成整個網絡節點的劃分。通過在模擬計算機合成網絡數據集上的比較試驗，證明了所提出算法的魯棒性和有效性。

1 異構網絡下的數據結構

一個包含種關系的異構網絡可以抽象地表示為，，其中表示含有個元素的節點集合，表示第維關系網絡的鄰接矩陣。將異構網絡中的不同關系看作是從不同角度對網絡節點的描述。此外，各維關系網并不是獨立存在的。本文的任務就綜合實體間的多種關系并從中挖掘其隱含的數據結構，引入了共享局部結構和節點簇凝聚度思想，提出了新的異構網絡挖掘算法。

2 基于局部共享結構的異構網絡數據挖掘

2.1 共享局部信息的提取

異構網絡的實體間存在的對應的關系為。由網絡進行數據劃分可以得到如下集合：，這里—第維網絡劃分出來的數據結構。如果將被假定的關系網格都劃分成為個數據集，并且在聚類時，隨機分配（1～k）數據標號。

目標是提取有關異質網絡之間的共享信息，有必要找到在劃分的方式不盡相同的情況下的數據標號的相互對應關系，其公式如下：

其中表示由關系劃分出來的標號為的數據集，為節點被劃分到的概率而則表示節點在關系與關系中分別被劃分到與中的概率。

2.2 共享局部結構的更新

將劃分的結果一并加入到各維網絡劃分的數據結構的集合之中，這時分集合將擴充為，算法的主要步驟可以歸納如下：

維度改進算法：

輸入：維異質關系網絡、數據集個數；

輸出：各節點所屬的數據集標號；

（1）分別對各單維網絡進行數據集劃分，得到種不同的劃分結果；

For ；

（2）將未標記節并入使節點簇的凝聚度增益最大的數據子集中；

（3）對未標記節點進行相應劃分，將劃分結果也并入集合（）。

3 實驗數據集及對比結果

通過對比實驗來驗證有效性及魯棒性。選取的方法有如下兩種方式：一、各單一的異構網絡下的數據集挖掘；二、關系矩陣加權組合的方法WAMM以及PMM算法。

為了比較各算法的數據集劃分性能，我們使用了兩種經典的指標：歸一化互信息（NMI）與準確率（Ac）。兩者的取值都在0-1之間，如果它們的值越大的話，說明結果越接近真實。

我們在計算機的合成數據上進行試驗分析的目的是為了驗證算法是否有效。這種合成網絡一共包括350個節點，將其劃分成了三個大小各不相同的數據集，并且各個網絡節點間存在4種關系，各關系圖的可以用對應圖1中的來表示。

圖2指出了每種算法在合成網絡中數據集劃分的性能，從圖中我們可以看出異質網絡的算法性能明顯比單一的關系網的數據集挖掘性能要好，并且基本上能實現了正確的劃分。

4 結語

針對異構網絡中多元化的節點關系，本文提出一種基于共享局部結構的異質網絡數據集挖掘算法。該算法將網絡節點通過提取多種關系間共享的局部信息基本實現了網絡節點的局部劃分，最后在通過在計算機合成的數據集上驗證了該算法的有效性。

參考文獻

[1]張春英，郭景峰.集對社會網絡α關系社區及動態挖掘算法[J].計算機學報，2013，（8）：1682-1692.

[2]孫榮德，邵峰晶，孫仁誠.一種基于復合網的面向微博關注的推薦算法[J].計算機光盤軟件與應用，2013，（24）：132-133.

[3]王會梅，鮮明，王國玉.基于擴展網絡攻擊圖的網絡攻擊策略生成算法[J].電子與信息學報，2011，（12）：3015-3021.

[4]黃光球，李艷.基于粗糙圖的網絡風險評估模型[J].計算機應用，2010，（1）：190-195.

[5]榮智海，吳枝喜，王文旭.共演博弈下網絡合作動力學研究進展[J].電子科技大學學報，2013，（1）：10-22.

[6]劉鈺峰，李仁發.異構信息網絡上基于圖正則化的半監督學習[J].計算機研究與發展，2015，（3）：606-613.