论文部分内容阅读
摘 要：边的聚类系数是用来度量复杂网络中两个结点的紧密程度的，被广泛的应用于识别网络模块。本文介绍了如何利用SQL及相关函数来求解边的聚类系数。
关键词：边的聚类系数 复杂网络 SQL
中图分类号：TP393 文献标识码：A 文章编号：1672-3791（2013）03（a）-0001-02
由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.2.2 求两结点邻居结点交集的个数
依次读出边表中的每一条元组，在中间表中用嵌套查询语句和count（）函数计算两个结点邻居结点交集的个数。并将最终的计算结果写入边表对应元组的第三列中。其核心语句是：
2.2.3 计算两结点度中的最小值
在中间表中分别统计边表中一条元组的两个结点的度，并通过比较，将较小的值写入边表对应元组的第四列中。其核心语句是：
2.2.4 求边的聚集系数
当两个结点邻居结点交集的个数及度中的最小值计算出来以后，可直接按照公式（2）求边的聚集系数，其核心语句是：
UPDATE 边表 SET ECC=（mind+1.0）/degree。
3 结语
本文通过SQL语句以及数据库中的相关函数计算了边的聚集系数，求解过程简单，求解思路清晰，为网络的进一步研究及相关的度量算法打下了基础，如果在建立表的时候按照相关字段建立索引可以提高求解效率。当然也可以借助其它的语言工具来编写程序计算边的聚集系数[6]。
参考文献
[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] 赵晓慧，刘微，谢凤宏，等.基于局部信息的复杂网络社团结构发现算法[J].微型机与应用，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环境的聚类系数的计算[J].山西师范大学学报（自然科学版），2009，23（3）：32-35.
关键词：边的聚类系数 复杂网络 SQL
中图分类号：TP393 文献标识码：A 文章编号：1672-3791（2013）03（a）-0001-02
由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.2.2 求两结点邻居结点交集的个数
依次读出边表中的每一条元组，在中间表中用嵌套查询语句和count（）函数计算两个结点邻居结点交集的个数。并将最终的计算结果写入边表对应元组的第三列中。其核心语句是：
2.2.3 计算两结点度中的最小值
在中间表中分别统计边表中一条元组的两个结点的度，并通过比较，将较小的值写入边表对应元组的第四列中。其核心语句是：
2.2.4 求边的聚集系数
当两个结点邻居结点交集的个数及度中的最小值计算出来以后，可直接按照公式（2）求边的聚集系数，其核心语句是：
UPDATE 边表 SET ECC=（mind+1.0）/degree。
3 结语
本文通过SQL语句以及数据库中的相关函数计算了边的聚集系数，求解过程简单，求解思路清晰，为网络的进一步研究及相关的度量算法打下了基础，如果在建立表的时候按照相关字段建立索引可以提高求解效率。当然也可以借助其它的语言工具来编写程序计算边的聚集系数[6]。
参考文献
[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] 赵晓慧，刘微，谢凤宏，等.基于局部信息的复杂网络社团结构发现算法[J].微型机与应用，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环境的聚类系数的计算[J].山西师范大学学报（自然科学版），2009，23（3）：32-35.