基于谱方法的无向赋权图剖分算法

Spectral-based weighted undirected graph partitioning algorithm

在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanc-zos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。

During the initial partitioning phase of multilevel method, this paper proposed the algorithm of spectral partitioning for weighted undirected graph （SPWUG） and gave the Fiedler vector calculation of Laplacian matrix using the Lanczos iteration method. The components of the Fiedler vector were weighted on the corresponding vertices of graph such that differences of the components provide information about the distances between the vertices. According to the distances, the SPWUG algorithm computed the initial partition of the coarsest graph by extending the Laplacian spectral graph theory from the unweighted undirected graph into the weighted undirected graph. The experimental evaluations show that the SPWUG algorithm produces the performance improvement. Meanwhile, the analysis shows that the approximate global minimum partition of the coarsest graph may be the local minimum partition of the finest graph and need to strengthen the global search ability of refinement algorithm in the refinement phase.