基于谱聚类的社区发现算法实现研究(2)
在复杂网络中通过分析网络的拓扑学结构信息，从而将网络中存在的节点分门别类为各个节点组，这样的过程被称之为社区发现。社区发现和图划分的相似之处在于处理对象都是抽象出的网络[1]。将复杂网络按照既定的规则或者条件进行分割，被称作图划分。图划分的规则或条件往往是划分分量的个数、大小等。寻找在给定网络中的子网络是社区发现的目标。而这个子网络的特点是，内部的节点互相关系紧密而与此网络外部的节点关系疏远。当对社区结构进行划分、切割的时候，社区发现的过程强调的是找出该网络中固有的划分而不是根据特殊的规则或条件来划分。社区发现过程与聚类处理过程都允许组或者类之间的重叠或者是嵌套，这是它们十分相像的一点。因此，当进行对一个复杂网络的社区发现时，通常情况下是可以使用聚类算法的。
社区发现有助于其他社会计算任务的实现，并被应用于许多实际问题的求解中。谱聚类算法源于图的划分问题[2]。图的划分的目标就是找到一种切割方法，使得切割最少的边就可以将结点分割为不相交的集合。本课题使用谱聚类方法实现社区发现，所要进行的步骤是：当被给定某一个网络的时候，可以构建一个效用矩阵。根据目标函数构建效用矩阵M，计算M的前k个特征向量得到软社区指标矩阵，应用k均值聚类算法得到社区划分。本设计拟通过分析人造数据以及Zachary柔道俱乐部网络来验证本方法可以有效地发现社团结构。
1.2 国内外研究现状
1.3 聚类分析
1.3.1 聚类分析简介
聚类分析简称聚类，是一个将数据对象划分为子集的过程[4]。每个子集称为“簇”，并且与同一个簇内的对象是相似的，但同时簇与簇间的对象却是相异的。
一个聚类是由聚类分析算法产生出来的簇的集合。它的产生和算法有关，在全部一样的数据集中，不一样的聚类方法或许会产生不一样的聚类。这种划分是通过聚类算法来进行的，并不是通过人来进行的。聚类非常有用，因为它可能会产生事先无法被人发现的新的群组。
聚类分析是统计数据学底下的一部分，主要是一种基于距离的分析。有很多种方法，比如K-means，K-medoids和一些别的方法，它们都已经作为工具被加入到了许多很有用的软件包或者是系统中。比较著名的有S-Plus、SPSS(Statistical Product and Service Solutions)以及SAS(Statistical Analysis System)等。
1.3.2 研究现状
聚类分析是数据挖掘中的重要研究内容之一[5]。聚类分析是一个非常关键的用于分析数据的技术，被很多开发人员所广泛的使用。人们使用聚类，来区分稀疏或者稠密的地方，发现全部的形式，以及各类不同数据属性中可能非常有意思的联系。聚类的用途十分的大，可以应用于商业、农业、地理信息系统中。同时，在其他算法（如关联分析）的预处理中，聚类分析算法也被用作重要的一部分，这使得这些算法的使用效率有了显著的提高。聚类算法的一个突出的优点就是它可以自动地去探测发现分组，所以它有的时候又被称为自动分类。在某些应用里面，聚类被使用于离群点检测，比如信用卡的诈骗以及有关电子商务的犯罪活动监控中。这么多的应用，使得在数据挖掘领域里面聚类分析是一个特别受瞩目的焦点。
数据挖掘领域谱聚类分析的方法并不少，但是目前集中的问题在于如何找到一种合适且高效的方法来对大型数据库进行谱聚类的分析。研究主题包括聚类方法的可伸缩性、对复杂形状以及各种数据的类型聚类的有效性上，另外还有一些高文的聚类技术，以及针对大型数据库中的混合数据的聚类方案[6]。