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

李圓媛

摘 要：邊的聚類系數(shù)是用來度量復(fù)雜網(wǎng)絡(luò)中兩個結(jié)點的緊密程度的，被廣泛的應(yīng)用于識別網(wǎng)絡(luò)模塊。本文介紹了如何利用SQL及相關(guān)函數(shù)來求解邊的聚類系數(shù)。

關(guān)鍵詞：邊的聚類系數(shù) 復(fù)雜網(wǎng)絡(luò) SQL

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2013）03（a）-0001-02

由Watts and Strogatz[1]提出的結(jié)點的聚類系數(shù)是用來刻畫網(wǎng)絡(luò)中結(jié)點的聚集程度的，已經(jīng)被用作一個有效工具來分析相互作用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)[2]。為了度量兩個結(jié)點的緊密程度，由此衍生出了邊的聚集系數(shù)的定義[3]，它被廣泛的應(yīng)用于識別網(wǎng)絡(luò)模塊，邊的聚類系數(shù)表示邊所連接的兩個結(jié)點的連接強(qiáng)度，值越大表明這兩個結(jié)點在同一個模塊的可能性越大[4]。

本文根據(jù)Structured Query Language（SQL）的優(yōu)點編寫了程序?qū)崿F(xiàn)了求解邊和結(jié)點數(shù)目眾多的復(fù)雜網(wǎng)絡(luò)中邊的聚集系數(shù)，為網(wǎng)絡(luò)的進(jìn)一步分析打下了基礎(chǔ)。

1 基本概念

Filippo Radicchi等人在文獻(xiàn)[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ù)目。

當(dāng)網(wǎng)絡(luò)中幾乎沒有三角形時，為了克服上述定義的不合理性，李敏等人[5]用兩個結(jié)點的共同的鄰居結(jié)點的數(shù)目取代了包含該邊的三角形的數(shù)目，改進(jìn)了邊的聚集系數(shù)的定義為 （2）

這里Ni和Nj分別是結(jié)點i和結(jié)點j的相鄰結(jié)點的集合。di和dj所代表的意義與（1）式相同。

2 邊的聚類系數(shù)的計算

既然（1）式中關(guān)于邊的聚類系數(shù)的定義存在不合理的地方，故本文按照（2）式來計算邊的聚類系數(shù)。

2.1 SQL server數(shù)據(jù)庫中表的設(shè)計

為了描述復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)并計算出邊的聚集系數(shù)，本數(shù)據(jù)庫涉及三張表：結(jié)點表、邊表、中間表。其中每一張表的結(jié)構(gòu)如下，主碼用下劃線標(biāo)出：

結(jié)點表（結(jié)點名稱）

中間表（結(jié)點1的名稱，結(jié)點2的名稱）

邊表（結(jié)點1的名稱，結(jié)點2的名稱，兩結(jié)點鄰居結(jié)點交集的個數(shù)，兩結(jié)點中度的最小值，邊的聚集系數(shù)）

其中結(jié)點表和邊表的初始值可以通過外部的excel表或者文本文檔導(dǎo)入到數(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的拓?fù)浣Y(jié)構(gòu)如下圖1所示。

為了描述這個網(wǎng)絡(luò)，先在結(jié)點表和邊表中的寫入初始數(shù)據(jù)。

2.2 計算過程

2.2.1 寫中間數(shù)據(jù)到中間表中

初始數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫中后，依次取出結(jié)點表中的結(jié)點名稱，分別在邊表中查詢結(jié)點1或結(jié)點2的名稱等于結(jié)點名稱的元組，并將查詢的結(jié)果寫入中間表中，在寫入的過程中，若是邊表中結(jié)點1的名稱等于結(jié)點表中的結(jié)點名稱，則原樣寫入，若是邊表中結(jié)點2的名稱等于結(jié)點表中的結(jié)點名稱，則交換結(jié)點1和結(jié)點2的順序?qū)懭搿＠缟侠性诓樵兞诉叡碇薪Y(jié)點1或結(jié)點2的名稱等于“A”的元組后，寫出中間表的結(jié)果如下：（如表1）。

最終中間表中所存放的元組的個數(shù)等于網(wǎng)絡(luò)中邊的條數(shù)的兩倍，也等于邊表中元組數(shù)目的兩倍。

2.2.2 求兩結(jié)點鄰居結(jié)點交集的個數(shù)

依次讀出邊表中的每一條元組，在中間表中用嵌套查詢語句和count（）函數(shù)計算兩個結(jié)點鄰居結(jié)點交集的個數(shù)。并將最終的計算結(jié)果寫入邊表對應(yīng)元組的第三列中。其核心語句是：

2.2.3 計算兩結(jié)點度中的最小值

在中間表中分別統(tǒng)計邊表中一條元組的兩個結(jié)點的度，并通過比較，將較小的值寫入邊表對應(yīng)元組的第四列中。其核心語句是：

2.2.4 求邊的聚集系數(shù)

當(dāng)兩個結(jié)點鄰居結(jié)點交集的個數(shù)及度中的最小值計算出來以后，可直接按照公式（2）求邊的聚集系數(shù)，其核心語句是：

UPDATE 邊表 SET ECC=（mind+1.0）/degree。

3 結(jié)語

本文通過SQL語句以及數(shù)據(jù)庫中的相關(guān)函數(shù)計算了邊的聚集系數(shù)，求解過程簡單，求解思路清晰，為網(wǎng)絡(luò)的進(jìn)一步研究及相關(guān)的度量算法打下了基礎(chǔ)，如果在建立表的時候按照相關(guān)字段建立索引可以提高求解效率。當(dāng)然也可以借助其它的語言工具來編寫程序計算邊的聚集系數(shù)[6]。

參考文獻(xiàn)

[1] Watts D J，Strogatz S H.Collective dynamics of small-world networks[J].Nature，1998，393：440-442.

[2] Friedel C，Zimmer R：Inferring topology from clustering coefficients in protein-protein interaction networks[J].BMC Bioinformatics，2006，7：519.

[3] Radicchi F，Castellano C，Cecconi F，Loreto V，Parisi D：Defining and identifying communities in networks[J].PNAS，2004，101：2658-2663.

[4] 趙曉慧，劉微，謝鳳宏，等.基于局部信息的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法[J].微型機(jī)與應(yīng)用，2011，30（15）：43-46.

[5] Li M，Wang J，Chen X，Wang H，Pan Y：A local average connectivity-based method for identifying essential proteins from the network level[J].Comput Biol Chem 2011，35：143-150.

[6] 李岸巍，阮豫紅.基于MATLAB環(huán)境的聚類系數(shù)的計算[J].山西師范大學(xué)學(xué)報（自然科學(xué)版），2009，23（3）：32-35.