应用SQL求边的聚类系数

应用SQL求边的聚类系数

作者：李圆媛

来源：《科技资讯》 2013年第7期

李圆媛

（武汉工程大学理学院智能机器人湖北省重点实验室 湖北武汉 430073）

基金项目：武汉工程大学青年科学基金（Q201208）

摘 要：边的聚类系数是用来度量复杂网络中两个结点的紧密程度的，被广泛的应用于识别网络模块。本文介绍了如何利用SQL及相关函数来求解边的聚类系数。

关键词：边的聚类系数 复杂网络 SQL

中图分类号： TP393

文献标识码：A

文章编号：1672-3791(2013)03(a)-0000-00

作者简介：李圆媛（1980-），女，湖北宜都人，硕士，研究方向：数据库、计算系统生物学，讲师。

0 前言

由Watts and Strogatz[1] 提出的结点的聚类系数是用来刻画网络中结点的聚集程度的，已经被用作一个有效工具来分析相互作用网络的拓扑结构 [2]。为了度量两个结点的紧密程度，由此衍生出了边的聚集系数的定义[3]，它被广泛的应用于识别网络模块，边的聚类系数表示边所连接的两个结点的连接强度，值越大表明这两个结点在同一个模块的可能性越大[4]。

本文根据Structured Query Language（SQL）的优点编写了程序实现了求解边和结点数目众多的复杂网络中边的聚集系数，为网络的进一步分析打下了基础。

1 基本概念

Filippo Radicchi等人在文献[2]中用类似于点的聚集系数的定义的方式定义了边的聚集系数为实际存在的包含该边的三角形的数目和总的可能包含该边的三角形数目之比。即

(1)

zij就是实际包含边(i,j)的三角形的数目。di和dj分别为结点i和j结点的度。di-1和dj-1中最小值min[(di-1),( dj-1)]即为可能包含该边的三角形的最大数目。

当网络中几乎没有三角形时，为了克服上述定义的不合理性，李敏等人[5]用两个结点的共同的邻居结点的数目取代了包含该边的三角形的数目，改进了边的聚集系数的定义为

(2)

这里Ni和Nj分别是结点i和结点j的相邻结点的集合。di和dj所代表的意义与(1)式相同。

2 边的聚类系数的计算

既然(1)式中关于边的聚类系数的定义存在不合理的地方，故本文按照(2) 式来计算边的聚类系数。

2.1 SQL server数据库中表的设计

为了描述复杂的网络结构并计算出边的聚集系数，本数据库涉及三张表：结点表、边表、中间表。其中每一张表的结构如下，主码用下划线标出：

结点表（结点名称）

中间表（结点1的名称，结点2的名称）

边表（结点1的名称，结点2的名称，两结点邻居结点交集的个数，两结点中度的最小值，边的聚集系数）

其中结点表和边表的初始值可以通过外部的excel表或者文本文档导入到数据库中，结点表中存放的是网络中所有结点的名称，结点表中元组的个数等于该网络中结点的个数。边表中存放的是网络中所有的边所对应的结点对，该网络中有多少条边，边表中就有多少条元组。中间表是为了计算边的聚集系数时所建立的一张过渡表，通过它可以比较方便的计算出结点的度，和两个结点的邻居结点的交集。起初中间表是一张空表。

例如有个网络1的拓扑结构如下图1所示。

为了描述这个网络，先在结点表和边表中的写入初始数据。

2.2 计算过程

2.2.1 写中间数据到中间表中

初始数据导入到数据库中后，依次取出结点表中的结点名称，分别在边表中查询结点1或结点2的名称等于结点名称的元组，并将查询的结果写入中间表中，在写入的过程中，若是边表中结点1的名称等于结点表中的结点名称，则原样写入，若是边表中结点2的名称等于结点表中的结点名称，则交换结点1和结点2的顺序写入。例如上例中在查询了边表中结点1或结点2的名称等于“A”的元组后，写出中间表的结果如下：

中间表

结点1的名称

结点2的名称

A

B

A

D

A

C

图1 网路1的拓扑结构图

最终中间表中所存放的元组的个数等于网络中边的条数的两倍，也等于边表中元组数目的两倍。

2.2.2 求两结点邻居结点交集的个数

依次读出边表中的每一条元组，在中间表中用嵌套查询语句和count（）函数计算两个结点邻居结点交集的个数。并将最终的计算结果写入边表对应元组的第三列中。其核心语句是：

SELECT @n=count(vertex2) FROM 中间表

WHERE vertex1=@node1 and vertex2 IN ( SELECT vertex2 FROM中间表

WHERE vertex1=@node2 );

UPDATE 边表 SET mind=@n WHERE vertex1=@node1 and vertex1=@node2;

2.2.3 计算两结点度中的最小值

在中间表中分别统计边表中一条元组的两个结点的度，并通过比较，将较小的值写入边表对应元组的第四列中。其核心语句是：

SELECT @i=COUNT(vertex2) FROM 中间表 WHERE vertex1=@node1;

SELECT @j=COUNT(vertex2) FROM中间表 WHERE vertex1=@node2;

IF(@i>@j) BEGIN UPDATE 边表 SET degree=@j

WHERE vertex1=@node1 and vertex1=@node2 END

ELSE BEGIN UPDATE 边表 SET degree=@i

WHERE vertex1=@node1 and vertex1=@node2 END

2.2.4 求边的聚集系数

当两个结点邻居结点交集的个数及度中的最小值计算出来以后，可直接按照公式(2)求边的聚集系数，其核心语句是：

UPDATE 边表 SET ECC=(mind+1.0)/degree;

3 总结