基于图压缩的重叠社区发现技术研究

来源 :东北大学 | 被引量 : 0次 | 上传用户:s5871212
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,寻找复杂网络中的社区结构已经成为复杂网络中研究的热点,社区发现问题也因此成为近年复杂网络领域中的热门问题。由于现实存在的网络社区通常并不是绝对彼此独立的,而是彼此重叠的,并且重叠社区可以反映更加真实的网络结构,因此关于重叠社区发现问题的讨论也成了复杂网络中的研究重点。本文先从社区发现的研究背景、意义出发,通过介绍基本理论知识,引出社区结构的概念,随后综述了近年来社会网络中社区结构的研究成果,介绍了目前主要的重叠社区发现算法,并对它们的优缺点进行了对比与分析。针对大多数现有的重叠社区发现算法在应用大规模网络时效率较低的问题,本文基于图压缩提出一个新的重叠社区发现算法,能在保证准确度的前提下,数量级地提高在单机上处理的网络规模,进而发现重叠社区。首先,通过基于图压缩的社区结构表示模型——凝聚图,来对网络进行无损压缩。然后,在凝聚图上基于种子迭代的思想,通过不断优化社区适应度函数来对种子进行扩展。当种子的社区适应度达到最大时,便形成社区。最后,再将相似度很高的社区进行合并,得到最终的重叠社区结果。由于压缩后的凝聚图大大降低了网络复杂程度,并且能在一定程度上减少重复计算,因此这种方法可以大大提高计算效率。本文实验部分从算法的有效性、效率以及重叠节点的准确性三个方面来对算法进行分析和验证。实验证明,本文提出的算法不但可以使发现的重叠社区趋于合理化,而且大大提高了单机上能够处理的网络规模,使有效解决大规模网络上的重叠社区发现问题成为可能。
其他文献
地方政府职能转变和机构改革,事关我国经济持续发展和转型升级,是党和国家改革开放事业大局的重要内容,也是深化行政体制改革的重要组成部分。改革的成功与否,不仅关系到中央
作为一种高效节水灌溉技术,近年来微灌技术在我国的应用越来越广。过滤器是微灌系统中不可或缺的关键设备之一,对微灌系统的安全高效运行有重要作用。目前的微灌过滤器在使用中仍存在一定不足,如网式过滤器对絮状杂质过滤效果差、叠片过滤器水头损失大,而串联使用的过滤器连接件较多,占据空间大等。在此背景下,本文设计了一种复合网式过滤器,围绕该过滤器的结构设计、样机性能试验及CFD数值模拟分析等方面展开了研究,主要
近几年,PPP模式在国家积极的推广下得到快速发展,盘锦市为全力推进辽东湾新区新港及配套设施建设,紧紧抓住PPP模式发展的“窗口期”,在此背景下,盘锦市体育中心PPP项目应运而生,项目的成功落地,有效盘活了体育场馆的存量资产,置换出政府投入,缓解财政压力,但由于该项目是盘锦市较早签约落地项目,政府缺少相关经验,因此在履行责任、职能发挥以及项目监管等方面还存在诸多问题。本文以委托代理理论、公共物品理论
油菜素类固醇(Brassinosteroids,BRs)是一类新发现的植物生长调节物质,在植物生长发育过程中扮演极其重要的角色,包括种子萌发、下胚轴的伸长、维管束的分化、光形态建成以及
植物的生长发育过程以及各种胁迫反应离不开各种酶的参与。GSNOR(S-nitrosoglutathione reductase)是亚硝基谷胱甘肽(GSNO)的还原酶。GSNOR能够高效特异的催化GSNO的还原反应
本文以分布在甘肃省西北部荒漠地区的荒漠伯劳指名亚种(Lanius isabellinus isabellinus)为研究对象,在2010-2014年对荒漠伯劳的卵大小与窝卵数、卵大小与产卵顺序之间的关系
自1965年Zadeh提出模糊集FS (Fuzzy Sets),以FS为基础概念而形成的模糊数学在理论研究和应用研究上均有长足发展,已经成为当今数学的一个重要分支。模糊集合概念提出后,模糊
本文采用磁控溅射方法在单晶硅衬底和玻璃衬底上制备了Ni-Mn-In-Co磁性形状记忆合金薄膜,采用了扫描电子显微观察、原子力显微镜表面形貌分析、X射线衍射分析和示差扫描热分
在植物适应多种复杂的外界环境中,LRR-RLKs(富含亮氨酸重复序列类受体激酶)在感受细胞外信号并启动细胞内多种反应等方面发挥着极其重要的作用。拟南芥Somatic Embryogenesis
血栓类疾病是当今致死率、致残率最高的疾病之一,严重威胁人类的生活和健康。血栓类疾病的治疗已经成为当今医学界研究的重点问题之一。目前,溶栓药物已经发展至第三代,主要