崔鵬宇

摘要：本文針對單一關(guān)系的數(shù)據(jù)挖掘方案不能精準(zhǔn)的發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的問題，通過提出異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)挖掘的算法達到網(wǎng)絡(luò)節(jié)點的初步劃分目標(biāo)的實并且能夠初步此得到各數(shù)據(jù)子集。

關(guān)鍵詞：異構(gòu)網(wǎng)絡(luò)；數(shù)據(jù)挖掘；共享局部結(jié)構(gòu)

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

隨著社會網(wǎng)絡(luò)分析的進一步發(fā)展，人們逐漸發(fā)現(xiàn)單一的關(guān)系網(wǎng)絡(luò)并不能很好的刻畫出實體間的真實結(jié)構(gòu)[1]。在現(xiàn)實的社會網(wǎng)絡(luò)中，實體之間往往是多種關(guān)系交織在一起的[2]。每種關(guān)系對應(yīng)一個關(guān)系圖，僅僅利用一種關(guān)系圖分析網(wǎng)絡(luò)結(jié)構(gòu)有可能會造成重要信息的缺失，從而不能精準(zhǔn)地挖掘其隱含的數(shù)據(jù)結(jié)構(gòu)[3-4]。將含有多種關(guān)系的網(wǎng)絡(luò)稱之為“異質(zhì)網(wǎng)絡(luò)”或者多關(guān)系網(wǎng)絡(luò)[5]。以信息共享為代表的各種異構(gòu)網(wǎng)絡(luò)應(yīng)用蓬勃發(fā)展，使得人們與互聯(lián)網(wǎng)間的聯(lián)系更加緊密與多向，由簡單單項的信息檢索轉(zhuǎn)變?yōu)橐杂脩魹橹鲗?dǎo)的信息的創(chuàng)建與傳播。隨著用戶之間的互交越來越密切與深入，異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)挖掘研究逐漸成為復(fù)雜網(wǎng)絡(luò)分析的一大熱點[6]。

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

1 異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)結(jié)構(gòu)

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

2 基于局部共享結(jié)構(gòu)的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)挖掘

2.1 共享局部信息的提取

異構(gòu)網(wǎng)絡(luò)的實體間存在的對應(yīng)的關(guān)系為。由網(wǎng)絡(luò)進行數(shù)據(jù)劃分可以得到如下集合：，這里—第維網(wǎng)絡(luò)劃分出來的數(shù)據(jù)結(jié)構(gòu)。如果將被假定的關(guān)系網(wǎng)格都劃分成為個數(shù)據(jù)集，并且在聚類時，隨機分配（1～k）數(shù)據(jù)標(biāo)號。

目標(biāo)是提取有關(guān)異質(zhì)網(wǎng)絡(luò)之間的共享信息，有必要找到在劃分的方式不盡相同的情況下的數(shù)據(jù)標(biāo)號的相互對應(yīng)關(guān)系，其公式如下：

其中表示由關(guān)系劃分出來的標(biāo)號為的數(shù)據(jù)集，為節(jié)點被劃分到的概率而則表示節(jié)點在關(guān)系與關(guān)系中分別被劃分到與中的概率。

2.2 共享局部結(jié)構(gòu)的更新

將劃分的結(jié)果一并加入到各維網(wǎng)絡(luò)劃分的數(shù)據(jù)結(jié)構(gòu)的集合之中，這時分集合將擴充為，算法的主要步驟可以歸納如下：

維度改進算法：

輸入：維異質(zhì)關(guān)系網(wǎng)絡(luò)、數(shù)據(jù)集個數(shù)；

輸出：各節(jié)點所屬的數(shù)據(jù)集標(biāo)號；

（1）分別對各單維網(wǎng)絡(luò)進行數(shù)據(jù)集劃分，得到種不同的劃分結(jié)果；

For ；

（2）將未標(biāo)記節(jié)并入使節(jié)點簇的凝聚度增益最大的數(shù)據(jù)子集中；

（3）對未標(biāo)記節(jié)點進行相應(yīng)劃分，將劃分結(jié)果也并入集合（）。

3 實驗數(shù)據(jù)集及對比結(jié)果

通過對比實驗來驗證有效性及魯棒性。選取的方法有如下兩種方式：一、各單一的異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)集挖掘；二、關(guān)系矩陣加權(quán)組合的方法WAMM以及PMM算法。

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

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

圖2指出了每種算法在合成網(wǎng)絡(luò)中數(shù)據(jù)集劃分的性能，從圖中我們可以看出異質(zhì)網(wǎng)絡(luò)的算法性能明顯比單一的關(guān)系網(wǎng)的數(shù)據(jù)集挖掘性能要好，并且基本上能實現(xiàn)了正確的劃分。

4 結(jié)語

針對異構(gòu)網(wǎng)絡(luò)中多元化的節(jié)點關(guān)系，本文提出一種基于共享局部結(jié)構(gòu)的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集挖掘算法。該算法將網(wǎng)絡(luò)節(jié)點通過提取多種關(guān)系間共享的局部信息基本實現(xiàn)了網(wǎng)絡(luò)節(jié)點的局部劃分，最后在通過在計算機合成的數(shù)據(jù)集上驗證了該算法的有效性。

參考文獻

[1]張春英，郭景峰.集對社會網(wǎng)絡(luò)α關(guān)系社區(qū)及動態(tài)挖掘算法[J].計算機學(xué)報，2013，（8）：1682-1692.

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

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

[4]黃光球，李艷.基于粗糙圖的網(wǎng)絡(luò)風(fēng)險評估模型[J].計算機應(yīng)用，2010，（1）：190-195.

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

[6]劉鈺峰，李仁發(fā).異構(gòu)信息網(wǎng)絡(luò)上基于圖正則化的半監(jiān)督學(xué)習(xí)[J].計算機研究與發(fā)展，2015，（3）：606-613.