2010 | OriginalPaper | Buchkapitel
Spectral Graph Partitioning Based on a Random Walk Diffusion Similarity Measure
verfasst von : Xi Li, Weiming Hu, Zhongfei Zhang, Yang Liu
Erschienen in: Computer Vision – ACCV 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Spectral graph partitioning is a powerful tool for unsupervised data learning. Most existing algorithms for spectral graph partitioning directly utilize the pairwise similarity matrix of the data to perform graph partitioning. Consequently, they are incapable of fully capturing the intrinsic structural information of graphs. To address this problem, we propose a novel random walk diffusion similarity measure (
RWDSM
) for capturing the intrinsic structural information of graphs. The
RWDSM
is composed of three key components—emission, absorbing, and transmission. It is proven that graph partitioning on the
RWDSM
matrix performs better than on the pairwise similarity matrix of the data. Moreover, a spectral graph partitioning objective function (referred to as
DGPC
) is used for capturing the discriminant information of graphs. The
DGPC
is designed to effectively characterize the intra-class compactness and the inter-class separability. Based on the
RWDSM
and
DGPC
, we further develop a novel spectral graph partitioning algorithm (referred to as
DGPCA
). Theoretic analysis and experimental evaluations demonstrate the promise and effectiveness of the developed
DGPCA
.