動態(tài)圖數(shù)據(jù)上查詢和挖掘算法探究綜述

《動態(tài)圖數(shù)據(jù)上查詢和挖掘算法探究綜述》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、動態(tài)圖數(shù)據(jù)上查詢和挖掘算法探究綜述　　收稿日期：2013-04-24基金項目：國家自然科學(xué)基金（61173023）。作者簡介：楊雅君（1983-），男，黑龍江哈爾濱人，博士研究生，主要研究方向：挖掘算法；高宏（1966-），女，黑龍江哈爾濱人，博士，教授，博士生導(dǎo)師，主要研究方向：圖數(shù)據(jù)管理、海量數(shù)據(jù)管理、物聯(lián)網(wǎng)數(shù)據(jù)管理；李建中（1950-），男，黑龍江哈爾濱人，教授，博士生導(dǎo)師，主要研究方向：并行數(shù)據(jù)庫、無線傳感器網(wǎng)絡(luò)、海量數(shù)據(jù)計算等。動態(tài)圖數(shù)據(jù)上查詢與挖掘算法的研究綜述楊雅君，高宏，李建中（哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001）摘要：近年

2、來，圖數(shù)據(jù)模型被廣泛地用于刻畫現(xiàn)實(shí)世界中各種各樣的實(shí)體間的復(fù)雜關(guān)系。然而，在現(xiàn)實(shí)世界中，描述實(shí)體對象的圖數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容往往不是固定不變的，而是會隨著時間的推移發(fā)生演繹與進(jìn)化。目前，越來越多的研究者開始關(guān)注動態(tài)圖數(shù)據(jù)方面的研究問題，也涌現(xiàn)除了很多優(yōu)秀的研究工作?？偨Y(jié)了近年來動態(tài)圖上查詢算法與挖掘算法方面的基礎(chǔ)性研究工作，討論了現(xiàn)有的工作和動態(tài)圖研究的發(fā)展方向。24關(guān)鍵詞：動態(tài)圖；查詢算法；挖掘算法中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2013）04-0024-05SurveyonQueryingandMiningAlgorithms

3、onDynamicGraphsYANGYajun，GAOHong，LIJianzhong（SchoolofComputerScienceandTechnology，HarbinInstituteofTechnology，Harbin150001，China）Abstract：Recently，graphshasbeenwidelyusedtomodelthecomplexityrelationshipsamongvariousentitiesinrealapplications.However，thestructureandthecontentingraphs

4、todescriberealentitiesarealwayschangingwithtimeevolving.Today，moreandmoreresearchworksfocusonthedynamicgraphsandthereexistmanyexcellentresults.Thispapersummarizestheworksaboutqueryingalgorithmandminingalgorithmondynamicgraphsinthepastyear，andalsodiscussesthefutureworkaboutdynamicgra

5、phs.Keywords：DynamicGraphs；QueryingAlgorithm；MiningAlgorithm241動態(tài)圖研究的背景和應(yīng)用意義隨著信息科技與互聯(lián)網(wǎng)的高速發(fā)展，各個應(yīng)用領(lǐng)域的信息量都呈現(xiàn)了爆炸性的增長趨勢。因此，不同應(yīng)用領(lǐng)域各自關(guān)注的實(shí)體對象之間的關(guān)系也變得愈加龐大和復(fù)雜。在這些復(fù)雜關(guān)系的背后，往往蘊(yùn)含著巨大的科學(xué)價值和商業(yè)價值。由此，吸引了諸多領(lǐng)域的研究者都開始專注于實(shí)體對象之間關(guān)系的研究，如計算生物學(xué)領(lǐng)域中，蛋白質(zhì)和酶之間所發(fā)生的復(fù)雜的交互、調(diào)控與代謝關(guān)系的研究；社會學(xué)領(lǐng)域中，對不同社交網(wǎng)絡(luò)中人與人之間交際關(guān)系的研究；商業(yè)領(lǐng)域中，對

6、金融網(wǎng)絡(luò)和貨幣流通網(wǎng)絡(luò)中商業(yè)關(guān)系的研究；以及互聯(lián)網(wǎng)搜索領(lǐng)域中，不同網(wǎng)頁之間超鏈接關(guān)系的研究。在這些領(lǐng)域中，如果采用傳統(tǒng)的關(guān)系數(shù)據(jù)庫來管理數(shù)據(jù)對象之間的這些錯綜復(fù)雜的關(guān)系，會用到巨量且昂貴的連接操作。因此，利用傳統(tǒng)的關(guān)系數(shù)據(jù)庫來研究復(fù)雜的結(jié)構(gòu)化數(shù)據(jù)并不具備現(xiàn)實(shí)可行性?！皥D”作為離散數(shù)學(xué)和計算機(jī)科學(xué)中基本的數(shù)據(jù)結(jié)構(gòu)，可以有效地表示存在多種關(guān)聯(lián)的數(shù)據(jù)以及內(nèi)部具有一般性結(jié)構(gòu)的數(shù)據(jù)。圖中，每個頂點(diǎn)代表現(xiàn)實(shí)世界中的實(shí)體對象；兩個不同頂點(diǎn)之間則可能會存在一條或多條邊，由其代表不同實(shí)體之間存在的某種關(guān)系。針對這種形式的結(jié)構(gòu)化的數(shù)據(jù)，研究者們將其稱作“圖數(shù)據(jù)”。24近年來，圖數(shù)

7、據(jù)已廣泛地用于刻畫現(xiàn)實(shí)世界中各類實(shí)體間的復(fù)雜關(guān)系。例如，傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)圖；互聯(lián)網(wǎng)領(lǐng)域中的頁面超鏈接關(guān)系圖；計算生物學(xué)中的蛋白質(zhì)交互和基因調(diào)控網(wǎng)絡(luò)；社交網(wǎng)絡(luò)中（如新浪微博、微信等）用戶之間交互關(guān)系圖及～Email～通信關(guān)系圖；物流學(xué)領(lǐng)域中的交通網(wǎng)絡(luò)、物流網(wǎng)絡(luò)等等。這些例子清楚地表示，圖數(shù)據(jù)現(xiàn)已無處不在，因此，對圖數(shù)據(jù)進(jìn)行管理則成為一個迫切重要的問題。由于圖數(shù)據(jù)具有的重大科學(xué)意義和巨大社會價值，數(shù)據(jù)領(lǐng)域內(nèi)的頂級學(xué)術(shù)會議SIGMOD、VLDB、ICDE、KDD以及重要學(xué)術(shù)會議CIKM、EDBT、ICDM等均設(shè)有與圖數(shù)據(jù)管理有關(guān)的研討議程。然而，在現(xiàn)實(shí)世界

8、中，實(shí)體對象間的關(guān)系卻每時每刻都在發(fā)生