论文部分内容阅读
摘要：针对复杂网络的特殊性质导致社区挖掘质量较低的问题，提出一种相似度度量方法代替传统的欧氏距离，从而将密度聚类CFSFDP（clustering bvfast search andfind of density peaks）算法应用到复杂网络聚类中去。首先，利用Pade逼近方法计算复杂网络的拉普拉斯算子矩阵指数;接着，归一化核心矩阵得到相似度矩阵，并求倒数得出复杂网络各节点间距离;最后，借鉴CFSFDP算法思想，将节点自身邻域密度、与其他邻域密度较高节点的距离结合作为判断依据，得出聚类中心并剔除噪声点，再将其余节点与距离最近的聚类中心划分为一类。在人工模拟数据和真实数据集上的实验结果表明：所提算法聚类准确率较高，以超几何定律为最佳匹配标准的已知组与实验组的随机重叠概率较高，算法可用于挖掘高质量的复杂网络社区。
关键词：复杂网络;社区挖掘;密度聚类;CFSFDP算法;相似度
中图分类号：TP301 文献标识码：A
文章编号：1009-3044（2019）33-0278-04
1概述
现实世界中的许多复杂系统均可以转化成复杂网络，比如自然界中的生物系统，群体生态系统，人类社会中的经济系统等州。在实际中，大部分的网络都具有一定的社区结构，即这些复杂网络可以自然的分成一些节点组，同一节点组内的节点连接紧密，相互作用较强，不同节点组间的节点连接稀疏，相互作用较弱。网络的这种拓扑特性被称为社区结构，相应地，每个节点组被称为一个社区。社区结构体现了网络中连边关系的局部聚集特性，同样体现了网络中连边的分布不均匀性。网络中同一社区内的节点通常是功能相似或者性质相似，因此社区结构与网络的功能结构和组织密切相关，通常对应着不同的功能单位。例如：万维网是通过超链接连接网页从而形成的一个个社区，由于超链接的紧密连接，每一个社区的内容都有着相近的话题。随着社会的发展，复杂网络成为越来越普遍的现象，因而如何将纷繁庞杂的网络高效聚类，划分为有现實意义的社区，成了当前多学科研究的重要问题，对研究人类社会与自然界有着至关重要的作用。
聚类算法根据元素相似性划分类别，有很多种不同的策略。K-means和K-medoids算法以到达聚类中心的最小距离定义目标函数，但是由于数据点始终被分到距离最近的聚类中心，这些方法无法检测到非球星的簇。在基于分布的算法中，准确性取决于实验概率表示数据的能力。基于密度的DB-SCAN算法能够发现任意形状的簇并识别噪声点，但是选择的密度阈值可能是非平凡的，均值平移聚类方法可避免这样的缺点，但是计算成本较高且只适用于一组坐标定义的数据。
本文提出了一种新型的基于密度聚类算法的复杂网络聚类算法，定义相似度矩阵求解节点间距离代替传统欧氏距离，从而将密度聚类方法应用到复杂网络聚类分析中，首先分析网络对应的相似度矩阵，确定距离、密度，进而引用CFSFDP算法确定社区划分。CFSFDP算法与K-medoids算法类似，他仅仅基于数据点之间的距离，与DBSCAN和均值平移算法一样，能够直观地确定聚类数，发现非球型簇，并识别噪声点。另外，CFSFDP算法不需要将数据嵌入进向量空间。本文基于此算法，可有效将复杂网络聚类。
2基于CFSFDP的复杂网络聚类算法
3实验结果分析
3.1模拟数据
为检验算法的准确性、实用性与一般性，人工模拟生成10000个包含30个节点的随机网络样本，并进行编号。设节点1-10为第1类，节点11-20为第II类，节点21-30为噪声点。同一类内节点之间有边相连的概率为P1=80%，每个噪声点与任意类有边相连的概率P2=20%，对10000个网络样本进行聚类，聚类结果如图2所示：
分类错误的节点出现的频率如图3所示，聚类精度为98.031%。
3.2在ZacharyKarateClub数据集上的测试
Zachary Katie Club网络㈣是通过对一个美国大学空手道俱乐部进行观测而构建出的一个社会网络，网络包含34个节点和78条边，其中节点表示俱乐部中的成员，而边表示成员之间存在的友谊关系。测试结果如图4所示，其中不同颜色的节点代表已知的划分类，不同形状的节点代表实验组测试结果，在本数据集上的聚类准确率达到100%。
3.3在Dolphin Social Network数据集上的测试
Dolphin数据集是D.Lusseau等人使用长达7年的时间观察新西兰Doubtful Sound海峡62只海豚群体的交流情况而得到的海豚社会关系网络。这个网络具有62个节点，159条边。节点表示海豚，而边表示海豚间的频繁接触。
聚类结果如图5所示，准确率为88.710%，有7个处于边缘的点划分错误，但是存在一定的节点本身歧义性的干扰。
3.4在American CoHege Football数据集上的测试
College Football网络是Newman根据美国大学生足球联赛而创建的一个复杂的社会网络。该网络包含115个节点和616条边，其中网络中的结点代表足球队，两个结点之间的边表示两只球队之间进行过一场比赛。参赛的115支大学生代表队被分为12个联盟，比赛的流程是联盟内部的球队先进行小组赛，然后再是联盟之间球队的比赛。这表明联盟内部的球队之间进行的比赛次数多于联盟之间的球队之间进行的比赛的次数。
联盟即可表示为该网络的真实社区结构，测试结果如图6所示，准确率为92.174%。
12个类的log（Pol）值如图7所示，除了第六类大于-17.00之外，其余类的聚类结果与已知结果的匹配度都较好。
4算法评价
本文基于CFsFDP算法对复杂网络进行聚类，利用相似度度量代替传统的欧式距离，从而将传统的cFSFDP算法运用到网络聚类中去。
虽然复杂网络具有小世界性，网络间的平均路径长较小，但是本算法可以很好地确定邻域半径。另外，本文算法不仅剔除了噪声点，还减少了聚类结果的局限性，能确定任意形状和维度的类，具有很强的现实意义。利用真实数据集进行分析比对时，可以证实本文算法有效性较强，划分的复杂网络有较好的准确性，较符合当今研究需求。
算法的缺点是对参数较敏感，不同的参数会导致不同的聚类结果，需要观察对比，选择最优结果。此外，因为密度聚类的特性，当空间密度分布极度不均匀时，聚类结果较差。
关键词：复杂网络;社区挖掘;密度聚类;CFSFDP算法;相似度
中图分类号：TP301 文献标识码：A
文章编号：1009-3044（2019）33-0278-04
1概述
现实世界中的许多复杂系统均可以转化成复杂网络，比如自然界中的生物系统，群体生态系统，人类社会中的经济系统等州。在实际中，大部分的网络都具有一定的社区结构，即这些复杂网络可以自然的分成一些节点组，同一节点组内的节点连接紧密，相互作用较强，不同节点组间的节点连接稀疏，相互作用较弱。网络的这种拓扑特性被称为社区结构，相应地，每个节点组被称为一个社区。社区结构体现了网络中连边关系的局部聚集特性，同样体现了网络中连边的分布不均匀性。网络中同一社区内的节点通常是功能相似或者性质相似，因此社区结构与网络的功能结构和组织密切相关，通常对应着不同的功能单位。例如：万维网是通过超链接连接网页从而形成的一个个社区，由于超链接的紧密连接，每一个社区的内容都有着相近的话题。随着社会的发展，复杂网络成为越来越普遍的现象，因而如何将纷繁庞杂的网络高效聚类，划分为有现實意义的社区，成了当前多学科研究的重要问题，对研究人类社会与自然界有着至关重要的作用。
聚类算法根据元素相似性划分类别，有很多种不同的策略。K-means和K-medoids算法以到达聚类中心的最小距离定义目标函数，但是由于数据点始终被分到距离最近的聚类中心，这些方法无法检测到非球星的簇。在基于分布的算法中，准确性取决于实验概率表示数据的能力。基于密度的DB-SCAN算法能够发现任意形状的簇并识别噪声点，但是选择的密度阈值可能是非平凡的，均值平移聚类方法可避免这样的缺点，但是计算成本较高且只适用于一组坐标定义的数据。
本文提出了一种新型的基于密度聚类算法的复杂网络聚类算法，定义相似度矩阵求解节点间距离代替传统欧氏距离，从而将密度聚类方法应用到复杂网络聚类分析中，首先分析网络对应的相似度矩阵，确定距离、密度，进而引用CFSFDP算法确定社区划分。CFSFDP算法与K-medoids算法类似，他仅仅基于数据点之间的距离，与DBSCAN和均值平移算法一样，能够直观地确定聚类数，发现非球型簇，并识别噪声点。另外，CFSFDP算法不需要将数据嵌入进向量空间。本文基于此算法，可有效将复杂网络聚类。
2基于CFSFDP的复杂网络聚类算法
3实验结果分析
3.1模拟数据
为检验算法的准确性、实用性与一般性，人工模拟生成10000个包含30个节点的随机网络样本，并进行编号。设节点1-10为第1类，节点11-20为第II类，节点21-30为噪声点。同一类内节点之间有边相连的概率为P1=80%，每个噪声点与任意类有边相连的概率P2=20%，对10000个网络样本进行聚类，聚类结果如图2所示：
分类错误的节点出现的频率如图3所示，聚类精度为98.031%。
3.2在ZacharyKarateClub数据集上的测试
Zachary Katie Club网络㈣是通过对一个美国大学空手道俱乐部进行观测而构建出的一个社会网络，网络包含34个节点和78条边，其中节点表示俱乐部中的成员，而边表示成员之间存在的友谊关系。测试结果如图4所示，其中不同颜色的节点代表已知的划分类，不同形状的节点代表实验组测试结果，在本数据集上的聚类准确率达到100%。
3.3在Dolphin Social Network数据集上的测试
Dolphin数据集是D.Lusseau等人使用长达7年的时间观察新西兰Doubtful Sound海峡62只海豚群体的交流情况而得到的海豚社会关系网络。这个网络具有62个节点，159条边。节点表示海豚，而边表示海豚间的频繁接触。
聚类结果如图5所示，准确率为88.710%，有7个处于边缘的点划分错误，但是存在一定的节点本身歧义性的干扰。
3.4在American CoHege Football数据集上的测试
College Football网络是Newman根据美国大学生足球联赛而创建的一个复杂的社会网络。该网络包含115个节点和616条边，其中网络中的结点代表足球队，两个结点之间的边表示两只球队之间进行过一场比赛。参赛的115支大学生代表队被分为12个联盟，比赛的流程是联盟内部的球队先进行小组赛，然后再是联盟之间球队的比赛。这表明联盟内部的球队之间进行的比赛次数多于联盟之间的球队之间进行的比赛的次数。
联盟即可表示为该网络的真实社区结构，测试结果如图6所示，准确率为92.174%。
12个类的log（Pol）值如图7所示，除了第六类大于-17.00之外，其余类的聚类结果与已知结果的匹配度都较好。
4算法评价
本文基于CFsFDP算法对复杂网络进行聚类，利用相似度度量代替传统的欧式距离，从而将传统的cFSFDP算法运用到网络聚类中去。
虽然复杂网络具有小世界性，网络间的平均路径长较小，但是本算法可以很好地确定邻域半径。另外，本文算法不仅剔除了噪声点，还减少了聚类结果的局限性，能确定任意形状和维度的类，具有很强的现实意义。利用真实数据集进行分析比对时，可以证实本文算法有效性较强，划分的复杂网络有较好的准确性，较符合当今研究需求。
算法的缺点是对参数较敏感，不同的参数会导致不同的聚类结果，需要观察对比，选择最优结果。此外，因为密度聚类的特性，当空间密度分布极度不均匀时，聚类结果较差。