2023人工智能圖計(jì)算

/uhome/6011145050000024.html人工智能圖計(jì)算/uhome/6011145050000024.html目錄概篇 1計(jì)的義 1計(jì)的生發(fā)展 2計(jì)的征 3計(jì)的展境 5技篇 6算法 6數(shù)計(jì)模型 7計(jì)系統(tǒng) 12計(jì)中關(guān)技術(shù) 20術(shù)戰(zhàn) 22術(shù)源 24引文 25人篇 27者況覽 27型者介 31產(chǎn)應(yīng)篇 39療業(yè)應(yīng)用 39融業(yè)應(yīng)用 39聯(lián)行的用 40趨篇 43局度 43期度 43叉究析 44術(shù)見 48附錄 50圖表目錄圖1圖據(jù)型子 1圖2圖算發(fā)展 3圖3圖據(jù)算型及應(yīng)系統(tǒng) 8圖4計(jì)系框分類 13圖5VenueColletionofOAG 24圖6PaperCollectionofOAG 24圖7AuthorCollectionofOAG 24圖8全圖算域?qū)W者布圖 27圖9中圖算域?qū)W者布圖 28圖10全圖算域躍學(xué)遷圖 29圖11全圖算域躍學(xué)機(jī)分布 29圖12全圖算域躍者h(yuǎn)-index分布 30圖13全圖算域躍學(xué)性比 30圖14全圖算域躍學(xué)性比 41圖15騰星應(yīng)場景 42圖16騰星應(yīng)場景 43圖17graphcomputing期熱度 43圖182007今graphcomputing與datamining領(lǐng)交叉析 45圖192007今graphcomputing與machinelearning領(lǐng)域叉析 46圖20圖算術(shù)見圖 48表1圖算應(yīng)用 2表2圖算型比 12表3圖算統(tǒng)覽 19表42007至今graphcomputing與datamining領(lǐng)叉分析 45表52007年今graphcomputing與datamining交叉研文citation分布 45表72007年今graphcomputing與machinelearning領(lǐng)交研學(xué)者h(yuǎn)-index分布 47表82007年今graphcomputing與machinelearning領(lǐng)交研論文citation分布 47摘要圖計(jì)算是基于圖數(shù)據(jù)的分析技術(shù)與關(guān)系技術(shù)應(yīng)運(yùn)而生的，圖計(jì)算系統(tǒng)是針對處理圖結(jié)圖計(jì)算領(lǐng)域?qū)＜医榻B。依據(jù)AMiner數(shù)據(jù)平臺信息，對圖計(jì)算領(lǐng)域研究學(xué)者進(jìn)行梳理，h-index圖計(jì)算趨勢研究。對圖計(jì)算的發(fā)展趨勢特點(diǎn)進(jìn)行分析。并基于AMiner數(shù)據(jù)平臺，對近/uhome/6011145050000024.html概述篇圖計(jì)算的定義Gap（即Eweb（（（）圖1圖數(shù)據(jù)典型例子圖相關(guān)的算法。比如圖的最短路徑算法可以做好友推薦，計(jì)算關(guān)系緊密程度；對圖做PageRankFacebook20147122GBTB1PAGEPAGE24.51.5數(shù)據(jù)包含全量的站點(diǎn)1425\h\h文件400GB表1圖計(jì)算的應(yīng)用應(yīng)用元素（圖計(jì)算頂點(diǎn)）連接（圖計(jì)算的邊）社交網(wǎng)絡(luò)社交成員友情計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)鏈接網(wǎng)頁內(nèi)容網(wǎng)頁超鏈接交通城市公路電路設(shè)備電線商務(wù)顧客、商品交易方式工廠機(jī)械設(shè)備生產(chǎn)線供應(yīng)鏈供應(yīng)商距離電信移動電話電話溝通圖計(jì)算的產(chǎn)生與發(fā)展盡管圖形分析一直以來都是計(jì)算機(jī)相關(guān)研究的一個重要領(lǐng)域，但圖計(jì)算的研究在近年20012004GoogleApacheHadoopHadoop（HDFS）以及新的HadoopMapReduce2009AMPLabSparkMapReduceMapReduce（buknchonouspocen）BSPBSPBSP基于BSP2010PregelGooglePregel統(tǒng)GraphLab，其經(jīng)過多個版本演化已發(fā)展成為當(dāng)前最有影響力的圖計(jì)算系統(tǒng)之一。雖然pregelGraphLab（iteration）是20142015KineograghChronos和ImmortalGraphGraphEngine系統(tǒng)變得格外受歡迎，出現(xiàn)了多個具有不同編程模型和功能的分布式圖處理框架，比如Giraph、Gemini圖2圖計(jì)算的發(fā)展圖計(jì)算的特征“圖”是針對“圖論”而言的，是一種以“圖論”為基礎(chǔ)的對現(xiàn)實(shí)世界的一種“圖”結(jié)構(gòu)圖計(jì)算系統(tǒng)將圖結(jié)構(gòu)化數(shù)據(jù)表示為屬性圖，它將用戶定義的屬性與每個頂點(diǎn)和邊緣相（（PageRankED，其中V圖計(jì)算系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)很好地表達(dá)了數(shù)據(jù)之間的關(guān)聯(lián)性，關(guān)聯(lián)性計(jì)算是大數(shù)據(jù)計(jì)算的核心——圖數(shù)據(jù)模型并行抽象圖的經(jīng)典算法中，從PageRank例如Pregel）或共享狀態(tài)（例如/uhome/6011145050000024.html圖模型系統(tǒng)優(yōu)化對圖數(shù)據(jù)模型進(jìn)行抽象和對稀疏圖模型結(jié)構(gòu)進(jìn)行限制，使一系列重要的系統(tǒng)得到了優(yōu)GraphLabGASGatherApplyScatterGASPregel圖計(jì)算的發(fā)展困境Spark[1]MapReduceMPIOpenMPSparkSparkScalaJVM128Spark2010TB往往需要數(shù)百TBSogou137TBSparkweb技術(shù)篇圖算法PageRank、BayesianBeliefPropagationPrim算法和Kruskal（1）（2）（3）（4）0，（CommunityDetection）66PAGEPAGE10FacebookTwitter等PageRankPageRankSergeyBrinLarryPage1998PageRankPageRank搜索weibo，會出來非常多有著weibo關(guān)鍵字的網(wǎng)頁，可能有上千上萬個相關(guān)網(wǎng)頁，而PageRank最短路徑用于計(jì)算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心圖數(shù)據(jù)計(jì)算模型圖計(jì)算模型即針對圖數(shù)據(jù)和圖計(jì)算特點(diǎn)設(shè)計(jì)實(shí)現(xiàn)的計(jì)算模型，一般應(yīng)用于圖計(jì)算系統(tǒng)中。與傳統(tǒng)計(jì)算模型相比，圖計(jì)算模型主要針對解決以下問題：（1）圖計(jì)算的頻繁迭代帶來的讀寫數(shù)據(jù)等待和通信開銷大的問題；（2）圖算法對節(jié)點(diǎn)和邊的鄰居信息的計(jì)算依賴問題；（3）圖數(shù)據(jù)的復(fù)雜結(jié)構(gòu)使得圖算法難以實(shí)現(xiàn)分布不均勻的分塊上并行計(jì)算的問題。圖3圖數(shù)據(jù)計(jì)算模型分類及應(yīng)用系統(tǒng)MapReduceMapReduce2010BSPopue函數(shù)；由于圖算法在不同節(jié)點(diǎn)上的迭代次數(shù)不同，每個節(jié)點(diǎn)都執(zhí)行相同輪次的迭代計(jì)算是不合理的，所以同步計(jì)算模型將節(jié)點(diǎn)分為活躍（active）和不活躍（inactive）兩種狀態(tài)。當(dāng)節(jié)（inneighbor）（不）MapReduceGiraphGPS、Mizan、xDGPLogGP2010GraphLab，2012distributedGraphLabBSP（1）（（GAS（gather、apply、scatter）Gonzalez等人提出了GASGAS（1）（gather）GASGASGASGASBiGraphPowerLyra。然而，GAS節(jié)點(diǎn)中心模型提高了圖計(jì)算系統(tǒng)實(shí)現(xiàn)圖數(shù)據(jù)計(jì)算分析的能力，但是在實(shí)際應(yīng)用中仍面（1）（2）為解決設(shè)備資源受限和邊數(shù)目遠(yuǎn)大于節(jié)點(diǎn)數(shù)目時的圖數(shù)據(jù)分析計(jì)算問題，洛桑聯(lián)邦理2013XStream1（2）應(yīng)用將目的節(jié)點(diǎn)列表重排序（shuffle）為更新消息流；（3）讀取更新消息流和源節(jié)點(diǎn)列表，更新源節(jié)點(diǎn)值。三步操作在一次迭代計(jì)算中順序執(zhí)行。邊中心計(jì)算模型將圖數(shù)據(jù)以邊列表為核心數(shù)據(jù)結(jié)構(gòu)并維護(hù)源節(jié)點(diǎn)列表，每次迭代的計(jì)限和通信開銷過大的難題。邊中心計(jì)算模型的流式順序計(jì)算特點(diǎn)使得在全局圖數(shù)據(jù)上的計(jì)邊中心計(jì)算模型和節(jié)點(diǎn)中心計(jì)算模型分別將圖算法轉(zhuǎn)換為可在節(jié)點(diǎn)和邊上執(zhí)行的迭代PathGraph。（oadedeaesle（ees-edgetraversaltree）路徑中心計(jì)算模型從數(shù)據(jù)結(jié)構(gòu)決定圖算法計(jì)算順序的角度出發(fā)，設(shè)計(jì)前向邊遍歷樹和心計(jì)算模型，當(dāng)圖節(jié)點(diǎn)規(guī)模在百萬級以上和邊規(guī)模在億級以上的數(shù)據(jù)集上測試BFS、PageRank~路徑中心計(jì)算模型相比以節(jié)點(diǎn)或邊作為計(jì)算中心的模型更接近圖結(jié)構(gòu)上的理想計(jì)算狀（1）（2）2013年在圖計(jì)算系統(tǒng)Giraph++：（1）；（2）表2圖計(jì)算模型對比圖計(jì)算模型任務(wù)調(diào)度數(shù)據(jù)劃分并行性系統(tǒng)實(shí)現(xiàn)優(yōu)勢局限節(jié)點(diǎn)中心同步/異步節(jié)點(diǎn)序列子集高分布式/單機(jī)邊中心同步/異步邊序列分塊中單機(jī)模型實(shí)現(xiàn)對設(shè)備資源要求低；數(shù)據(jù)存儲、分塊和讀寫訪問更加簡單；數(shù)據(jù)訪問順序執(zhí)行，易于維護(hù)數(shù)據(jù)一致性計(jì)算并行性受邊列表分塊限制；圖算法遷移復(fù)雜，且適用范圍小路徑中心同步子樹中分布式/單機(jī)數(shù)據(jù)查找訪問簡單快捷；基于兩步操作，圖算法實(shí)現(xiàn)簡單構(gòu)建遍歷樹的初始化開銷大；數(shù)據(jù)一致性實(shí)現(xiàn)復(fù)雜；模型實(shí)現(xiàn)困難，且數(shù)據(jù)存儲復(fù)雜子圖中心同步/異步子圖低分布式/單機(jī)超步運(yùn)算之間通信開銷??；完成圖算法的迭代次數(shù)少圖計(jì)算系統(tǒng)2080OracleMySQL（RDBMS）Neo4j、InfiniteGraph依據(jù)大規(guī)模圖計(jì)算系統(tǒng)的使用場景以及計(jì)算平臺架構(gòu)的不同，我們將其分為單機(jī)內(nèi)存圖計(jì)算系統(tǒng)、單機(jī)外存圖計(jì)算系統(tǒng)、分布式內(nèi)存圖計(jì)算系統(tǒng)和分布式外存圖計(jì)算系統(tǒng)。圖4計(jì)算系統(tǒng)框架分類單機(jī)內(nèi)存圖處理系統(tǒng)就是圖處理系統(tǒng)運(yùn)行在單機(jī)環(huán)境，并且將圖數(shù)據(jù)全部緩沖到內(nèi)存（Single-machineout-of-coresystems）trillion的圖。下面對各類典型的圖計(jì)算系統(tǒng)逐一做簡單介紹：2013LigraGalois2015年發(fā)布的GraphMat和Polymer。其中LigraGalois使用出更復(fù)雜的算法完成圖分析工作，并發(fā)現(xiàn)當(dāng)輸入圖是道路網(wǎng)絡(luò)或者具有較大直徑的圖時能DSLs基礎(chǔ)上提供了輕量級的GraphMat是第一個對多核CPUPolymerNUMAintra-node還是RAMSSD、SASHDDGraphChi、TurboGraphX-StreamPathGraphGridGraphFlashGraph。這些系統(tǒng)在最大化磁盤順序讀寫、選擇調(diào)度和同異步計(jì)算模式等方面做出了重要探索，TurboGraphFlashGraphGraphChiGraphChiGASshard（PSW）shardPSWGraphChi在計(jì)算前首先會對圖數(shù)據(jù)進(jìn)行預(yù)處理，將輸入的圖劃分成多個shard，每個shardIDshardshardGraphChi心的計(jì)算模型，使用并行滑動窗口（parallelslidingwindow）來加載數(shù)據(jù)進(jìn)行計(jì)算。每次shard（）shard（），X-StreamX-StreamscattergatherX-Stream（CacheRAM，RAMSSD/Disk）X-Stream流式訪問圖數(shù)據(jù)，其流劃分相比于GraphChi無需shardwork-stealingScatter-Gather導(dǎo)X-StreamshuffleVENUS2013VENUS成為10IOGraphLab+（scale（scaleup）（scaleout）VENUS每一個數(shù)據(jù)分片被分為v-shard和g-shardv-shardg-shardVENUSg-shardIOg-shards-shardv-shardg-shardv-shardg-shardv-shardIOGridGraphGridGraphPchunkP*PblockchunkchunkCache/RAM/DiskStreamverticesandedges（DualSlidingWindows）大大減少了開blockX-Streamshuffleblock能達(dá)到最大化的Cache/Memory命中率。PregelPiccolo，同時支持同步和異步的系統(tǒng)PowerGraphGraphLabGraphXPowerSwitch和PowerLyra則對PowerGraphPregel為了更有效地解決大規(guī)模圖上的計(jì)算問題，學(xué)術(shù)界與工業(yè)界提出了大量專門為圖優(yōu)化PregelGoogle的圖計(jì)算領(lǐng)域的開山之作，是首個采用BSP（messageBSP（BarrierGiraph是PregelFacebook在Pregelcompute(（activevertex）會執(zhí)行compute()（（inactivevertex）在下一輪收到消息時，就會重新處于活躍狀態(tài)。當(dāng)所有活躍的點(diǎn)執(zhí)行完compute()函數(shù)之后，當(dāng)前迭代結(jié)束，并且進(jìn)入到下一次迭代。如果系統(tǒng)當(dāng)中所有的點(diǎn)都處于不活躍狀態(tài)，并且沒有任何新的消息，算法結(jié)束。GiraphGiraph構(gòu)建在HadoopGooglePregelFacebookGiraphGiraphGiraphGraphLabPregelBSPGraphLabGASGraphLab（sharedmemory）GraphLab上GAS行該函數(shù)。在gather階段，每個執(zhí)行GASapplyscatter的鄰點(diǎn)。在GraphLabGraphLab（synchronous（asynchronousexecution）PageRankBP）PowerGraphPowerGraph是面向分布式內(nèi)存的解決方案，通過使用更多的機(jī)器來擴(kuò)展能夠處理的圖的規(guī)模。PowerGraph包含在GraphLab2.2中，是在GraphLab的基礎(chǔ)上對符合冪律分布（power-law）PowerGraph少了通信量以及由度數(shù)較高頂點(diǎn)導(dǎo)致的負(fù)載不均衡。后續(xù)的很多分布式圖計(jì)算系統(tǒng)比如GraphXPowerLyra等均沿用了PowerGraphGraphXGraphX是一個基于ApacheSpark（ApacheSparkGraphXPregel和GraphLabSpark中RDD（resilientdistributeddataset），引入了RDG（resilientdistributedjoinmapSparkvertex-cutGraphXGraphXAPIGraphX化重新分配為分布式連接優(yōu)化和材料化視圖維護(hù)。通過利用分布式數(shù)據(jù)流框架的進(jìn)步，GraphXGeminiGeminiGemini針對圖結(jié)構(gòu)的稀疏或稠密情況使用與Ligra相同的自適應(yīng)推動/拉動了eniokeang）的GeminiSingle-machineout-of-coresystems2015Chaos。ChaosX-Streamwork-stealingChaos新集依然很龐大與邊量級相當(dāng)；計(jì)算與存儲獨(dú)立設(shè)計(jì)增加了系統(tǒng)的復(fù)雜性和不可避免的通信開銷；存儲子系統(tǒng)為了使存儲設(shè)備時刻忙碌而占用了較多的計(jì)算資源。TuX2TuX210TuX2表3圖計(jì)算系統(tǒng)概覽年份系統(tǒng)編程模型架構(gòu)運(yùn)算模型通信模型調(diào)度存儲方式2009PEGASUSN/ADN/ADFSynchDB2010PregelVDBSPMPSynchDB2010Signal/CollectVSSignal/CollectMPBothDB2010SurfurVDTransfer-combineMPSynchDB2010JPregelVDBSPMPSynchDB2010GraphLabVSN/ASMAsynchDB2010PiccoloDaDThreePhasesDFSynchDB2011GoldenOrdVDBSPSMSynchDB2011GBaseEDN/ADFSynchDB2011HipGVDBSPSMBothDB2012GiraphVDBSPMPSynchDB2012DistributedGraphLabVDGASSMBothDB2012KineoGraphVDPush/pullMPSynchMB2012PowerGraphEDGASSMBothDB2012SedgeVDBSPMPSynchDB2012GraphChiVSPSWSMAsynchDB2013TOTEMVHBSPMP&SMAsynchMB2013MizanVDBSPMPSynchDB2013TrinityVDTSLSMAsynchMB2013GraceVSThreephasesMPAsynchDB2013GPSVDBSPMPSynchDB2013Giraph++CDBSPMP&SMBothDB2013NaiadVDTimelydataflowSMBothMB2013PAGEVDPartition-awareMPSynchDB2013StratospherVDPush/pullDFSynchDB2013TurboGraphVSPin-and-slideSMAsynchDB2013xDGPVDBSPMPSynchDB2013X-StreamESScatter-gatherMPSynchDB2013GiraphXVDBSPSMAsynchDB2013GraphXEDGASDFSynchMB2013GaloisVSADPSMAsynchDB2013GREVDScatter-combineMPSynchDB2013LigraCSPush-pullSMAsynchMB2013LFGreaphVDN/ASMSynchMB2013PowerSwitchVDHybridSMBothDB2013PrestoVDN/ADFSynchDB2013MedusaVHEMVMPSynchMB2014RASPVSScatter-gatherSMAsynchDB2014GoFFishCDIterativeBSPMP&SMSynchMB2014GasCLVHGASMPSynchMB2014CuSHaVHGASSMAsynchMB2014BPPVSBSPSMAsynchDB2014ImitatorVDBSPMPSynchDB2014GraphHPVDBSPMPSynchDB2014PathGraphPSScatter-gatherSMAsynchDB2014SeraphVDGESMPSynchDB2014GraphGenVHN/ASMSynchMB2014BlogelBDN/AMPSynchMB2015PregelixVDJoin-operatorbasedMPSynchDB2015FlashGraphVSBSPMP&SMAsynchDB2015GraSPVDN/AMPSynchMB2015ChaosEDGASMPSynchDB2015GraphMapVDBSPMPSynchDB2015GridGraphESStreaming-ApplySMAsynchDB2015GraphTwistESSlice/CutpruningSMAsynchDB2015GraphQVSCheck/RefineSMAsynchDB2016GunrockDaHBSPSMSynchMB2016GraphInVDI-GASMPSynchMB2016LCC-GraphVDLLC-BSPMPSynchMB2016DUALSIMVSN/ASMAsynchDB2016iGiraphVDBSPMPSynchDB2017GraphMPVSVSWSMAsynchDB2017GraphGenVSN/ASMAsynchMB2017MosaicV/ESPRAMPSynchDB-編程模型：以頂點(diǎn)為中心（V），以邊緣為中心（E），以組件為中心（C），以路徑為中心（P），以數(shù)據(jù)為中心（Da），以塊為中心（B）-架構(gòu)：分布式（D），單機(jī)（S），異構(gòu)（H）-運(yùn)算模型：不同系統(tǒng)使用不同的名稱-通信模型：消息傳遞（MP），存儲器共享（SM），數(shù)據(jù)流（DF）-調(diào)度：同步（Synch），異步（Asynch），混合調(diào)度（Both）-存儲方式：基于磁盤（DB），基于內(nèi)存（MB）-N/A表示沒有特定的名稱或定義圖計(jì)算中的關(guān)鍵技術(shù)本節(jié)將重點(diǎn)介紹在分布式和單機(jī)圖處理系統(tǒng)中常用的技術(shù)。GPUCPUTOTEMCPUGPUMapGraph和CuShaGPUGPUCPUharddiskdrive如TurboGraphFlashGraph）針對SSDSDDPregelGiraphGraphLab和PowerGraph）（ghostNPGphhi使用shdshdedge-cutvertexcutedge-cutvertex-cutvertex-cut有助于系統(tǒng)的負(fù)載均衡，但是圖計(jì)算系統(tǒng)需要使用以邊為中心的計(jì)算模型，如PowerGraph。負(fù)載均衡的算法分為靜態(tài)負(fù)載均衡和動態(tài)負(fù)載均衡，靜態(tài)負(fù)載均衡在算法執(zhí)行之前進(jìn)容錯checkpointlog技術(shù)挑戰(zhàn)MPINP高訪存/計(jì)算比I/O/技術(shù)資源OpenAcademicMicrosoftAcademicAMIner（\h/oag2019）OGA2019呈現(xiàn)為下面三個圖，包括VenueCollectionPaperCollectionAuthorCollection圖5VenueColletionofOAG圖6PaperCollectionofOAG圖7AuthorCollectionofOAG高引論文下邊是一些圖計(jì)算相關(guān)引用量較高的論文：\hPregel:asystemforlarge-scalegraphprocessingSIGMODConference,,pp.135-146,(2010)DistributedGraphLab:aframeworkformachinelearninganddatamininginthecloud8PowerGraph:distributedgraph-parallelcomputationonnaturalgraphsGraphLab:ANewFrameworkForParallelMachineLearning.YuchengLow,JosephGonzalez,AapoKyrola,DannyBickson,CarlosGuestrin,JosephM.HellersteinClinicalOrthopaedicsandRelatedResearch,(2014)GraphChi:large-scalegraphcomputationonjustaPCAapoKyrola,GuyBlelloch,andCarlosGuestrin.GraphChi:large-scalegraphcomputationonjustaPC.OSDI,2012.Graphx:GraphprocessinginadistributeddataflowframeworkJosephE.Gonzalez,ReynoldS.Xin,AnkurDave,DanielCrankshaw,MichaelJ.Franklin,IonStoicaOSDI,,pp.599-613,(2014)X-Stream:edge-centricgraphprocessingusingstreamingpartitionsAmitabhaRoy,IvoMihailovic,IvoMihailovic,WillyZwaenepoelSOSP,,pp.472-488,(2013)\h/pdf/20170130/pdfs/sosp/ozz12hqruancqbijue8b6pm7siewytf0.pdfLigra:alightweightgraphprocessingframeworkforsharedmemoryJulianShun,GuyE.BlellochPPOPP,,pp.135-146,(2013)\h/pdf/20170130/pdfs/ppopp/gxrite4sseq1juzxofcanzbnplrhh5kv.pdfPowerLyra:differentiatedgraphcomputationandpartitioningonskewedgraphsGridGraph:Large-ScaleGraphProcessingonaSingleMachineUsing2-LevelHierarchicalPartitioningXiaoweiZhu,WentaoHan,WenguangChenUSENIXAnnualTechnicalConference,,(2015)GridGraph:Large-ScaleGraphProcessingonaSingleMachineUsing2-LevelHierarchicalPartitioningXiaoweiZhu,WentaoHan,WenguangChenUSENIXAnnualTechnicalConference,,(2015)RongChen,JiaxinShi,YanzheChen,andHaiboChen.PowerLyra:differentiatedgraphcomputationandpartitioningonskewedgraphs.EuroSys,2015.人才篇Google還是圖計(jì)算相關(guān)的重要會議包括：OSDI（USENIXSymposiumonOperatingSystemsDesignandImplementation）SOSP（SymposiumonOperatingSystemsPrinciples）USENIXATC（USENIXAnnualTechnicalConference）VLDB（InternationalConferenceonVeryLargeDataBases）SIGMOD（SpecialInterestGrouponManagementOfData）EuroSys（TheEuropeanConferenceonComputerSystems）SIGPLANAnnualSymposiumPrinciplesandPracticeofParallelProgramming）等。10年（20092018）graphgraphcomputinggraphpatterngraphmininggraphprocessing等1000學(xué)者情況概覽本節(jié)對這些學(xué)者進(jìn)行了簡單的統(tǒng)計(jì)分析，包括他們的分布地圖、遷徙狀況、機(jī)構(gòu)分布、h-index水平、性別分布等。27圖8全球圖計(jì)算領(lǐng)域活躍學(xué)者分布圖27PAGEPAGE28AMiner89圖9中國圖計(jì)算領(lǐng)域活躍學(xué)者分布圖10圖10全球圖計(jì)算領(lǐng)域活躍學(xué)者遷徙圖UniversityofCaliforniaUniversityofIllinoisatUrbanaChampaignTheChineseUniversityofHongKongCarnenieMellonUniversityNationalUniversityofSingaporeUniversityofScienceandTechnologyofChinaUniversityofWashingtonTeradataAsterCornellParasolPekingUniversityStanfordUniversityUniversityofWaterlooHongKongUniversityofScienceandTechnologyFudanNanyangTechnologicalUniversityUniversityofNewSouthWalesTsinghuaUniversity5526201717171615121110988888766650 10 20 30 40 50 60圖11全球圖計(jì)算領(lǐng)域活躍學(xué)者機(jī)構(gòu)分布11Microsoft（）5526UniversityofCalifornia（2010171110人以下的機(jī)構(gòu)分別有PekingUniversity（北京大學(xué)）HongKongUniversityofScienceandTechnology（、FudanUniversity（復(fù)旦大學(xué)）以及TsinghuaUniversity（清華大學(xué)）。700184987018498706495004003002001000≥61 41-60 21-40 ≤20圖12全球圖計(jì)算領(lǐng)域活躍學(xué)者h(yuǎn)-index分布h-index21h-index≥2138.03%；可見，h-index61.97%h-index2064964.84%；h-index≥60706.99%。女37人，3.69%男964人，96.31%圖13全球圖計(jì)算領(lǐng)域活躍學(xué)者性別比在性別比例方面，男性（占比96.31%）占據(jù)多數(shù)，比例要遠(yuǎn)高于該領(lǐng)域女性所占比例（3.69%）。典型學(xué)者簡介h-index（有疏漏，還請與AMiner\h/國外學(xué)者簡介IonStoicaIonStoica\h，美國加州大學(xué)伯克利分校的\h計(jì)算機(jī)科學(xué)系\h教授，\hAMPLab的共同創(chuàng)始人，Spark核心作者。\h\h\h，\h\h。2000\h業(yè)博士學(xué)位。其研究主題包括\hChord（（CSFQ）InternetHuiZhang是P2PEndSystemMulticastIonStoicaHuiZhang的基礎(chǔ)上進(jìn)一步將P2P技SIGCOMM'01Chord:Ascalablepeer-to-peerlookupserviceforinternetapplications》成為結(jié)構(gòu)化P2PIonStoica的研究興趣包括\h云計(jì)算、\h網(wǎng)絡(luò)、\h分布式系統(tǒng)和\h大數(shù)據(jù)。他在\h計(jì)算機(jī)科學(xué)的各個領(lǐng)域撰寫或共同撰寫了100多篇\h同行評審論文。2001年獲得獎；20032007年獲得CoNEXT（InternationalConferenceonemergingNetworkingEXperimentsandTechnologies）2011SIGCOMM（SpecialInterestGrouponDataCommunication美國計(jì)算機(jī)協(xié)會ACM數(shù)據(jù)通信專業(yè)組）時間測試獎。\h\hStoica在\h擔(dān)任\h2006Conviva\h（CTO）CMU\hEndSystemMulticast2013\hDatabricks，20161\hAliGhodsiACM（）Fellow。WillyZwaenepoelWillyZwaenepoel，ACM2018615WillyZwaenepoel1984WebTreadmarksOpenMP的工作促成了iMimicNetworking20002005他目前的興趣包括大規(guī)模數(shù)據(jù)存儲和軟件測試。他在軟件測試方面的工作促成了一家BugBusterBugBuster1998IEEEFellow，2000ACMFellow19982002IEEE年擔(dān)任OSDI項(xiàng)InternationalConferenceonMobileSystems,Applications,andServices）2006Eurosys項(xiàng)目主席。20029月，他加入了polytechniquefédéraledeLausanne20022011EPFLEPFL之前，（RiceUniversity）KarlHasselmann2000他分別在1984年SigComm，1999年的OSDI、Usenix2000、Usenix2006和Eurosys2007上獲得了最佳論文獎。他還獲得了2007年IEEETsutomuKanai獎。KeshavKPingaliKeshavKPingali，美國計(jì)算機(jī)科學(xué)家，ACMFellow，IEEEFellow\h，德克薩斯大學(xué)奧斯\h汀分校網(wǎng)格和分布式計(jì)算的\hWilliamMoncrief主席。KeshavKPingali于1986年獲得麻省理工學(xué)院碩士和博士學(xué)位。他曾獲得2013年IITKanpur杰出校友獎。KeshavKPingali\h\hWilliamMoncrief2003年-2006\h\hNRamaRao教授。他還是AAAS（\hACMIEEEFellow。GuyE.BlellochGuyE.Blelloch，ACMFellow，卡內(nèi)基梅隆大學(xué)計(jì)算機(jī)科學(xué)系教授，以并行編程和并行算法領(lǐng)域的研究而聞名。GuyE.Blelloch在卡內(nèi)基梅隆大學(xué)教授現(xiàn)實(shí)世界中的算法、并行算法課程，以及并行和順序數(shù)據(jù)結(jié)構(gòu)和算法課程。10CarlosGuestrinCaosGueTui曾用名Gaphab和DaTur）PpuarScec（208Bant1010。CarlosGuestrinPaulG.AllenCarlosGuestrinFinmeccanicaTuri2009年卡耐2016andWorkshoponNeuralInformationProcessingSystems）2003和2007，VLDB2004，UAI（ConferenceonUnceanynAcalnelgence200CM（nenaonalCneenceonMhneeanng）2005，IPSN（InternationalConferenceonInformationProcessinginSensorNetworks）2005和DiscoveryandData（InternationalConferenceonArtificialIntelligenceandStatistics）2010，JAIR（JournalofArtificialIntelligenceResearch）20072012ONRNSF（NationalScienceFoundationAlfredP.Sloan獎學(xué)金和斯坦福百年教學(xué)助理獎的獲得者。他還獲得了IJCAI（InternationalJointConferenceonArtificialIntelligence）計(jì)算機(jī)和思想獎以及科學(xué)家和PECASE（。PDeenedancedReeachPoecsgency）（ISAT）ChristosFaloutsosChristosFaloutsos，被譽(yù)為“數(shù)據(jù)庫大師”。ChristosFaloutsos19891994SIGMOD1997年以他的R+VLDBforComputingMachinery）2010SIGKDDChristosFaloutsos發(fā)表了300多篇評論文章，一篇專著，并擁有五項(xiàng)專利。他是SIGKDD國際會議執(zhí)行委員會成員，并在2010年被任命為ACMFellow。國內(nèi)學(xué)者簡介陳文光陳文光于2000年獲得清華大學(xué)計(jì)算機(jī)系博士學(xué)位。2007年-2015年任清華大學(xué)計(jì)算機(jī)系副主任、現(xiàn)任清華大學(xué)計(jì)算機(jī)系學(xué)術(shù)委員會副主任，兼任青海大學(xué)計(jì)算機(jī)系主任。他是ACM中國操作系統(tǒng)分會ChinaSysAmericanCommonMarket）JournalofComputerScienceandTechnolog》計(jì)算機(jī)系統(tǒng)與體系結(jié)構(gòu)LeadingEditor，《軟件學(xué)報(bào)》責(zé)任編委，曾經(jīng)參與編著《JAVA虛擬機(jī)規(guī)范》以及《MPI與OpenMP并行程序設(shè)計(jì)：C語言版世界著名計(jì)算機(jī)教材精選》等書。ASPLOS（ACMInternationalConferenceonArchitecturalSupportforProgrammingLanguagesandOperatingSystems），PLDI（ACMSIGPLANconferenceonProgrammingLanguageDesignandImplementation），PPoPP，SC（SupercomputingConference算大會），CGO（InternationalSymposiumonCodeGenerationandOptimization），IPDPS（InternationalParallelandDistributedProcessingSymposium），APSYS（ACMAsia-PacificWorkshoponSystems）等領(lǐng)域內(nèi)重要會議的程序委員會委員。11陳文光長期研究高性能計(jì)算編程模型和編譯系統(tǒng)，近幾年在以圖計(jì)算系統(tǒng)為代表的新一代大數(shù)據(jù)處理系統(tǒng)方面取得了進(jìn)展。2014GridGraph性能比國際上同類單機(jī)圖處理引擎如X-STREAM和GraphChi個數(shù)量級，論文在USENIXATC152016/據(jù)分析應(yīng)用（如PageRank、ALS等）上的性能是國際同類圖計(jì)算系統(tǒng)PowerGraph和PowerLyraSpark100其十分之一，其論文在OSDI16陳海波陳海波，現(xiàn)任上海交通大學(xué)軟件學(xué)院教授，PowerLyra共同作者，主要研究領(lǐng)域?yàn)橄到y(tǒng)軟件，系統(tǒng)結(jié)構(gòu)與系統(tǒng)虛擬化。他于2009年獲得復(fù)旦大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)專業(yè)博士學(xué)位。VMWare2011ACM（APSys2011）2012年UENXUsnAC2022013（SOSP（EuroSys2013）程序委員會委員。其相關(guān)研究成果發(fā)表在諸多國際頂級會議如國際操作系統(tǒng)原理大會國（MICRO）（ICSE），IEEETransactionsonSoftwareEngineering等。2009IT2010IBMX1020112009年中國計(jì)算機(jī)學(xué)會優(yōu)秀博士論文獎，他還于2012年獲得NetApp學(xué)院獎學(xué)金。武永衛(wèi)IEEECloudComputing2002（/系統(tǒng)的遠(yuǎn)程部署方法、基于網(wǎng)絡(luò)的高性他提出了基于區(qū)間的高性能計(jì)算系統(tǒng)的負(fù)載預(yù)測方法，為改善高性能計(jì)算系統(tǒng)的運(yùn)行效能提供支持。該方法系統(tǒng)分析和聚類各種高性能計(jì)算系統(tǒng)的運(yùn)行trace特點(diǎn)，通過自適應(yīng)//作為開發(fā)組組長，他研制完成的網(wǎng)格中間件系統(tǒng)CGSP支持了中國教育科研網(wǎng)格GlobusToolkitsTsinghuaCloudCloudBookCorsair200811ScalComIMIS2014FSEACMSIGSOFT杰出論文獎；20152015ScienceandTechnology代亞非代亞非，現(xiàn)\h任北京大學(xué)信息科學(xué)技術(shù)學(xué)院\h教授，從事分布式系統(tǒng)方面的研究工作。她于1993年從哈爾濱工業(yè)大學(xué)計(jì)算機(jī)系獲得\h博士學(xué)位。\h\h\h和\hP2PP2PP2P存儲系統(tǒng)Amazingstore973863\h\h國\h\h2142015產(chǎn)業(yè)應(yīng)用篇2016IBMFacebookTwitter醫(yī)療行業(yè)的應(yīng)用圖計(jì)算的出現(xiàn)使得對病人的智能診斷成為可能。對病人開具處方需要依據(jù)病人的病情（SQL金融行業(yè)的應(yīng)用39（39PAGEPAGE40業(yè)務(wù)場景的數(shù)據(jù)分析和挖掘目標(biāo)。而圖計(jì)算和基于圖的認(rèn)知分析正是在這方面彌補(bǔ)了傳統(tǒng)（Placement）面對這樣的復(fù)雜困難問題，目前金融機(jī)構(gòu)采取的手段都是基于預(yù)先設(shè)定的規(guī)則來分析80%[3]?；ヂ?lián)網(wǎng)行業(yè)的應(yīng)用ITGooglePregel、FacebookGraphGES華為——GESEngine其主要應(yīng)用場景如下：圖14全球圖計(jì)算領(lǐng)域活躍學(xué)者性別比百度——Hugegraph百度安全開源的圖數(shù)據(jù)庫（Vertex）和邊（Edge），實(shí)現(xiàn)ApacheTinkerPop3框架，支持Gremlin（StarKnowledgeGraph，即SKG）14圖15騰訊星圖應(yīng)用場景分析（地圖LightningGraphNeptuneAmazonNeptuneAmazonNeptune以存儲數(shù)十億個關(guān)系并將圖查詢延遲降低到毫秒級。AmazonNeptune支持常見的圖模型PropertyGraphW3CRDFApacheTinkerPopGremlinSPARQL。NeptuneTigerGraphTigerGraph（3TigerGraph的Parallel趨勢篇全局熱度16圖16騰訊星圖應(yīng)用場景從全局的角度來看，自1992年至今，datamining、computervision、graphmatching、patternrecognition等一直都是研究人員研究的重點(diǎn)。近期熱度相較于全局熱點(diǎn)，largegraph、socialnetwork、graphtheory、datamining、editdistance等則是近期的研究重點(diǎn)，具體熱度趨勢如下圖所示：43圖17graphcomputing近期熱度43PAGEPAGE44交叉研究分析根據(jù)全局熱點(diǎn)與近期熱點(diǎn)的趨勢圖，我們選取graphcomputing&datamining、graphcomputing&machinelearning、graphcomputing&socialnetwork2007預(yù)測僅以未來3年為周期來探討。領(lǐng)域交叉熱力值由交叉研究的論文的citation等數(shù)據(jù)加權(quán)計(jì)算得出，熱力值越高，表明這兩個交叉子領(lǐng)域交叉研究的越深入和廣泛。學(xué)者研究影響度由交叉領(lǐng)域內(nèi)論文量，h-index等計(jì)算得出；論文相關(guān)度由交叉領(lǐng)域內(nèi)論文的關(guān)聯(lián)程度和引用數(shù)量等計(jì)算得出。（citation）GraphComputing&DataMining我們選取graphcomputing的11個相關(guān)領(lǐng)域作為研究對象，具體包括：1.graphcomputing 2.datastructures3.graphmining 4.database5.graphtheory 6.algorithms7.distributedcomputing 8.putationalgeometry 10.numericalanalysis11.textanalysisdatamining101.datamining 2.clustering3.textmining 4.classification5.taxonomy 6.timeseriesanalysis7.associationrule 8.bigdata9.datamanagement 10.networkanalysis對兩個領(lǐng)域的細(xì)分子領(lǐng)域進(jìn)行笛卡爾乘積熱點(diǎn)挖掘，得出歷史交叉熱點(diǎn)圖如下所示：圖182007至今graphcomputing與datamining領(lǐng)域交叉分析2007492166graphcomputingdatamining16922034.38%223063h-indexcitation表42007至今graphcomputing與datamining領(lǐng)域交叉分析h-index專家人數(shù)分布占比小于1046937995.37%10~20158223.21%20~4052531.07%大于4011280.23%總計(jì)492166100%表52007年至今graphcomputing與datamining交叉研究論文citation分布citation專家人數(shù)分布占比小于109911944.44%1~107653334.31%10~1004265419.12%100~20029461.32%大于20018110.81%總計(jì)223063100%GraphComputing&MachineLearninggraphcomputing111.graphcomputing 2.datastructures3.supervisedlearning 4.database5.algorithms 6.graphworkanalysis 8.distributedcomputing9.systemmodeling 10.numericalanalysis11.textanalysismachinelearning101.machinelearning 2.neuralnetworks3.unsupervisedlearning 4.clusteranalysis5.regularization 6.anomalydetection7.reinforcementlearning 8.dynamicprogramming9.supportvectormachines 10.objectrecognition對兩個領(lǐng)域的細(xì)分子領(lǐng)域進(jìn)行笛卡爾乘積熱點(diǎn)挖掘，得出歷史交叉熱點(diǎn)圖如下所示：圖192007至今graphcomputing與machinelearning領(lǐng)域交叉分析2007331387graphcomputingmachinelearning12679338.26%151511h-indexcitation表62007年至今graphcomputing與machinelearning領(lǐng)域交叉研究學(xué)者h(yuǎn)-index分布h-index專家人數(shù)分布占比小于1031016193.59%10~20133304.02%20~4056621.71%大于4013440.41%總計(jì)331387100%表72007年至今graphcomputing與machinelearning領(lǐng)域交叉研究論文citation分布Citation專家人數(shù)分布占比小于106590543.50%1~105316235.09%10~1002893519.10%100~20021641.43%大于20013450.89%總計(jì)151511100%技術(shù)預(yù)見AMinercobnaoalagohasoaonsheeuanodn、empiricalentropysuffixtreehypergraphssub-dominanthypercubedissimilaritypathsandconnectivityproblemsroutingnp-completenesscomputationalcomplexityshortestpathgraphenumeration。圖20圖計(jì)算技術(shù)預(yù)見圖PAGEPAGE51附錄GraphComputing知識圖譜（共包含二級節(jié)點(diǎn)15個，三級節(jié)點(diǎn)93個）：領(lǐng)域二級分類三級分類圖計(jì)