文献综述范例--研究类

《文献综述范例--研究类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杭州电子科技大学毕业设计（论文）文献综述毕业设计（论文）题目信任网络的社区挖掘分析文献综述题目社区挖掘算法分析学院软件工程学院专业软件工程姓名吕进班级09106531学号09109061指导教师邱洪君1.前言近年来,社会网络分析作为知识发现与数据挖掘领域中的热点问题,受到广[2,3]泛关注。从数据挖掘的观点来说,一个社会网络就是用图表示的一个异种的和多关系的数据集,用节点代表被研究的个体,边代表个体之间存在的某种关[15]系。社区结构是社会网络的常见特征,表现为组内节点之间连接紧密,组间节[13]点之间连接松散。社区识别是识别社会网络中特定的节点归属于哪个社区;社区发现是从给

2、定的社会网络中抽取出社区,目前已成为数据挖掘领域研究的热点,广泛应用于疾病的传播、供电网格、WorldWideWeb、科学家的合作及文献[14]引用和恐怖分子网络等方面,产生了一些经典的方法,如层次聚类算法、边聚[7][14]类系数算法、GN算法和基于二部图的Web社群挖掘算法等.社区对理解社会网络的结构有重要意义,因此社区挖掘成为社会网络分析的重要研究方向之一。2.主题Kernighan-Lin算法[12]Kernighan-Lin算法是一种试探优化法。它是一种基于贪婪算法原理将网络划分为两个大小已知的社团的二分法。其基本思想就是为网络的划分引进一个增益函数Q,定义为两个社

3、团内部的边数减去连接两个社团之间的边数,然后寻找使[14]Q值最大的划分方法。整个算法可描述如下:首先,将网络中的节点随机地划分为已知大小的两个社团。在此基础上,考虑所有可能的节点对,其中每个节点对的节点分别来自两个社团。对每个节点对,计算如果交换这两个节点可能得到的Q的增益ΔQ=Q交换后-Q交换前,然后交换最大的ΔQ对应的节点对,同时记录交换以后的Q值。规定每个节点只能交换一次。重复这个交换过程,直到某个社团内所有的节点都被交换一次为止。需要注意的是,在节点对交换的过程中,Q值并不一定是单调增加的。不过,即使某一步的交换会使Q值有所下降,仍然可能在其后的步骤中出现一个更大的

4、Q值。当交换完毕后,便找到上述交换过程中所记录的最大的Q值。这时对应的社团结构就认为是该网络实际的社团结构。但是Kernighan-Lin算法要求必须事先知道该网络的各个社团的大小，否则，就可能不会得到正确的结果。Kernighan-Lin算法的这个缺陷使得他在实际网络分析中难以应用。这个问题到目前还是没有得到解决。GN算法Girvan和Newnan于2001年提出一个基于边介数的社团发现算法,该算法是[14]一种分裂方法,依据边介数把不属于任何社团的边逐步删除。边介数定义为网络中经过每条边的最短路径数目,即所有最短路径通过该边的次数之和为该边的边介数。它为区分一个社团的内部

5、边和连接社团之间的边提供了一种有效的度量标准。按照复杂网络中社团的定义,社团内部结点之间联系紧密,而社团之连接比较松散。所以连接社团之间的边比社区内部的边有更大的边介数。通过逐步移去这些边介数较高的边就能够把它们连接的社团分割开来。GN算法的基本步骤如下:(1)计算网络结点中所有边的介数;(2)找到介数最高的边并将它从网络中删除;(3)重复执行步骤(1),(2),直到每个节点就是一个退化的社团为止。GN算法弥补了一些传统算法的不足,但是,在不知道社团数目的情况下,GN算法也不知道这种分解要进行到哪一步终止。为解决这个问题,Newman等人引进了一个衡量网络划分质量的标准——模

6、块性(Modularity)。它是基于同类匹配(AssociativeMixing)来定义的。考虑某种划分形式,它将网络划分为k个社团。定义一个k×k维的对称矩阵e=(e),其中ij元素e表示网络中连接两个不同社团的节点的边在所有边中所占的比例;这两个ij节点分别位于第i个社团和第j个社团。注意,在这里所说的所有的边是在原始网络中的,而不必考虑是否被社团结构算法移除。因此,该模块性的衡量标准是利用完整的网络来计算的。经过Newman等人的改进以后，GN算法必以来多余的信息来判断得到的社团结构是否具有实际意义。而是可以直接从网络的拓扑结构来进行分析。但是该3算法的耗时比较大，为

7、O(n)，因此它仅仅使用于中等规模的大型网络（n=10000以下）。为了解决这个问题，人们在GN算法的基础上提出了很多种改进的算法，主要包括采用节点集的GN算法、自包含GN算法、极值优化算法等。Newman快速算法GN算法虽然准确度比较高,分析社团结构的效果比原有的一些算法也要好得多,但是它的算法复杂度还是比较大,因此仅仅局限于研究中等规模的复杂网络。现在,对于Internet、WWW和电子邮件网络等的研究越来越多,而这些网络通常都包含几百万个以上的节点。在这种情况下,传统的GN算法就不能满足要求。基于