符号网络和异构网络中的社区检测方法

摘要

近年来,复杂网络已经成为备受关注的研究领域,越来越多的研究人员投身于对复杂网络的研究。研究发现,很多复杂网络都具有社区结构这一特性。所以,如何能有效地找到实际社会网络中的社区结构,是近年来对复杂网络研究的重点之一。其中,大部分现有的研究都是检测传统无符号、非异构网络的社区结构方法,即网络中边的符号都为正,或网络中的节点种类单一。而在真实社会网络中,节点之间不仅有表示“友好、联盟”等的正向关系,而且有表示“敌视、竞争”等的负向关系。这种网络中既存在正向关系又存在负向关系的网络被称为符号网络(Signed networks, SNs)。除此之外,还存在多种类型节点的网络,称为异构网络(Multi-dimensional networks,MDNs)。本论文主要研究符号网络和异构网络中的社区检测问题。基于多目标进化算法( Multi-Objective Evolutionary Algorithm, MOEAs)、聚类算法(Cluster Algorithms, CAs)和遗传算法(Genetic Algorithms, GAs),提出了一种符号网络的社区检测方法和两种异构网络的社区检测方法。下面是本论文的主要工作:
　　1.改进了原始的模块度函数(Q),将其扩展为评价符号网络社区结构质量的两个指标Q+和Q-。改进后的Q+和Q-保留了原始Q函数的特性,能够很好的应用于检测符号网络的社区结构。基于Q+和Q-两个目标,提出了基于多目标进化算法的符号网络社区检测方法(MOEA-SN)。实验中采用了4个基准符号网络和随机生成的符号网络对MOEA-SN的性能进行了测试,结果表明MOEA-SN是一种有效的符号网络社区检测方法。
　　2.设计了一种基于聚类方法的异构网络社区检测方法(CA-MDN)。根据马尔科夫随机游走的模型计算网络中节点之间的相似性,并以此计算社区间的相似性,作为聚类方法中的相似性度量,并使用了一种局部模块度增量来确定聚合聚类的停止标准。实验中,采用了1个真实社会网络和随机生成的异构网络对CA-MDN的性能进行了测试,结果表明CA-MDA是一种有效的异构社会网络社区检测方法。
　　3.提出了一种基于遗传算法的异构网络社区检测方法(GA-MDN),改进了模块密度函数D以用于衡量异构网络的社区结构质量,并将其作为遗传算法的适应度函数进行优化;改进了一种带局部搜索的变异算子,避免进化陷入局部最优,并提高了算法的效率。采用了1个真实社会网络和随机生成的异构网络对GA-MDN进行了实验分析,结果表明GA-MDN是一种有效的异构网络社区检测方法,能够准确检测出异构网络的社区结构,并且获得较高的正确率。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 符号网络和异构网络中的社区检测问题

1.3国内外研究现状

1.4 本文工作及论文章节安排

第二章基于多目标进化算法的符号网络社区检测方法

2.1引言

2.2基于多目标进化算法的符号网络社区检测方法

2.3仿真实验及结果分析

2.4本章小结

第三章 基于聚类算法的异构网络社区检测方法

3.1引言

3.2基于聚类算法的异构网络社区检测方法

3.3仿真实验及结果分析

3.4本章小结

第四章 基于遗传算法的异构网络社区检测方法

4.1引言

4.2基于遗传算法的异构网络社区检测方法

4.3仿真实验及结果分析

4.4本章小结

第五章总结与展望

5.1本文工作总结

5.2未来工作的展望

致谢

参考文献

作者研究生期间的科研成果

作者研究生期间参与的科研项目