复杂网络中社区发现及进化的研究.pdf

摘 要 摘 要 伴随着互联网的快速发展，Web 上出现了大量的社区。社区可以代表 Web 的社会 活动，将 Web 组织成社区的形式，可以使用户了解互联网中资源的组织形式和信息的 发展趋势，而且可以通过识别和区分社区达到有效组织网络层次的目的，因而社区发现 技术成为目前的一个研究热点。 在实际的应用过程中，现有的社区发现方法存在两个问题，第一，仅考虑社区中结 点之间的连接关系，而忽略了结点所代表的实体的内容；第二，没有考虑网络的动态性， 忽略了社区在进化过程中的变化。针对以上不足，本文面向互联网中的网页，提出了一 种新的社区发现算法，并在此基础上对社区的进化过程进行研究。主要工作如下： 考虑到不同网页表达的内容有所不同，本文提出基于网页内容相似度和链接关系的 社区发现算法。该算法利用改进的余弦相似度公式计算网页与主题的相似度。随后，根 据网页之间的超链接，将存在链接关系而且在内容上相关的网页挖掘出来组成关于某一 主题的社区。该算法不仅关注了网页之间存在的链接关系而且考虑了网页在内容上的相 似性，从而保证了社区在内容和结构上的完整性。 在社区中，可能存在这样的结点，它们之间的联系比其他结点更加紧密，于是形成 了紧密度更高的小社区，社区出现了层次结构。针对社区的这一结构特点，本文引入社 区层次结构的概念，以社区中结点之间的紧密度为依据将社区分层，分析社区的层次结 构。最后，对在社区进化过程中可能出现的类型进行形式化定义，同时给出度量准则， 并以层次结构为基础分析网络社区的进化过程，反映社区在进化过程中主题变化的趋势 和特点。 实验结果表明，本文提出的社区发现算法可以有效的发现复杂网络中的社区结构， 同时可以很好的反映社区的进化过程。 关键词 复杂网络 社区发现 社区层次结构 社区进化 I Abstract Abstract With the rapid development of Internet, the Web, which have been a lot of communities. The communities can represent the Webs social activities. Web will be organized into communities which allow users to understand the knowledge of information and the development trend of organizational structure of the Web, and can achieve the purposes of organizing the network level by identifying and distinguishing the communities. The technology of community identification that becomes a research hotspot. In practice, existing community identification methods are being two major problems to be solved. First, considering only the community connections between nodes, while ignoring contents of the entities represent by nodes; second, ignoring the Dynamic of the network. To overcome the above shortcomings, proposing a new algorithm for community i