图拉普拉斯矩阵特征值优化及其应用

摘要

谱图论是一种常用的研究方法,其可以利用拉普拉斯矩阵来描述图的结构。通过分析拉普拉斯矩阵及其特征值能够对图结构有更清晰的认识,特别是在很多情况下,需要提高拉普拉斯矩阵的次小特征值λ2,以使图结构得到优化。在一定约束条件下,提高λ2是一个典型的优化问题。部分优化问题的求解较为困难,但是对于凸优化问题,存在着一系列有效的求解算法。半正定规划是凸优化问题的一种特殊形式,因此,将一个优化问题转换为半正定规划问题后,则说明该问题可解。
　　本文主要关注于在交通网络规划问题以及影响力提高问题中,λ2的提高在相应问题中的作用,并且将该问题转换为半正定规划问题从而进行求解。
　　交通网络规划问题是指,为了应对越来越多的交通需求,如何在一定的约束条件下,对现有的交通网络中部分道路进行扩展,以使得整个交通网络的性能达到最优。交通网络规划问题的求解较为困难。通常一个交通网络的直径越小,交通网络的连通情况越好,越有利于出行。因此,规划一个具有较小直径的交通网络符合出行的需求。对于交通网络直径与λ2的关系,本文证明,提高λ2,能够同时降低交通网络直径的上界和下界。于是,将交通网络规划的目标由降低交通网络的直径,转变为提高λ2。该问题可以转换为半正定规划形式,即该问题可解。
　　影响力提高问题是为了在社会网络中销售某一商品而提出的。影响力提高问题是指在经过影响力最大化问题后,提高社会网络中某些个体与个体间的影响程度,来促进网络中商品信息的传播,提高整个商品在社会网络中的影响力,并且最终达到提高商品销售量的目的。一个社会网络中,信息传播速度越快,信息传播越趋向于某些特定个体(如购买量较大的个体等),越符合商品销售的需求。提高社会网络中的λ2,可以提高信息传播的收敛速度。并且,可以通过调节随机游走的稳态来促进信息向某些特定个体流动。基于以上现象,将影响力提高问题的求解目标转换为在一个满足需求的稳态条件下,提高社会网络的λ2。该问题可以转换为半正定规划形式,即该问题可解。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题背景及意义

1.2 课题内容及创新点

1.3 论文结构安排

第二章 背景知识

2.1 凸优化及半正定规划

2.2 谱图论

第三章 交通网络规划

3.1 交通网络规划的背景介绍

3.2 代数连通度与直径的关系

3.3 提高代数连通度λ2

3.4 交通网络规划方法

3.5 实验验证

第四章 影响力提高问题

4.1 影响力提高问题的引入

4.2 理论分析

4.3 影响力提高问题的求解

4.4 实验验证

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

发表论文和参加科研情况说明

致谢