[發(fā)明專利]分層簡化大規(guī)模圖數(shù)據(jù)的運算方法

有效

• 申請?zhí)枺?/td>: 201210176708.3
• 申請日: 2012-05-31
• 公開（公告）號: CN102750460A
• 公開（公告）日: 2012-10-24
• 發(fā)明（設計）人: 毛國勇;張燕紅;張永春;徐磊;彭穎
• 申請（專利權(quán)）人: 常州工學院
• 主分類號: G06F19/18
• 分類號: G06F19/18
• 代理公司: 常州市江海陽光知識產(chǎn)權(quán)代理有限公司 32214
• 代理人: 湯志和

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

本發(fā)明涉及一種分層簡化大規(guī)模圖數(shù)據(jù)的運算方法。

背景技術(shù)

在數(shù)學上，一個圖（Graph）是表示物件與物件之間的關(guān)系的方法，是圖論的基本研究對象。一個圖看起來是由一些小圓點（稱為頂點或結(jié)點）和連結(jié)這些圓點的直線或曲線（稱為邊）組成的。

在金融、生物信息、社會學、交通管理以及軟件工程等多個領(lǐng)域，經(jīng)常需要對大規(guī)模圖數(shù)據(jù)進行分析，而對數(shù)據(jù)的可視化則是分析、理解這些數(shù)據(jù)的直觀、有效的方法，受到了越來越多的關(guān)注。由于很難一次性載入大規(guī)模數(shù)據(jù)進行分析，人們通常先根據(jù)圖的特性將原始圖簡化，得到具備一定代表性意義的母圖的縮略圖，然后再通過子圖與母圖交互，根據(jù)需要對數(shù)據(jù)進行顯示、分析。

圖簡化方法通常分為圖聚合法和圖過濾法兩類。圖聚合法將多個點合并，將多條邊合并，從而減小圖的大小，并揭示一組點間的關(guān)系。這種方法可以被多次重復，從而得到層次化的圖。但是，用這種方法得到的合并后的點和邊失去了其原始的語義，因此，簡化后子圖的代表性不強。

與圖聚合法相比，圖過濾法能夠保留點和邊的語義，因為簡化后的圖是原始圖的子圖。圖過濾法又分為隨機性過濾和確定性過濾兩種。隨機性過濾也稱為采樣,用來從大規(guī)模圖中得到代表性的樣本。但是，由于對數(shù)據(jù)進行隨機采樣，因此，用這種簡化方法得到的子圖的代表性也不強。確定性過濾采用確定性的算法來選擇待移除的點和邊，這種過濾可以基于點和邊的性質(zhì)以及圖的拓撲結(jié)構(gòu)等特性。目前使用最多的是基于介數(shù)進行過濾的方法，介數(shù)表示的是一個節(jié)點位于其它節(jié)點間的最短路徑上的頻率，頻率越高，則該點的介數(shù)越高，該點就越重要。這種方法得到的簡化子圖的代表性最好，但是，由于介數(shù)方法需要計算所有頂點間最短路徑，而所有頂點間最短路徑的計算非常耗時，因此，該方法難以應用于大規(guī)模圖數(shù)據(jù)的簡化。

隨著人類基因組計劃和許多物種全基因組測序的完成，生命科學研究的重點已經(jīng)逐漸從基因組學轉(zhuǎn)移到了蛋白質(zhì)組學。蛋白質(zhì)是構(gòu)成一切細胞和組織結(jié)構(gòu)必不可少的成分，它是生理功能的執(zhí)行者，是生命活動最重要的物質(zhì)基礎。然而，不同的蛋白質(zhì)對生命活動的重要性是有差異的。以此為依據(jù)，可以將蛋白質(zhì)分為關(guān)鍵蛋白質(zhì)?(essential?proteins)和非關(guān)鍵蛋白質(zhì)(non一?essential?proteins)兩類。關(guān)鍵蛋白質(zhì)為通過基因剔除式突變將其移除后造成有關(guān)蛋白質(zhì)復合物功能喪失，并導致生物體無法生存的蛋白質(zhì)。簡而言之，關(guān)鍵蛋白質(zhì)是生物體生存和繁殖所必需的蛋白質(zhì)。由于關(guān)鍵蛋白質(zhì)在生命活動中扮演重要角色，因此對于關(guān)鍵蛋白質(zhì)的預測與識別成為一項重要的研究工作。在生物學上，關(guān)鍵蛋白質(zhì)的識別主要是依靠生物實驗的方法，例如RNA干擾、單基因敲除、條件性基因剔除等。通過這些實驗技術(shù)得到的結(jié)論雖然是明確和有效的，但是代價高、效率低，并且適用的物種范圍有限。針對蛋白質(zhì)互相作用網(wǎng)絡進行非關(guān)鍵蛋白質(zhì)分子的篩選，保留關(guān)鍵蛋白質(zhì)分子，已經(jīng)成為急需解決的問題。

相關(guān)參考文獻：

?[1]?《圖論導引》，美國：?Gray?chartrand?,?Ping?Zhang著，范益政，汪毅，朱明譯，人民郵電出版社，2007年9月第1版，ISBN：?9787115161536；

[2]?《圖論算法理論、實現(xiàn)及應用》，中國:王桂平，王衍，任嘉辰主編,北京大學出版社，2011年1月第1版，ISBN：?978-7-301-17578-1/TP·1122；?

[3]?《離散數(shù)學》，中國：左孝凌、李為鑒、劉永才著，上海科學技術(shù)文獻出版社，1982年9月第一版，ISBN：7805130698,?9787805130699。

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

本發(fā)明的目的是：一、針對目前圖簡化方法得到的子圖的代表性不強或計算復雜度過大的問題，提出一種新的適用于大規(guī)模圖數(shù)據(jù)的簡化方法，該方法的計算速度快且得到的簡化子圖具備較強的代表性；二、針對目前蛋白質(zhì)互相作用網(wǎng)絡的圖數(shù)據(jù)，提出一種適于對蛋白質(zhì)相互作用網(wǎng)絡的分層簡化大規(guī)模圖數(shù)據(jù)的運算方法,解決了傳統(tǒng)方法中成本昂貴和耗時的問題。