Document Detail


Fast detection of dense subgraphs with iterative shrinking and expansion.
MedLine Citation:
PMID:  23868775     Owner:  NLM     Status:  In-Data-Review    
Abstract/OtherAbstract:
In this paper, we propose an efficient algorithm to detect dense subgraphs of a weighted graph. The proposed algorithm, called the shrinking and expansion algorithm (SEA), iterates between two phases, namely, the expansion phase and the shrink phase, until convergence. For a current subgraph, the expansion phase adds the most related vertices based on the average affinity between each vertex and the subgraph. The shrink phase considers all pairwise relations in the current subgraph and filters out vertices whose average affinities to other vertices are smaller than the average affinity of the result subgraph. In both phases, SEA operates on small subgraphs; thus it is very efficient. Significant dense subgraphs are robustly enumerated by running SEA from each vertex of the graph. We evaluate SEA on two different applications: solving correspondence problems and cluster analysis. Both theoretic analysis and experimental results show that SEA is very efficient and robust, especially when there exists a large amount of noise in edge weights.
Authors:
Hairong Liu; Longin Jan Latecki; Shuicheng Yan
Related Documents :
11248985 - Recording depth of the heterodyne laser interferometer for cochlear vibration measurement.
20733885 - Novel holographic shearing interferometer for measuring lens lateral aberration.
19773835 - Holographic interferometry using anisotropic self-diffraction in bi(12)sio(20).
19658985 - Atom interferometers with scalable enclosed area.
914725 - A digital computer technique for analyzing respiratory muscle emg's.
591195 - Neural modeling of human behavior: a proposal for a new type of modifiable synapse.
Publication Detail:
Type:  Journal Article    
Journal Detail:
Title:  IEEE transactions on pattern analysis and machine intelligence     Volume:  35     ISSN:  1939-3539     ISO Abbreviation:  IEEE Trans Pattern Anal Mach Intell     Publication Date:  2013 Sep 
Date Detail:
Created Date:  2013-07-22     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  9885960     Medline TA:  IEEE Trans Pattern Anal Mach Intell     Country:  United States    
Other Details:
Languages:  eng     Pagination:  2131-42     Citation Subset:  IM    
Affiliation:
National University of Singapore, Singapore.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization.
Next Document:  FOCUSR: Feature Oriented Correspondence Using Spectral Regularization--A Method for Precise Surface ...