research-article

Deconstruct Densest Subgraphs

Authors:

Miao QiaoAuthors Info & Claims

WWW '20: Proceedings of The Web Conference 2020

Pages 2747 - 2753

https://doi.org/10.1145/3366423.3380033

Published: 20 April 2020 Publication History

Abstract

In this paper, we aim to understand the distribution of the densest subgraphs of a given graph under the density notion of average-degree. We show that the structures, the relationships and the distributions of all the densest subgraphs of a graph G can be encoded in O(L) space in an index called the ds-Index. Here L denotes the maximum output size of a densest subgraph of G. More importantly, ds-Indexcan report all the minimal densest subgraphs of G collectively in O(L) time and can enumerate all the densest subgraphs of G with an O(L) delay. Besides, the construction of ds-Indexcosts no more than finding a single densest subgraph using the state-of-the-art approach. Our empirical study shows that for web-scale graphs with one billion edges, the ds-Indexcan be constructed in several minutes on an ordinary commercial machine.

References

[1]

[n.d.]. full version, https://lijunchang.github.io/pdf/dds.pdf.

[2]

T. Akiba, Y. Iwata, and Y. Yoshida. 2013. Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction. In Proc. of CIKM’13.

[3]

A. Angel, N. Koudas, N. Sarkas, and D. Srivastava. 2012. Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification. PVLDB 5, 6 (2012), 574–585.

Digital Library

[4]

B. Bahmani, R. Kumar, and S. Vassilvitskii. 2012. Densest Subgraph in Streaming and MapReduce. PVLDB 5, 5 (2012), 454–465.

Digital Library

[5]

O. D. Balalau, F. Bonchi, T.-H. H. Chan, F. Gullo, and M. Sozio. 2015. Finding Subgraphs with Maximum Total Density and Limited Overlap. In Proc. of WSDM’15. 379–388.

[6]

V. Batagelj and M. Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR (2003).

[7]

A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos. 2013. CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In Proc. of WWW’13. 119–130.

[8]

S. Bhattacharya, M. Henzinger, D. Nanongkai, and C. E. Tsourakakis. 2015. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. In Proc. of STOC’15. 173–182.

Digital Library

[9]

N. Biggs, E. K. Lloyd, and R. J. Wilson. 1986. Graph Theory, 1736-1936. Clarendon Press.

[10]

C. Bron and J. Kerbosch. 1973. Finding All Cliques of an Undirected Graph (Algorithm 457). CACM 16, 9 (1973), 575–576.

Digital Library

[11]

Lijun Chang. 2019. Efficient Maximum Clique Computation over Large Sparse Graphs. In Proc. of KDD’19. 529–538.

Digital Library

[12]

Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences.

[13]

L. Chang, J. X. Yu, L. Q., X. Lin, C. Liu, and W. Liang. 2013. Efficiently computing k-edge connected components via graph decomposition. In Proc. of SIGMOD’13.

[14]

M. Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization, Third International Workshop. 84–95.

[15]

J. Cohen. 2008. Trusses: Cohesive Subgraphs for Social Network Analysis.

[16]

M. Danisch, T.-H. H. Chan, and M. Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In Proc. of WWW’17. 233–242.

[17]

Y. Dourisboure, F. Geraci, and M. Pellegrini. 2007. Extraction and classification of dense communities in the web. In Proc. of WWW’07. 461–470.

[18]

Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. 2015. Efficient Densest Subgraph Computation in Evolving Graphs. In Proc. of WWW’15. 300–310.

Digital Library

[19]

Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, and Xuemin Lin. 2019. Efficient Algorithms for Densest Subgraph Discovery. PVLDB 12, 11 (2019), 1719–1732.

Digital Library

[20]

G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. 1989. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM J. of Comp. 18, 1 (1989), 30–55.

Digital Library

[21]

D. Gibson, R. Kumar, and A. Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In PVLDB. 721–732.

[22]

A. V. Goldberg. 1984. Finding a Maximum Density Subgraph. Technical Report. Berkeley, CA, USA.

[23]

V. E. Lee, N. Ruan, R. Jin, and C. C. Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. In Managing and Mining Graph Data. 303–336.

[24]

Robert Mokken. 1979. Cliques, clubs and clans. Quality & Quantity 13(1979), 161–173.

[25]

L. Qin, R. H. Li, L. Chang, and C. Zhang. 2015. Locally Densest Subgraph Discovery. In Proc. of KDD’15. 965–974.

[26]

A. E. Sariyüce, C. Seshadhri, A. Pinar, and Ü. V. Çatalyürek. 2015. Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In Proc. of WWW’15. 927–937.

Digital Library

[27]

S. B. Seidman and B. L. Foster. 1978. A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology 6 (1978), 139–154.

[28]

M. Sozio and A. Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In Proc. of KDD’10. 939–948.

[29]

N. Tatti and A. Gionis. 2015. Density-friendly Graph Decomposition. In Proc. of WWW’15. 1089–1099.

[30]

Charalampos E. Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In Proc. of WWW’15. 1122–1132.

Digital Library

[31]

E. Valari, M. Kontaki, and A. N. Papadopoulos. 2012. Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections. In Proc. of SSDBM’12. 213–230.

Digital Library

[32]

J. Wang and J. Cheng. 2012. Truss Decomposition in Massive Networks. PVLDB 5, 9 (2012).

Cited By

Feng WLiu SKoutra DCheng X(2024)Unified Dense Subgraph Detection: Fast Spectral Theory Based AlgorithmsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327257436:3(1356-1370)Online publication date: Mar-2024
https://doi.org/10.1109/TKDE.2023.3272574
Qin HLi RYuan YDai YWang G(2023)Densest Periodic Subgraph Mining on Large Temporal GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323378835:11(11259-11273)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2022.3233788
Saha AKe XKhan ALong C(2023)Most Probable Densest Subgraphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00115(1447-1460)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00115
Show More Cited By

Index Terms

Deconstruct Densest Subgraphs

Index terms have been assigned to the content through auto-classification.

Recommendations

Sandwiching a densest subgraph by consecutive cores

In this paper, we show that in the random graph Gn,c/n, with high probability, there exists an integer kï such that a subgraph of Gn,c/n, whose vertex set differs from a densest subgraph of Gn,c/n by Olog2n vertices, is sandwiched by the kï and the kï +...
Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present 32-...
Finding densest k-connected subgraphs
Abstract
Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '20: Proceedings of The Web Conference 2020

April 2020

3143 pages

ISBN:9781450370233

DOI:10.1145/3366423

Editors:
Yennun Huang
Acadmica sinica, Taiwan
,
Irwin King
The Chinese University of Hong Kong, Hong Kong
,
Tie-Yan Liu
Microsoft Research Asia, China
,
Maarten van Steen
University of Twente, Netherlands

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '20

Sponsor:

SIGWEB

WWW '20: The Web Conference 2020

April 20 - 24, 2020

Taipei, Taiwan

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
265
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng WLiu SKoutra DCheng X(2024)Unified Dense Subgraph Detection: Fast Spectral Theory Based AlgorithmsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327257436:3(1356-1370)Online publication date: Mar-2024
https://doi.org/10.1109/TKDE.2023.3272574
Qin HLi RYuan YDai YWang G(2023)Densest Periodic Subgraph Mining on Large Temporal GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323378835:11(11259-11273)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2022.3233788
Saha AKe XKhan ALong C(2023)Most Probable Densest Subgraphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00115(1447-1460)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00115
Trung TChang LLong NYao KThanh Binh H(2023)Verification-Free Approaches to Efficient Locally Densest Subgraph Discovery2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00008(1-13)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00008
Chang LWang Z(2023)A near-optimal approach to edge connectivity-based hierarchical graph decompositionThe VLDB Journal10.1007/s00778-023-00797-x33:1(49-71)Online publication date: 6-May-2023
https://doi.org/10.1007/s00778-023-00797-x
Fang YLuo WMa C(2022)Densest subgraph discovery on large graphsProceedings of the VLDB Endowment10.14778/3554821.355489515:12(3766-3769)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.14778/3554821.3554895
Ma CCheng RLakshmanan LHan X(2022)Finding locally densest subgraphsProceedings of the VLDB Endowment10.14778/3551793.355182615:11(2719-2732)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551826
Chang LWang Z(2022)A near-optimal approach to edge connectivity-based hierarchical graph decompositionProceedings of the VLDB Endowment10.14778/3514061.351406315:6(1146-1158)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.14778/3514061.3514063

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents