受到圖拉普拉斯理論的部分啟發(fā),本文提出了一種加權(quán)拉普拉斯方法來更加方便地研究現(xiàn)階段比較流行的圖問題,例如,多層圖分割,以及平衡最小割問題.由于加權(quán)拉普拉斯策略繼承了譜方法的眾多優(yōu)點(diǎn),因此相比于其他現(xiàn)有的啟發(fā)式算法,用加權(quán)拉普拉斯設(shè)計圖算法在算法性能上具有更強(qiáng)的理論保證.為了說明其在理論與實(shí)際中的強(qiáng)有力的應(yīng)用價值,我們將分別給出加權(quán)拉普拉斯方法在多層圖分割和平衡最小割問題上的應(yīng)用.借助變分法和偏微分方程（PDE）理論,我們在加權(quán)分割問題（weighted cut problem）,平衡最小割問題（balanced minimum cut problem）,以及初始聚類問題（initial clustering problem）之間建立了等價性.其中,初始聚類問題會在基于多層結(jié)構(gòu)的圖分割算法的中間階段出現(xiàn).這些等價性的建立為基于加權(quán)拉普拉斯方法的圖算法提供了很強(qiáng)的理論支撐.另外,從加權(quán)拉普拉斯方法在平衡最小割問題的應(yīng)用的角度看,加權(quán)拉普拉斯方法使得偏微分方程數(shù)值解這一成熟的理論得以應(yīng)用到圖問題的算法設(shè)計當(dāng)中,這也進(jìn)一步證實(shí)了我們提出的加權(quán)拉普拉斯方法的有效性. 

【文章來源】：微電子學(xué)與計算機(jī). 2020,37(07)北大核心

【文章頁數(shù)】：5 頁

【文章目錄】：
1 引言
2 相關(guān)工作
    2.1 圖拉普拉斯與平衡最小割問題
    2.2 多層圖分割
3 加權(quán)拉普拉斯
    3.1 定義和引理
    3.2 加權(quán)拉普拉斯方法
4 兩個理論應(yīng)用
    4.1 平衡最小割問題和加權(quán)割問題的等價性
    4.2 初始聚類問題和加權(quán)割問題的等價性
    4.3 加權(quán)譜算法
5 結(jié)束語



本文編號：3319360