文档介绍：河北大学
硕士学位论文
复杂网络中的社区发现及进化研究
姓名:云颖
申请学位级别:硕士
专业:计算机软件与理论
指导教师:袁方
2011-06
摘要
摘要
伴随着互联网的快速发展,Web 上出现了大量的社区。社区可以代表 Web 的社会
活动,将 Web 组织成社区的形式,可以使用户了解互联网中资源的组织形式和信息的
发展趋势,而且可以通过识别和区分社区达到有效组织网络层次的目的,因而社区发现
技术成为目前的一个研究热点。
在实际的应用过程中,现有的社区发现方法存在两个问题,第一,仅考虑社区中结
点之间的连接关系,而忽略了结点所代表的实体的内容;第二,没有考虑网络的动态性,
忽略了社区在进化过程中的变化。针对以上不足,本文面向互联网中的网页,提出了一
种新的社区发现算法,并在此基础上对社区的进化过程进行研究。主要工作如下:
考虑到不同网页表达的内容有所不同,本文提出基于网页内容相似度和链接关系的
社区发现算法。该算法利用改进的余弦相似度公式计算网页与主题的相似度。随后,根
据网页之间的超链接,将存在链接关系而且在内容上相关的网页挖掘出来组成关于某一
主题的社区。该算法不仅关注了网页之间存在的链接关系而且考虑了网页在内容上的相
似性,从而保证了社区在内容和结构上的完整性。
在社区中,可能存在这样的结点,它们之间的联系比其他结点更加紧密,于是形成
了紧密度更高的小社区,社区出现了层次结构。针对社区的这一结构特点,本文引入社
区层次结构的概念,以社区中结点之间的紧密度为依据将社区分层,分析社区的层次结
构。最后,对在社区进化过程中可能出现的类型进行形式化定义,同时给出度量准则,
并以层次结构为基础分析网络社区的进化过程,反映社区在进化过程中主题变化的趋势
和特点。
实验结果表明,本文提出的社区发现算法可以有效的发现复杂网络中的社区结构,
同时可以很好的反映社区的进化过程。

关键词复杂网络社区发现社区层次结构社区进化
I
Abstract
Abstract
With the rapid development of , the Web, which have been a lot munities.
munities can represent the Web's social activities. Web will anized into
communities which allow users to understand the knowledge of information and the
development trend anizational structure of the Web, and can achieve the purposes of
organizing work level by identifying and distinguishing munities. The
technology munity identification that es a research hotspot.
In practice, munity identification methods are being two major problems to
be solved. First, considering only munity connections between nodes, while ignoring
contents of the entities represent by nodes; second, ignoring the Dynamic of work. To
e the above ings, proposing a new algorithm munity identification,
and analyzing munity evolution. The main work includes the following aspects:
First of all, taking into account the different pages in the express different
contents, the paper proposes an algorithm munity identification based on the Web
pages contents similarity and the link relation between the Web pages. It uses the i