高维大规模网络的结构估计

论文摘要

随着计算和数据采集技术的发展,在各个应用领域中积累了大量复杂数据.这些数据中往往蕴含着直接或潜在的网络（图）结构.网络数据分析已成为近年来统计、生物信息、统计物理等领域的研究热点之一.现实世界中的网络通常具有无标度特征、社区特征、动态特征,并且往往规模大,同时伴随很多额外的数据信息.如何有效利用网络数据的特点分析和挖掘其背后的本质信息具有非常重要的科学意义.本学位论文聚焦于大规模网络的结构估计问题.特别地,我们关注于两大类问题.一类问题是网络结构未知,如何有效利用数据信息估计网络的结构,即网络的边.在图模型框架下,我们从数据包含协变量、网络具有无标度特征、网络为动态且有社区结构这三个方面开展研究.另一类问题是网络结构已知,如何高效发现大规模网络的社区结构.在随机块模型框架下,我们聚焦于谱聚类并利用随机化技术开展研究.具体地,主要获得了如下研究成果:1.提出了具有协变量的有向图模型.通过将变量之间的因果关系表示为协变量的线性组合,从而将协变量有效引入模型中.在基于l1的稀疏正则化框架下估计参数.在算法方面,基于有向无环约束,给出了问题求解的坐标下降算法.在理论方面,在节点次序已知的情形下,证明了估计的高维变量选择相合性.大量模拟实验表明了所提方法的有效性,并将其应用于肺腺癌数据,得到了可解释的结果.2.提出了无标度网络的结构估计方法.在正则化框架下,通过Log和l1复合的惩罚函数引入网络这一结构先验.在算法方面,给出了问题求解的坐标下降算法,并讨论了算法的收敛性.在理论方面,证明了估计的相合性.实验表明所提方法表现良好,优于重赋权迭代算法.所提方法尤其适用于样本少、信号强度弱的情形.另外,所提方法具有一定的稳健性,适用于除无标度网络之外的其他多种复杂网络结构.3.提出了具有社区特征的动态网络的估计方法.在正则化框架下,利用Fused lasso惩罚函数融合每个时间节点对应的数据信息,并通过对网络中边对应的参数施以不同的惩罚从而使所得网络具有明显的社区结构.我们给出了模型理论上的解释,并给出问题求解的ADMM算法.将所提方法应用于PM2.5数据估计城市之间的PM2.5污染网络以及社区,所得结果具有一定的可解释性.4.利用随机化技术提出了社区发现的两种随机谱聚类算法,分别为基于随机投影和基于随机抽样的随机谱聚类算法.在随机块模型框架下,从总体矩阵的估计误差,错误聚类率,连接概率矩阵的估计误差这三个方面给出了两种随机谱聚类算法对应的非渐近误差界.结果表明,在一定条件下,随机谱聚类的理论界与原始谱聚类的相关结果一致,从而说明了随机谱聚类的价值.模拟实验和实际数据实验表明了理论的有效性.

论文目录

• 中文摘要
• 英文摘要
• 第一章 绪论
•   §1.1 图模型及网络结构估计
•     §1.1.1 无向图模型
•     §1.1.2 有向图模型
•   §1.2 随机块模型及网络社区发现
•   §1.3 本文主要工作和结构安排
• 第二章 具有协变量的有向图模型及其结构估计
•   §2.1 相关研究
•   §2.2 模型与估计
•     §2.2.1 具有协变量的Gaussian有向图模型
• 1罚似然估计'>    §2.2.2 具有协变量Gaussian有向图模型的l₁罚似然估计
•   §2.3 变量选择相合性
•   §2.4 理论证明
•   §2.5 坐标下降算法
•   §2.6 模拟研究
•   §2.7 肺腺癌数据的应用
•   §2.8 本章小结
• 第三章 基于无标度先验的有向图模型的结构估计
•   §3.1 相关研究
•   §3.2 估计方法
•   §3.3 坐标下降算法
•   §3.4 估计相合性
•   §3.5 模拟研究
•   §3.6 实际数据的应用
•     §3.6.1 E-coli数据
•     §3.6.2 Yeast数据
•   §3.7 本章小结
• 第四章 具有社区结构的动态网络的结构估计
•   §4.1 相关研究
•   §4.2 估计方法
•   §4.3 ADMM算法
•   §4.4 模拟研究
•   §4.5 PM2.5数据的应用
•   §4.6 本章小结
• 第五章 基于随机谱聚类的大规模随机块模型的社区发现
•   §5.1 随机块模型与谱聚类
•   §5.2 随机谱聚类算法
•     §5.2.1 基于随机投影的随机谱聚类算法
•     §5.2.2 基于随机抽样的随机谱聚类算法
•   §5.3 理论分析
•     §5.3.1 投影
•     §5.3.2 抽样
•   §5.4 理论证明
•     §5.4.1 定理5.1的证明
•     §5.4.2 定理5.2的证明
•     §5.4.3 定理5.3的证明
•     §5.4.4 定理5.4的证明
•   §5.5 模拟研究
•   §5.6 实际数据的应用
•   §5.7 本章小结
• 第六章 结论和展望
•   §6.1 结论
•   §6.2 展望
• 参考文献
• 攻读博士学位期间取得的科研成果
• 致谢

文章来源

类型: 博士论文

作者: 郭骁

导师: 张海

关键词: 复杂网络,图模型,高维,大规模数据,社区发现,稀疏

来源: 西北大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 西北大学

分类号: O212.1;O157.5

DOI: 10.27405/d.cnki.gxbdu.2019.000371

总页数: 171

文件大小: 7063K

下载量: 96