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

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

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

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



本文編號(hào)：3319360