摘要：圖采樣通過對(duì)圖數(shù)據(jù)進(jìn)行約簡操作，獲得比原圖的規(guī)模更小的圖結(jié)構(gòu)，進(jìn)而服務(wù)于圖譜分析、圖可視化等下游任務(wù). 現(xiàn)有的圖采樣算法側(cè)重于保留圖中顯著的結(jié)構(gòu)特征而忽略了節(jié)點(diǎn)屬性，導(dǎo)致采樣圖在許多下游任務(wù)如頻繁模式挖掘等，難以取得預(yù)期效果. 為此，提出基于Motif 的節(jié)點(diǎn)有偏采樣算法（Motif?Based Node Biased Sampling，MNBS），利用頻繁Motif 結(jié)構(gòu)重新定義圖中節(jié)點(diǎn)的重要性，隨后進(jìn)行有偏節(jié)點(diǎn)采樣，實(shí)現(xiàn)融合節(jié)點(diǎn)屬性與結(jié)構(gòu)特征的采樣. 為了快速識(shí)別頻繁Motif 模式，設(shè)計(jì)了具有“提前終止”特性的Motif 模式快速發(fā)現(xiàn)算法（Fast Motif?Pattern Discovery，F(xiàn)MPD），能高效且準(zhǔn)確地發(fā)現(xiàn)Motif 模式以支持圖采樣. 實(shí)驗(yàn)表明，MNBS 采樣算法在多項(xiàng)指標(biāo)上優(yōu)于其他基線算法，其對(duì)數(shù)歸一化累積組相關(guān)性指標(biāo)平均降低0. 54，使用包含“提前終止”特性策略的FMPD 算法的時(shí)間消耗和內(nèi)存消耗比基線算法分別降低56. 1% 和29. 8%.

關(guān)鍵詞：圖采樣，圖數(shù)據(jù)挖掘，網(wǎng)絡(luò)分析，Motif 結(jié)構(gòu)

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A

近年來圖數(shù)據(jù)的規(guī)模在各領(lǐng)域呈爆炸增長的趨勢［1］，現(xiàn)有的圖數(shù)據(jù)處理算法，如圖挖掘［2］、圖聚類［3］、圖可視化［4］等，在面對(duì)海量圖數(shù)據(jù)時(shí)越來越力不從心. 圖采樣是從原圖中抽取一個(gè)規(guī)模較小的子圖的方法，對(duì)采樣子圖進(jìn)行分析可以幫助評(píng)估原圖的結(jié)構(gòu)屬性［5］. 由于圖采樣對(duì)下游任務(wù)十分關(guān)鍵，所以大量圖采樣算法被提出. 現(xiàn)有的圖采樣算法大致分三類：基于節(jié)點(diǎn)的圖采樣、基于邊的圖采樣以及基于拓?fù)浣Y(jié)構(gòu)的圖采樣［6］. 然而，這些圖采樣算法主要針對(duì)圖的結(jié)構(gòu)特征，即保留聚類系數(shù)、最短路徑、節(jié)點(diǎn)中心性等結(jié)構(gòu)屬性［7］，但忽略了節(jié)點(diǎn)標(biāo)簽、邊類別等自有屬性，實(shí)際上這些自有屬性在實(shí)際應(yīng)用中扮演著重要角色［8］.