[發(fā)明專利]一種異構(gòu)網(wǎng)絡(luò)可交互可視化方法

在審

• 申請?zhí)枺?/td>: 201410327034.1
• 申請日: 2014-07-10
• 公開（公告）號: CN104090957A
• 公開（公告）日: 2014-10-08
• 發(fā)明（設(shè)計）人: 時磊;趙月;林闖
• 申請（專利權(quán)）人: 中國科學院軟件研究所;清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 馮藝東

技術(shù)領(lǐng)域

本發(fā)明涉及聚類分析、異構(gòu)網(wǎng)絡(luò)、數(shù)據(jù)挖掘、拓撲結(jié)構(gòu)分析、大型數(shù)據(jù)網(wǎng)絡(luò)可視化分析等領(lǐng)域，提出了一種基于異構(gòu)網(wǎng)絡(luò)節(jié)點屬性及網(wǎng)絡(luò)拓撲結(jié)構(gòu)相結(jié)合的處理大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的方法。該方法適用于社會化網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)及知識網(wǎng)絡(luò)等典型信息網(wǎng)絡(luò)數(shù)據(jù)。是一種可以進行交互分析的可視化展示方法。

背景技術(shù)

大數(shù)據(jù)時代的到來，在短時間內(nèi)產(chǎn)生了復(fù)雜多變的大型數(shù)據(jù)網(wǎng)絡(luò)，很多人開始針對這些量大、質(zhì)雜的網(wǎng)絡(luò)數(shù)據(jù)進行分析和深入研究。這些數(shù)據(jù)網(wǎng)絡(luò)中，一些是在網(wǎng)絡(luò)節(jié)點上具有不同屬性特征的網(wǎng)絡(luò)類型，一些是拓撲結(jié)構(gòu)和關(guān)聯(lián)關(guān)系復(fù)雜的網(wǎng)絡(luò)類型。本發(fā)明所指的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)主要指同時具有以上兩種特征的網(wǎng)絡(luò)，即由一些具有不同屬性、類型的數(shù)據(jù)節(jié)點所構(gòu)成的較為復(fù)雜的關(guān)系/關(guān)聯(lián)網(wǎng)絡(luò)。當前，已有一些研究是針對異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)進行聚類分析。主要是根據(jù)網(wǎng)絡(luò)數(shù)據(jù)上節(jié)點所具有的不同屬性，進行聚類可視化分析。同時，網(wǎng)絡(luò)拓撲結(jié)構(gòu)主要指數(shù)據(jù)節(jié)點和數(shù)據(jù)節(jié)點之間因為某種關(guān)聯(lián)關(guān)系而相互聯(lián)系形成的網(wǎng)絡(luò)，基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的聚類分析也較為常見，如圖聚類、譜聚類方法。

在可視化研究領(lǐng)域，大部分的網(wǎng)絡(luò)數(shù)據(jù)可視化研究均集中于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的可視化。隨著web2.0時代的到來，數(shù)據(jù)量不斷的增加，網(wǎng)絡(luò)數(shù)據(jù)的形式已經(jīng)發(fā)生了很大的改變。現(xiàn)有的一些數(shù)據(jù)網(wǎng)絡(luò)很多的結(jié)點及他們的邊都擁有了屬性，對于這種具有屬性的異構(gòu)網(wǎng)絡(luò)可視化，現(xiàn)在仍很少有研究。并且，已知的方法均不能結(jié)合網(wǎng)絡(luò)節(jié)點屬性及拓撲結(jié)構(gòu)進行聯(lián)合分析，不能同時基于此兩類信息實現(xiàn)可視化展示與分析。例如，Wattenberg對異構(gòu)網(wǎng)絡(luò)的可視化分析進行了研究。但是，他僅僅利用了網(wǎng)絡(luò)節(jié)點屬性實現(xiàn)可視化，并沒有針對以上兩種異構(gòu)網(wǎng)絡(luò)信息進行二者相結(jié)合的可視化研究。

具體說來，針對這一類的大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)可視化的研究問題如下：

1)現(xiàn)有的異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)可視化聚類分析研究，有一些是基于網(wǎng)絡(luò)節(jié)點屬性數(shù)據(jù)的聚類分析，一些是基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)數(shù)據(jù)的聚類分析，聚類分析方法僅采用網(wǎng)絡(luò)拓撲結(jié)構(gòu)或節(jié)點屬性的單一來源，不能實現(xiàn)結(jié)合兩類數(shù)據(jù)類型同時進行聚類分析。.例如，在包含“論文、作者、會議/期刊”三類節(jié)點的學術(shù)異構(gòu)網(wǎng)絡(luò)中，已有可視化分析方法不能直觀展示“哪些作者的合作者發(fā)表了更多的高/中/低引用論文，哪些作者發(fā)表的論文有近似的引用率分布”等探索式問題。

現(xiàn)有的大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)可視化聚類分析研究，可根據(jù)網(wǎng)絡(luò)節(jié)點屬性或拓撲結(jié)構(gòu)，生成一定數(shù)目的網(wǎng)絡(luò)節(jié)點聚類。然而，這兩種方法的聚類結(jié)果顆粒度或過于粗糙以至于丟失大量網(wǎng)絡(luò)細節(jié)(如基于節(jié)點屬性的方法將整個網(wǎng)絡(luò)壓縮為幾個節(jié)點聚類，對應(yīng)節(jié)點屬性的幾個取值)，或過于細密因此難以布局和展示(如基于網(wǎng)絡(luò)結(jié)構(gòu)的聚類)。雖然已有一些方法可以聚類數(shù)目為輸入(如圖分割方法)，然而用戶難以控制并理解聚類結(jié)果，且不能支持用戶自定義的自頂向下可視化瀏覽分析過程。

發(fā)明內(nèi)容

針對上述大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的分析問題，本發(fā)明的目的在于提出一種異構(gòu)網(wǎng)絡(luò)可交互可視化方法。本發(fā)明提供了可以解決上述問題的可視數(shù)據(jù)分析方法以及其可視化實現(xiàn)形式——洋蔥圖。這是一種可以根據(jù)任意節(jié)點本身的屬性、拓撲關(guān)系，或是兩類信息的混合來進行聚類分析及可視化展示的大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)分析方法。各網(wǎng)絡(luò)結(jié)點或節(jié)點聚類都可以靈活的根據(jù)屬性或拓撲關(guān)系進行二次拆分或聚類。在可視化展現(xiàn)上，網(wǎng)絡(luò)節(jié)點根據(jù)所在的聚類層級的不同，用多個同心圓來顯示，形象如同一個被切開的洋蔥。因此，我們的方法以洋蔥圖命名。

本發(fā)明基于國家973科技項目(Supportedby?the?National?Basic?Research?Program?of?China?under?Grant?No.2014CB340301)和國家自然科學基金(the?National?Science?Foundation?of?China?(NSFC)under?Grant?No.61379088)的支持，通過分析網(wǎng)絡(luò)數(shù)據(jù)的屬性特征及拓撲關(guān)系，將大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)壓縮成分層次的網(wǎng)絡(luò)節(jié)點聚類，提供直觀的可視化形式(洋蔥圖)展示所計算的網(wǎng)絡(luò)節(jié)點聚類及聚類之間的關(guān)系，并通過簡單、易用的交互形式來指引用戶分層瀏覽并可視化分析大型異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的聚類結(jié)果。特別地，本方法支持用戶按照自己的分析需求，選擇特定的異構(gòu)網(wǎng)絡(luò)局部數(shù)據(jù)，并從將所選擇的某個層次的網(wǎng)絡(luò)節(jié)點聚類，繼續(xù)按照分析需求逐層放大(向較低層次聚類)或合并(向較低層次聚類)。通過在同一異構(gòu)網(wǎng)絡(luò)可視化視圖種展示不同層次的聚類粒度，實現(xiàn)用戶關(guān)注的局部異構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的詳細關(guān)聯(lián)分析。