Please use this identifier to cite or link to this item:
https://doi.org/10.1109/TPAMI.2013.16
Title: | Fast detection of dense subgraphs with iterative shrinking and expansion | Authors: | Liu, H. Latecki, L.J. Yan, S. |
Keywords: | cluster analysis correspondence 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. https://doi.org/10.1109/TPAMI.2013.16 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/56012 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.