Srt结题报告.doc

SRT 结题报告一、研究背景及意义现实生活中存在着各式各样的网络结构, 对网络结构的研究能够解决人们生活中很多的问题。在各类现实的网络结构中, 人们对社交网络存在更大的兴趣, 在这方面从事了大量的研究工作。人类社会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。许多真实系统都可以用网络的形式加以描述, 一个典型的网络是由许多节点与链接节点之间的边组成的. 节点代表系统中的个体, 边则表示节点之间的作用关系。真实网络的普遍存在, 促使来自不同学科领域的科学家共同致力于复杂网络的研究。复杂网络的研究可以使人们更好的了解现实世界的复杂系统, 为设计具有良好性能的网络提供依据。二、现状分析目前很多学者针对不同类型的 Web 社区提出了不同的算法。在传统的 Web 社区发现中, 一般将网络结构表示为图的形式, 图中的结点表示 Web 网页, 边表示网页间的连接关系,如 Kleinberg 提出的 HITS 算法、 PageRank 算法、 Kummar 等提出的拖网算法。以上这些算法取得了成就, 但由于大多基于链接结构分析或者主题分析, 容易产生结果漂移, 且大多只能识别单一社区,无法挖掘更真实的信息。针对新型社交网络,学者们也提出了一些搜索方法, 典型的有 Kernighan 算法、基于 Laplace 图特征值的谱平分法、利用分级聚类概念提出的分裂算法和凝聚算法。这些算法或需要丰富的先验知识, 或是时间复杂度高, 或者是对网络规模敏感。三、研究内容 V 和边集合 E 组成的图 G= (V,E) 。节点数记为 n= |V|, 边数记为 m= |E|。E 中每条边都有 V 中一对点与之相对应。如果任意点对(i, j)与(j, i) 对应同一条边, 则该网络称为无向网络(work) , 否则称为有向网络(work) 。如果给每条边都赋予相应的权值,那么该网络就称为加权网络(work) ,否则称为无权网络(work) 。真实世界中复杂网络具有三个基本性质:包括小世界性质,无标度性质以及社团结构性质。 小世界性质 20 世纪 60 年代美国哈佛大学的社会心理学家 Stanley Milgram 的通过一些社会调查后给出了一个推断: 地球上任意两个人之间的平均距离是 6。也就是说, 平均中间只要通过 5 个人,你就能与地球上任何一个角落的任何一个人发生联系。这就是小世界效应(small-wor ld effect) 。具体地说, 一个网络称为是有小世界效应的, 如果对于固定的网络节点平均度?d?,平均路径长度 l 的增加速度至多与网络规模 n 的对数成正比。如果考虑网络上信息或任何事物的传播,小世界效应意味着在多数真实世界网络中传播是非常快速的。 无标度性质网络中节点的度的分布情况可用度分布函数(degree distribution function)P (d) 来描述, 它表示的是一个随机选定的节点的度恰好为 d 的概率。许多网络的度分布可以用幂律(power law) 形式???ddp)( 来更好地描述。幂律(power law) 分布也称为无标度(scale-free) 分布, 具有幂律度分布的网络也称为无标度网络, 这是由于幂律分布函数具有无标度性质。在