复杂网络社区发现若干问题的研究

论文摘要

现实世界中的许多系统都可表示成网络,如生物系统、社会系统和交通系统等。然而,这些网络往往因过于复杂而难于理解。复杂网络分析有助于人们认识和理解网络的内在机制,因而具有重要的研究意义。社区发现是复杂网络分析的重要内容。它有助于人们认识网络的组织结构和链接模式,进而指导实践,如传染病防控、舆情监控、交通规划和配电网资源优化配置等,因此,对社区发现的研究具有重要的理论意义和实用价值。社区发现引起了学者们的广泛关注,然而,如何进一步提高社区发现的精度和效率依然是一个挑战性难题。本文对社区发现进行了研究并提出了相应的算法。研究内容主要包括:基于符号随机块模型和精确完整数据综合似然（the exact integrated complete data likelihood,ICLex）的符号网络社区发现,基于统计推理的动态网络社区发现,基于统计模型的网络节点分类的批量模式主动学习,以及基于飞蛾烛火优化的社区发现。本文的具体工作和贡献如下:第一、针对符号网络社区发现问题,本文提出了一个基于统计推理和ICLex的符号网络社区发现方法SSBMI（Signed Stochastic Block Model and ICLex）.据我们所知,这是首次利用ICLex解决符号网络社区发现问题的努力。首先,本文推导出基于符号网络随机块模型SSBM（Signed Stochastic Block Model）的ICLex;然后,本文利用一个贪婪搜索技术来优化ICLex;最终,将所发现的具有最高ICLex的社区结构作为结果返回。与2015年发表在AAAI上的基于统计推理的符号网络社区发现方法SSL相比,SSBMI不需要通过对模型空间的模型逐个进行参数估计并在估计结果中选优来实现模型选择,从而节省了大量的计算时间。SSBMI不需要用户事先掌握网络结构的先验知识,这不仅降低了用户的使用门槛,而且也使拟合主要由数据来驱动。在合成网络和真实网络数据上的实验结果表明,与SSL等几个有代表性的方法相比,SSBMI能够更精确地发现符号网络中的社区。同时,与SSL相比,SSBMI的效率更高。第二、针对动态网络社区发现问题,本文提出了一个基于统计推理的动态网络社区发现方法DSBMC（Dynamic Stochastic Block Model with Constraints）.首先,本文提出了一个新的动态随机块模型。该模型使用转移概率建模节点社区分配的动态变化,并且在该模型中,所有节点共享同一个社区转移概率,所有社区内的节点对共享同一个链接概率,所有社区间的节点对共享同一个链接概率。其次,基于贝叶斯推理和吉布斯采样,本文给出了该模型的学习方法。在人工合成和真实数据上的实验表明,与几个有代表性的算法相比,DSBMC能获得更高的精度。第三、为了解决网络节点分类中单节点模式主动学习效率不高的问题,本文提出了一个基于统计模型的可用于同配或异配网络节点分类的批量模式主动学习方法BALN（Batch Active Learning for Networks）.该方法采用互信息和随机游走思想选择用于标注标签的节点。BALN适用于同配或异配网络。与单节点模式主动学习不同,BALN一次可选择多个节点用于标注。同时,BALN仅使用网络拓扑作为输入数据,不需要事先知道网络中块（社区）的个数,也不需要对块连接模式作初始假设。在两个不同类型（同配和异配）的网络上,本文将BALN与基于单节点模式主动学习的Moore方法以及几个使用互信息和简单启发式的批量模式主动学习方法进行了实验比较,结果表明,在使用同样的查询节点数的情况下,BALN方法可使用明显少的查询次数获得和Moore方法大体相当的分类精度;在使用同样查询成本的前提下,与上述几个使用互信息和简单启发式的批量模式主动学习方法相比,BALN方法在精度上具有明显优势。第四、针对无符号网络社区发现问题,本文提出了一个基于飞蛾烛火优化的复杂网络社区发现方法MFOCD（Moth-Flame Optimization based Community Detection）.该方法使用字符串编码重新设计飞蛾烛火优化的个体表示,使用单点交叉,变异与爬山算法思想相结合的方式来重新设计飞蛾围绕烛火的搜索,使得飞蛾烛火优化技术适合处理社区发现问题。在人工合成和真实数据集上的实验表明,与几个相关算法相比,MFOCD能获得更高的精度。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 研究背景和意义
•     1.1.1 复杂网络概述
•     1.1.2 复杂网络的研究概况
•     1.1.3 社区结构
•   1.2 社区发现方法的研究现状
•   1.3 论文研究内容
•   1.4 论文组织结构
• 第2章 基于符号随机块模型和ICLex的符号网络社区发现方法..
•   2.1 引言
•   2.2 模型与方法
•     2.2.1 模型
•     2.2.2 精确完整数据综合似然
•     2.2.3 优化
•     2.2.4 时间复杂度分析
•   2.3 实验
•     2.3.1 评价指标
•     2.3.2 合成数据上的实验
•     2.3.3 真实数据上的实验
•   2.4 本章小结
• 第3章 基于统计推理的动态网络社区发现方法
•   3.1 引言
•   3.2 模型与方法
•     3.2.1 模型
•     3.2.2 参数估计
•     3.2.3 时间复杂度分析
•   3.3 实验
•     3.3.1 合成数据上的实验
•     3.3.2 真实数据上的实验
•   3.4 本章小结
• 第4章 基于统计模型的网络节点分类的批量模式主动学习
•   4.1 引言
•   4.2 模型与方法
•     4.2.1 批量模式主动学习的模型
•     4.2.2 批量模式主动学习的框架
•     4.2.3 基于互信息和随机游走的批量模式节点选择方法
•     4.2.4 时间复杂度分析
•   4.3 实验
•     4.3.1 评价标准
•     4.3.2 实验数据
•     4.3.3 实验结果
•   4.4 本章小结
• 第5章 基于飞蛾烛火优化的复杂网络社区发现方法
•   5.1 引言
•   5.2 飞蛾烛火优化
•   5.3 基于飞蛾烛火优化的社区发现
•     5.3.1 适应度函数
•     5.3.2 个体表示和初始化
•     5.3.3 交叉
•     5.3.4 变异
•     5.3.5 爬山
•     5.3.6 时间复杂度分析
•   5.4 实验
•     5.4.1 合成数据上的实验
•     5.4.2 真实数据上的实验
•   5.5 本章小结
• 第6章 总结与展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 作者简介及在学期间所取得的科研成果
• 致谢

文章来源

类型: 博士论文

作者: 平树秋

导师: 刘大有

关键词: 复杂网络,社区发现,统计模型,主动学习,进化计算

来源: 吉林大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 吉林大学

分类号: O157.5

总页数: 114

文件大小: 7263K

下载量: 375