论文部分内容阅读
近年来，网络的社区结构得到了广泛而深入的研究。传统的社区发现算法针对的是数据间的关联特性，而忽略了数据的固有属性。然而，结合数据的社区特性和固有属性挖掘得到的离群点可解释性更强，社区离群点就是其中之一。现有的社区离群点挖掘算法针对传统无重叠社区采用概率模型进行挖掘。为了达到更准确的社区划分，社区间的重叠现象成了社区离群点检测中不可忽略的一部分。因此，优秀的社区离群点检测算法要做到准确的社区划分和离群点检测。为了评估社区划分的结果，Newman等提出的NG模块度作为衡量网络划分好坏的标准也引起了学者的广泛关注。但是NG模块度在应用上存在着分辨率限制的缺陷，即通过模块度优化不能检测到规模较小但结构显著的社区。
因此，挖掘社区离群点首先需要:1）克服分辨率极限问题，以达到更准确的社区划分;2）结合网络的社区特性和对象的固有属性，在重叠社区中挖掘到更准确的社区离群点。论文的主要工作如下:
(1)提出模块密度的概念，即模块内平均边数与总边数的商，并在此基础上重新构造了重叠模块度函数—CQ来评价社区的划分，从而解决NG模块度的分辨率限制、不能分辨小于一定规模的社区的问题。理论方式证明，提出的重叠模块度克服了NG模块度函数的分辨率极限问题，经典网络和真实数据集的实验验证了构造的模块度的准确性和有效性。
(2)提出基于重叠模块度的社区离群点挖掘算法OCODA(Overlappingcommunityoutlierdetectionalgorithm)以克服现有社区离群点检测算法由于忽略社区间的重叠现象而导致社区离群点划分不准确的问题。两个对象属性值的偏差程度越大，对象间的相似度越小，属于同一社区的概率也越小。据此，提出属性偏离程度和属性贡献因子，并分别引入到相似度和模块度的计算中，从而使其适用于社区离群点挖掘。OCODA首先根据节点间的相似度对节点进行聚类，并根据固有属性的偏离程度进行离群点判断，若属性偏离程度高于阈值λ，则将此节点划分为社区离群点，然后根据重叠模块度的变化进行迭代聚类，若前后两次的重叠模块度之差大于0，则迭代终止，最终选取重叠模块度最大的作为划分结果，并得的相应的社区离群点。实验结果表明，提出的算法不仅能准确地发现重叠社区而且能有效地检测社区离群点。
(3)为验证本文提出算法的有效性，采用面向对象的设计思想，利用C++语言在VisualC++6.0开发平台上，设计并实现一个基于重叠模块度的社区离群点检测的原型系统，并对系统进行测试，测试结果表明系统运行良好，达到预期的目标。