论文部分内容阅读
现实世界中,诸多复杂系统都可以由一个网络来进行抽象,如计算机邮件网络,生物学中的蛋白质网络,基因表达网络等。真实世界中的复杂网络普遍存在一些统计特征,例如“小世界网络特性”,“无标度特性”,“社区结构特性”等。其中社区结构的挖掘对于理解复杂网络的拓扑结构,分析复杂网络的功能,挖掘复杂网络隐藏的规律以及预测复杂网络未来的行为变化等都具有非常重要的理论意义和应用背景。近十年来,来自数学、物理学和统计物理学的研究者已经提出许多复杂网络社区挖掘方法。这些算法有传统的基于图划分的社区挖掘算法,有基于模块化质量函数优化的方法,动力学方法,还有基于统计推理的块模型方法等。其中块模型方法因为其能反映对复杂网络更基本的认识,并可用于挖掘多种社区结构正成为研究者们的研究热点。本文基于主动学习、块模型和吉布斯采样等方法,对社区挖掘问题进行研究,提出了相应的社区挖掘算法。本文的主要工作概况如下:(1)改进了一种基于随机块模型的主动学习策略下的网络社区挖掘方法,提出了新的高效方法。通过将原策略中吉布斯采样方法更改为贪心吉布斯采样方法,并通过按照各个局部极值的概率大小对原分布进行拟合,降低了计算开销,在保证社区分类正确性的前提下,很好的提升了算法的效率。(2)在以上工作的基础上,对主动学习策略进行了改进。原随机块模型通过对网络结点标签的主动学习来进行社区挖掘,而在许多真实网络中,更容易获得的知识是结点之间的边的标签:一条边链接的两个结点是否属于同一个社区。通过将原随机块模型中对网络结点标签的主动学习更改为对网络中边的主动学习,提高了算法的一般性,使得算法适用于更多的真实网络。(3)在人工合成网络和真实世界网络上对本文提出的算法进行了实验验证,并与原方法在准确性和计算效率上进行了对比分析。实验表明:本文提出的改进算法在保证较高网络社区挖掘准确率的前提下,大幅提高了算法的运行效率,计算时间远低于原随机块算法;本文提出的对边的主动学习策略,提高了算法的普适性,因而具有更好的算法实用性,适用于更多真实世界中网络。