大規(guī)模生物網(wǎng)絡(luò)馬爾可夫聚類的并行化算法

孫佳敏 朱嘉富 楊伏長 謝江

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

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

中圖分類號： TP301.6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

馬爾可夫聚類算法屬于圖聚類算法，可有效解決圖形分類問題。具體實(shí)現(xiàn)步驟（主要步驟如圖2圖形與文字描述重復(fù)，是否可以刪除圖2？請明確。回復(fù)：答復(fù)二：圖2可以刪除。）如下所示：

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

第2步 通過鄰接矩陣A標(biāo)準(zhǔn)化得到概率矩陣A*。具體計(jì)算如式（2）所示：

舉例說明：

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

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

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

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

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

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

第5步 標(biāo)準(zhǔn)化Expansion和Inflation操作后的矩陣得到矩陣C*。

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

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

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

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

3.1 矩陣Expansion操作并行化

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

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

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

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

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

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

假設(shè)并行核數(shù)為p，初始方陣階數(shù)為y，并行計(jì)算中，實(shí)際使用的方陣階數(shù)是n，即使用p個(gè)處理器并行化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個(gè)方塊Ai， j和Bi， j（0≤i， j≤p-1），令x=p-1，如圖4（a）和（b）所示，每塊大小為（n/p）×（n/p），將每塊分配給p×p個(gè)處理器（P0，0，P0，1，…，Pp-1，p-1）。處理器Pi， j存儲分塊矩陣Ai， j和Bi， j，如圖4（c）所示，并且計(jì)算塊Ci， j，算法執(zhí)行第5～7步。

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

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

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

將塊Bi， j（0≤i， j

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

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

3.2 矩陣Inflation操作并行化

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

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

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

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

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

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

4.2.1 模擬實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

4.3.1 模擬網(wǎng)絡(luò)實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn) （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ì)[J].系統(tǒng)工程理論與實(shí)踐，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ā).無標(biāo)度網(wǎng)絡(luò)及其系統(tǒng)科學(xué)意義[J].系統(tǒng)工程理論與實(shí)踐，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] 黃海濱，楊路明，王建新，等.基于復(fù)合參數(shù)的蛋白質(zhì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別技術(shù)[J].自動化學(xué)報(bào)，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].長沙：國防科學(xué)技術(shù)大學(xué)，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ì)算機(jī)上的運(yùn)用研究[J].計(jì)算機(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].新疆師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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.