1、第27卷第6期增刊2006年6月儀器儀表學(xué)報(bào)Chinese Journal of Scientific InstrumentJ une.2006復(fù)雜網(wǎng)絡(luò)中的完全子圖搜索算法研究3劉夫云1,21(桂林電子科技大學(xué)機(jī)電與交通工程系桂林5410042(浙江大學(xué)現(xiàn)代制造工程研究所杭州310027摘要現(xiàn)實(shí)生活中,許多實(shí)際網(wǎng)絡(luò)中通常包含由若干結(jié)點(diǎn)組成的完全子圖,一些實(shí)際網(wǎng)絡(luò)甚至是由一些完全子圖通過公共節(jié)點(diǎn)鏈接而成的,如何搜索這類網(wǎng)絡(luò)中的完全子圖,是一件很有意義的事情。提出了一種搜索這類特殊復(fù)雜網(wǎng)絡(luò)的完全子圖的算法,編制了實(shí)現(xiàn)算法的程序,將算法程序應(yīng)用于機(jī)械制造中的產(chǎn)品零部件關(guān)系網(wǎng)、中藥方劑網(wǎng)等實(shí)際的復(fù)雜網(wǎng)

2、絡(luò),取得了良好的效果。為深入研究這一類型的復(fù)雜網(wǎng)絡(luò)提供了有力的工具。關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)完全子圖搜索算法Algorithm for detecting complete sub 2graph in complex net w orkLiu Fuyun 1,21(Dept.of Elect ronic M achinery and T rans portation Engineering ,Guilin Universit y of Elect ronic Technology ,Guilin 541004,China 2(I nst.of Contem porary M anuf acturing

3、Eng.,Zhej iang Universit y ,Hangz hou 310027,China Abstract Many real networks always contain some complete sub 2graphs ,some networks are even composed of complete sub 2graphs t hrough t heir public nodes.It would be a very interested t hing to detect complete sub 2graphs of t hese networks.An algo

4、rithm for detecting complete sub 2graphs in complex networks was presented ,and t he algorit hm was realized t hrough programming.The algorit hm was used in part s relation network of product and Chinese traditional medicine network ,it works well in bot h networks.It will provide a useful tool for

5、researching complex network deeply.K ey w ords complex network complete sub 2graph detecting algorit hm3基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(603740571引言網(wǎng)絡(luò)是頂點(diǎn)以及邊的集合,網(wǎng)絡(luò)形式的系統(tǒng)在現(xiàn)實(shí)世界的各個(gè)領(lǐng)域隨處可見。近年來,隨著計(jì)算技術(shù)的發(fā)展,計(jì)算能力和存儲(chǔ)能力得到很大的提高,使得研究復(fù)雜網(wǎng)絡(luò)成為可能,因此,國際上興起了一股研究復(fù)雜網(wǎng)絡(luò)的熱潮,并取得了令人矚目的成果12。盡管如此,但我們還是可以說,到目前為止,所有這些研究涉及的僅是復(fù)雜網(wǎng)絡(luò)的皮毛,復(fù)雜網(wǎng)絡(luò)尚有許許多多未知的內(nèi)在

6、的規(guī)律有待我們進(jìn)行更深入的研究。尋找復(fù)雜網(wǎng)絡(luò)中的聚類(或社團(tuán)就是其中之一。近年來,對這一算法的研究引起了人們極大的興趣,國外相繼有人從事這一方面的研究并取得了一些研究成果326。遺憾的是迄今為止,尚沒有一種通用的能搜索所有復(fù)雜網(wǎng)絡(luò)的聚類的好算法。在紛繁復(fù)雜的各種類型的復(fù)雜網(wǎng)絡(luò)中,有一類很特殊的復(fù)雜網(wǎng)絡(luò),這類網(wǎng)絡(luò)是由一些完全子圖(某些文獻(xiàn)又稱“固定局域世界”7通過某些公共節(jié)點(diǎn)而組成的?，F(xiàn)實(shí)生活中這種特殊類型的網(wǎng)絡(luò)隨處可見。比較常見的這種類型的網(wǎng)絡(luò)有:機(jī)械制造業(yè)中的產(chǎn)品零部件關(guān)系網(wǎng)、科學(xué)家合作網(wǎng)、電影演員合作網(wǎng)、中藥方劑926儀器儀表學(xué)報(bào)第27卷網(wǎng)7等等。事實(shí)上,所有可用二部圖(或二分圖表達(dá)的網(wǎng)絡(luò)

7、類型都可以通過適當(dāng)?shù)霓D(zhuǎn)換而成為由完全子圖組成的網(wǎng)絡(luò)。在產(chǎn)品零部件關(guān)系網(wǎng)中,以零件作為節(jié)點(diǎn),若干零件構(gòu)成一個(gè)部件,在構(gòu)成部件的零件中兩兩連邊,從而構(gòu)成一個(gè)完全子圖,而不同的部件通過共有的零件構(gòu)成整個(gè)網(wǎng)絡(luò)。在科學(xué)家合作網(wǎng)中,以科學(xué)家為節(jié)點(diǎn),如果若干科學(xué)家合作寫了一篇論文(或合作一項(xiàng)科研項(xiàng)目,則在代表這些科學(xué)家的節(jié)點(diǎn)間兩兩連邊,構(gòu)成一完全子圖,不同的完全子圖通過共有的節(jié)點(diǎn)構(gòu)成整個(gè)網(wǎng)絡(luò)。在電影演員合作網(wǎng)中,以電影演員作為節(jié)點(diǎn),若干演員合演一部電影,則在代表這些演員的節(jié)點(diǎn)間兩兩連邊,構(gòu)成一完全子圖,不同的完全子圖間通過共有的節(jié)點(diǎn)構(gòu)成整個(gè)復(fù)雜網(wǎng)絡(luò)。中藥方劑網(wǎng)以每一味藥材作為節(jié)點(diǎn),若干味藥材構(gòu)成一方中藥,代

8、表這些藥材的節(jié)點(diǎn)間兩兩連邊,構(gòu)成一完全子圖,不同的完全子圖通過共有的節(jié)點(diǎn)構(gòu)成整個(gè)網(wǎng)絡(luò),部分中藥方劑構(gòu)成的網(wǎng)絡(luò)如圖1所示7。圖中共有20味藥材(圖中的20個(gè)節(jié)點(diǎn),搭配組成6方中藥方劑(圖中的6個(gè)完全子圖?，F(xiàn)實(shí)生活中與此類似的網(wǎng)絡(luò)還有許許多多,在此不一一列舉。 圖1部分中藥方劑組成的網(wǎng)絡(luò)示意圖2算法研究由上述可知,這些網(wǎng)絡(luò)具有相同的結(jié)構(gòu),都是由完全子圖通過公共節(jié)點(diǎn)連接而成網(wǎng)絡(luò)。研究發(fā)現(xiàn),上述網(wǎng)絡(luò)中的完全子圖的數(shù)目及每個(gè)節(jié)點(diǎn)歸屬于完全子圖的數(shù)目有著非常明顯的物理意義。例如,產(chǎn)品零部件關(guān)系網(wǎng)中,一個(gè)完全子圖代表一個(gè)部件,每個(gè)完全子圖包含的節(jié)點(diǎn)代表這個(gè)部件由哪些零件組成,節(jié)點(diǎn)歸屬于多少個(gè)完全子圖則說明這

9、個(gè)零件可用在哪幾個(gè)部件中。在科學(xué)家合作網(wǎng)中,完全子圖代表合作的成果(論文或科研項(xiàng)目,完全子圖包含的節(jié)點(diǎn)數(shù)說明這項(xiàng)合作成果由哪些科學(xué)家共同完成,每個(gè)節(jié)點(diǎn)歸屬于完全子圖的數(shù)目則說明某個(gè)科學(xué)家參與合作項(xiàng)目的數(shù)量。電影演員合作網(wǎng)中,一個(gè)完全子圖代表一部電影,完全子圖包含的節(jié)點(diǎn)數(shù)表示這部電影由哪些演員合作演出,每個(gè)節(jié)點(diǎn)歸屬于的完全子圖的數(shù)目表示某個(gè)演員演了幾部電影。在中藥方劑網(wǎng)中,完全子圖代表一方中藥,完全子圖包含的節(jié)點(diǎn)數(shù)代表該方中藥由哪幾味藥材組成,每個(gè)節(jié)點(diǎn)屬于的完全子圖數(shù)目表示該味藥材可用于哪些中藥方劑中7。在研究上述這類特殊類型的網(wǎng)絡(luò)中經(jīng)常遇到的一個(gè)問題就是如何在整個(gè)網(wǎng)絡(luò)中正確地分離出完全子圖,計(jì)

10、算整個(gè)網(wǎng)絡(luò)中完全子圖的數(shù)目,每個(gè)完全子圖包含的節(jié)點(diǎn)數(shù)及每個(gè)節(jié)點(diǎn)歸屬于哪些完全子圖。這具有非常重要的理論意義和實(shí)際意義。如果將算法用在機(jī)械產(chǎn)品零部件網(wǎng)絡(luò)中,查找出完全子圖的數(shù)目,則可得知整個(gè)機(jī)器由多少個(gè)部件組成,每個(gè)部件又由哪些零件組成,從而可以計(jì)算出零件的用量,并得知零件用在哪些部件中,如果修改了該零件,哪些部件中與該零件相關(guān)的其它零件有可能要做相應(yīng)修改,這在產(chǎn)品零部件ABC 分類及產(chǎn)品配置8中都將產(chǎn)生非常重要的作用。如果將算法用在其他相類似的網(wǎng)絡(luò)中,也將同樣產(chǎn)生非常重要的實(shí)際作用。為此,我們對搜索算法進(jìn)行了研究,提出一種比較好的搜索上述特殊類型的復(fù)雜網(wǎng)絡(luò)中完全子圖的算法。算法的關(guān)鍵是抓住這類

11、網(wǎng)絡(luò)最本質(zhì)的東西,那就是該網(wǎng)絡(luò)由完全子圖組成,網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)至少歸屬于一個(gè)完全子圖。因此,我們從度數(shù)最少的節(jié)點(diǎn)開始搜索,找出度數(shù)最少的節(jié)點(diǎn)所屬的完全子圖,然后依次類推,按度數(shù)的大小依次搜索出圖中所有的完全子圖。搜索算法的搜索步驟如下:(1計(jì)算網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度數(shù),并找出度數(shù)最小且大于零的節(jié)點(diǎn);(2找出該節(jié)點(diǎn)的鄰接節(jié)點(diǎn);(3找出構(gòu)成完全子圖的節(jié)點(diǎn),并輸出一個(gè)完全子圖;按相關(guān)規(guī)則修改這個(gè)完全子圖的各條邊所對應(yīng)的鄰接矩陣元素值;(4判斷網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的度數(shù)是否都為零(即整個(gè)網(wǎng)絡(luò)是否搜索完?,如果否,則轉(zhuǎn)1;如果是,則轉(zhuǎn)5;(5網(wǎng)絡(luò)中所有的完全子圖均已輸出,程序結(jié)束。算法對應(yīng)的程序框圖如圖2所示:第6

12、期增刊復(fù)雜網(wǎng)絡(luò)中的完全子圖搜索算法研究927 圖2程序框圖3程序設(shè)計(jì)及實(shí)現(xiàn)根據(jù)上述算法,采用C +語言編制了實(shí)現(xiàn)上述算法的程序,程序調(diào)試通過并運(yùn)行正確。利用所設(shè)計(jì)的程序?qū)D2進(jìn)行了完全子圖搜索,搜索結(jié)果如下: 完全子圖1包含的節(jié)點(diǎn):11,10,12完全子圖2包含的節(jié)點(diǎn):1,2,3,4完全子圖3包含的節(jié)點(diǎn):9,6,8,10完全子圖4包含的節(jié)點(diǎn):18,17,19,20完全子圖5包含的節(jié)點(diǎn):5,3,6,7,8完全子圖6包含的節(jié)點(diǎn):3,7,13,14,15,16,17由上可見,搜索結(jié)果準(zhǔn)確。利用程序?qū)ζ渌W(wǎng)絡(luò)進(jìn)行搜索,都能得到正確的結(jié)果。說明算法及所設(shè)計(jì)的程序正確實(shí)用。4算法效率分析由文獻(xiàn)3可知,以往

13、的許多搜索算法的運(yùn)行效率很低,有些算法的運(yùn)行時(shí)間高達(dá)O (n 4,使得運(yùn)算時(shí)間隨節(jié)點(diǎn)數(shù)的增加而急劇增加,大大限制了這些算法的使用范圍。因此,算法的運(yùn)行效率是算法設(shè)計(jì)中一個(gè)極為重要的考慮因素。本算法的運(yùn)行次數(shù)如下:計(jì)算每個(gè)節(jié)點(diǎn)的度數(shù)需要的加法運(yùn)行次數(shù):n 2次;排序算法:n 3(1+n /2次;修改矩陣元素的值:n 2次;循環(huán)次數(shù):E 次故總的最多運(yùn)行次數(shù)為:E 3(n 2+n 3(1+n /2+E ;可見,該算法的運(yùn)行次數(shù)對稀疏矩陣來說是O(n 2的線性函數(shù),最壞的情況下其運(yùn)行次數(shù)為O (n 3,而實(shí)際上這類網(wǎng)絡(luò)通常都是稀疏矩陣,因此該算法具有較高的運(yùn)行效率。5結(jié)論由上述可知,該搜索算法是可行

14、的,算法不僅能準(zhǔn)確搜索出上述特殊類型網(wǎng)絡(luò)中的完全子圖,并且具有較高的運(yùn)行效率,為研究實(shí)際生活中大量存在的這類復(fù)雜網(wǎng)絡(luò)提供了強(qiáng)有力的工具,具有重要的實(shí)際意義。參考文獻(xiàn)review ,J.Stat J .Phys.,2000,101:819841.2ALB ER T R.,A 2L BARAB SI.Statistical mechanicsof complex networksJ .Review of Modern Physics ,2002,74(1:47297.4CL AUSET A ,N EWMAN M. E.J ,MOORE C.MU OZMA.Detectingnetworkcommunities :a new systematic and efficient algorithm J .J St