作者简介:王贵参(1987-), 男, 博士研究生.研究方向:社会网络与数据挖掘.E-mail:clouddragon2@qq.com
针对在连接相似度的计算过程中原始连接聚类(LC)方法并未考虑非相邻连接的相似关系,本文提出的极值非相邻连接相似度策略,弥补了原有连接相似度的不足。新的极值非相邻连接相似度(MLS)策略考虑了连接之间相似关系的邻居节点集合的最大、最小情况。在此基础上,结合EQ评估策略,给出了新的引入极值非相邻连接的连接聚类(MLC)方法。在3组测试数据集上的实验结果表明:本文MLC方法相比原始LC、经典重叠社区发现(CPM)方法和扩展的连接聚类ELC方法在多种评估指标上表现优异。
Traditional clustering methods can be applied to the research of overlapping community detection directly with link similarity. However, Link Clustering (LC) method does not consider the relationship between non-neighbor links in the calculation of link similarity. In this paper, two link similarity strategies are proposed based on the maxima and minima non-neighbor (MLS) in order to overcome the shortcomings of the original link clustering. The two link similarity strategies consider the minimum and maximum conditions of link similarity relationships. Then, a link clustering method is put forward based on MLS strategies (MLC) with EQ evaluation. Experimental results on three real-world networks show that the proposed MLC method achieves better performance than the original LC method, classical CPM method and Extended Link Clustering (ELC) method under several evaluation criteria.
Palla等[1]于2005年率先揭示了社区间的重叠现象, 提出了重叠社区发现(CPM)方法, 使重叠社区发现迅速成为复杂网络研究中的热门研究方向。CPM方法是用于无向无权图的重叠社区发现算法, 由
本文针对连接聚类LC方法中连接相似度未考虑非相邻连接的不足, 通过引入连接之间相似程度的邻居节点集合的最大、最小情况, 考虑了非相邻连接之间的相似关系, 提出了引入极值的非相邻连接相似度策略; 进而结合EQ评估, 提出了引入极值的非相邻连接的连接聚类(MLC)方法。在空手道俱乐部、海豚社会网络、美国政治图书等真实的复杂网络的测试中, MLC方法与原始LC方法[3]、经典CPM方法[1]和ELC[6]方法相比, 在多种评估策略上表现优异。
2010年, Ahn等[3]提出了基于连接相似度的连接聚类方法。该方法首先使用连接相似度计算连接与连接之间的相似度, 并得到连接之间的相似度矩阵; 然后, 根据相似度矩阵进行层次聚类; 最后, 对层次聚类得到的树状谱系图使用分割密度评估策略进行层次划分。
定义1[3] 与节点
连接聚类方法LC的等法流程如下:
输入:社区对应的图
输出:社区
(1)设图
式中:intersection(i, j)为节点i和节点j的邻居节点集合的交集; union(i, j)为节点i和节点j的邻居节点集合的并集;
(2)对得到的连接相似度矩阵
(3)针对树状谱系图的层次聚类结果, 使用分割密度策略进行评估, 每层的分割密度定义如下:
其中, 每层中每个单独社区i连接的数量记为mi, 节点的数目记为
由原始LC连接相似度计算公式可知, 其在连接相似度上未考虑非相邻连接的情况; 同时, 分割密度公式中, 通常情况下连接的数量
定义2 不具有公共节点的两条连接
由原始LC方法可知, 对于没有公共节点的连接之间的连接相似度均为0。如图1所示, 对于连接
针对原始连接相似度的不足, 本文将极值非相邻连接引入到连接相似度计算中。与文献[6]中的扩展连接相似度ELS不同, 本文将邻居节点集合的最大最小情况引入到连接相似度策略中, 即MLS(Maxima and minima link similarity),
本文考虑两条连接中4个节点的邻居节点集合的最小数目和最大数目, 是连接的拓扑结构的两种极值情况。而这两种方式的改变, 会导致社区发现的不同。极值非相邻连接相似度MLS与原始连接相似度LS之间的比较如图2所示, 该网络包括6个节点和9条连接。从图2(b)~(e)所示的相似度矩阵的密度图中可以看出, 两种新的极值非相邻连接相似度的相似度矩阵都比原始的连接相似度矩阵稠密, 使得示例网络(见图2(a))聚类划分更为清晰。
由式(2)可知, 原始分割密度PD策略在对社区进行划分时, 随着社区中连接的增长,
Shen等[10]在2009年提出了改进的EQ策略, 并将改进的模块度EQ这一概念应用于重叠社区发现评估上, 公式如下:
式中:
本文采用的EQ与文献[6]中的不同之处在于, 文献[6]中采用的EQ是在无向无权图中, 节点
引入极值非相邻连接的连接聚类MLCmin和MLCmax的MLC方法流程如下。
输入:社区对应的图
输出:社区
(1)设图
(2)对连接相似度矩阵
(3)针对树状谱系图的层次聚类结果, 使用EQ策略进行评估, 选择EQ值最高的层作为最佳的划分层次。
在空手道、海豚、政治图书3个测试数据集上, 将MLC方法在社区分类数目(Community number, CN)、EQ、ENMI三个评估策略上与原始LC方法、经典的CPM方法以及ELC方法进行对比。
本文算法采用的数据集如表1所示, 包括空手道数据集(Karate)、海豚数据集(Dolphin)和政治图书数据集(Political), 这3个数据集都是重叠社区发现研究中经常使用的数据集[5], 这3个数据集的标准划分分别为2、2、3个社区。
在实验结果评估上, 本文使用了社区分类数目CN、EQ和ENMI三个评估策略。其中, 社区分类数目CN指的就是算法最终得到的社区分类数目; ENMI策略则是由Lancichinetti等人提出的[11]。ENMI以互信息作为评估基础, 需要预先知道接近真实分类的标准划分结果。
针对空手道(Karate)、海豚(Dolphin)和政治图书(Political)3个数据集将本文MLC方法与原始LC、经典的CPM和ELC方法进行了横向比较。3个数据集的网络拓扑结构图, 以及在4种方法下对应的树状谱系图和分类决策图如图3所示, 对应的CN、ENMI和EQ评估效果如表2所示。根据表2的实验结果可以看出, 在空手道数据集中, MLCmin方法和ELC方法均得到了与标准划分相同的社区数目, 但是MLCmin方法具有最高的ENMI值。MLCmax方法得到了最高的EQ值, 而社区数目与标准划分略有不同。ELC方法获得了与标准划分相同的社区数目, 并且与MLCmin和MLCmax方法的结果比较接近。相比之下, LC方法与标准划分的社区数目相差较多, CPM方法得到的结果中有一个包括25个节点的大社区, 这两种方法与真实情况相比都有很大差异。在海豚数据集中, ELC方法取得了最优结果, 和标准划分的社区数目相同, MLCmin方法取得了次优结果, 在EQ值上与ELC方法相比仅差0.02。而MLCmax与CPM方法的结果较为接近。LC方法得到了13个社区, 这与标准划分的3个社区结果相差甚远。在政治图书数据集中, MLCmin方法得到了与标准划分相同的社区数目和最高的EQ值, ELC方法得到了最高的ENMI值, 但与MLCmin方法的ENMI值相差不多。LC方法得到了32个社区, 这与标准划分的3个社区结果相比存在很大差异。尽管CPM方法也得到了最高的EQ值, 但与同样具有最高EQ值的MLCmin方法相比, 后者获得了与标准划分相同的社区数目。因此, 在综合考虑3个评估策略的情况下, MLCmin方法的效果是最理想的。总体来说, MLC方法表现优异。
本文对于重叠社区发现问题提出了引入极值非相邻连接的连接聚类方法(MLC), 在MLCmin和MLCmax两种极值非相邻连接相似度基础上, 结合EQ评估来弥补原始连接聚类方法的不足。在3个真实的复杂网络测试中, 与原始的LC、经典的CPM和ELC方法进行比较, 引入极值非相邻连接的连接聚类方法(MLC)在多个评估策略下表现优异。对于大规模复杂网络中的重叠社区分析及动态复杂网络分析, 将是进一步需要深入研究的内容。
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|