Srt结题报告Srt结题报告.doc

SRT结题报告 研究背景及意义 现实生活中存在着各式各样的网络结构，对网络结构的研究能够解决人们生活中很多的问题。在各类现实的网络结构中，人们对社交网络存在更大的兴趣，在这方面从事了大量的研究工作。人类社会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。许多真实系统都可以用网络的形式加以描述, 一个典型的网络是由许多节点与链接节点之间的边组成的. 节点代表系统中的个体, 边则表示节点之间的作用关系。真实网络的普遍存在, 促使来自不同学科领域的科学家共同致力于复杂网络的研究。复杂网络的研究可以使人们更好的了解现实世界的复杂系统, 为设计具有良好性能的网络提供依据。 现状分析 目前很多学者针对不同类型的Web社区提出了不同的算法。在传统的Web社区发现中，一般将网络结构表示为图的形式，图中的结点表示Web网页，边表示网页间的连接关系，如Kleinberg提出的HITS算法、PageRank算法、Kummar等提出的拖网算法。以上这些算法取得了成就，但由于大多基于链接结构分析或者主题分析，容易产生结果漂移，且大多只能识别单一社区，无法挖掘更真实的信息。针对新型社交网络，学者们也提出了一些有哪些信誉好的足球投注网站方法，典型的有Kernighan算法、基于Laplace图特征值的谱平分法、利用分级聚类概念提出的分裂算法和凝聚算法。这些算法或需要丰富的先验知识，或是时间复杂度高，或者是对网络规模敏感。 研究内容 3．1复杂网络及其基本性质 一个具体的网络可抽象为一个由节点集合 V 和边集合 E 组成的图 G = (V,E)。节点数记为 n = |V |，边数记为 m = |E|。E 中每条边都有 V 中一对点与之相对应。如果任意点对 (i, j) 与 (j, i) 对应同一条边，则该网络称为无向网络 (undirected network)，否则称为有向网络 (directed network)。如果给每条边都赋予相应的权值，那么该网络就称为加权网络 (weighted network)，否则称为无权网络 (unweighted network)。真实世界中复杂网络具有三个基本性质：包括小世界性质，无标度性质以及社团结构性质。 3．1．1小世界性质 20 世纪 60 年代美国哈佛大学的社会心理学家 Stanley Milgram 的通过一些社会调查后给出了一个推断：地球上任意两个人之间的平均距离是6。也就是说，平均中间只要通过 5 个人，你就能与地球上任何一个角落的任何一个人发生联系。这就是小世界效应(small-world effect)。具体地说，一个网络称为是有小世界效应的，如果对于固定的网络节点平均度 ?d?，平均路径长度 l 的增加速度至多与网络规模 n 的对数成正比。如果考虑网络上信息或任何事物的传播，小世界效应意味着在多数真实世界网络中传播是非常快速的。 3．1．2无标度性质 网络中节点的度的分布情况可用度分布函数 (degree distribution function)P (d) 来描述, 它表示的是一个随机选定的节点的度恰好为 d 的概率。许多网络的度分布可以用幂律 (power law) 形式来更好地描述。幂律 (power law) 分布也称为无标度 (scale-free) 分布，具有幂律度分布的网络也称为无标度网络，这是由于幂律分布函数具有无标度性质。在一个度分布为具有适当幂指数 (通常为 2 ≤ γ ≤ 3) 的幂律形式的大规模无标度网络中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点。 3．1．3社团结构性质 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质, 即社团结构 (community structure)。也就是说，整个网络是由若干个“群 (group)”或“团 (cluster)”构成的。每个社团内部的节点之间的连接相对非常紧密，但是各个社团之间的连接相对来说却非常稀疏。 3．2研究复杂网络社团结构的主要算法 3．2．1传统算法 复杂网络社团结构划分的传统算法主要包括图形分割法、分级聚类方法、k-means型方法和谱方法。这些算法或需要丰富的先验知识，或是时间复杂度高，或者是对网络规模敏感。所以对于这几类算法大部分我们只是定性的了解没有做更加深入的研究。我们只选择了分级聚类方法中在web发现领域具有重要意义的两个算法：GN算法和FN算法进行了深入研究并在Matlab软件中编码测试。 GN算法首次提出了边介数概念表示复杂网络中普遍存在的社区结构，启发了其他研究者对这个问题进行深入研究。该算法采用的启发式规则为：社区间链接的边介数应大于社区内链接的边介数。其中每个链接的边介数被定义为网络中经过该链接的任意两点间最短路径的条数。算法通过反复计算边介数，识