應(yīng)用SQL求邊的聚類系數(shù)

1、應(yīng)用SQL求邊的聚類系數(shù)摘要：邊的聚類系數(shù)是用來度量復雜網(wǎng)絡(luò)中兩個結(jié)點的緊密程度的，被廣泛的應(yīng)用于識別網(wǎng)絡(luò)模塊。本文介紹了如何利用SQL及相關(guān)函數(shù)來求解邊的聚類系數(shù)。關(guān)鍵詞：邊的聚類系數(shù)復雜網(wǎng)絡(luò)SQL0前言由WattsandStrogatz1提出的結(jié)點的聚類系數(shù)是用來刻畫網(wǎng)絡(luò)中結(jié)點的聚集程度的，已經(jīng)被用作一個有效工具來分析相互作用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)2。為了度量兩個結(jié)點的緊密程度，由此衍生出了邊的聚集系數(shù)的定義3，它被廣泛的應(yīng)用于識別網(wǎng)絡(luò)模塊，邊的聚類系數(shù)表示邊所連接的兩個結(jié)點的連接強度，值越大表明這兩個結(jié)點在同一個模塊的可能性越大4。本文根據(jù)StructuredQueryLanguage(SQL)

2、的優(yōu)點編寫了程序?qū)崿F(xiàn)了求解邊和結(jié)點數(shù)目眾多的復雜網(wǎng)絡(luò)中邊的聚集系數(shù)，為網(wǎng)絡(luò)的進一步分析打下了基礎(chǔ)。1基本概念FilippoRadicchi等人在文獻2中用類似于點的聚集系數(shù)的定義的方式定義了邊的聚集系數(shù)為實際存在的包含該邊的三角形的數(shù)目和總的可能包含該邊的三角形數(shù)目之比。即(1)zij就是實際包含邊(i,j)的三角形的數(shù)目。di和dj分別為結(jié)點i和j結(jié)點的度。di-1和dj-1中最小值min(di-1),(dj-1)即為可能包含該邊的三角形的最大數(shù)目。當網(wǎng)絡(luò)中幾乎沒有三角形時，為了克服上述定義的不合理性，李敏等人5用兩個結(jié)點的共同的鄰居結(jié)點的數(shù)目取代了包含該邊的三角形的數(shù)目，改進了邊的聚集系數(shù)

3、的定義為(2)這里Ni和Nj分別是結(jié)點i和結(jié)點j的相鄰結(jié)點的集合。di和dj所代表的意義與(1)式相同。2邊的聚類系數(shù)的計算既然(1)式中關(guān)于邊的聚類系數(shù)的定義存在不合理的地方，故本文按照(2)式來計算邊的聚類系數(shù)。2.1SQLserver數(shù)據(jù)庫中表的設(shè)計為了描述復雜的網(wǎng)絡(luò)結(jié)構(gòu)并計算出邊的聚集系數(shù)，本數(shù)據(jù)庫涉及三張表：結(jié)點表、邊表、中間表。其中每一張表的結(jié)構(gòu)如下，主碼用下劃線標出：結(jié)點表(結(jié)點名稱)中間表(結(jié)點1的名稱，結(jié)點2的名稱)邊表(結(jié)點1的名稱，結(jié)點2的名稱，兩結(jié)點鄰居結(jié)點交集的個數(shù)，兩結(jié)點中度的最小值，邊的聚集系數(shù)）其中結(jié)點表和邊表的初始值可以通過外部的excel表或者文本文檔導入到

4、數(shù)據(jù)庫中，結(jié)點表中存放的是網(wǎng)絡(luò)中所有結(jié)點的名稱，結(jié)點表中元組的個數(shù)等于該網(wǎng)絡(luò)中結(jié)點的個數(shù)。邊表中存放的是網(wǎng)絡(luò)中所有的邊所對應(yīng)的結(jié)點對，該網(wǎng)絡(luò)中有多少條邊，邊表中就有多少條元組。中間表是為了計算邊的聚集系數(shù)時所建立的一張過渡表，通過它可以比較方便的計算出結(jié)點的度，和兩個結(jié)點的鄰居結(jié)點的交集。起初中間表是一張空表。例如有個網(wǎng)絡(luò)1的拓撲結(jié)構(gòu)如下圖1所示。為了描述這個網(wǎng)絡(luò)，先在結(jié)點表和邊表中的寫入初始數(shù)據(jù)。2.2計算過程221寫中間數(shù)據(jù)到中間表中初始數(shù)據(jù)導入到數(shù)據(jù)庫中后，依次取出結(jié)點表中的結(jié)點名稱，分別在邊表中查詢結(jié)點1或結(jié)點2的名稱等于結(jié)點名稱的元組，并將查詢的結(jié)果寫入中間表中，在寫入的過程中，若是

5、邊表中結(jié)點1的名稱等于結(jié)點表中的結(jié)點名稱，則原樣寫入，若是邊表中結(jié)點2的名稱等于結(jié)點表中的結(jié)點名稱，則交換結(jié)點1和結(jié)點2的順序?qū)懭?。例如上例中在查詢了邊表中結(jié)點1或結(jié)點2的名稱等于“A的元組后，寫出中間表的結(jié)果如下：中間表結(jié)點1的名稱結(jié)點2的名稱ABADAC圖1網(wǎng)路1的拓撲結(jié)構(gòu)圖最終中間表中所存放的元組的個數(shù)等于網(wǎng)絡(luò)中邊的條數(shù)的兩倍，也等于邊表中元組數(shù)目的兩倍。222求兩結(jié)點鄰居結(jié)點交集的個數(shù)依次讀出邊表中的每一條元組，在中間表中用嵌套查詢語句和count()函數(shù)計算兩個結(jié)點鄰居結(jié)點交集的個數(shù)。并將最終的計算結(jié)果寫入邊表對應(yīng)元組的第三列中。其核心語句是：SELECTn二count(vertex

6、2)FROM中間表WHEREvertex仁門0de1andvertex2IN(SELECTvertex2FROM中間表WHEREvertexnode2);UPDATE邊表SETmind=nWHEREvertex1=node1andvertex仁node2;計算兩結(jié)點度中的最小值在中間表中分別統(tǒng)計邊表中一條元組的兩個結(jié)點的度，并通過比較，將較小的值寫入邊表對應(yīng)元組的第四列中。其核心語句是:SELECTi=C0UNT(vertex2)FROM中間表WHEREvertex仁nodel;SELECTj=COUNT(vertex2)FROM中間表WHEREvertex仁node2;IF(ij)BEGIN

7、UPDATE邊表SETdegree=jWHEREvertexnode1andvertex仁node2ENDELSEBEGINUPDATE邊表SETdegree=iWHEREvertexnode1andvertex仁node2END求邊的聚集系數(shù)當兩個結(jié)點鄰居結(jié)點交集的個數(shù)及度中的最小值計算出來以后，可直接按照公式(2)求邊的聚集系數(shù)，其核心語句是：UPDATE邊表SETECC=(mind+1.0)/degree;3總結(jié)本文通過SQL語句以及數(shù)據(jù)庫中的相關(guān)函數(shù)計算了邊的聚集系數(shù)，求解過程簡單，求解思路清晰，為網(wǎng)絡(luò)的進一步研究及相關(guān)的度量算法打下了基礎(chǔ)，如果在建立表的時候按照相關(guān)字段建立索引可以提

8、高求解效率。當然也可以借助其它的語言工具來編寫程序計算邊的聚集系數(shù)。參考文獻WattsDJ,StrogatzSH.Collectivedynamicsofsmall-worldnetworksJ.Nature,1998,393:440-442.FriedelC,ZimmerR:Inferringtopologyfromclusteringcoefficientsinprotein-proteininteractionnetworksJ.BMCBioinformatics,2006,7:519.RadicchiF,CastellanoC,CecconiF,LoretoVParisiD:DefiningandidentifyingcommunitiesinnetworksJ.PNAS,2004,101:2658-2663.趙曉慧，劉微,謝鳳宏,趙鳳霞.基于局部信息的復雜網(wǎng)絡(luò)社團結(jié)構(gòu)發(fā)現(xiàn)算法J.微型機與應(yīng)用,2011,30(15):43-46.LiM,WangJ,ChenX,WangH,PanY:Alocalaverageconnectivity-basedmethodforide