论文部分内容阅读
近年来随着复杂网络的发展,在现实世界中复杂网络无处不在,从因特网到万维网,从航空路线到大型电力网络,从超大规模集成电路图到人际关系网等等。随着近年来对复杂网络性质的物理意义和数学特性的深入研究,人们发现许多实际网络都具有一个共同的性质,即社区结构。所以在复杂网络中自动搜寻或发现社区具有重要的实用价值,发现这些网络中的社区有助于更加有效的理解和开发这些网络。特别是Internet的迅速发展,互联网上的信息量越来越庞大,它已成为全球最大的信息发布库。目前互联网上的信息纷繁复杂,如何对其内容进行分析从而挖掘出人们所需要的内容这一问题亟待解决。社区发现技术可在一定程度上解决这个问题,不仅节省了用户的时间,而且提高了分析的效率。因此,将此技术用于Web挖掘具有重要的理论意义和实用价值。本文将从理论、算法和实现等三个方面研究社区发现技术。但是,由于我们事先不知道到底应该将网络分为多少个社区,这使得这一问题极具挑战性。本文首先阐述了社区发现技术基本理论,对现有的典型社区发现算法作了分析,例如,Belief Propagation算法、k-means(k-centers)算法、Kernighan-Liu算法、谱平分法、W-H算法、GN算法、派系过滤算法等,并研究了各个算法的核心思想,算法复杂度,以及适用范围等。我们将社区发现经典的GN算法加以实现,并用数据集进行实验。此外,我们还实现了Frey提出的Affinity Propagation(AP)算法,通过编程和实验分析,对AP算法的算法思想,及算法复杂度有了深刻的认识和理解,并在原有AP算法的基础上,做了一些改进。并且还利用了社会网络中的联系关系设计了一个新的社区发现方法,称之为联系关系算法。并通过实验结果对这三种算法进行分析研究,为以后的进一步研究做准备。