楊伏長(zhǎng) 朱嘉富 孫佳敏 謝江

摘 要：生物復(fù)雜網(wǎng)絡(luò)motif發(fā)現(xiàn)是一種研究生物網(wǎng)絡(luò)的重要方法，它基于復(fù)雜網(wǎng)絡(luò)的理論研究，以新的視角來(lái)研究生命現(xiàn)象和生命機(jī)制，但是在處理較大的網(wǎng)絡(luò)規(guī)模或者需挖掘較大的motif時(shí)計(jì)算效率低。針對(duì)這個(gè)問(wèn)題，在現(xiàn)有串行網(wǎng)絡(luò)motif發(fā)現(xiàn)算法ESU的基礎(chǔ)上，提出一種基于消息傳遞接口（MPI）的并行化ESU算法。該方法在ESU計(jì)算過(guò)程中優(yōu)化了節(jié)點(diǎn)值以解決節(jié)點(diǎn)值依賴(lài)問(wèn)題，并以ESU算法的子圖發(fā)現(xiàn)策略統(tǒng)計(jì)各節(jié)點(diǎn)子圖數(shù)，利用動(dòng)態(tài)規(guī)劃策略尋找最佳節(jié)點(diǎn)分配策略以解決負(fù)載不均衡問(wèn)題。模擬網(wǎng)絡(luò)數(shù)據(jù)和真實(shí)生物網(wǎng)絡(luò)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明，并行化ESU算法優(yōu)化了節(jié)點(diǎn)值依賴(lài)問(wèn)題，實(shí)現(xiàn)了基于動(dòng)態(tài)規(guī)劃的負(fù)載均衡策略，其運(yùn)行時(shí)間比串行算法縮短了90%，并且該并行算法對(duì)不同類(lèi)型不同規(guī)模的網(wǎng)絡(luò)都具有較強(qiáng)的適用性，有效地提高了網(wǎng)絡(luò)motif發(fā)現(xiàn)問(wèn)題的計(jì)算效率。

關(guān)鍵詞：網(wǎng)絡(luò)motif發(fā)現(xiàn);子圖枚舉;同構(gòu)比較;并行化;消息傳遞接口

中圖分類(lèi)號(hào)： TP301.6

文獻(xiàn)標(biāo)志碼：A

Abstract： Biological complex network motifs discovery， based on theoretical research of complex networks， is an important method for studying biological networks， which provides a new perspective on life phenomena and life mechanisms. However， it computes inefficiently when dealing with large networks or mining big motifs. On the basis of existing serial ESU （Enumerate SUbgraph） algorithm of network motifs discovery， a parallelized ESU algorithm based on Message Passing Interface （MPI） was proposed. The node values in ESU algorithm were optimized to solve the problem of node value dependency， the number of subgraphs was counted by using subgraph discovery strategy of ESU algorithm， and a dynamic programming method was used to determine optimal node allocation strategy to satisfy load balancing. The experiments on simulated and biological networks show that the parallelized ESU algorithm addresses node value dependency and realizes a load balancing strategy， which saves more than 90% running time compared to serial algorithm. Furthermore， the parallel algorithm is suitable for different types and different scales of networks， and effectively improves computation efficiency of network motifs discovery.

Key words： network motifs discovery; Enumerate SUbgraph （ESU）; homogeneous comparison; parallelization; Message Passing Interface （MPI）

0 引言

生物網(wǎng)絡(luò)比對(duì)對(duì)網(wǎng)絡(luò)醫(yī)學(xué)和物種演化等領(lǐng)域的發(fā)展有著重大的意義[1]，其中，一項(xiàng)很重要的研究就是生物網(wǎng)絡(luò)motif發(fā)現(xiàn)。生物網(wǎng)絡(luò)motif發(fā)現(xiàn)是指在生物網(wǎng)絡(luò)中尋找所有特定大小、拓?fù)浣Y(jié)構(gòu)一致的子圖[2]，它包括在生物網(wǎng)絡(luò)中枚舉子圖和計(jì)算子圖之間的同構(gòu)關(guān)系等問(wèn)題。生物網(wǎng)絡(luò)motif是生物網(wǎng)絡(luò)的基本單元，它所表現(xiàn)的局部性質(zhì)與網(wǎng)絡(luò)的構(gòu)成機(jī)制密切相關(guān)，對(duì)它的研究可以加深對(duì)生物網(wǎng)絡(luò)的結(jié)構(gòu)和功能的理解，有助于揭示很多重要的生物學(xué)問(wèn)題[3];然而精確識(shí)別網(wǎng)絡(luò)motif是一個(gè)計(jì)算復(fù)雜度很高的問(wèn)題[4]，每一個(gè)枚舉的子圖都需要執(zhí)行同構(gòu)比較，而子圖之間同構(gòu)關(guān)系的計(jì)算一直是NP（Non-deterministic Polynomial）難問(wèn)題，無(wú)法通過(guò)改進(jìn)算法來(lái)降低其時(shí)間復(fù)雜度。隨著生物網(wǎng)絡(luò)研究的規(guī)模和motif的大小不斷增大，參與枚舉和同構(gòu)比較的子圖數(shù)呈指數(shù)級(jí)別的增長(zhǎng)，其計(jì)算量越來(lái)越大，給網(wǎng)絡(luò)motif的發(fā)現(xiàn)帶來(lái)了挑戰(zhàn)。

當(dāng)前網(wǎng)絡(luò)motif發(fā)現(xiàn)研究算法仍以Wernicke[5]于2006年提出的ESU（Enumerate SUbgraph）算法為主流，其衍生算法如Ribeiro等[6]于2010提出的基于G-Tries的改進(jìn)算法，通過(guò)G-Tries來(lái)存儲(chǔ)motif所枚舉的圖，減少了比較子圖同構(gòu)次數(shù)來(lái)降低時(shí)間、提高性能;Khakabimamaghani等[7]于2013年提出了QuateXelero算法，該算法利用四分樹(shù)結(jié)構(gòu)來(lái)減少同構(gòu)計(jì)算次數(shù);Luo等[8]于2018年提出的LCNM（Large Co-regulatory Network Motifs）算法，通過(guò)結(jié)合枚舉和隨機(jī)化ESU算法，提高了網(wǎng)絡(luò)motif發(fā)現(xiàn)的計(jì)算效率。

目前，已有的網(wǎng)絡(luò)motif發(fā)現(xiàn)算法，在計(jì)算規(guī)模上都存在瓶頸[9]。隨著生物網(wǎng)絡(luò)數(shù)據(jù)獲取的渠道越來(lái)越多，生物網(wǎng)絡(luò)規(guī)模越來(lái)越大，對(duì)計(jì)算效率的要求也會(huì)越來(lái)越高，因此，實(shí)現(xiàn)高效的并行化網(wǎng)絡(luò)motif發(fā)現(xiàn)算法是很有必要的。本文從串行的ESU算法著手，分析算法中各個(gè)部分的耗時(shí)，針對(duì)算法中耗時(shí)最長(zhǎng)的部分，以消息傳遞接口（Message Passing Interface， MPI）為基礎(chǔ)實(shí)現(xiàn)并行化，并結(jié)合優(yōu)化節(jié)點(diǎn)值和動(dòng)態(tài)分配節(jié)點(diǎn)策略改進(jìn)并行算法，最后通過(guò)仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)進(jìn)行了分析和討論。

1 網(wǎng)絡(luò)motif發(fā)現(xiàn)

網(wǎng)絡(luò)motif發(fā)現(xiàn)問(wèn)題本質(zhì)上是統(tǒng)計(jì)各種非同構(gòu)子圖在網(wǎng)絡(luò)中出現(xiàn)的頻率，并與隨機(jī)網(wǎng)絡(luò)所產(chǎn)生的子圖的頻率進(jìn)行比較，出現(xiàn)頻率明顯高于隨機(jī)網(wǎng)絡(luò)的那些子圖可能會(huì)揭示網(wǎng)絡(luò)的重要功能[2]。然而，隨著估計(jì)重要性方法的出現(xiàn)，網(wǎng)絡(luò)motif發(fā)現(xiàn)問(wèn)題的計(jì)算負(fù)擔(dān)就落在原始網(wǎng)絡(luò)的子圖統(tǒng)計(jì)上[10]，因此網(wǎng)絡(luò)motif發(fā)現(xiàn)過(guò)程就是各種子圖的統(tǒng)計(jì)過(guò)程，其形式化定義[11]如下：

定義1 網(wǎng)絡(luò)motif發(fā)現(xiàn)。給定一個(gè)網(wǎng)絡(luò)G和參數(shù)k，找出所有大小為k的子圖，并根據(jù)各個(gè)子圖間的同構(gòu)關(guān)系進(jìn)行分類(lèi)。

根據(jù)子圖間的同構(gòu)關(guān)系進(jìn)行分類(lèi)是網(wǎng)絡(luò)motif發(fā)現(xiàn)過(guò)程中計(jì)算量最大的部分，目前尚無(wú)多項(xiàng)式級(jí)別的算法能夠完成這個(gè)分類(lèi)過(guò)程，即使在較高效的算法如nauty算法[12]，其在最壞情況下，計(jì)算復(fù)雜度仍達(dá)到O（n?。?/p>

2.1 串行ESU算法

2.1.1 算法實(shí)現(xiàn)原理

ESU算法是一種枚舉子圖的motif發(fā)現(xiàn)算法，ESU算法可以大致分為網(wǎng)絡(luò)構(gòu)建、枚舉子圖、子圖同構(gòu)比較和統(tǒng)計(jì)子圖結(jié)果四個(gè)步驟，其中ESU算法所提出的枚舉子圖的過(guò)程保證了所枚舉子圖的唯一性和子圖數(shù)的準(zhǔn)確性，枚舉子圖的過(guò)程是后續(xù)子圖同構(gòu)比較過(guò)程的實(shí)現(xiàn)前提，因此，下文對(duì)ESU算法的枚舉子圖過(guò)程展開(kāi)介紹。

ESU算法的輸入為邊集的形式，節(jié)點(diǎn)的序號(hào)（在后文中使用節(jié)點(diǎn)值來(lái)表示節(jié)點(diǎn)的序號(hào)）以連續(xù)的數(shù)值表示，利用基于節(jié)點(diǎn)值的方式構(gòu)建圖，在不斷構(gòu)建的過(guò)程中記錄節(jié)點(diǎn)值比節(jié)點(diǎn)本身大的鄰居，以防止重復(fù)搜索子圖，在搜索子圖的過(guò)程中，不斷加入節(jié)點(diǎn)值比自身大的鄰居，并將新加入節(jié)點(diǎn)的符合規(guī)則的鄰居也作為待搜索節(jié)點(diǎn)，以防止遺漏子圖。ESU算法偽代碼[5]描述如下：

其中，輸入用節(jié)點(diǎn)集V和邊集E描述的圖G，和給定一個(gè)k用來(lái)描述motif的大小，算法將會(huì)輸出所有在G中motif大小為k的子圖。算法從V中的每一個(gè)節(jié)點(diǎn)v開(kāi)始，初始時(shí)確定VExtension集合，VExtension集合包含了所有節(jié)點(diǎn)值大于v的鄰居節(jié)點(diǎn)，偽代碼中用N來(lái)描述鄰居關(guān)系，VSubgraph集合初始化為{v}，是存儲(chǔ)子圖節(jié)點(diǎn)值的集合，然后調(diào)用ExtendSubgraph函數(shù)進(jìn)行子圖搜索和同構(gòu)比較;ExtendSubgraph函數(shù)中，其關(guān)鍵步驟在于對(duì)VExtension中的每一個(gè)節(jié)點(diǎn)w進(jìn)行如下操作：將w從VExtension集合中移出并加入VSubgraph集合，更新VExtension集合，新的VExtension集合由VSubgraph集合的所有節(jié)點(diǎn)值大于v的鄰居組成，偽代碼中用Nexcl來(lái)描述這種新的鄰居關(guān)系，每當(dāng)VSubgraph中的節(jié)點(diǎn)數(shù)達(dá)到了指定的k大小，就執(zhí)行網(wǎng)絡(luò)同構(gòu)比較。

ESU算法枚舉子圖的過(guò)程如圖1所描述，在圖1中，枚舉過(guò)程被描述為樹(shù)形結(jié)構(gòu)，這種樹(shù)被稱(chēng)為ESU樹(shù)[5]。ESU樹(shù)是建立ESU算法正確性的基礎(chǔ)，它能保證所枚舉的每個(gè)子圖不重復(fù)，其向下延伸的過(guò)程正好對(duì)應(yīng)了EnumerateSubgraph函數(shù)。其中，圖G是一個(gè)包含9個(gè)節(jié)點(diǎn)9條邊的拓?fù)渚W(wǎng)絡(luò)，其節(jié)點(diǎn)值依次從1到9。算法從Root開(kāi)始，枚舉圖G所有存在的子圖，圖1中最后輸出16個(gè)葉子節(jié)點(diǎn)，對(duì)應(yīng)為所有motif大小為3的子圖。

2.1.2 算法分析

ESU算法中最重要的兩個(gè)步驟就是子圖枚舉和子圖同構(gòu)比較。

子圖枚舉是ESU算法的核心步驟，通過(guò)記錄節(jié)點(diǎn)值比自身大的鄰居，以防止在搜索過(guò)程中得到重復(fù)的子圖，但是，基于節(jié)點(diǎn)值的枚舉過(guò)程，會(huì)導(dǎo)致各個(gè)計(jì)算量集中在某些特殊的節(jié)點(diǎn)，比如一些鄰居很多而且鄰居節(jié)點(diǎn)值都比自身大的那些節(jié)點(diǎn)（如圖1中1，2，3節(jié)點(diǎn)），這種問(wèn)題被稱(chēng)為節(jié)點(diǎn)值依賴(lài)問(wèn)題，這種問(wèn)題在串行過(guò)程中體現(xiàn)不出來(lái)，但是在并行過(guò)程中，一旦出現(xiàn)這種問(wèn)題，就會(huì)造成負(fù)載不均衡，大幅度影響并行的性能。

子圖同構(gòu)比較是整個(gè)串行ESU算法耗時(shí)時(shí)間最長(zhǎng)也是計(jì)算復(fù)雜度最高的部分[7]，在串行ESU算法中，子圖同構(gòu)使用了高效的nauty算法[12]，基于子圖枚舉的結(jié)果，對(duì)每個(gè)子圖進(jìn)行同構(gòu)比較;然而nauty算法僅僅是提高了兩個(gè)子圖之間同構(gòu)比較的計(jì)算效率，它并不能解決并行過(guò)程中存在的其他問(wèn)題，如負(fù)載不均衡問(wèn)題，而這些問(wèn)題正是提高并行效率的關(guān)鍵。

由于每一個(gè)枚舉的子圖都進(jìn)行同構(gòu)比較的計(jì)算，枚舉子圖的結(jié)果就直接決定了各個(gè)節(jié)點(diǎn)子圖同構(gòu)比較的計(jì)算量，所以本文對(duì)子圖枚舉的過(guò)程進(jìn)行并行處理，以均衡各個(gè)節(jié)點(diǎn)的計(jì)算量。

2.2 ESU算法并行化

由于子圖同構(gòu)比較是整個(gè)算法最耗時(shí)的部分，因此并行處理的關(guān)鍵就是均衡各個(gè)節(jié)點(diǎn)所需比較子圖同構(gòu)的次數(shù)。本文就均衡子圖同構(gòu)比較次數(shù)上，提出了結(jié)合優(yōu)化節(jié)點(diǎn)值和動(dòng)態(tài)規(guī)劃分配節(jié)點(diǎn)的改進(jìn)方法。

1）優(yōu)化節(jié)點(diǎn)值。由于節(jié)點(diǎn)值依賴(lài)問(wèn)題使得在枚舉子圖的過(guò)程中，部分枚舉的子圖集中在少數(shù)的節(jié)點(diǎn)上，直接導(dǎo)致各個(gè)節(jié)點(diǎn)所需比較子圖同構(gòu)的次數(shù)差異很大，對(duì)并行性能造成很大影響，因此在2.2.1節(jié)中，優(yōu)化了節(jié)點(diǎn)值，改善了節(jié)點(diǎn)值依賴(lài)問(wèn)題。

2）動(dòng)態(tài)規(guī)劃分配節(jié)點(diǎn)。由于各個(gè)節(jié)點(diǎn)出發(fā)枚舉的子圖數(shù)不可能完全一致，在分配任務(wù)時(shí)就可能造成各節(jié)點(diǎn)計(jì)算量不一致，導(dǎo)致負(fù)載不均衡，因此在2.2.2節(jié)中，提出了基于動(dòng)態(tài)規(guī)劃的節(jié)點(diǎn)分配策略，實(shí)現(xiàn)了負(fù)載均衡。

2.2.1 解決節(jié)點(diǎn)值依賴(lài)問(wèn)題

由于ESU算法是根據(jù)輸入網(wǎng)絡(luò)的節(jié)點(diǎn)值來(lái)記錄相應(yīng)符合條件的鄰居以防止重復(fù)搜索，造成了網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)之間的計(jì)算存在一定的依賴(lài)關(guān)系。對(duì)于網(wǎng)絡(luò)的不同輸入形式，比如同一拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，其節(jié)點(diǎn)賦予不同的節(jié)點(diǎn)值，會(huì)導(dǎo)致同一節(jié)點(diǎn)在不同節(jié)點(diǎn)值的情況下計(jì)算量差異很大，最典型的便是那些度很高的節(jié)點(diǎn)，如果其鄰居的節(jié)點(diǎn)值都大于它本身會(huì)使計(jì)算量全部集中在這些度很高的節(jié)點(diǎn)上，就會(huì)對(duì)并行的性能造成很大的影響，因此本文在網(wǎng)絡(luò)分發(fā)之前進(jìn)行節(jié)點(diǎn)值優(yōu)化，步驟如下：首先統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)值在邊集中出現(xiàn)的頻次，然后將節(jié)點(diǎn)值集合從大到小依次賦給出現(xiàn)頻次從大到小的節(jié)點(diǎn)，完成對(duì)節(jié)點(diǎn)值的優(yōu)化過(guò)程。具體如圖2所示。

對(duì)于圖2中兩個(gè)同一拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，網(wǎng)絡(luò)A中那些度很大的節(jié)點(diǎn)的節(jié)點(diǎn)值都很小，網(wǎng)絡(luò)B那些度很大的節(jié)點(diǎn)的節(jié)點(diǎn)值都很大，兩種網(wǎng)絡(luò)分別調(diào)用ESU算法進(jìn)行計(jì)算，得出各個(gè)節(jié)點(diǎn)出發(fā)所需計(jì)算比較同構(gòu)子圖數(shù)如表1所示。

結(jié)合分析表1中的數(shù)據(jù)和圖1的拓?fù)浣Y(jié)構(gòu)可知，當(dāng)節(jié)點(diǎn)度的大小與節(jié)點(diǎn)值的大小成正比時(shí)，各個(gè)節(jié)點(diǎn)出發(fā)的計(jì)算量差異相對(duì)較小，也就是說(shuō)節(jié)點(diǎn)值優(yōu)化使得各個(gè)節(jié)點(diǎn)的計(jì)算量相對(duì)均衡。

2.2.2 網(wǎng)絡(luò)節(jié)點(diǎn)分配過(guò)程

由前面的分析可知，對(duì)ESU算法進(jìn)行并行化處理的關(guān)鍵在于將搜索入口節(jié)點(diǎn)分發(fā)給各個(gè)進(jìn)程以實(shí)現(xiàn)并行計(jì)算，而對(duì)ESU算法的并行化過(guò)程存在兩個(gè)很明顯的特點(diǎn)：

1）每個(gè)搜索入口頂點(diǎn)進(jìn)行深度搜索時(shí)所需要的圖的區(qū)域是未知的，因此每個(gè)搜索入口都需要對(duì)整個(gè)圖的區(qū)域進(jìn)行搜索，無(wú)法對(duì)圖進(jìn)行區(qū)域分發(fā);

2）每個(gè)搜索入口頂點(diǎn)進(jìn)行深度搜索時(shí)所得到的子圖數(shù)是未知的，那么在將所有的子圖進(jìn)行同構(gòu)比較時(shí)，所需的時(shí)間也是未知，所有節(jié)點(diǎn)所花費(fèi)的時(shí)間不一，對(duì)并行性能會(huì)造成很大的影響。

對(duì)于特點(diǎn)1）可知，需要將整個(gè)圖分發(fā)給所有進(jìn)程，每個(gè)進(jìn)程都存儲(chǔ)一個(gè)圖的內(nèi)存，雖然會(huì)占用一定的資源，但是一般的圖占用的內(nèi)存都很小，對(duì)于現(xiàn)代內(nèi)存大都大于10GB以上的計(jì)算機(jī)而言，這點(diǎn)內(nèi)存顯得微不足道。

對(duì)于特點(diǎn)2）可知，每個(gè)搜索入口節(jié)點(diǎn)所需的計(jì)算時(shí)間差異很大，對(duì)于并行算法而言，以頂點(diǎn)作為分發(fā)手段不是明智的選擇，需要考慮其他的負(fù)載平衡策略，當(dāng)仔細(xì)分析算法計(jì)算過(guò)程時(shí)間消耗分布時(shí)，發(fā)現(xiàn)與ESU算法中深度搜索得到的子圖數(shù)這個(gè)過(guò)程相比，將所得到的每個(gè)子圖進(jìn)行同構(gòu)比較的時(shí)間要遠(yuǎn)遠(yuǎn)大于搜索的過(guò)程，于是，本文在原有的算法上增加了一步：先從每個(gè)搜索入口節(jié)點(diǎn)出發(fā)，深度搜索得到每個(gè)節(jié)點(diǎn)所需同構(gòu)比較的子圖數(shù)，接著不進(jìn)行同構(gòu)比較，而是依據(jù)各節(jié)點(diǎn)統(tǒng)計(jì)的子圖數(shù)對(duì)所有節(jié)點(diǎn)進(jìn)行排序，同時(shí)使用動(dòng)態(tài)規(guī)劃將頂點(diǎn)分配到各個(gè)進(jìn)程，使得進(jìn)程子圖數(shù)總和之間的方差最小。具體步驟描述如下。

1）使用ESU算法的子圖發(fā)現(xiàn)策略統(tǒng)計(jì)各節(jié)點(diǎn)子圖數(shù);

2）依據(jù)子圖數(shù)將節(jié)點(diǎn)進(jìn)行降序排序;

3）確定節(jié)點(diǎn)與進(jìn)程號(hào)之間的關(guān)系：首先將所有子圖數(shù)求和得到SubgraphSum，將其除以進(jìn)程數(shù)n得到每個(gè)進(jìn)程所需比較同構(gòu)子圖數(shù)的上限AverageSum，確定每個(gè)進(jìn)程初始子圖數(shù)CurSum為0，不斷將已排序的節(jié)點(diǎn)移出并逐個(gè)賦給不同進(jìn)程，并更新CurSum，對(duì)于每一個(gè)進(jìn)程，如果CurSum>AverageSum，則不加入這個(gè)節(jié)點(diǎn)，并嘗試將節(jié)點(diǎn)加入下一個(gè)進(jìn)程。

2.2.3 ESU算法并行框架

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

該程序運(yùn)行在上海大學(xué)高性能計(jì)算集群自強(qiáng)4000平臺(tái)，實(shí)驗(yàn)使用2臺(tái)計(jì)算節(jié)點(diǎn)，每個(gè)計(jì)算節(jié)點(diǎn)使用2顆Intel E5-2690 CPU（2.9GHz/8-core），內(nèi)存大小為64GB，集群節(jié)點(diǎn)間使用標(biāo)準(zhǔn)的Clos二層Infiniband網(wǎng)絡(luò)架構(gòu)。實(shí)驗(yàn)運(yùn)行操作系統(tǒng)為CentOS 6.3，編程語(yǔ)言為C++，MPI庫(kù)版本為IntelMPI。

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)同時(shí)使用了模擬數(shù)據(jù)和真實(shí)生物網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行性能分析，其中模擬數(shù)據(jù)使用NetworkX[13]的Python包模擬了三類(lèi)不同的網(wǎng)絡(luò)模型，分別是無(wú)標(biāo)度網(wǎng)絡(luò)模型[14]、小世界網(wǎng)絡(luò)模型[15]和規(guī)則網(wǎng)絡(luò)模型[16]，每類(lèi)網(wǎng)絡(luò)模型隨機(jī)地改變邊數(shù)和節(jié)點(diǎn)數(shù)，產(chǎn)生具有不同平均節(jié)點(diǎn)度的網(wǎng)絡(luò)，以探討在不同的平均節(jié)點(diǎn)度下并行ESU算法的性能。實(shí)驗(yàn)中使用固定的4000個(gè)節(jié)點(diǎn)，同時(shí)變化邊的條數(shù)，分別為20000、40000和60000條邊，來(lái)產(chǎn)生不同的節(jié)點(diǎn)平均度，分別是5、10和15，每種平均節(jié)點(diǎn)度模型均生成10個(gè)網(wǎng)絡(luò);真實(shí)生物網(wǎng)絡(luò)則選取了酵母菌代謝網(wǎng)絡(luò)、酵母菌蛋白質(zhì)網(wǎng)絡(luò)和人類(lèi)蛋白質(zhì)網(wǎng)絡(luò)三個(gè)生物網(wǎng)絡(luò)數(shù)據(jù)集，其節(jié)點(diǎn)數(shù)和邊數(shù)如表2所示，其中：酵母菌的蛋白質(zhì)網(wǎng)絡(luò)和代謝網(wǎng)絡(luò)數(shù)據(jù)集來(lái)源于Uri Alon實(shí)驗(yàn)室[2]，人類(lèi)蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)來(lái)源于STRING（Search Tool for Recurring Instances of Neighbouring Genes）在線(xiàn)數(shù)據(jù)庫(kù)[17]。

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 優(yōu)化節(jié)點(diǎn)值依賴(lài)的結(jié)果

為驗(yàn)證有優(yōu)化節(jié)點(diǎn)值策略和無(wú)優(yōu)化節(jié)點(diǎn)值策略對(duì)網(wǎng)絡(luò)并行性能的影響，本文對(duì)前文提到的3種模擬網(wǎng)絡(luò)進(jìn)行測(cè)試，每種模擬網(wǎng)絡(luò)都在不同的motif大小以及不同的平均節(jié)點(diǎn)度下進(jìn)行測(cè)試，各種條件下的測(cè)試結(jié)果都很相似，因此，本文選取其中一種測(cè)試條件下的測(cè)試結(jié)果進(jìn)行描述，選取的條件為節(jié)點(diǎn)數(shù)為4000、邊數(shù)為20000、motif大小為4，測(cè)試結(jié)果如圖3所示。

從圖3中可以看出，使用優(yōu)化節(jié)點(diǎn)值策略與否對(duì)無(wú)標(biāo)度網(wǎng)絡(luò)模型的并行性能影響很大，而對(duì)小世界網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)的并行性能影響很小。這是由于小世界網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)的演化規(guī)則與節(jié)點(diǎn)演化的先后順序無(wú)關(guān)。小世界網(wǎng)絡(luò)中那些度很大的節(jié)點(diǎn)的節(jié)點(diǎn)值具有隨機(jī)性，使用優(yōu)化節(jié)點(diǎn)值策略對(duì)并行性能影響不大。規(guī)則網(wǎng)絡(luò)中，各節(jié)點(diǎn)的度一致，其并行性能與使用優(yōu)化節(jié)點(diǎn)值策略與否無(wú)關(guān)。無(wú)標(biāo)度網(wǎng)絡(luò)的演化模型恰好是一種節(jié)點(diǎn)值依賴(lài)問(wèn)題的極端情況，最先演化的那些點(diǎn)恰好是度最大且節(jié)點(diǎn)值最小的點(diǎn)，而計(jì)算量正是集中在這些最先演化的點(diǎn)上，導(dǎo)致并行性能很差。使用優(yōu)化節(jié)點(diǎn)值策略，對(duì)那些最度此句不通順很大且節(jié)點(diǎn)值很小的點(diǎn)的節(jié)點(diǎn)值重新賦值，使各個(gè)節(jié)點(diǎn)所枚舉子圖的數(shù)量差異相對(duì)較小，從而提高并行性能。在進(jìn)程數(shù)達(dá)到32時(shí)，未使用優(yōu)化節(jié)點(diǎn)值策略的加速比為13.5，而使用優(yōu)化節(jié)點(diǎn)值依賴(lài)策略的加速比為29.7?？梢?jiàn)對(duì)節(jié)點(diǎn)值之間的依賴(lài)關(guān)系進(jìn)行優(yōu)化是非常有必要的。