基于代數(shù)連通性的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)研究
發(fā)布時間:2018-04-25 20:04
本文選題:矩陣的譜 + 拉普拉斯矩陣 ; 參考:《計算機應用與軟件》2013年02期
【摘要】:網(wǎng)絡的代數(shù)連通性是拉普拉斯矩陣的第二小特征值,它可以用于測量網(wǎng)絡的連通程度。為改善復雜網(wǎng)絡分割算法的時間復雜度,基于代數(shù)連通性提出一種譜優(yōu)化模型,并將其應用于復雜網(wǎng)絡的小社區(qū)發(fā)現(xiàn)中。通過最小化網(wǎng)絡連通性函數(shù)在候選邊集中選擇要刪除的邊集。該凸優(yōu)化問題可由半正定規(guī)劃解決,但其時間復雜度高,所以只能處理規(guī)模適中的復雜網(wǎng)絡。為解決這個模型優(yōu)化問題,采用貪婪策略優(yōu)化方法,使該算法可以應用于大規(guī)模復雜網(wǎng)絡。另一方面,社區(qū)邊界的邊影響代數(shù)連通性函數(shù)的優(yōu)化效果,根據(jù)費德勒向量為每條邊設定權重來解決這一問題。最后應用該模型對模擬復雜網(wǎng)絡和真實復雜網(wǎng)絡實例進行驗證,結果表明該模型有效降低了GN算法的迭代次數(shù),從而降低其時間復雜度,并有效保持其分割效果。
[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.
【作者單位】: 天津大學計算機科學與技術學院;天津財經大學計算機科學與技術學院;
【基金】:國家教育部人文社科青年基金項目(08JC870008)
【分類號】:TP393.09;TP301.6
【相似文獻】
相關碩士學位論文 前1條
1 秦洋;基于潛在語義分析的真核啟動子識別[D];煙臺大學;2009年
,本文編號:1802753
本文鏈接:http://sikaile.net/guanlilunwen/ydhl/1802753.html
最近更新
教材專著