动态网络结构特征表示及多层网络模式挖掘

论文摘要

复杂网络作为分析复杂系统中个体之间关联关系以及系统结构功能的有效工具,已经被广泛应用于各个领域。现阶段,随着科学技术的不断发展,产生了大量多维、动态、多层次的数据需要研究人员去分析并挖掘出有用信息,而传统静态、单一的复杂网络模型已经不足以刻画丰富数据下的深层次特征。因此,作为传统复杂网络模型的升级与扩展,多层网络模型被提出并用来刻画和挖掘复杂系统中更真实的特性。多层网络是结合多种连接关系的耦合网络,如包含朋友关系、家庭成员关系以及同事关系等多种类型人与人关系构成的不同层次的社会网络。多层网络按照层间耦合关系的不同,可以被分为多种形式,如具有时序关系的动态网络、层与层因个体相同而具有关联性的多层关联网络、层与层之间节点具有强依赖关系的多层依赖网络等。对多层网络中重要结构特征进行刻画,挖掘诸如动态演化、保守结构等模式,对理解和分析复杂系统具有非常积极的意义。近来,多层网络中的拓扑特征分析、动态演化分析、结构特征刻画以及功能结构模式的定义与挖掘成为了研究的热点。本文主要从多层网络结构特征刻画以及模式挖掘两个方面展开研究,包括动态网络相似性度量及动态社团检测、动态网络表示学习、多层网络保守模块结构检测。具体而言,本文的主要研究内容及贡献如下:1.扩展了静态网络上的结构扰动理论,将相邻时刻网络之间的动态变化作为扰动项,提出一个适合动态网络的结构扰动相似性度量,并通过结合局部拓扑相似性,从不同层面对动态网络的结构特征进行刻画。在该相似性基础上,本文提出一个基于进化聚类和密度聚类的动态社团检测算法,用以挖掘随时间变化的网络上的社团结构。该研究优势在于:1)动态网络上的结构扰动相似性充分结合了动态信息,并且结构扰动理论是基于矩阵特征值分解的,体现了网络的拓扑特征,有助于刻画动态社团结构;2)基于进化聚类的方式考虑了社团演化信息,并且密度聚类的方式无需事先设定潜在的社团数目。在人工合成网络以及几个真实动态网络上,都表明该方法能够有效地检测动态社团结构,进而反映了所提出的相似性度量的优越性。2.针对当前大多数网络表示学习的研究缺乏对时序动态因素的考虑,本文提出一个动态网络表示学习的方法,旨在将动态网络中的节点用低维的包含时间信息的向量进行表示,以方便灵活处理动态网络上的机器学习任务。该方法基于两层的非负矩阵分解模型,充分结合局部邻居结构和社团结构信息,并利用进化聚类的思想将动态演化信息考虑到这些拓扑结构上。该研究的优势在于:1)两层非负矩阵分解可以同时获得社团结构与节点的低维表示向量,并且得到的社团结构信息融入到了该向量表示中;2)时间因素分别以两种形式被考虑到局部拓扑结构和社团结构中,充分考虑了动态变化对不同层次拓扑结构的影响。本文在不同人工合成及真实数据集上,针对节点分类任务和动态社团检测任务,对方法得到的节点向量表示的性能进行了评估。结果表明所提方法结合不同层面拓扑结构及动态信息对动态网络表示学习的有效性。3.多层网络中的保守结构模式非常重要,它能体现出多层网络的共有特性。本文提出两个特征度量指标——连接强度和参与系数,分别用来衡量每对节点在多层网络整体水平上连接的紧密程度和连接权重的均匀程度,以此来刻画多层网络中的保守模块结构。根据提出的两个特征度量,多层网络可以被压缩为两个相关的特征矩阵,之后仅在这两个特征矩阵上,利用多视图非负矩阵分解得到保守模块结构。由于保守模块的识别仅需要在两个特征矩阵上协同进行,使得方法本身与网络的层次个数无关,大大降低了计算的空间和时间复杂度。将该方法应用于多层生物网络并做了深入分析,其中在33个癌症相关的基因共表达网络上,识别出核糖体合成、免疫应答等生物功能的保守基因模块,体现了癌症发生和发展的共性;在人类脑组织15个不同区域的蛋白质相互作用网络上,检测到了与神经系统发育相关的保守功能模块。

论文目录

摘要

ABSTRACT

符号对照表

缩略语对照表

第一章绪论

1.1 研究背景与意义

1.2 研究现状及存在问题

1.2.1 研究现状分析

1.2.2 主要存在的问题

1.3 本文研究内容及组织结构

1.3.1 本文研究思路

1.3.2 本文主要贡献

1.3.3 本文组织结构

第二章基于结构扰动和拓扑相似性的动态社团检测

2.1 引言

2.2 符号定义及问题描述

2.3 动态网络的相似性度量

2.3.1 静态网络中的结构扰动模型

2.3.2 动态网络中的结构扰动模型

2.3.3 结构扰动与局部拓扑相似性的结合

2.4 动态社团检测ESPRA算法

2.4.1 相似性水平上的时间平滑性

2.4.2 动态社团检测

2.5 算法复杂度分析

2.6 实验结果与分析

2.6.1 评价指标

2.6.2 人工合成网络上的准确性分析

2.6.3 真实网络上的准确性分析

2.6.4 参数讨论

2.7 本章小结

第三章基于社团结构和进化聚类的动态网络表示学习

3.1 引言

3.2 动态网络表示学习dynNEC算法

3.2.1 符号定义及问题描述

3.2.2 基于非负矩阵分解的表示学习

3.2.3 基于局部随机游走的节点拓扑相似性

3.2.4 含社团结构信息的两层非负矩阵分解模型

3.2.5 基于进化聚类的时间信息融合

3.2.6 模型优化求解

3.3 算法复杂度分析

3.4 实验结果与分析

3.4.1 实验数据

3.4.2 实验比较的方法

3.4.3 任务及评价指标

3.4.4 节点分类性能分析

3.4.5 动态社团检测性能分析

3.4.6 稳定性分析

3.4.7 参数讨论

3.5 本章小结

第四章多层生物网络保守功能模块识别

4.1 引言

4.2 符号定义及问题描述

4.3 保守功能模块识别ConMod算法

4.3.1 多层网络保守结构特征刻画

4.3.2 保守功能模块识别

4.3.3 模块的统计显著性检验

4.4 算法复杂度分析

4.5 实验结果与分析

4.5.1 人工合成数据上的性能分析

4.5.2 癌症保守功能模块识别与分析

4.5.3 人类脑组织保守功能模块识别与分析

4.5.4 参数讨论

4.6 本章小结

第五章总结与展望

5.1 本文工作总结

5.2 下一步的研究工作

参考文献

致谢

作者简介

文章来源

类型: 博士论文

作者: 王培卓

导师: 高琳

关键词: 动态网络,多层网络,结构特征,表示学习,模式

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O157.5

DOI: 10.27389/d.cnki.gxadu.2019.000098

总页数: 120

文件大小: 5826K

下载量: 186

动态网络结构特征表示及多层网络模式挖掘

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢