本文選題：矩陣的譜 + 拉普拉斯矩陣��； 參考：《計(jì)算機(jī)應(yīng)用與軟件》2013年02期

【摘要】：網(wǎng)絡(luò)的代數(shù)連通性是拉普拉斯矩陣的第二小特征值,它可以用于測(cè)量網(wǎng)絡(luò)的連通程度。為改善復(fù)雜網(wǎng)絡(luò)分割算法的時(shí)間復(fù)雜度,基于代數(shù)連通性提出一種譜優(yōu)化模型,并將其應(yīng)用于復(fù)雜網(wǎng)絡(luò)的小社區(qū)發(fā)現(xiàn)中。通過最小化網(wǎng)絡(luò)連通性函數(shù)在候選邊集中選擇要?jiǎng)h除的邊集。該凸優(yōu)化問題可由半正定規(guī)劃解決,但其時(shí)間復(fù)雜度高,所以只能處理規(guī)模適中的復(fù)雜網(wǎng)絡(luò)。為解決這個(gè)模型優(yōu)化問題,采用貪婪策略優(yōu)化方法,使該算法可以應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)。另一方面,社區(qū)邊界的邊影響代數(shù)連通性函數(shù)的優(yōu)化效果,根據(jù)費(fèi)德勒向量為每條邊設(shè)定權(quán)重來(lái)解決這一問題。最后應(yīng)用該模型對(duì)模擬復(fù)雜網(wǎng)絡(luò)和真實(shí)復(fù)雜網(wǎng)絡(luò)實(shí)例進(jìn)行驗(yàn)證,結(jié)果表明該模型有效降低了GN算法的迭代次數(shù),從而降低其時(shí)間復(fù)雜度,并有效保持其分割效果。
[Abstract]:The algebraic connectivity of the network is the second smallest eigenvalue of the Laplace matrix, which can be used to measure the connectivity of the network. In order to improve the time complexity of complex network segmentation algorithm, a spectral optimization model based on algebraic connectivity is proposed and applied to small community discovery of complex networks. By minimizing the network connectivity function, the edge set to be deleted is selected in the candidate edge set. The convex optimization problem can be solved by positive semidefinite programming, but its time complexity is high, so it can only deal with moderate scale complex networks. In order to solve the model optimization problem, the greedy strategy optimization method is adopted to make the algorithm applicable to large-scale complex networks. On the other hand, the edge of community boundary affects the optimization effect of algebraic connectivity function. According to Federer vector, the weight of each edge is set to solve this problem. Finally, the model is used to verify the simulation of complex networks and real complex networks. The results show that the model can effectively reduce the number of iterations of GN algorithm, thus reduce its time complexity, and effectively maintain its segmentation effect.
【作者單位】： 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;天津財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：國(guó)家教育部人文社科青年基金項(xiàng)目(08JC870008)
【分類號(hào)】：TP393.09;TP301.6

【相似文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 秦洋;基于潛在語(yǔ)義分析的真核啟動(dòng)子識(shí)別[D];煙臺(tái)大學(xué);2009年

，

本文編號(hào)：1802753