Document Detail

Fast detection of dense subgraphs with iterative shrinking and expansion.
MedLine Citation:
PMID:  23868775     Owner:  NLM     Status:  In-Data-Review    
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.
Hairong Liu; Longin Jan Latecki; Shuicheng Yan
Related Documents :
20856455 - Artwork diagnostics with fiber-optic digital speckle pattern interferometry.
19655945 - Windowed high-order ambiguity function method for fringe analysis.
21102925 - Optical coating without phase dispersion for a fabry-perot interferometer.
20700335 - Three-channel phase stepped system for moire interferometry.
18374935 - Advancement in the modeling of pressure-flow for the guidance of development and scale-...
23187475 - Taming the flow of light via active magneto-optical impurities.
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    
National University of Singapore, Singapore.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms

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 ...