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