孫佳敏 朱嘉富 楊伏長 謝江

摘 要：馬爾可夫聚類算法（MCL）是在大規(guī)模生物網(wǎng)絡(luò)中尋找模塊的一個有效方法，能夠挖掘網(wǎng)絡(luò)結(jié)構(gòu)和功能影響力較大的模塊。算法涉及到大規(guī)模矩陣計算，因此復雜度可達立方階次。針對復雜度高的問題，提出了基于消息傳遞接口（MPI）的并行化馬爾可夫聚類算法以提高算法的計算性能。首先，生物網(wǎng)絡(luò)轉(zhuǎn)化成鄰接矩陣;然后，根據(jù)算法的特性，按照矩陣的規(guī)模判斷并重新生成新矩陣以處理非平方倍數(shù)矩陣的計算;其次，并行計算通過按塊分配的方式能夠有效地實現(xiàn)任意規(guī)模矩陣的運算;最后，循環(huán)并行計算直至收斂，得到網(wǎng)絡(luò)聚類結(jié)果。通過模擬網(wǎng)絡(luò)和真實生物網(wǎng)絡(luò)數(shù)據(jù)集的實驗結(jié)果表明，與全塊集體式通信（FCC）并行方法相比，平均并行效率提升了10個百分點以上，因此可以將該優(yōu)化算法應(yīng)用在不同類型的大規(guī)模生物網(wǎng)絡(luò)中。

關(guān)鍵詞：消息傳遞接口;并行化;馬爾可夫聚類;Cannon算法;大規(guī)模生物網(wǎng)絡(luò)

中圖分類號： TP301.6

文獻標志碼：A

Abstract： Markov Clustering Algorithm （MCL） is an effective method to find modules in large-scale biological networks. It can mine modules that have significant influence on network structure and function. The algorithm involves large-scale matrix calculations， so its complexity can reach cubic orders. For the problem of high complexity， a parallel algorithm of Markov clustering based on Message Passing Interface （MPI） was proposed to improve computational performance of algorithm. Firstly， a biological network was transformed into an adjacency matrix. Secondly， according to the characteristics of the algorithm， the matrix size was judged and a new matrix was regenerated to handle the calculation of non-square multiple matrix. Thirdly， the algorithm was calculated in parallel by means of block allocation， which could effectively implement the operation of matrix of any size. Finally， the loop was parallelized until the matrix was converged to obtain network clustering results. The experimental results on simulated network and real biological network datasets show that compared with Full-block Collective Communication （FCC） parallel method， the average parallel efficiency is improved by more than 10 percentage points， so the optimization algorithm can be applied in different types of large-scale biological networks.

Key words： Message Passing Interface （MPI）; parallelization; Markov clustering; Cannon algorithm; large-scale biological network

0 引言

生物網(wǎng)絡(luò)一般具有小世界和無標度的特性[1]。小世界網(wǎng)絡(luò)一般具有較短的平均路徑[2]、較大的聚類系數(shù)[3];而無標度網(wǎng)絡(luò)一般是指少數(shù)節(jié)點連接了大量的邊，多數(shù)節(jié)點連接的邊較少[4]。這些特性說明了在生物網(wǎng)絡(luò)中只有少數(shù)節(jié)點在網(wǎng)絡(luò)中能夠起到關(guān)鍵的作用，而這些關(guān)鍵節(jié)點[5]在維持正常生理功能、疾病發(fā)生及其預(yù)防等生物過程中起著重大作用。事實上，本文注重關(guān)鍵節(jié)點的同時，更加關(guān)注大規(guī)模生物網(wǎng)絡(luò)中具有關(guān)鍵節(jié)點的關(guān)系緊密模塊。通過聚類算法可以分解網(wǎng)絡(luò)，找尋對網(wǎng)絡(luò)結(jié)構(gòu)和功能影響力較大的模塊，獲取到更加全面、準確的模塊信息。

因此，如何通過聚類算法找出具有關(guān)鍵節(jié)點的關(guān)系緊密模塊是問題的關(guān)鍵。

較為典型的生物網(wǎng)絡(luò)聚類方法有基于節(jié)點密度和層次聚類的算法，例如分子復合體檢測算法[6]和Girvan-Newman（GN）算法[7]。除了這兩類以外，也出現(xiàn)了如支持向量聚類（Support Vector Clustering， SVC）[8]、馬爾可夫聚類算法（Markov Clustering Algorithm， MCL）[9]等。

其中，馬爾可夫聚類算法常被應(yīng)用于生物信息學領(lǐng)域[10]，是一種簡易有效、適應(yīng)性強、可拓展的聚類算法[11]。

與其他已有的一些聚類算法相比，如基于節(jié)點密度的分子復合體檢測算法會損失大量聯(lián)系稀疏的節(jié)點，不能保證檢測到的所有模塊都有意義，會影響模塊功能和預(yù)測的準確性;基于層次聚類的GN算法耗時較長，僅限于中等規(guī)模的復雜網(wǎng)絡(luò)研究;馬爾可夫聚類算法對于網(wǎng)絡(luò)具有非常好的穩(wěn)定性，抗噪聲能力強[12]，能夠較為快速準確地識別網(wǎng)絡(luò)模塊，因此，對于在相互作用網(wǎng)絡(luò)中提取模塊方面，具有很大的優(yōu)勢。

生物數(shù)據(jù)量大規(guī)模增長給聚類算法帶來了巨大的挑戰(zhàn)。隨著數(shù)據(jù)集規(guī)模的擴大，聚類問題需要更大的內(nèi)存和更長的運行時間[13]。在馬爾可夫聚類算法中，Expansion和Inflation是兩個主要操作[11]，一般以矩陣的形式進行計算，計算機在這兩個主要操作中需要消耗大量的內(nèi)存存儲矩陣[14]，同時需要消耗大量的時間，因此，本文提出馬爾可夫聚類并行算法解決大規(guī)模生物網(wǎng)絡(luò)聚類問題，提高運行速度，提高計算效率。

1 馬爾可夫聚類算法主要思想

馬爾可夫聚類算法的主要思想是模擬圖中的隨機游走（Random Walk）的過程。位于同一簇的點，內(nèi)部聯(lián)系緊密，而和外部聯(lián)系較少，即任意選一點出發(fā)，它的一階鄰居節(jié)點和這點在同一簇的可能性遠大于離開當前簇到達新簇的可能性。

圖1展示了馬爾可夫鏈（Markov Chain）[15]實現(xiàn)隨機游走（random walk）過程。

圖1中的網(wǎng)絡(luò)可以分成兩個子圖，即兩簇族V（1，2，3）和V（4，5，6，7），每一簇族全連接各個節(jié)點。在這兩個簇族中，僅存在一條邊E（3，5）。

假設(shè)每一條邊都是一樣的。如果從點1出發(fā)，到達點2的概率是50%，到達點3的概率是50%，到達點4、5、6和7的概率為0。如果從點2出發(fā)，到達點1、3的概率是50%，到達其余點的概率均為0。如果從點3出發(fā)，到達點1、2、5的概率均為33.33%，到達其余點的概率均為0。

通過計算可知每一個點到達其他點的概率，如下所示，得到相應(yīng)的概率矩陣A，矩陣中非零數(shù)取兩位有效數(shù)字：

馬爾可夫鏈描述了一種狀態(tài)序列，其每個狀態(tài)值取決于前面的有限個狀態(tài)。馬爾可夫鏈是指具有馬爾可夫性質(zhì)的隨機變量的數(shù)列。這些變量的范圍，即它們所有可能取值的集合，被稱為“狀態(tài)空間”，而Xn的值則是在n的狀態(tài)，如果Xn+1對于過去狀態(tài)的條件概率分布滿足式（1）：

則稱其是一條馬爾可夫鏈。

馬爾可夫鏈模擬馬爾可夫聚類算法中的隨機游走過程，能夠得到相應(yīng)概率矩陣。馬爾可夫聚類算法經(jīng)歷多次隨機游走過程，可較大概率地發(fā)現(xiàn)簇群，最終得到聚類結(jié)果。

2 馬爾可夫聚類算法的實現(xiàn)

馬爾可夫聚類算法屬于圖聚類算法，可有效解決圖形分類問題。具體實現(xiàn)步驟（主要步驟如圖2圖形與文字描述重復，是否可以刪除圖2？請明確?；貜停捍饛投簣D2可以刪除。）如下所示：

第1步 通過生物網(wǎng)絡(luò)建立鄰接矩陣。生物網(wǎng)絡(luò)可以用圖的方式表示，先轉(zhuǎn)為鄰接矩陣。奇偶冪次可能會導致結(jié)果無法收斂，本文通過鄰接矩陣添加自環(huán)來消除這個影響，得到了一個添加自環(huán)的鄰接矩陣A。

第2步 通過鄰接矩陣A標準化得到概率矩陣A*。具體計算如式（2）所示：

舉例說明：

圖G轉(zhuǎn)為添加自環(huán)的鄰接矩陣A，經(jīng)過式（2）計算可得概率矩陣A*：

第3步 Expansion操作。Expansion操作每次對矩陣進行e次冪方。一般e值取2。式（3）表示對矩陣A*Expansion操作后得到矩陣B：

第4步 Inflation操作。Inflation操作每次對矩陣B內(nèi)的每一個值，即矩陣Brij進行r次冪方，

然后將求出結(jié)果除以所在列中的k個元素的r次冪方的和，即ΓrB，其中m為參數(shù)經(jīng)驗值，一般與r相等。

主要作用是將概率矩陣中的每一個值進行r次冪次擴大化，使得緊密的點更緊密，松散的點更松散，一般r值取2。如式（4）所示得到矩陣C：

（4）前面的問題說得很清晰，但又出現(xiàn)新問題了，變量k是何意？在求和公式中沒有出現(xiàn)k，k的出現(xiàn)，感覺突兀，請作調(diào)整。切記：將問題回復清晰一些，不要再扯出其他問題，越改越復雜了。請在正文中說明Γr的說明

第5步 標準化Expansion和Inflation操作后的矩陣得到矩陣C*。

第6步 判斷第5步得到的矩陣是否與Expansion操作前的矩陣收斂至近似相等，即矩陣中任意同一位置元素值相差小于0.01。如果兩矩陣不收斂至近似相等，循環(huán)第3、4、5步;如果兩矩陣收斂至近似相等，則輸出聚類結(jié)果。最終，結(jié)果矩陣變成聚類的聚簇。

以上6步是算法的完整流程，其中，馬爾可夫聚類算法主要耗時在Expansion和Inflation操作上[11]。這兩個操作中，Expansion耗時相對更多，因此，本研究需要將耗時較長的兩大操作并行化。

3 馬爾可夫聚類算法并行化實現(xiàn)及其優(yōu)化

使用MPI常用的并行化方法有主從式（Master-Slaves， MS）和集體通信式（Collective Communication， CC）兩種并行方式。根據(jù)文獻[16]可知，在Expansion過程中，同一數(shù)據(jù)集使用集體通信式無論從時間耗費、加速比還是效率上均比主從式并行方式較好，因此，整體算法選擇集體通信式完成并行化。

3.1 矩陣Expansion操作并行化

Expansion操作的計算過程主要是矩陣的e冪次方，以e值取2為例說明其并行化過程。

當e=2時，Expansion操作相當于兩個矩陣相乘的操作。矩陣相乘并行化分配方式多種，常見的分配方法有按行、按列和按塊劃分[17]等。與按行或按列的分配方法相比，按塊劃分具有更好的并行效果。針對馬爾可夫聚類算法來說，計算的主體是n階方陣，按塊分配最多可以使用n2個處理器并行計算;而如果使用按行或者按列分配的方法最多只能使用n個處理器并行加速，因此，按塊分配能夠更充分利用處理器。

按塊分配的方法需要并行核數(shù)為平方數(shù)，即分成的小塊均為規(guī)模一致的小方陣。在并行核數(shù)足夠時，設(shè)置并行核數(shù)為平方數(shù)是完全易行的。

在此，本文選用按塊分配中的Cannon算法[18]并行化Expansion操作。Cannon算法是一種存儲有效的算法，有目的地在各行列間循環(huán)移位，從而降低處理器的總存儲需求。在多CPU處理器并行計算上，可以減少通信時延，提高計算速度，提高計算效率。

然而，這里的按塊分配方法要求進程數(shù)必須是平方數(shù)且矩陣的階數(shù)必須是平方數(shù)的倍數(shù)。在實際的生物網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的節(jié)點規(guī)模往往不是平方數(shù)的倍數(shù)，因此，本文拓展Cannon算法，基于此提出了馬爾可夫聚類并行化算法，可并行計算任意規(guī)模的網(wǎng)絡(luò)，如圖3所示，其中虛線框中為并行的主要過程，詳細過程如圖4所示。

本文算法中出現(xiàn)的矩陣特點是所有矩陣均為n階方陣。由矩陣相乘的性質(zhì)可知，兩n階方陣相乘得到的結(jié)果矩陣也必然是n階方陣。

假設(shè)并行核數(shù)為p，初始方陣階數(shù)為y，并行計算中，實際使用的方陣階數(shù)是n，即使用p個處理器并行化n階方陣相乘。并行化馬爾可夫聚類算法的主要操作流程如下。

第1步 判斷y是否是平方數(shù)的倍數(shù)。

第2步 如果y是平方數(shù)的倍數(shù)，令n=y;如果y不是平方數(shù)的倍數(shù)，令n=y+p-（y%p），即將大于y的最小并行核數(shù)倍數(shù)賦值給n。

第3步 初始化n階方陣為零階矩陣。接下來主要是圖3虛線框中的主要并行過程，如圖4所示。

第4步 為了更好地說明并區(qū)分，在這里用B=A，表示兩矩陣相乘C=A×B，即C=A2。將矩陣A和矩陣B分成p個方塊Ai， j和Bi， j（0≤i， j≤p-1），令x=p-1，如圖4（a）和（b）所示，每塊大小為（n/p）×（n/p），將每塊分配給p×p個處理器（P0，0，P0，1，…，Pp-1，p-1）。處理器Pi， j存儲分塊矩陣Ai， j和Bi， j，如圖4（c）所示，并且計算塊Ci， j，算法執(zhí)行第5～7步。

第5步 各行列間的循環(huán)移位，即圖4（d），將塊Ai， j（0≤i， j

第6步 Pi， j執(zhí)行乘加運算，循環(huán)移位的過程可參照圖4（d）;

然后，將塊Ai， j（0≤i， j

將塊Bi， j（0≤i， j

第7步 重復第6步，在Pi， j中執(zhí)行p次乘加運算和p次塊Ai， j和Bi， j的循環(huán)單位移位。

第8步 收集分塊計算結(jié)果，每一個元素獨自進行r次冪方運算，即并行Inflation操作。

3.2 矩陣Inflation操作并行化

如圖3所示，Inflation操作緊跟Expansion操作，是在分塊收集結(jié)果時一并進行。

Inflation操作主要是指矩陣中的每一個元素獨自r次進行冪方運算，默認r值為2，且矩陣中每一個元素是獨立的，各元素之間相互獨立。Expansion操作后，按照分塊收集矩陣中的每一個獨立元素，與此同時，分塊并行Inflation操作。

4 實驗與分析

4.1 實驗環(huán)境

算法使用的實驗平臺是上海大學高性能計算集群自強4000。實驗使用3個計算節(jié)點，每個節(jié)點的CPU個數(shù)為2，每個CPU的核數(shù)為8，CPU型號為Intel Xeon CPU E5645 @2.40GHz。實驗的操作系統(tǒng)版本為CentOS 6.3，編程語言為C++，MPI庫的版本為MPICH2。

4.2 實驗數(shù)據(jù)

4.2.1 模擬實驗數(shù)據(jù)

實驗同時使用了模擬數(shù)據(jù)和真實生物網(wǎng)絡(luò)數(shù)據(jù)進行性能分析，其中模擬數(shù)據(jù)使用NetworkX[19]的Python包模擬了三類不同的網(wǎng)絡(luò)模型，分別是無標度網(wǎng)絡(luò)模型[20]、小世界網(wǎng)絡(luò)模型[5]和隨機網(wǎng)絡(luò)模型[21]。

為了確保實驗結(jié)果的準確性，下述模擬實驗使用表1中的10類模擬網(wǎng)絡(luò)數(shù)據(jù)集進行實驗，每類網(wǎng)絡(luò)模型改變節(jié)點數(shù)和邊數(shù)，隨機產(chǎn)生10個不同的網(wǎng)絡(luò)。

4.2.2 真實網(wǎng)絡(luò)實驗數(shù)據(jù)

為了確保實驗結(jié)果的準確性，下述模擬實驗使用表2中的3種真實網(wǎng)絡(luò)數(shù)據(jù)集進行實驗。

真實生物網(wǎng)絡(luò)選取了三個生物網(wǎng)絡(luò)數(shù)據(jù)集，即含有2362個節(jié)點、6646條邊的酵母菌蛋白質(zhì)網(wǎng)絡(luò)，含有4677個節(jié)點、16213條邊和16064個節(jié)點159989條邊的兩個人類蛋白質(zhì)網(wǎng)絡(luò)，其中酵母菌的蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集來源于Uri Alon實驗室[22]，人類蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)來源于STRING在線數(shù)據(jù)庫[23]。

4.3 實驗結(jié)果與分析

4.3.1 模擬網(wǎng)絡(luò)實驗設(shè)計

馬爾可夫聚類并行化算法在大規(guī)模生物網(wǎng)絡(luò)的應(yīng)用中可能受到的影響因素有以下三點：生物網(wǎng)絡(luò)模型的類別、網(wǎng)絡(luò)中節(jié)點的平均度（即網(wǎng)絡(luò)稠密程度）和網(wǎng)絡(luò)中節(jié)點數(shù)量（即網(wǎng)絡(luò)規(guī)模），因此，實驗分別以三個因素設(shè)計模擬實驗，探討算法在不同網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)類型上的性能。

根據(jù)分塊分配的特點，選定的并行核數(shù)為平方數(shù)，即4、9、16、25、36核進行并行實驗。

4.3.2 模擬網(wǎng)絡(luò)實驗結(jié)果與分析

1）不同的生物網(wǎng)絡(luò)模型的類別。

不同的生物網(wǎng)絡(luò)模型具有不同的特征，如平均路徑長度、聚集系數(shù)、度及其分布等。為了驗證非平方數(shù)倍數(shù)規(guī)模網(wǎng)絡(luò)在并行算法中的可行性，選取表1中編號為1、2、3，節(jié)點數(shù)為2018的三個不同網(wǎng)絡(luò)模型作為數(shù)據(jù)集，其中，網(wǎng)絡(luò)節(jié)點數(shù)均不是平方數(shù)倍數(shù)?；诖藬?shù)據(jù)集，在不同并行核數(shù)程序時間消耗及加速比如圖5所示。

圖5（a）為2018節(jié)點數(shù)的三種網(wǎng)絡(luò)模型耗時實驗結(jié)果。橫向觀察，隨著并行核數(shù)增加，程序運行時間逐漸減少，起到較好的并行作用?？v向觀察，在節(jié)點數(shù)和并行核數(shù)相同情況下，從所耗時間上相比，三種網(wǎng)絡(luò)模型所耗時間相差無幾。

圖5（b）為2018節(jié)點數(shù)的三種網(wǎng)絡(luò)模型的加速比實驗結(jié)果，橫向觀察，在16核前幾乎呈線性加速比，隨著并行核數(shù)的增加，加速比逐漸上升?？v向觀察，三種網(wǎng)絡(luò)模型的加速比折線曲線幾乎重合，加速比數(shù)值幾乎相同，說明優(yōu)化后的馬爾可夫聚類并行化算法應(yīng)用范圍廣，在不同模型中均有較好的作用。

2）不同的網(wǎng)絡(luò)中節(jié)點的平均度。

網(wǎng)絡(luò)中節(jié)點的平均度體現(xiàn)了網(wǎng)絡(luò)的稠密程度，而網(wǎng)絡(luò)稠密程序很大程度上可能會影響算法的計算量，因此，選取表1中編號為4、5、6、7的四個節(jié)點數(shù)為4500的網(wǎng)絡(luò)作為數(shù)據(jù)集，它們的節(jié)點平均度分別約為1、30、70、110?；诖藬?shù)據(jù)集，在不同并行核數(shù)程序時間消耗及加速比如圖6所示。

圖6（a）為4500節(jié)點數(shù)的不同平均節(jié)點度的網(wǎng)絡(luò)耗時實驗結(jié)果。橫向觀察，隨著并行核數(shù)增加，程序運行時間逐漸減少，起到較好的并行作用。縱向觀察，在節(jié)點數(shù)和并行核數(shù)相同情況下，從所耗時間上相比，不同平均節(jié)點度網(wǎng)絡(luò)耗時相近，說明馬爾可夫聚類算法在稠密程度不同的矩陣上均有良好的作用。

圖6（b）為4500節(jié)點數(shù)的不同平均節(jié)點度的網(wǎng)絡(luò)加速比實驗結(jié)果，橫向觀察，隨著并行核數(shù)的增加，加速比逐漸上升。縱向觀察，兩種網(wǎng)絡(luò)模型的加速比折線曲線幾乎重合，加速比數(shù)值幾乎相同，說明優(yōu)化后的馬爾可夫聚類并行化算法在稠密度不同的矩陣中均有很好的應(yīng)用效果。

3）不同的網(wǎng)絡(luò)中的節(jié)點數(shù)。

網(wǎng)絡(luò)中的節(jié)點數(shù)決定網(wǎng)絡(luò)的規(guī)模。本節(jié)選取表1中編號為1、4、8，節(jié)點數(shù)分別為2018、4500、15000的三種網(wǎng)絡(luò)數(shù)據(jù)集?；诖藬?shù)據(jù)集，在不同并行核數(shù)程序時間消耗和加速比如圖7所示。

根據(jù)下面的這個描述，圖7（a）中的圖例是否錯了？是否應(yīng)該改為與圖7（b）一樣的圖例，即改為“2018節(jié)點，4500節(jié)點，15000節(jié)點”？請明確。

圖7（a）為不同節(jié)點數(shù)的網(wǎng)絡(luò)耗時的實驗結(jié)果。橫向觀察，隨著并行核數(shù)增加，程序運行時間逐漸減少，起到較好的并行作用?？v向觀察，在節(jié)點數(shù)和并行核數(shù)相同情況下，從所耗時間上相比，節(jié)點數(shù)越多，耗時越久;節(jié)點數(shù)成倍增加時，耗時成數(shù)倍增加。

圖7（b）為不同節(jié)點數(shù)的網(wǎng)絡(luò)加速比實驗結(jié)果。橫向觀察，隨著并行核數(shù)的增加，加速比逐漸上升。縱向觀察，并行核數(shù)小于16時，三種網(wǎng)絡(luò)的加速比折線曲線幾乎重合，加速比數(shù)值幾乎相同;在并行核數(shù)增大后，節(jié)點數(shù)量多的并行加速比更大。隨著節(jié)點數(shù)增加，網(wǎng)絡(luò)規(guī)模變大，并行加速比增長越快，說明網(wǎng)絡(luò)中的節(jié)點數(shù)量對并行的影響較大，馬爾可夫聚類算法在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集上有良好的效果。

通過上面三組模擬實驗分析結(jié)果可知，并行馬爾可夫聚類算法在不同模型類別、不同稠密度、不同規(guī)模的網(wǎng)絡(luò)中均有較好的效果。在網(wǎng)絡(luò)的規(guī)模不同時，規(guī)模越大，并行效果越佳。

4.3.3 真實網(wǎng)絡(luò)實驗結(jié)果與分析

在網(wǎng)絡(luò)規(guī)模量足夠時可以達到較高的效率，因此，為了驗證算法的可靠性和效率，本文采取三組真實網(wǎng)絡(luò)實驗數(shù)據(jù)驗證上述想法。

真實生物網(wǎng)絡(luò)選取了三個蛋白質(zhì)網(wǎng)絡(luò)，表3列出了三個網(wǎng)絡(luò)的消耗時間。其中：YPIN代表2362個節(jié)點的酵母菌蛋白質(zhì)網(wǎng)絡(luò)，PIN1和PIN2分別代表4677和16064個節(jié)點的兩個人類蛋白質(zhì)網(wǎng)絡(luò)。

圖8（a）為三個真實生物網(wǎng)絡(luò)耗時實驗結(jié)果。橫向觀察，隨著并行核數(shù)增加，程序運行時間逐漸減少，起到較好的并行作用。縱向觀察，在節(jié)點數(shù)和并行核數(shù)相同情況下，從所耗時間上相比，節(jié)點數(shù)越多，耗時越久。

圖8（b）為三個真實生物網(wǎng)絡(luò)加速比實驗結(jié)果。橫向觀察，隨著并行核數(shù)的增加，加速比逐漸上升，近似線性增長。在16064個節(jié)點并行核數(shù)為36時，加速比最高可達到27.4?？v向觀察，并行核數(shù)相同時，隨著節(jié)點增多，并行加速比更大。

文獻[16]中采取并比較了多種方法并行馬爾可夫聚類算法，其中，文中提出全塊集體式通信方法（Full-block Collective Communication， FCC）效率最好。數(shù)據(jù)集為5156節(jié)點、51050條邊網(wǎng)絡(luò)時，最高效率75%，最低約50%;數(shù)據(jù)集為23175個節(jié)點、137104條邊的網(wǎng)絡(luò)時最高效率近似85%，最低效率為45%。

圖8（c）為三個真實生物網(wǎng)絡(luò)效率實驗結(jié)果。橫向觀察，隨著并行核數(shù)的增加，效率逐步下降。在16064個節(jié)點，并行核數(shù)小于16時，加速效率可達到92%以上;并行核數(shù)為36時，加速比為27.4，效率可達到76%。縱向觀察，并行核數(shù)相同時，節(jié)點數(shù)量多的并行加速比更大。在真實網(wǎng)絡(luò)的結(jié)果說明在節(jié)點數(shù)足夠多，即網(wǎng)絡(luò)規(guī)模計算量足夠大時，該并行算法可以在大規(guī)模生物網(wǎng)絡(luò)上達到較好的并行效果。

本文在相同真實數(shù)據(jù)集上結(jié)果與文獻[16]相比，在并行核數(shù)相同時，加速效率提高了10個百分點以上，提出的并行馬爾可夫聚類算法有著更好的加速效率，說明該算法在大規(guī)模生物網(wǎng)絡(luò)中，應(yīng)用范圍大，實驗效果佳。

5 結(jié)語

本文提出了基于消息傳遞接口（MPI）的并行化馬爾可夫聚類算法，解決了原馬爾可夫聚類算法中Expansion操作耗時問題，可并行計算任意規(guī)模矩陣。實驗使用了模擬網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集：模擬網(wǎng)絡(luò)結(jié)果說明在不同模擬網(wǎng)絡(luò)模型、不同稠密度網(wǎng)絡(luò)集上均有良好的效果。在真實網(wǎng)絡(luò)結(jié)果中，與全塊集體式通信并行方法相比，平均效率提高了10個百分點以上。說明算法在生物網(wǎng)絡(luò)上具有較好的效果，能夠有效地解決大規(guī)模生物網(wǎng)絡(luò)尋找網(wǎng)絡(luò)模塊的問題。

參考文獻 （References）

[1] HOPKINS A L. Network pharmacology： the next paradigm in drug discovery[J]. Nature Chemical Biology， 2008， 4（11）： 682-690.

[2] 劉業(yè)政，周云龍.無尺度網(wǎng)絡(luò)平均路徑長度的估計[J].系統(tǒng)工程理論與實踐，2014，34（6）：1566-1571.（LIU Y Z， ZHOU Y L. Estimation for the average path length of scale-free networks[J]. Systems Engineering — Theory & Practice， 2014， 34（6）： 1566-1571.）

[3] WATTS D J，STROGATZ S H. Collective dynamics of ‘small-world networks[J]. Nature， 1998， 393（6684）： 440-442.

[4] 車宏安，顧基發(fā).無標度網(wǎng)絡(luò)及其系統(tǒng)科學意義[J].系統(tǒng)工程理論與實踐，2004，24（4）：11-16.（CHE H A， GU J F. Scale-free networks and their significance for systems science[J]. Systems Engineering — Theory & Practice， 2004， 24（4）： 11-16.）

[5] 黃海濱，楊路明，王建新，等.基于復合參數(shù)的蛋白質(zhì)網(wǎng)絡(luò)關(guān)鍵節(jié)點識別技術(shù)[J].自動化學報，2008，34（11）：1388-1395.（HUANG H B， YANG L M， WANG J X， et al. Identification technique of essential nodes in protein networks based on combined parameters[J]. Acta Automatica Sinica， 2008， 34（11）： 1388-1395.）

[6] BADER G D， HOGUE C W V. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics， 2003， 4（1）： 2-27.

[7] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

[8] BEBHUR A， HORN D， SIEGELMANN H T， et al. Support vector clustering[J]. Journal of Machine Learning Research， 2001， 2（2）： 125-137.

[9] VAN DONGEN S M. Graph clustering by flow simulation[D]. Utrecht： University of Utrecht， 2000.

[10] CHEN G， ZHAO J， COHEN T， et al. Using ontology fingerprints to disambiguate gene name entities in the biomedical literature [J]. Database the Journal of Biological Databases & Curation， 2015， 2015（13）：bav034.

[11] HE L， LU L， WANG Q. An optimal parallel implementation of Markov clustering based on the coordination of CPU and GPU[J]. Journal of Intelligent & Fuzzy Systems， 2017， 32（5）： 3609-3617.

[12] 王曉敏.基于蛋白質(zhì)相互作用網(wǎng)絡(luò)的功能模塊識別及功能預(yù)測研究[D].長沙：國防科學技術(shù)大學，2013.（WANG X M. The detection of functional modules and protein function prediction based on protein-protein interaction networks[D]. Changsha： National University of Defense Technology， 2013.）

[13] WANG M， ZHANG W， DING W， et al. Parallel clustering algorithm for large-scale biological data sets[J]. PLoS One， 2014， 9（4）： e91315.

[14] AZAD A， PAVLOPOULOS G A， OUZOUNIS C A， et al. HipMCL： a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks[J]. Nucleic Acids Research， 2018， 46（6）：1-11.

[15] GASPARINI M. Markov chain Monte Carlo in practice[J]. Technometrics， 1999， 39（3）：338-338.

[16] BUSTAMAM A， SEHGAL M S， WONG S， et al. Parallel Markov clustering for large-scale protein-protein interaction networks using MPI [EB/OL]. [2018-05-30]. https：//pdfs.semanticscholar.org/c62d/5b5abc12a3fe566fce668974436e7cdd273e.pdf.

[17] 蔣瀚洋.論Cannon算法在并行計算機上的運用研究[J].計算機光盤軟件與應(yīng)用，2012（20）：154-155.（JIANG H Y. Research on application of Cannon algorithm in parallel computer [J]. Computer CD Software and Applications， 2012（20）： 154-155.）

[18] 陳鵬，樊小超.幾種矩陣乘并行算法的對比分析[J].新疆師范大學學報（自然科學版），2012，31（3）：5-10.（CHEN P， FAN X C. Several kinds of parallel algorithm for matrix multiplication comparative analysis[J]. Journal of Xinjiang Normal University （Natural Sciences Edition）， 2012， 31（3）： 5-10.）

[19] HAGBERG A， SCHULT D， SWART P. Exploring network structure， dynamics， and function using NetworkX[R]. Los Alamos， NM： Los Alamos National Lab， 2008.

[20] BARABSI A， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）：509-512.

[21] KIM J， VU V. Generating random regular graphs[C]// Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing. New York： ACM， 2003：213-222.

[22] MILO R， SHEN-ORR S， ITZKOVITZ S， et al. Network motifs： simple building blocks of complex networks[J]. Science， 2002， 298（5594）： 824-827.

[23] SNEL B， LEHMANN G， BORK P， et al. STRING： a Web-server to retrieve and display the repeatedly occurring neighbourhood of a gene[J]. Nucleic Acids Research， 2000， 28（18）： 3442-3444.