李圓媛

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

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

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

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

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

1 基本概念

Filippo Radicchi等人在文獻(xiàn)[2]中用類似于點(diǎn)的聚集系數(shù)的定義的方式定義了邊的聚集系數(shù)為實(shí)際存在的包含該邊的三角形的數(shù)目和總的可能包含該邊的三角形數(shù)目之比。即（1）

zij就是實(shí)際包含邊（i，j）的三角形的數(shù)目。di和dj分別為結(jié)點(diǎn)i和j結(jié)點(diǎn)的度。di-1和dj-1中最小值min[（di-1），（dj-1）]即為可能包含該邊的三角形的最大數(shù)目。

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

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

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

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

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

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

結(jié)點(diǎn)表（結(jié)點(diǎn)名稱）

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

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

其中結(jié)點(diǎn)表和邊表的初始值可以通過外部的excel表或者文本文檔導(dǎo)入到數(shù)據(jù)庫(kù)中，結(jié)點(diǎn)表中存放的是網(wǎng)絡(luò)中所有結(jié)點(diǎn)的名稱，結(jié)點(diǎn)表中元組的個(gè)數(shù)等于該網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)。邊表中存放的是網(wǎng)絡(luò)中所有的邊所對(duì)應(yīng)的結(jié)點(diǎn)對(duì)，該網(wǎng)絡(luò)中有多少條邊，邊表中就有多少條元組。中間表是為了計(jì)算邊的聚集系數(shù)時(shí)所建立的一張過渡表，通過它可以比較方便的計(jì)算出結(jié)點(diǎn)的度，和兩個(gè)結(jié)點(diǎn)的鄰居結(jié)點(diǎn)的交集。起初中間表是一張空表。

例如有個(gè)網(wǎng)絡(luò)1的拓?fù)浣Y(jié)構(gòu)如下圖1所示。

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

2.2 計(jì)算過程

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

初始數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫(kù)中后，依次取出結(jié)點(diǎn)表中的結(jié)點(diǎn)名稱，分別在邊表中查詢結(jié)點(diǎn)1或結(jié)點(diǎn)2的名稱等于結(jié)點(diǎn)名稱的元組，并將查詢的結(jié)果寫入中間表中，在寫入的過程中，若是邊表中結(jié)點(diǎn)1的名稱等于結(jié)點(diǎn)表中的結(jié)點(diǎn)名稱，則原樣寫入，若是邊表中結(jié)點(diǎn)2的名稱等于結(jié)點(diǎn)表中的結(jié)點(diǎn)名稱，則交換結(jié)點(diǎn)1和結(jié)點(diǎn)2的順序?qū)懭?。例如上例中在查詢了邊表中結(jié)點(diǎn)1或結(jié)點(diǎn)2的名稱等于“A”的元組后，寫出中間表的結(jié)果如下：（如表1）。

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

2.2.2 求兩結(jié)點(diǎn)鄰居結(jié)點(diǎn)交集的個(gè)數(shù)

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

2.2.3 計(jì)算兩結(jié)點(diǎn)度中的最小值

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

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

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

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

3 結(jié)語(yǔ)

本文通過SQL語(yǔ)句以及數(shù)據(jù)庫(kù)中的相關(guān)函數(shù)計(jì)算了邊的聚集系數(shù)，求解過程簡(jiǎn)單，求解思路清晰，為網(wǎng)絡(luò)的進(jìn)一步研究及相關(guān)的度量算法打下了基礎(chǔ)，如果在建立表的時(shí)候按照相關(guān)字段建立索引可以提高求解效率。當(dāng)然也可以借助其它的語(yǔ)言工具來編寫程序計(jì)算邊的聚集系數(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ì)算[J].山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，23（3）：32-35.