基于结构粒化的社区发现方法研究

发布时间：2020-10-15 08:24

　　 现实生活中存在着各种各样由复杂系统抽象而来的复杂网络,研究和分析这些网络,能够使我们对其结构和行为有更好的认识。社区结构是复杂网络中的一个重要结构特性,它对网络的运行有着重要影响。所谓社区,即一群紧密联系的个体所形成的团体,其中社区内部的联系紧密,而社区之间的联系稀疏,如QQ、微信中的朋友圈、贴吧上某个话题论坛、科学家合作网络中的合作团体以及蛋白质交互网络中构成某一功能模块的蛋白质团体等等。挖掘复杂网络中的社区结构已成为复杂网络分析中的热门研究,对理解网络结构、分析网络行为和预测网络安全都有着极为重要的意义,复杂网络中的社区发现研究已成为一个具有重要理论意义和实际应用价值的研究课题。社区发现研究发展至今已提出很多有效算法,但随着互联网和移动终端的快速发展,数据规模的几何式扩张,很多传统算法已难以有效处理大规模复杂网络。针对这一问题,本文将粒化思想引入社区发现研究,旨在通过粒化手段压缩网络结构(网络的节点和边),缩减网络规模,从而降低问题求解复杂度。在对社区发现相关理论和算法以及粒计算相关理论知识深入研究后,本文提出两种结构粒化算法:基于局部模块度的多层粒化社区发现方法(Multilayer granulation community detection method based on local modularity,MGr-LM)和基于节点相似度的自适应粒化社区发现方法(An adaptive granulation algorithm for community detection based on nodesimilarity,AGr-NS)。通过将它们应用于8个不同类型和规模的真实世界网络数据集以验证算法的可行性和有效性,并同当前流行的多个算法进行实验对比。本文的主要工作如下:1)提出基于局部模块度的多层粒化社区发现方法(MGr-LM)。本文首先研究压缩网络的结构粒化操作,包括基于局部模块度的节点粒化操作和边粒化操作。然后通过结构粒化操作对网络进行多层次粒化,形成逐层粒化、逐层抽象的多粒度超网络,其中每层超网络对应一个粒度的社区划分(一个超点代表一个社区)。最后依据所求问题选择评价最优的粒层作为最终划分结果。在公用数据集上的系列实验结果表明,该方法能快速划分不同类型和规模的网络并获得较高质量的社区结构,且在获得更真实更有意义的社区结构方面具有明显优势。2)提出基于节点相似度的自适应粒化社区发现方法(AGr-NS)。算法MGr-LM需要获取粒化过程中的全部粒层再选择最佳结果,为了改进这一过程,使算法能够自适应揭示令人满意的粒层,本文提出一种自适应的粒化方法AGr-NS。首先计算得到网络中相邻节点间的相似度;然后通过改进的结构粒化操作自适应粒化网络,并自动收敛于满意的社区粒层;最后处理该粒层上的孤立节点,将其分配到较小的邻接社区,得到最终的划分结果。其中,粒化过程以节点相似度和基于节点相似度的网络模块度为条件启发式优化,保证划分精度的同时消除了由完全基于网络模块度优化所附带的分辨率限制问题。系列实验结果表明,所提算法AGr-NS可行且有效,可直接自适应获得与算法MGr-LM所获最佳结果的相同结果或相近结果。
【学位单位】：安徽大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
    1.3 本文研究内容与组织结构
        1.3.1 研究内容
        1.3.2 组织结构
第二章 相关理论知识
    2.1 社区发现概述
        2.1.1 复杂网络简介
        2.1.2 社区结构定义
        2.1.3 社区衡量指标
        2.1.4 社区发现的经典算法
    2.2 结构粒化方法
    2.3 本章小结
第三章 基于局部模块度的多层粒化社区发现方法
    3.1 局部模块度
    3.2 MGr-LM算法
        3.2.1 结构粒化操作
        3.2.2 MGr-LM算法流程
        3.2.3 MGr-LM算法复杂度分析
    3.3 实验设置及结果分析
        3.3.1 实验数据集
        3.3.2 参数设置
        3.3.3 实验结果与分析
    3.4 本章小结
第四章 基于节点相似度的自适应粒化社区发现方法
    4.1 节点相似性的度量
    4.2 AGr-NS算法
        4.2.1 结构粒化操作
        4.2.2 AGr-NS算法流程
        4.2.3 AGr-NS算法复杂度分析
    4.3 实验设置及结果分析
        4.3.1 相似度指标对比
        4.3.2 自适应粒化对网络的作用
        4.3.3 实验结果与分析
        4.3.4 AGr-NS与MGr-LM对比实验分析
    4.4 本章小结
第五章 总结与展望
    5.1 总结
    5.2 展望
参考文献
附录A 图索引
Appendix A Figure Index
附录B 表格索引
Appendix B Table Index
致谢
攻读硕士期间的成果与参与的科研项目

【相似文献】

相关期刊论文 前10条

1 闫硕;闫林;;数据关联的粒化树描述方法[J];模式识别与人工智能;2015年12期

2 张夏苇;;多粒化粗糙集性质的几个充分条件[J];厦门理工学院学报;2016年03期

3 陈艳艳;马杰伟;洪流;杨国华;赵海涛;曹智程;;高温熔渣离心粒化机理与实验研究[J];科学技术与工程;2014年33期

4 李大鹏;;国内外高炉渣干法粒化技术进展分析[J];冶金设备;2015年S1期

5 陶启威;张文英;俞元春;杨靖宇;高捍东;白林;;柠条丸粒化种子吸水及崩解特性研究[J];福建林学院学报;2014年04期

6 赵姝;柯望;陈洁;张燕平;;基于聚类粒化的社团发现算法[J];计算机应用;2014年10期

7 张海鑫;;铜锍粒化工艺的发展[J];有色冶金节能;2013年03期

8 薛树红,刘雪峰;炉渣轮法粒化装置在太钢四高炉上的应用[J];山西冶金;2001年03期

9 庄伊美,潘东明,李健,黄育宗;琯溪蜜柚果实粒化症矫治研究[J];亚热带植物科学;2000年04期

10 王树奇,何镇明,崔向红,姜启川;莱氏体钢中共晶碳化物的热处理粒化[J];金属热处理;1997年09期

相关博士学位论文 前8条

1 曾凯;邻域粒化粗糙计算的关键技术研究与应用[D];电子科技大学;2015年

2 卢伟;基于粒计算的时间序列分析与建模方法研究[D];大连理工大学;2015年

3 钱宇华;复杂数据的粒化机理与数据建模[D];山西大学;2011年

4 许凯;云模型支持下的遥感图像分类粒计算方法研究[D];武汉大学;2010年

5 钟凤林;琯溪蜜柚汁胞发育过程的差异蛋白质组学研究[D];福建农林大学;2009年

6 丁健;柑橘果实粒化变异体的遗传背景及其性状形成的机理研究[D];华中农业大学;2009年

7 陈洁;商空间的粒化关键技术及问题求解研究[D];安徽大学;2014年

8 佘文琴;琯溪蜜柚汁胞粒化过程中生理变化与基因差异表达分析[D];福建农林大学;2009年

相关硕士学位论文 前10条

1 崔光明;基于商空间粒化的服务组合优化问题研究[D];安徽大学;2018年

2 闵星;基于结构粒化的社区发现方法研究[D];安徽大学;2018年

3 张晶;柑橘贮藏过程中汁胞粒化相关miRNA的筛选及功能分析[D];中国农业科学院;2016年

4 吴君军;高炉渣离心粒化机理及规律[D];重庆大学;2016年

5 杨志远;高炉渣干法离心粒化理论与实验研究[D];青岛理工大学;2010年

6 闫兆民;高炉渣离心粒化系统研究开发[D];青岛理工大学;2010年

7 赵丹;基于粒计算的数据粒化聚类方法研究[D];哈尔滨工程大学;2016年

8 曹磊;鼓泡流化床中粒化高炉渣颗粒流化及换热特性数值研究[D];重庆大学;2017年

9 彭金金;手指多模态传统粒化识别问题研究[D];中国民航大学;2015年

10 柯望;基于层次粒化的社团发现方法研究[D];安徽大学;2016年

本文编号：2841932