基于网络中节点间紧密度的层次聚类社区发现算法

《基于网络中节点间紧密度的层次聚类社区发现算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、在网络理论研宄屮，数量巨大的节点以及节点之间复杂的交互关系构成了复杂网络和复杂网络的网络结构。用数学语言表达，即一个图有着足够复杂的拓扑结构特征［1］。复杂网络中的一种普遍现象就是社区现象，它表达了社区中的个体具有某一方面共同特征的性质。社区发现在很多学科有重要应用，如在计算机学科中，增强网络销售功能、提高网络服务质量等；在社会学中，发现动物社会组织结构、揭示政府职能构成和运行方式、发现某一领域的科学家群组等；在生物学领域功能基因聚类等。近年来，科学家们提出了关于社区发现的很多新方法。本文首先介绍了几种常见的复杂网络以及其的特性。在此基础上介绍了基于迭代二分法(

2、IterativeBisection)的Kernighan—Lin算法、i普二分法(Spectralbisection),棊于去边方法的G-N算法、Radicchi算法，层次聚类法(HierarchicalClustering)和W-H算法。分析了这些算法的时间复杂度等因素，指出了它们的优势和不足，并且还给出了这些算法的适用范围。本文的主要研允内容是基于网络中节点间紧密度的层次聚类社区发现算法。在层次聚类算法中，传统的节点间紧密度的计算方法主要是基于网络的拓扑结构，如余弦相似性(cosinesimilarity)、欧拉距离和皮尔逊系数(Pearsoncorrel

3、ationcoefficient)等。本文节点间相似度的计算是基于节点之间信息交流来往的频率，即节点间边权值的大小来衡量节点的紧密度。两个节点之间交流越频繁，说明这两个节点的紧密度就越高，同属于一个社区的可能性就越大。将计算出来的紧密度值存储与紧密度二叉堆中。同时把节点之间的相似度计算扩展到社区之间，更新紧密度二叉堆中的值，利用二叉堆中的值，合并社区，直到社区的合并结果满足某一条件为止。实验表明，该方法能较好且合理的发现社区结构。关键词：社区发现；复杂网络；社区结构；层次聚类第1章绪论1.1研究背景和意义最近几年，人多数国家对复杂网络的研究都趋于狂热。随着计算机

4、对数据的存储和处理的能力越來越强，以及人规模系统的数据库的兴起，使我们真正认识了网络的特征数据，发现真实网络既不是规则的，也不是随机的，而是复杂的，并II呈现一定规律的。在信息时代，网络的社区发现存在更加普遍，发现技术应用更加方便，其服务价值和商业价值更人。研究在线社会网络离不开社会网络的分析方法，尤其是社区可为信息推送、个性化服务等提供基本数据。所以，在复杂网络屮进行社区发现意义非比寻常。大量与社区发现相关的论文都被刊登上丫《PhysicalReviewE》《PNAS》《Nature》《Science》等世界顶级的学术期刊，WWW、CIKM、SIGIR、SIG

5、KDD、ICDM、ECMLPKDD等著名的工作组以及越來越多的国际会议都在研究探讨社区发现的问题。社区发现技术在数据挖掘和探查性分析屮是一种非常重要的技术。研究大型复杂网络，更加关注搜索和发现潜在的网络社区，这是研究中更重要的方面。主要涉及的领域有：市场学、数据挖掘、社会网络分析、统计学、机器学习、空间数据库技术和生物学等领域，其应用非常广泛。在线社会网络相比其他在线网络而言，则是更能影响人们现实生活关系的网络。心理学家和社会学家研宄人尺度社会网因其发展也有了较人的提高，对他们在这些网络屮寻找新形式的集体或个人行为有许多帮助。社会学家分析非在线社会网络会借鉴在线

6、社会网络，或者研究在线社会网络在新的社会行为特征，参考在线社会网络拓扑结构研究的基础。信息社会的一些急需回答的问题在社会网络分析的一些初步应用上有了答案。例如：Bany在其文献上用社会网络分析的思想和方法研究了现代社会中人际关系的变化特征。在线社会网络的研究有跟现实社会网络密切相关的动力学，网络演化规律，结构特性等方面的主题。最近几年，关于复杂网络的研宂屮，复杂网络社区发现算法的研究设计己成为重中之重。首先，社区发现技术的实用价值非常重大。例如，在社会网络屮，社区代表是真实的社会团体，社会团体内部的每个人都具有相同或类似的背景和兴趣；在引文网络中，若干个论文的集

7、合组成一个社区，II每个社区中的论文代表的是一个相同的主题；在万维网屮，社区发现的结果是一些网站的集合，但是每个网站集合讨论主题都是相同或类似的[2][3];在电子电路网络或者生物化学网络中，社区发现的结果是一些功能单元，同一类功能单元被划分到同一个社区中[4]。发现这些网络中的社区不仅为个性化服务、信息推送，提供基本的理论根据，而且有助于加深我们有效的理解和帮助这些网络的开发。在如今的信息时代，随着越来越普遍存在的社区，以及越来越方便的发现技术，社区发现技术的商业价值更是越来越大。其次，社区发现技术的发展在一定程度上影响了对复杂网络的研允。在实际网络世界屮，很

8、多处都有复杂网络，它对社