Please use this identifier to cite or link to this item: https://doi.org/10.1109/TPAMI.2013.16
DC FieldValue
dc.titleFast detection of dense subgraphs with iterative shrinking and expansion
dc.contributor.authorLiu, H.
dc.contributor.authorLatecki, L.J.
dc.contributor.authorYan, S.
dc.date.accessioned2014-06-17T02:49:43Z
dc.date.available2014-06-17T02:49:43Z
dc.date.issued2013
dc.identifier.citationLiu, 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
dc.identifier.issn01628828
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/56012
dc.description.abstractIn 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1109/TPAMI.2013.16
dc.sourceScopus
dc.subjectcluster analysis
dc.subjectcorrespondence
dc.subjectDense subgraph
dc.subjectmaximum common subgraph
dc.subjectpoint set matching
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.departmentELECTRICAL & COMPUTER ENGINEERING
dc.description.doi10.1109/TPAMI.2013.16
dc.description.sourcetitleIEEE Transactions on Pattern Analysis and Machine Intelligence
dc.description.volume35
dc.description.issue9
dc.description.page2131-2142
dc.description.codenITPID
dc.identifier.isiut000322029000007
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

28
checked on Oct 15, 2019

WEB OF SCIENCETM
Citations

20
checked on Jul 5, 2019

Page view(s)

56
checked on Oct 13, 2019

Google ScholarTM

Check

Altmetric


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