圖拉普拉斯矩陣特征值優(yōu)化及其應用.pdf

1、譜圖論是一種常用的研究方法,其可以利用拉普拉斯矩陣來描述圖的結(jié)構(gòu)。通過分析拉普拉斯矩陣及其特征值能夠?qū)D結(jié)構(gòu)有更清晰的認識,特別是在很多情況下,需要提高拉普拉斯矩陣的次小特征值λ2,以使圖結(jié)構(gòu)得到優(yōu)化。在一定約束條件下,提高λ2是一個典型的優(yōu)化問題。部分優(yōu)化問題的求解較為困難,但是對于凸優(yōu)化問題,存在著一系列有效的求解算法。半正定規(guī)劃是凸優(yōu)化問題的一種特殊形式,因此,將一個優(yōu)化問題轉(zhuǎn)換為半正定規(guī)劃問題后,則說明該問題可解。
　　本

2、文主要關注于在交通網(wǎng)絡規(guī)劃問題以及影響力提高問題中,λ2的提高在相應問題中的作用,并且將該問題轉(zhuǎn)換為半正定規(guī)劃問題從而進行求解。
　　交通網(wǎng)絡規(guī)劃問題是指,為了應對越來越多的交通需求,如何在一定的約束條件下,對現(xiàn)有的交通網(wǎng)絡中部分道路進行擴展,以使得整個交通網(wǎng)絡的性能達到最優(yōu)。交通網(wǎng)絡規(guī)劃問題的求解較為困難。通常一個交通網(wǎng)絡的直徑越小,交通網(wǎng)絡的連通情況越好,越有利于出行。因此,規(guī)劃一個具有較小直徑的交通網(wǎng)絡符合出行的需求。對于交

3、通網(wǎng)絡直徑與λ2的關系,本文證明,提高λ2,能夠同時降低交通網(wǎng)絡直徑的上界和下界。于是,將交通網(wǎng)絡規(guī)劃的目標由降低交通網(wǎng)絡的直徑,轉(zhuǎn)變?yōu)樘岣擀?。該問題可以轉(zhuǎn)換為半正定規(guī)劃形式,即該問題可解。
　　影響力提高問題是為了在社會網(wǎng)絡中銷售某一商品而提出的。影響力提高問題是指在經(jīng)過影響力最大化問題后,提高社會網(wǎng)絡中某些個體與個體間的影響程度,來促進網(wǎng)絡中商品信息的傳播,提高整個商品在社會網(wǎng)絡中的影響力,并且最終達到提高商品銷售量的目的。