表征學(xué)習(xí)驅(qū)動(dòng)的多重網(wǎng)絡(luò)圖采樣

虞瑞麒，劉玉華*，沈禧龍，翟如鈺，張翔，周志光

（1.杭州電子科技大學(xué)數(shù)字媒體與藝術(shù)設(shè)計(jì)學(xué)院，浙江 杭州 310018；2.浙江財(cái)經(jīng)大學(xué)信息管理與人工智能學(xué)院，浙江 杭州 310018）

表征學(xué)習(xí)驅(qū)動(dòng)的多重網(wǎng)絡(luò)圖采樣

虞瑞麒1，劉玉華1*，沈禧龍2，翟如鈺1，張翔2，周志光1

（1.杭州電子科技大學(xué)數(shù)字媒體與藝術(shù)設(shè)計(jì)學(xué)院，浙江 杭州 310018；2.浙江財(cái)經(jīng)大學(xué)信息管理與人工智能學(xué)院，浙江 杭州 310018）

已有的圖采樣方法側(cè)重于單圖采樣，關(guān)注如何在一張圖上通過(guò)采樣保留其特定的拓?fù)浣Y(jié)構(gòu)特征。隨著數(shù)據(jù)采集能力的提升，多重網(wǎng)絡(luò)圖在實(shí)際應(yīng)用中越來(lái)越普遍，即相同的節(jié)點(diǎn)集在不同場(chǎng)景中具有不同的網(wǎng)絡(luò)關(guān)系。針對(duì)傳統(tǒng)圖采樣方法無(wú)法兼顧多重網(wǎng)絡(luò)圖結(jié)構(gòu)特征的問(wèn)題，提出了表征學(xué)習(xí)驅(qū)動(dòng)的多重網(wǎng)絡(luò)圖采樣算法。首先，設(shè)計(jì)融合多重網(wǎng)絡(luò)圖結(jié)構(gòu)特征的圖表征學(xué)習(xí)方法，將節(jié)點(diǎn)投影至二維的表征學(xué)習(xí)空間；其次，利用改進(jìn)的自適應(yīng)藍(lán)噪聲采樣算法，考慮節(jié)點(diǎn)密度和網(wǎng)絡(luò)連通性，從表征學(xué)習(xí)空間篩選節(jié)點(diǎn)，以保持其多重網(wǎng)絡(luò)結(jié)構(gòu)特征及圖上下文結(jié)構(gòu)特征。進(jìn)而開發(fā)了一套多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)，支持用戶交互式地探索多重網(wǎng)絡(luò)圖采樣，并與已有采樣算法進(jìn)行對(duì)比。案例分析和評(píng)估實(shí)驗(yàn)證明了本文算法在多重網(wǎng)絡(luò)圖采樣中的有效性。

多重網(wǎng)絡(luò)圖；圖采樣；可視分析；評(píng)估

網(wǎng)絡(luò)圖是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，可對(duì)實(shí)體與實(shí)體之間的關(guān)聯(lián)關(guān)系進(jìn)行有效建模，廣泛應(yīng)用于社交媒體、地理交通和生物醫(yī)學(xué)等領(lǐng)域。隨著數(shù)據(jù)采集能力的提升，網(wǎng)絡(luò)圖的規(guī)模不斷增大，結(jié)構(gòu)也變得越來(lái)越復(fù)雜，這不僅加重了網(wǎng)絡(luò)圖特征分析的計(jì)算負(fù)擔(dān)，也嚴(yán)重影響了網(wǎng)絡(luò)圖的視覺(jué)表達(dá)［1］。因此，提出了一系列圖采樣方法［2］，從原始網(wǎng)絡(luò)中選取部分具有代表性的節(jié)點(diǎn)和邊以簡(jiǎn)化和稀疏大規(guī)模網(wǎng)絡(luò)圖。

在實(shí)際應(yīng)用場(chǎng)景中，節(jié)點(diǎn)之間的關(guān)系可能不止一種，這種具有多種關(guān)聯(lián)關(guān)系的節(jié)點(diǎn)構(gòu)成了一組多重網(wǎng)絡(luò)［3］。例如，同一組社交用戶群體分別在使用QQ、微信和微博等不同社交軟件，并在不同的社交媒體平臺(tái)上擁有不同的好友關(guān)系，由此產(chǎn)生的多種社交關(guān)系網(wǎng)就是典型的多重網(wǎng)絡(luò)。

傳統(tǒng)的圖采樣算法都是單圖采樣，即關(guān)注如何在一張網(wǎng)絡(luò)圖上通過(guò)采樣保留其特定的拓?fù)浣Y(jié)構(gòu)特征，如度分布、聚類系數(shù)、平均路徑長(zhǎng)度等。如果直接將單圖采樣算法分別應(yīng)用于多重網(wǎng)絡(luò)的每一重圖，則會(huì)令采樣得到的節(jié)點(diǎn)集不一致，增大圖采樣結(jié)果的存儲(chǔ)空間，也會(huì)造成采樣分析和探索不連貫。如果只對(duì)多重網(wǎng)絡(luò)中的某張圖進(jìn)行采樣，然后依據(jù)該結(jié)果重構(gòu)其他圖的采樣網(wǎng)絡(luò)關(guān)系，會(huì)造成采樣參照的網(wǎng)絡(luò)圖結(jié)構(gòu)特征保持相對(duì)較好，而其他圖的結(jié)構(gòu)特征極易丟失。因此，傳統(tǒng)的圖采樣算法不適用于多重網(wǎng)絡(luò)圖，不利于多重網(wǎng)絡(luò)圖的聯(lián)合采樣分析。

為解決以上問(wèn)題，本文提出表征學(xué)習(xí)驅(qū)動(dòng)的多重網(wǎng)絡(luò)圖采樣算法。首先，設(shè)計(jì)多重網(wǎng)絡(luò)圖表征學(xué)習(xí)方法，綜合考慮多重網(wǎng)絡(luò)的結(jié)構(gòu)特征，將所有節(jié)點(diǎn)投影至二維表征學(xué)習(xí)空間；其次，利用和改進(jìn)經(jīng)典的自適應(yīng)藍(lán)噪聲采樣算法，考慮節(jié)點(diǎn)密度和網(wǎng)絡(luò)連通性，從二維表征學(xué)習(xí)空間中啟發(fā)式地篩選出部分節(jié)點(diǎn)，以實(shí)現(xiàn)多重網(wǎng)絡(luò)圖上下文結(jié)構(gòu)特征的同步保持；進(jìn)一步，開發(fā)了一套多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)，支持用戶交互式地探索和評(píng)估多重網(wǎng)絡(luò)圖的采樣結(jié)果，將其與已有采樣算法進(jìn)行對(duì)比?；谡鎸?shí)數(shù)據(jù)的案例分析和量化實(shí)驗(yàn)均顯示，本文算法在進(jìn)行多重網(wǎng)絡(luò)圖采樣時(shí)是有效的，其重要節(jié)點(diǎn)、網(wǎng)絡(luò)連通和社區(qū)相似性等多項(xiàng)指標(biāo)均優(yōu)于傳統(tǒng)的圖采樣算法。

1 相關(guān)工作

1.1 圖采樣算法

傳統(tǒng)的圖采樣算法可分為三類。（1）基于點(diǎn)的采樣［4］，在原始網(wǎng)絡(luò)圖中隨機(jī)選取一組節(jié)點(diǎn)，再添加與之關(guān)聯(lián)的邊生成采樣圖。（2）基于邊的采樣［5］，在原始網(wǎng)絡(luò)圖中隨機(jī)選取一組邊，再添加與之對(duì)應(yīng)的節(jié)點(diǎn)生成采樣圖。（3）以上方法獲得的采樣圖其連通性往往難以保持，為此提出基于游走的采樣［6］，首先在圖中隨機(jī)選取1個(gè)節(jié)點(diǎn)，然后基于一定的遍歷策略從當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中隨機(jī)選取1個(gè)節(jié)點(diǎn)作為下一個(gè)采樣節(jié)點(diǎn)，不斷迭代以上過(guò)程，實(shí)現(xiàn)圖采樣。

在可視化領(lǐng)域，圖采樣已廣泛應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)圖的簡(jiǎn)化表達(dá)，通過(guò)降低點(diǎn)線交叉重疊引起的視覺(jué)混淆，增強(qiáng)用戶對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的認(rèn)知和理解。HU等［7］提出基于圖連通性的光譜頂點(diǎn)采樣算法，能較好地保持原始網(wǎng)絡(luò)圖的連通性和全局拓?fù)浣Y(jié)構(gòu)。ZHOU等［8］設(shè)計(jì)了多目標(biāo)的自適應(yīng)藍(lán)噪聲采樣算法，降低人群移動(dòng)網(wǎng)絡(luò)的規(guī)模，同時(shí)保持空間分布特征和社區(qū)結(jié)構(gòu)的一致性。GUO等［9］提出了流采樣算法，對(duì)大規(guī)模遷徙網(wǎng)絡(luò)進(jìn)行簡(jiǎn)化表達(dá)，改進(jìn)和利用核密度模型，提取和展示重要邊。ZHAO等［10］提出了小結(jié)構(gòu)保持的圖采樣算法，盡可能保留原始圖中的少數(shù)結(jié)構(gòu)，如橋節(jié)點(diǎn)、邊緣節(jié)點(diǎn)和高度節(jié)點(diǎn)。ZHOU等［1］基于圖表征學(xué)習(xí)，提出了保持上下文結(jié)構(gòu)特征的采樣算法，在保留全局結(jié)構(gòu)的同時(shí)有效保持聚類密度等特征。

但以上算法均側(cè)重于解決單一網(wǎng)絡(luò)的采樣問(wèn)題，關(guān)注的是如何提高單圖的采樣效率或如何保持特定的拓?fù)浣Y(jié)構(gòu)特征。

1.2 圖采樣評(píng)估

為檢驗(yàn)圖采樣算法的有效性，研究者從結(jié)構(gòu)屬性和視覺(jué)感知角度出發(fā)，設(shè)計(jì)和提出了多種圖采樣評(píng)估指標(biāo)。一類是由圖的結(jié)構(gòu)屬性特征驅(qū)動(dòng)的采樣評(píng)估。例如，MAYIA等［11］利用節(jié)點(diǎn)度分布、聚類質(zhì)量和網(wǎng)絡(luò)覆蓋度等指標(biāo)，對(duì)幾種基于遍歷的圖采樣算法進(jìn)行了評(píng)估。另一類是由用戶視覺(jué)感知驅(qū)動(dòng)的采樣評(píng)估。NGUYEN等［12］借助代理圖的概念提出了基于形狀的視覺(jué)質(zhì)量指標(biāo)，并對(duì)比了不同圖采樣算法對(duì)樣本視覺(jué)質(zhì)量的影響。WU等［13］通過(guò)用戶實(shí)驗(yàn)總結(jié)了影響圖采樣視覺(jué)感知的多項(xiàng)指標(biāo)，并進(jìn)一步探索了傳統(tǒng)圖采樣策略在這些指標(biāo)上的表現(xiàn)力。ZHANG等［14］提出了一套視覺(jué)感知標(biāo)準(zhǔn)，包括聚類的大小、形狀和數(shù)量等，評(píng)估了圖采樣算法在視覺(jué)特征保留上的有效性。

1.3 圖表征學(xué)習(xí)

圖表征學(xué)習(xí)廣泛應(yīng)用于網(wǎng)絡(luò)分析領(lǐng)域，關(guān)注如何獲取網(wǎng)絡(luò)節(jié)點(diǎn)在低維空間中的向量表示，幫助用戶理解和探索在向量空間中的網(wǎng)絡(luò)結(jié)構(gòu)。根據(jù)實(shí)現(xiàn)原理，圖表征學(xué)習(xí)大致分為三類。（1）基于矩陣分解的表征學(xué)習(xí)［15］，以矩陣形式表示網(wǎng)絡(luò)節(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系，并通過(guò)矩陣分解的方式生成節(jié)點(diǎn)向量；（2）基于隨機(jī)游走的表征學(xué)習(xí)，通過(guò)隨機(jī)游走的方式得到節(jié)點(diǎn)序列集合，根據(jù)節(jié)點(diǎn)之間的共現(xiàn)關(guān)系估計(jì)節(jié)點(diǎn)的向量表示，最典型的有DeepWalk［16］和node2vec［17］；（3）基于深度學(xué)習(xí)的表征學(xué)習(xí)［15］，能對(duì)網(wǎng)絡(luò)圖中的非線性結(jié)構(gòu)進(jìn)行建模，并通過(guò)深度自編碼器和自解碼器學(xué)習(xí)和獲取節(jié)點(diǎn)的向量化表示。

2 多重網(wǎng)絡(luò)圖采樣算法

多重網(wǎng)絡(luò)圖采樣算法流程如圖1所示，包括融合多重網(wǎng)絡(luò)圖結(jié)構(gòu)特征的表征學(xué)習(xí)和基于表征學(xué)習(xí)空間的多重網(wǎng)絡(luò)圖采樣。

2.1 融合多重網(wǎng)絡(luò)圖結(jié)構(gòu)特征的表征學(xué)習(xí)

利用node2vec［17］的游走策略將多重網(wǎng)絡(luò)圖結(jié)構(gòu)特征轉(zhuǎn)換至統(tǒng)一的向量化空間，如圖1（b）所示，在保持多重網(wǎng)絡(luò)圖上下文結(jié)構(gòu)的同時(shí)，為后續(xù)采樣提供遍歷基礎(chǔ)和搜索空間。步驟如下：

Step 1 生成序列樣本集。首先，假設(shè)t為上一個(gè)訪問(wèn)節(jié)點(diǎn)，當(dāng)前隨機(jī)游走經(jīng)過(guò)邊（t，v），到達(dá)節(jié)點(diǎn)v，而由v經(jīng)過(guò)邊（v，x）跳轉(zhuǎn)至下一節(jié)點(diǎn)x的概率為

其中，dtx為t與x之間的最短路徑。由式（1）知，當(dāng)dtx為0時(shí)，t和x為同一個(gè)節(jié)點(diǎn)，此時(shí)參數(shù)p控制的是已訪問(wèn)節(jié)點(diǎn)的概率，即返回概率，且p越大，游走訪問(wèn)新節(jié)點(diǎn)的概率越高。當(dāng)dtx為1時(shí)，t和x相連，默認(rèn)跳轉(zhuǎn)概率為1。當(dāng)dtx為2時(shí)，t和x不相連，參數(shù)q控制的是隨機(jī)游走的方向策略。當(dāng)qgt;1時(shí)，傾向于訪問(wèn)與t接近的節(jié)點(diǎn)，反映廣度優(yōu)先的遍歷特性；當(dāng)qlt;1時(shí)，傾向于訪問(wèn)遠(yuǎn)離t的節(jié)點(diǎn)，反映深度優(yōu)先的遍歷特性。

由式（1）設(shè)置歸一化v跳轉(zhuǎn)至各鄰居節(jié)點(diǎn)的概率，在隨機(jī)跳轉(zhuǎn)至下一節(jié)點(diǎn)后按照相同方式訪問(wèn)其他節(jié)點(diǎn)，直至達(dá)到隨機(jī)游走的最大路徑長(zhǎng)度L，一條序列樣本生成完畢。接著以任一節(jié)點(diǎn)為源節(jié)點(diǎn)，利用上述游走策略在每一重網(wǎng)絡(luò)背景下生成對(duì)應(yīng)的序列樣本。最終將這些樣本組成完整的多重網(wǎng)絡(luò)圖序列數(shù)據(jù)集，作為下一步表征學(xué)習(xí)的輸入。

Step 2 向量化表示?；讷@得的所有序列樣本集，設(shè)置目標(biāo)函數(shù)：

其中，f（u）表示將節(jié)點(diǎn)u映射為向量的函數(shù)，Ns（u）表示和u出現(xiàn)在同一條序列樣本中的鄰近節(jié)點(diǎn)集合，即在給定某個(gè)節(jié)點(diǎn)的條件下，使其所在序列樣本集中其他節(jié)點(diǎn)出現(xiàn)的概率最大。用Skip-Gram模型訓(xùn)練輸入序列樣本集，最終得到每個(gè)節(jié)點(diǎn)的向量化表示。

圖1 多重網(wǎng)絡(luò)圖采樣算法流程Fig.1 Flow chart of the multiple graph sampling

Step 3 降維。經(jīng)以上2個(gè)步驟將多重網(wǎng)絡(luò)圖的所有節(jié)點(diǎn)轉(zhuǎn)化為高維向量，同時(shí)保留每一重圖的上下文結(jié)構(gòu)特征，如果在大部分網(wǎng)絡(luò)背景下2個(gè)節(jié)點(diǎn)處于鄰近關(guān)系，那么它們?cè)谙蛄靠臻g中的分布也接近。采用分布式隨機(jī)鄰居嵌入（t-distributed stochastic neighbor embedding，t-SNE）［18］算法將節(jié)點(diǎn)的高維學(xué)習(xí)向量投影至二維平面，為下一步采樣做準(zhǔn)備。

2.2 基于表征學(xué)習(xí)空間的多重網(wǎng)絡(luò)圖采樣

2.2.1 保持上下文結(jié)構(gòu)特征的采樣

基于二維表征學(xué)習(xí)空間，采用自適應(yīng)藍(lán)噪聲采樣算法篩選節(jié)點(diǎn)，盡可能保留和覆蓋原始多重網(wǎng)絡(luò)圖上下文結(jié)構(gòu)特征，如圖1（c）所示。

Step 1 隨機(jī)選擇一個(gè)節(jié)點(diǎn)u，并以此為中心構(gòu)造一個(gè)半徑為r的泊松盤，且r=ra/den（u），ra為由用戶設(shè)置的可以調(diào)整采樣率的參數(shù)，采樣率越大，ra越小，泊松盤就越小。den（u）代表節(jié)點(diǎn)u所處局部區(qū)域的節(jié)點(diǎn)密度，即以u(píng)為圓心、ra為半徑的圓包含的節(jié)點(diǎn)數(shù)量。密度越大，泊松盤的尺寸就越小，在泊松盤內(nèi)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為該局部區(qū)域的代表性節(jié)點(diǎn)。

Step 2 在選擇代表性節(jié)點(diǎn)后，將其所在泊松盤內(nèi)的其他節(jié)點(diǎn)標(biāo)記為非活動(dòng)節(jié)點(diǎn)，再將位于圓盤ra和2ra之間環(huán)形區(qū)域的節(jié)點(diǎn)標(biāo)記為活動(dòng)節(jié)點(diǎn)。隨機(jī)選擇一個(gè)活動(dòng)節(jié)點(diǎn)按照step 1構(gòu)造新的泊松盤，并隨機(jī)選擇代表性節(jié)點(diǎn)。

Step 3 重復(fù)以上2個(gè)步驟，直至所有節(jié)點(diǎn)被標(biāo)記為代表性節(jié)點(diǎn)或非活動(dòng)節(jié)點(diǎn)，采樣結(jié)束。

綜上可知，傳統(tǒng)的藍(lán)噪聲采樣算法可較好地覆蓋整個(gè)數(shù)據(jù)空間，還可根據(jù)節(jié)點(diǎn)疏密自適應(yīng)地調(diào)整采樣圓盤大小，進(jìn)而控制采樣節(jié)點(diǎn)的數(shù)量，保證節(jié)點(diǎn)密度分布的一致性。

2.2.2 多目標(biāo)采樣優(yōu)化

基于向量化空間的藍(lán)噪聲采樣在保持多重網(wǎng)絡(luò)圖上下文結(jié)構(gòu)特征上具有一定優(yōu)勢(shì)，但在結(jié)構(gòu)連通性保持上存在明顯不足。例如，具有較大中介度的節(jié)點(diǎn)（橋節(jié)點(diǎn)），在網(wǎng)絡(luò)連通中很重要，但在泊松盤內(nèi)隨機(jī)選擇代表性節(jié)點(diǎn)時(shí)易被忽略。此外，藍(lán)噪聲采樣過(guò)程沒(méi)有考慮多重網(wǎng)絡(luò)圖的復(fù)雜連接關(guān)系，使得多重網(wǎng)絡(luò)圖的連通性保持存在較大的不確定性。為此，做以下兩點(diǎn)改進(jìn)以增強(qiáng)多重網(wǎng)絡(luò)圖連通性的同步保持。

?項(xiàng)賢明:《教育全球化全景透視:維度、影響與張力》，《北京師范大學(xué)學(xué)報(bào)》(社會(huì)科學(xué)版)2008年第1期。

（1）增加橋節(jié)點(diǎn)被選擇的概率。在采樣模型中加入中介度分析，計(jì)算每一重圖所有節(jié)點(diǎn)的中介度（即任意兩節(jié)點(diǎn)間的最短路徑經(jīng)過(guò)該點(diǎn)的次數(shù)），并做歸一化處理。節(jié)點(diǎn)u在多重網(wǎng)絡(luò)圖中的綜合中介度定義為其在每一重圖中的中介度總和。記bet （u）為節(jié)點(diǎn)u所處局部區(qū)域的連通重要性，即以u(píng)為圓心、ra為半徑的圓包含的所有節(jié)點(diǎn)的平均綜合中介度。對(duì)以u(píng)為中心的泊松盤的半徑進(jìn)行優(yōu)化：

其中，α和β為密度和連通重要性的權(quán)重，且滿足α+β=1.0，α不為0，初始設(shè)置α=β=0.5。若某個(gè)泊松盤包含橋節(jié)點(diǎn)的數(shù)量越多，則泊松盤的半徑將相應(yīng)減小，進(jìn)一步，保證盤內(nèi)節(jié)點(diǎn)的綜合中介度與采樣概率成正比，從而有效增加橋節(jié)點(diǎn)被選為代表性節(jié)點(diǎn)的概率。如圖2（a）所示，優(yōu)化前，以u(píng)為圓心的泊松盤半徑相對(duì)較大，當(dāng)隨機(jī)選擇一個(gè)代表性節(jié)點(diǎn)時(shí)，容易丟失節(jié)點(diǎn)u鄰域范圍內(nèi)的多個(gè)橋節(jié)點(diǎn)（黑色圓點(diǎn)）。優(yōu)化后的泊松盤如圖2（b）所示，以u(píng)為圓心的泊松盤半徑減小，同時(shí)周邊區(qū)域需要填充的泊松盤數(shù)量增加，使得分處不同小盤內(nèi)的多個(gè)橋節(jié)點(diǎn)都有較大概率成為代表性節(jié)點(diǎn)，從而增加了采樣結(jié)果中橋節(jié)點(diǎn)的數(shù)量。

圖2 泊松盤優(yōu)化Fig.2 Optimization of the Poisson disks

（2）考慮多重網(wǎng)絡(luò)圖的同步連通性。雖然在向量化空間中，彼此鄰近的節(jié)點(diǎn)之間相互連接的可能性較高，但由于采樣的隨機(jī)性，難以保證多重網(wǎng)絡(luò)圖在不同網(wǎng)絡(luò)結(jié)構(gòu)上連接。因此，當(dāng)一個(gè)泊松盤向外拓展確定另一個(gè)泊松盤時(shí)，需遍歷其周邊多個(gè)不同的泊松盤，同時(shí)考慮其包含的節(jié)點(diǎn)與當(dāng)前泊松盤內(nèi)代表性節(jié)點(diǎn)在多重網(wǎng)絡(luò)圖上的連接關(guān)系。如圖3所示，中間黑實(shí)線圓為當(dāng)前的采樣圓盤，黑圓點(diǎn)為選中的代表性節(jié)點(diǎn)。假定當(dāng)前為3重網(wǎng)絡(luò)圖，在周邊預(yù)設(shè)的多個(gè)不同泊松盤（虛線圓）中，三角形節(jié)點(diǎn)表示與之前的代表性節(jié)點(diǎn)在每一重圖上均存在連接關(guān)系，圖3右側(cè)圖例中，三角形后面的每個(gè)方框表示其中1重網(wǎng)絡(luò)圖，對(duì)號(hào)表示在對(duì)應(yīng)網(wǎng)絡(luò)圖上連接，叉號(hào)表示不連接。菱形節(jié)點(diǎn)表示與代表性節(jié)點(diǎn)在其中2重網(wǎng)絡(luò)圖上存在連接，圓形節(jié)點(diǎn)表示與代表性節(jié)點(diǎn)在其中1重網(wǎng)絡(luò)圖上存在連接。如果周邊某個(gè)泊松盤包含與上一個(gè)代表性節(jié)點(diǎn)在所有圖（或數(shù)量較多的圖）上都存在連接關(guān)系的節(jié)點(diǎn)且節(jié)點(diǎn)數(shù)量較多，那么這個(gè)泊松盤將優(yōu)先作為下一個(gè)采樣圓盤。相比于其他采樣圓盤，在該圓盤內(nèi)選擇某個(gè)代表性節(jié)點(diǎn)維持多重網(wǎng)絡(luò)圖同步連通性的概率更大。如圖3所示，箭頭指向的右側(cè)圓盤包含2個(gè)與中心圓盤黑色代表性節(jié)點(diǎn)在3重網(wǎng)絡(luò)上都連接的節(jié)點(diǎn)，因此優(yōu)先選中作為下一個(gè)采樣盤。

圖3 考慮多重網(wǎng)絡(luò)圖連通性的泊松盤遍歷Fig.3 Traversal across different Poisson disks for the retention of multiple graph connection.

3 多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)

多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)如圖4所示。

3.1 多重網(wǎng)絡(luò)圖數(shù)據(jù)集

系統(tǒng)內(nèi)置2套多重網(wǎng)絡(luò)圖數(shù)據(jù)集（https：//manliodedomenico.com/data.php）。第一套是熱點(diǎn)Twitter轉(zhuǎn)發(fā)數(shù)據(jù)集MOSS，從中選取400個(gè)用戶，根據(jù)轉(zhuǎn)發(fā)、提及和回復(fù)構(gòu)造3重網(wǎng)絡(luò)。第二套是線蟲連接體數(shù)據(jù)CELE，包含237個(gè)神經(jīng)元節(jié)點(diǎn)，通過(guò)不同的信號(hào)傳遞方式（電突觸、化學(xué)突觸和多元突觸）構(gòu)建3重網(wǎng)絡(luò)。

圖4 多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)Fig.4 Visual analytics system of multiple network sampling

3.2 采樣算法和評(píng)估指標(biāo)

系統(tǒng)包含3種經(jīng)典的網(wǎng)絡(luò)圖采樣算法。（1）基于節(jié)點(diǎn)的采樣：本文算法（Our）、隨機(jī)節(jié)點(diǎn)采樣（random node，RN）［4］；（2）基于邊的采樣：隨機(jī)邊（random edge，RE）采樣［5］、全誘導(dǎo)邊（total induction edge，TIE）采樣［10］；（3）基于游走的采樣：簡(jiǎn)單隨機(jī)游走（simple random walk，SRW）采樣［19］、隨機(jī)跳轉(zhuǎn)（random jump，RJ）采樣［13］、誘導(dǎo)子圖隨機(jī)游走（induced subgraph random walk，ISRW）采樣［1］。利用可視分析系統(tǒng)對(duì)表1所示的各項(xiàng)指標(biāo)進(jìn)行對(duì)比。

表1 評(píng)估指標(biāo)Table 1 Evaluation metrics

3.3 可視化視圖和交互

通過(guò)圖4左上角的控制面板加載多重網(wǎng)絡(luò)數(shù)據(jù)集，選擇不同的采樣算法并設(shè)置采樣率等參數(shù)完成圖采樣工作。系統(tǒng)提供以下可視化形式幫助用戶交互式地探索采樣結(jié)果，并評(píng)估各類采樣算法。

3.3.1 網(wǎng)絡(luò)視圖

圖4中間。用點(diǎn)線連接式的圖布局展示采樣前后的多重網(wǎng)絡(luò)結(jié)構(gòu)。上方并排展示采樣圖，下方對(duì)應(yīng)展示每一重網(wǎng)絡(luò)的原始圖。系統(tǒng)還支持節(jié)點(diǎn)、社區(qū)結(jié)構(gòu)和連通分量的高亮等操作，幫助用戶自主選擇和探索感興趣的結(jié)構(gòu)。

圖4右上角。利用散點(diǎn)圖將表征學(xué)習(xí)得到的節(jié)點(diǎn)向量在二維空間展示，點(diǎn)與點(diǎn)之間的距離表示節(jié)點(diǎn)之間的上下文結(jié)構(gòu)相似性，此外，系統(tǒng)還提供了一套交互工具，可支持高亮采樣節(jié)點(diǎn)、選擇感興趣的局部區(qū)域，為探索多重網(wǎng)絡(luò)上下文結(jié)構(gòu)特征提供便利。

3.3.3 評(píng)估視圖

（1）圖4左下角。以直方圖的形式展示采樣前后某些結(jié)構(gòu)特征的分布情況，包括節(jié)點(diǎn)中介度、節(jié)點(diǎn)中心性、最短路徑長(zhǎng)度、局部聚類系數(shù)和社區(qū)節(jié)點(diǎn)數(shù)量。例如，可通過(guò)堆疊的直方圖清晰直觀地觀察采樣前后節(jié)點(diǎn)中介度的分布變化，從而估計(jì)采樣后是否保留原始圖中中介度較高的節(jié)點(diǎn)。

（2）圖4右下角。以雷達(dá)圖的形式展示所有采樣算法在各項(xiàng)指標(biāo)上的表現(xiàn)情況。每個(gè)徑向軸代表一項(xiàng)度量指標(biāo)，且與同一類別的指標(biāo)軸相鄰，而指標(biāo)值由內(nèi)向外表示從小到大。位于雷達(dá)圖右上方的徑向軸為ABD，沿順時(shí)針?lè)较蚺帕械妮S依次為ACC，CC，APL，SSC，SC，GCC和LCC，不同顏色的閉合連線代表不同的采樣算法，可幫助用戶快速對(duì)比和評(píng)估不同采樣算法的有效性。

4 評(píng)估

4.1 量化實(shí)驗(yàn)

每種采樣算法在多重網(wǎng)絡(luò)數(shù)據(jù)集上運(yùn)行20次（采樣率設(shè)置為10%），統(tǒng)計(jì)所有網(wǎng)絡(luò)圖各項(xiàng)指標(biāo)的平均值。傳統(tǒng)的算法是單圖采樣，因此在每次測(cè)試中，隨機(jī)將其應(yīng)用于某一重圖，并將采樣點(diǎn)的結(jié)果推廣至其他幾重圖。表2和表3分別為各算法在MOSS數(shù)據(jù)集和CELE數(shù)據(jù)集上的評(píng)估結(jié)果，箭頭↑和↓分別表示指標(biāo)值越大越優(yōu)和越小越優(yōu)。

表2 各采樣算法在MOSS數(shù)據(jù)集中的評(píng)估結(jié)果Table 2 Evaluation results of different sampling algorithm on MOSS dataset

表3 各采樣算法在CELE數(shù)據(jù)集中的評(píng)估結(jié)果Table 3 Evaluation results of different sampling algorithm on CELE dataset

如表2所示，在MOSS數(shù)據(jù)集中，本文算法在ABD，ACC，APL，CC，SC和LCC指標(biāo)上表現(xiàn)最優(yōu)，ISRW算法在SSC和GCC上最優(yōu)。如表3所示，在CELE數(shù)據(jù)集中，本文算法在ABD，ACC，CC和SC指標(biāo)上依然維持最優(yōu)；在SSC指標(biāo)上排名由MOSS數(shù)據(jù)集中的第5升至第1；雖然在APL和LCC指標(biāo)上排名有所下滑，但依然排在前3；在GCC指標(biāo)上排名由MOSS數(shù)據(jù)集中的第5升至第2。SRW，ISRW和TIE算法分別在APL，LCC和GCC 3項(xiàng)指標(biāo)上排名第1。

對(duì)比MOSS和CELE兩套數(shù)據(jù)集的特點(diǎn)，發(fā)現(xiàn)MOSS數(shù)據(jù)集的節(jié)點(diǎn)數(shù)量為400，每一重圖包含連邊的數(shù)量均在500左右。而CELE數(shù)據(jù)集的節(jié)點(diǎn)數(shù)量為237，但每一重圖包含連邊的數(shù)量均在1 300左右，網(wǎng)絡(luò)連接關(guān)系更為緊密和復(fù)雜。由以上量化結(jié)果可知，本文算法在面對(duì)具有不同結(jié)構(gòu)特點(diǎn)的多重網(wǎng)絡(luò)數(shù)據(jù)時(shí)，大部分指標(biāo)更為優(yōu)秀和穩(wěn)定，但在某些指標(biāo)上有所起伏。

分析可知，本文算法注重維持所有網(wǎng)絡(luò)圖的全局結(jié)構(gòu)以及它們之間的關(guān)聯(lián)和互通性，因此當(dāng)節(jié)點(diǎn)連接相對(duì)稀疏時(shí)（如MOSS數(shù)據(jù)集），本文算法在APL指標(biāo)上的優(yōu)勢(shì)更明顯，但當(dāng)節(jié)點(diǎn)連接普遍緊密時(shí)（如CELE數(shù)據(jù)集），其他算法也能相對(duì)較好地保持連通關(guān)系，一定程度上弱化了本文算法在該指標(biāo)上的優(yōu)勢(shì)。

此外，本文算法忽略了局部區(qū)域之間連接關(guān)系的相對(duì)強(qiáng)弱，尤其在MOSS數(shù)據(jù)集中，區(qū)域之間的關(guān)聯(lián)強(qiáng)弱變化明顯，本文算法在采樣后打破了原有節(jié)點(diǎn)間的強(qiáng)弱關(guān)聯(lián)關(guān)系，從而改變了原有的社區(qū)結(jié)構(gòu)穩(wěn)定性（SSC）和全局聚類系數(shù)（GCC）。但在CELE數(shù)據(jù)集中，節(jié)點(diǎn)之間的連接普遍緊實(shí)，局部區(qū)域之間的連接關(guān)系都很強(qiáng)且相對(duì)穩(wěn)定，彌補(bǔ)了本文算法在關(guān)系強(qiáng)弱保持上的不足，使得本文算法的這2項(xiàng)指標(biāo)得到提升。

在實(shí)驗(yàn)結(jié)果中，只在某1～2項(xiàng)指標(biāo)上排名第1的ISRW和SRW采樣算法，均考慮局部特征，在保持社區(qū)結(jié)構(gòu)穩(wěn)定性和局部聚類系數(shù)方面有一定優(yōu)勢(shì)。但在更多的全局特征上，如反映重要節(jié)點(diǎn)保留的ABD和ACC指標(biāo)、反映全局社區(qū)采樣的SC指標(biāo)和反映連通性的CC指標(biāo)，本文算法均優(yōu)于傳統(tǒng)的圖采樣算法，能在更大程度上保留多重網(wǎng)絡(luò)圖的全局特征。

4.2 案例分析

在多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)中，加載MOSS數(shù)據(jù)集，將采樣率設(shè)置為15%。從基于點(diǎn)、邊和游走的算法中各選擇一種經(jīng)典的采樣算法RN，RE和SRW，將其應(yīng)用于第一重圖，進(jìn)一步應(yīng)用于第二和第三重圖，得到節(jié)點(diǎn)接近中心性分布直方圖，如圖5所示，從左到右依次為第一、二、三重圖的采樣結(jié)果。在行列相間位置的直方圖中，橫軸表示節(jié)點(diǎn)接近中心性經(jīng)歸一化后的度量值，縱軸表示落在相應(yīng)區(qū)間的節(jié)點(diǎn)數(shù)量的對(duì)數(shù)值，從而縮小了柱狀圖之間的高度差，方便對(duì)比。

圖5 節(jié)點(diǎn)接近中心性分布直方圖對(duì)比（MOSS）Fig.5 Comparison of histogram distributions for node closeness centrality （MOSS）

由圖5可知，相較傳統(tǒng)算法，本文算法獲得的采樣結(jié)果涵蓋原有直方圖分布區(qū)間的范圍較廣，且采樣柱狀圖的高度和大小比例與原始圖更一致。例如，最后一行的RN采樣算法效果最差，在每一重圖上的深色柱狀圖較少，與原始網(wǎng)絡(luò)圖的節(jié)點(diǎn)接近中心性分布差異較大。而RE和SRW算法形成的直方圖分布連續(xù)性較差，在中間某1～2段區(qū)間出現(xiàn)了缺失（右側(cè)第三重圖最明顯），在左側(cè)或右側(cè)的空白區(qū)間易產(chǎn)生新的直方圖，表現(xiàn)極不穩(wěn)定。結(jié)合量化實(shí)驗(yàn)可知，本文算法不僅在節(jié)點(diǎn)接近中心性上的宏觀統(tǒng)計(jì)表現(xiàn)最優(yōu)，而且在每一重圖上均能較好地保持分布特征。

圖6為本文算法和在量化實(shí)驗(yàn)中表現(xiàn)相對(duì)較好的ISRW和TIES算法的對(duì)比，其中，（a）為在MOSS數(shù)據(jù)集中每一重圖的力導(dǎo)向布局，（b）（c）和（d）依次為本文、ISRW和TIES算法在15%采樣率下得到的可視化效果，（c）和（d）均為將對(duì)應(yīng)算法應(yīng)用于第一重網(wǎng)絡(luò)，然后將采樣結(jié)果推廣至其他2重圖得到的采樣結(jié)果。所有結(jié)果均按第一、二、三重圖的順序從左到右依次展示，每一重圖的節(jié)點(diǎn)顏色都映射為在該網(wǎng)絡(luò)結(jié)構(gòu)下的社區(qū)分類。

圖6 在MOSS數(shù)據(jù)集中的采樣結(jié)果可視化對(duì)比Fig.6 Comparison of sampling results of MOSS dataset

由圖6可知，本文算法在每一重圖的區(qū)域覆蓋和連通性上均表現(xiàn)最優(yōu)。例如，ISRW算法在第一重圖上出現(xiàn)了嚴(yán)重的社區(qū)丟失現(xiàn)象。對(duì)比圖6（a）原始的第一重圖，不難發(fā)現(xiàn)圖6（c）在左上角區(qū)域的灰色社區(qū)和青色社區(qū)中沒(méi)有采樣到任何一個(gè)節(jié)點(diǎn)，使得用戶對(duì)全局結(jié)構(gòu)的感知極易出現(xiàn)偏差。圖6（d）所示的TIES算法在第二重圖的中間出現(xiàn)了明顯的空白區(qū)域，無(wú)法保留一些起關(guān)鍵連通作用的節(jié)點(diǎn)和連邊。

本文算法使用了綜合所有圖上下文結(jié)構(gòu)特征的圖表征學(xué)習(xí)方法，并在此空間內(nèi)使用覆蓋性較好的藍(lán)噪聲采樣算法，使得每一重圖的社區(qū)或局部區(qū)域都有點(diǎn)被采樣，從而較為完整地保留了全局結(jié)構(gòu)。此外，圖6（c）中的第二、三重圖和圖6（d）中的第一、三重圖均存在較多的孤立點(diǎn)和明顯的不連通分量，無(wú)法正確推斷網(wǎng)絡(luò)間的區(qū)域互聯(lián)和社區(qū)連通情況，而此類問(wèn)題在圖6（b）中出現(xiàn)較少，關(guān)聯(lián)缺失的現(xiàn)象不明顯，進(jìn)一步驗(yàn)證了本文算法在CC和SC這2項(xiàng)指標(biāo)上表現(xiàn)最優(yōu)。

最后利用多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)加載CELE數(shù)據(jù)集，將采樣率設(shè)置為20%。選擇RJ算法和TIES算法，并將其應(yīng)用于第三重網(wǎng)絡(luò)，進(jìn)一步探索得到的采樣結(jié)果在每一重圖中的連通情況，見(jiàn)圖7。其中，（a）展示了原始的多重網(wǎng)絡(luò)圖布局，（b）（c）和（d）依次為本文、RJ和TIES算法的連通分量高亮可視化效果，其中孤立節(jié)點(diǎn)用同一種顏色高亮展示，其余的連通分量用不同顏色的包圍盒展示。

圖7 在CELE數(shù)據(jù)集中的采樣結(jié)果可視化對(duì)比Fig.7 Comparison of sampling results of CELE dataset

由圖7（b）知，本文算法在第一重圖上表現(xiàn)稍差，出現(xiàn)了10個(gè)左右的孤立節(jié)點(diǎn)，在第二、三重圖上均出現(xiàn)了5個(gè)左右的孤立節(jié)點(diǎn)，而在每個(gè)圖中生成的主體連通子圖，均能較好地還原初始網(wǎng)絡(luò)的全局結(jié)構(gòu)和整體特征。相比之下，圖7（c）和（d）均在第三重圖上表現(xiàn)較好，只有1～2個(gè)孤立節(jié)點(diǎn)，但在其余2重圖上表現(xiàn)較差，除產(chǎn)生10多個(gè)孤立節(jié)點(diǎn)外，還形成了2～3個(gè)規(guī)模較大的連通子圖，容易破壞用戶對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的整體認(rèn)知。具體原因?yàn)镽J和TIES算法均以第三重圖為參照進(jìn)行采樣，沒(méi)有考慮其他重圖，因此只有參照?qǐng)D維持了一定的結(jié)構(gòu)特征，無(wú)法同時(shí)保持多重網(wǎng)絡(luò)圖的結(jié)構(gòu)屬性。本文算法能同步保持每一重圖的結(jié)構(gòu)關(guān)聯(lián)，因此在多重網(wǎng)絡(luò)圖上的采樣表現(xiàn)更穩(wěn)定。

5 結(jié)論

利用改進(jìn)的自適應(yīng)藍(lán)噪聲采樣算法，從多重網(wǎng)絡(luò)圖表征學(xué)習(xí)空間中啟發(fā)式地篩選節(jié)點(diǎn)，盡可能地實(shí)現(xiàn)多重網(wǎng)絡(luò)圖的特征保持?；诙嘀鼐W(wǎng)絡(luò)圖采樣可視分析系統(tǒng)的案例分析和量化實(shí)驗(yàn)均顯示了本文算法在多重網(wǎng)絡(luò)圖采樣中的有效性。下一步將在規(guī)模更大、網(wǎng)絡(luò)圖數(shù)量更多的多重網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行采樣效果實(shí)驗(yàn)，以分析和測(cè)試本文算法的可拓展性。此外，通過(guò)與領(lǐng)域?qū)＜颐芮杏懻撨M(jìn)一步改進(jìn)多重網(wǎng)絡(luò)圖采樣可視分析系統(tǒng)的視圖設(shè)計(jì)和交互功能，提高系統(tǒng)的實(shí)用性。

［1］ZHOU Z， SHI C，SHEN X， et al. Context-aware sampling of large networks via graph representation learning［J］. IEEE Transactions on Visualization and Computer Graphics，2020， 27（2）：1709-1719. DOI：10.1109/TVCG.2020.3030440

［2］CHENG K. Sampling from large graphs with a reservoir［C］// Proceedings of the 2014 17th International Conference on Network-Based Information Systems. Los Alamitos：IEEE Computer Society Press， 2014：347-354. DOI：10. 1109/NBiS.2014.25

［3］MAGNANI M， ROSSI L. Formation of multiple networks［C］// International Conference on Social Computing， Behavioral-Cultural Modeling and Prediction. Berlin/Heidelberg： Springer，2013： 257-264. DOI：10.1007/978-3-642-37210-0_28

［4］SUN R， ZHANG L，CHEN Z. A sample-based approximate ranking method for large graphs［C］// 2018 6th International Conference on Advanced Cloud and Big Data（CBD）. Los Alamitos： IEEE Computer Society Press，2018： 112-117. DOI：10. 1109/CBD.2018.00029

［5］TüRKOGLU D， TURK A. Edge-based wedge sampling to estimate triangle counts in very large graphs［C］// 2017 IEEE International Conference on Data Mining（ICDM）. Los Alamitos： IEEE Computer Society Press，2017： 455-464. DOI：10. 1109/ICDM.2017.55

［6］YOON S H， KIM K N，HONG J， et al. A community-based sampling method using DPL for online social networks［J］. Information Sciences， 2015，306： 53-69. DOI：10.1016/j.ins. 2015.02.014

［7］HU J， HONG S H，CHEN J， et al. Connectivity-based spectral sampling for big complex network visualization［C］// International Conference on Complex Networks and Their Applications. Cham：Springer， 2020：237-248. DOI：10.1007/978-3-030-65347-7_20

［8］ZHOU Z， MENG L，TANG C， et al. Visual abstraction of large scale geospatial origin-destination movement data［J］. IEEE Transactions on Visualization and Computer Graphics，2018， 25（1）：43-53. DOI：10.1109/TVCG.2018.2864503

［9］GUO D， ZHU X. Origin-destination flow data smoothing and mapping［J］. IEEE Transactions on Visualization and Computer Graphics，2014， 20（12）：2043-2052. DOI：10.1109/TVCG.2014. 2346271

［10］ZHAO Y， JIANG H，CHEN Q， et al. Preserving minority structures in graph sampling［J］. IEEE Transactions on Visualization and Computer Graphics，2020， 27（2）：1698-1708. DOI：10.1109/TVCG.2020.3030428

［11］MAIYA A S， BERGER-WOLF T Y. Benefits of bias： Towards better characterization of network sampling［C］// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2011： 105-113. DOI：10.1145/2020408. 2020431

［12］NGUYEN Q H， HONG S H，EADES P， et al. Proxy graph：Visual quality metrics of big graph sampling［J］. IEEE Transactions on Visualization and Computer Graphics， 2017，23（6）： 1600-1611. DOI：10.1109/TVCG.2017.2674999

［13］WU Y， CAO N，ARCHAMBAULT D， et al. Evaluation of graph sampling： A visualization perspective［J］. IEEE Transactions on Visualization and Computer Graphics，2016， 23（1）：401-410. DOI：10.1109/TVCG.2016.2598867

［14］ZHANG F Y， ZHANG S，WONG P C， et al. A visual evaluation study of graph sampling techniques［J］. Electronic Imaging， 2017，2017（1）： 110-117. DOI：10.2352/ISSN.2470-1173.2017.1.VDA-394

［15］ZHANG D， YIN J，ZHU X， et al. Network representation learning： A survey［J］. IEEE Transactions on Big Data， 2020，6（1）： 3-28. DOI：10.1109/TBDATA.2018.2850013.

［16］PEROZZI B， AL-RFOU R，SKIENA S. Deepwalk： online learning of social representations［C］// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2014： 701-710. DOI：10.1145/2623330.2623732

［17］GROVER A， LESKOVEC J. Node2vec：Scalable feature learning for networks［C］// Proceedings of the 22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press，2016： 855-864. DOI：10.1145/2939672.2939754

［18］WANG Y， CHEN L，JO J， et al. Jointt-SNE for comparable projections of multiple high-dimensional datasets［J］. IEEE Transactions on Visualization and Computer Graphics，2022， 28（1）：623-632. DOI：10.1109/TVCG.2021.3114765.

［19］SARMA A D， NANONGKAI D，PANDURANGAN G， et al. Distributed random walks［J］. Journal of the ACM，2013， 60（1）：1-31. DOI：10.1145/2432622. 2432624

Representation learning driven multiple graph sampling

YU Ruiqi1, LIU Yuhua1, SHEN Xilong2, ZHAI Ruyu1, ZHANG Xiang2, ZHOU Zhiguang1

（1. School of Media and Design，Hangzhou Dianzi University，Hangzhou310018，China；2. School of Information Management and Artificial Intelligence，Zhejiang University of Finance and Economics，Hangzhou310018，China）

The existing graph sampling techniques pay attention mainly to single graph sampling, focusing on how to preserve the specific topological features of a graph by sampling, such as node degree, cluster coef?cient, connectivity. With the improvement of data acquisition capability, multiple graphs, namely a set of nodes exhibits different relationships in different scenarios, have become quietly ubiquitous in the real world. To address this problem, a multiple graph sampling driven by representation learning is proposed. First, a graph representation learning method is designed to fuse the structural features of multiple graphs, through which the nodes are projected into a two-dimensional representation learning space. Then, considering node density and network connectivity, an improved the adaptive blue noise sampling algorithm is employed to select nodes from the representation learning space meanwhile simultaneously preserving the contextual structure features of multiple graphs. Furthermore, an interactive visual analytics system is developed allowing users to explore and analyze multiple graph sampling, and visually compare results with various sampling strategies. Case studies and the experimental results based on two real-world datasets have demonstrated the effectiveness of the proposed method in sampling multiple graphs.

multiple network graphs; graph sampling; visual analysis; evaluation

TP 391.41

A

1008?9497（2022）03?271?09

2022?01?30.

國(guó)家自然科學(xué)基金資助項(xiàng)目（61802339，61872314）；浙江大學(xué)CADamp;CG國(guó)家重點(diǎn)實(shí)驗(yàn)室開放課題（A2224）.

虞瑞麒（2001—），ORCID：https：//orcid.org/0000-0001-6116-6678，男，本科生，主要從事數(shù)據(jù)可視化研究，E-mail：yrq0121@hdu.edu.cn.

通信作者，ORCID：https：//orcid.org/0000-0003-0600-4056，E-mail：liuyuhua@hdu.edu.cn.

10.3785/j.issn.1008-9497.2022.03.002