Skip to main content

Tradeoffs between density and size in extracting dense subgraphs: A unified framework

Publication ,  Conference
Wang, Z; Chu, L; Pei, J; Al-Barakati, A; Chen, E
Published in: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
November 21, 2016

Extracting dense subgraphs is an important step in many graph related applications. There is a challenging struggle in exploring the tradeoffs between density and size in subgraphs extracted. More often than not, different methods aim at different specific tradeoffs between the two factors. To the best of our knowledge, no existing method can allow a user to explore the full spectrum of the tradeoffs using a single parameter. In this paper, we investigate this problem systematically. First, since the existing studies cannot find highly compact dense subgraphs, we formulate the problem of finding very dense but relatively small subgraphs. Second, we connect our problem with the existing methods and propose a unified framework that can explore the tradeoffs between density and size of dense subgraphs extracted using a hyper-parameter. We give theoretical upper and lower bounds on the hyper-parameter so that the range where the unified framework can produce non-trivial subgraphs is determined. Third, we develop an efficient quadratic programming method for the unified framework, which is a generalization and extension to the existing methods. We show that optimizing the unified framework is essentially a relaxation of the maximization of a family of density functions. Last, we report a systematic empirical study to verify our findings.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

DOI

Publication Date

November 21, 2016

Start / End Page

41 / 48
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Wang, Z., Chu, L., Pei, J., Al-Barakati, A., & Chen, E. (2016). Tradeoffs between density and size in extracting dense subgraphs: A unified framework. In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 (pp. 41–48). https://doi.org/10.1109/ASONAM.2016.7752211
Wang, Z., L. Chu, J. Pei, A. Al-Barakati, and E. Chen. “Tradeoffs between density and size in extracting dense subgraphs: A unified framework.” In Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, 41–48, 2016. https://doi.org/10.1109/ASONAM.2016.7752211.
Wang Z, Chu L, Pei J, Al-Barakati A, Chen E. Tradeoffs between density and size in extracting dense subgraphs: A unified framework. In: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. 2016. p. 41–8.
Wang, Z., et al. “Tradeoffs between density and size in extracting dense subgraphs: A unified framework.” Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, 2016, pp. 41–48. Scopus, doi:10.1109/ASONAM.2016.7752211.
Wang Z, Chu L, Pei J, Al-Barakati A, Chen E. Tradeoffs between density and size in extracting dense subgraphs: A unified framework. Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016. 2016. p. 41–48.

Published In

Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

DOI

Publication Date

November 21, 2016

Start / End Page

41 / 48