Please use this identifier to cite or link to this item:
Title: Fast detection of dense subgraphs with iterative shrinking and expansion
Authors: Liu, H. 
Latecki, L.J.
Yan, S. 
Keywords: cluster analysis
Dense subgraph
maximum common subgraph
point set matching
Issue Date: 2013
Citation: Liu, H., Latecki, L.J., Yan, S. (2013). Fast detection of dense subgraphs with iterative shrinking and expansion. IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (9) : 2131-2142. ScholarBank@NUS Repository.
Abstract: 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. © 1979-2012 IEEE.
Source Title: IEEE Transactions on Pattern Analysis and Machine Intelligence
ISSN: 01628828
DOI: 10.1109/TPAMI.2013.16
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 15, 2019


checked on Jul 5, 2019

Page view(s)

checked on Oct 28, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.