Community detection in graphs using singular value decomposition

S Sarkar, A Dong - Physical Review E—Statistical, Nonlinear, and Soft …, 2011 - APS
Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 2011APS
A spectral algorithm for community detection is presented. The algorithm consists of three
stages:(1) matrix factorization of two matrix forms, square signless Laplacian for unipartite
graphs and rectangular adjacency matrix for bipartite graphs, using singular value
decompostion (SVD);(2) dimensionality reduction using an optimal linear approximation;
and (3) clustering vertices using dot products in reduced dimensional space. The algorithm
reveals communities in graphs without placing any restriction on the input network type or …
A spectral algorithm for community detection is presented. The algorithm consists of three stages: (1) matrix factorization of two matrix forms, square signless Laplacian for unipartite graphs and rectangular adjacency matrix for bipartite graphs, using singular value decompostion (SVD); (2) dimensionality reduction using an optimal linear approximation; and (3) clustering vertices using dot products in reduced dimensional space. The algorithm reveals communities in graphs without placing any restriction on the input network type or the output community type. It is applicable on unipartite or bipartite unweighted or weighted networks. It places no requirement on strict community membership and automatically reveals the number of clusters, their respective sizes and overlaps, and hierarchical modular organization. By representing vertices as vectors in real space, expressed as linear combinations of the orthogonal bases described by SVD, orthogonality becomes the metric for classifying vertices into communities. Results on several test and real world networks are presented, including cases where a mix of disjointed, overlapping, or hierarchical communities are known to exist in the network.
American Physical Society
以上显示的是最相近的搜索结果。 查看全部搜索结果