The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees
Abstract
Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density, research has focused on optimizing alternative density functions. A very popular among such functions is the average degree, whose maximization leads to the well-known densest-subgraph notion. Surprisingly enough, however, densest subgraphs are typically large graphs, with small edge density and large diameter.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
A Gene-Expression Signature as a Predictor of Survival in Breast Cancer
van de Vijver, M. J., He, Y. D., van 't Veer, L. J., Dai, H., Hart, A. A. M., Voskuil, D. W., Schreiber, G. J., Peterse, J. L., Roberts, C., Marton, M. J., et al. (2002) · New England Journal of Medicine · doi:10.1056/nejmoa021967 · Cited by 6,488
Repeated observation of breast tumor subtypes in independent gene expression data sets
Sørlie, T., Tibshirani, R., Parker, J., Hastie, T., Marron, J. S., Nobel, A., Deng, S., Johnsen, H., Pesich, R., Geisler, S., et al. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0932692100 · Cited by 5,429
Algorithm 457: finding all cliques of an undirected graph
Bron, C., & Kerbosch, J. (1973) · Communications of the ACM · doi:10.1145/362342.362367 · Cited by 2,452
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Feige, U., Peleg, D., & Kortsarz, G. (2001) · Algorithmica · doi:10.1007/s004530010050 · Cited by 592
The community-search problem and how to plan a successful cocktail party
Sozio, M., & Gionis, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835923 · Cited by 490
Self-citationGreedy Approximation Algorithms for Finding Dense Components in a Graph
Charikar, M. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44436-x_10 · Cited by 479
A Fast Parametric Maximum Flow Algorithm and Applications
Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218003 · Cited by 427
Finding a Maximum Density Subgraph
Goldberg, A. V. (1984) · UC Berkeley · Cited by 342
Massive Quasi-Clique Detection
Abello, J., Resende, M. G. C., & Sudarsky, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45995-2_51 · Cited by 331
The Average Distance in a Random Graph with Given Expected Degrees
Chung, F., & Lu, L. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129081 · Cited by 307
A scalable pattern mining approach to web graph compression with communities
Buehrer, G., & Chellapilla, K. (2008) · Proceedings of the international conference on Web search and web data mining - WSDM '08 · doi:10.1145/1341531.1341547 · Cited by 246
Khuller, S., & Saha, B. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-02927-1_50 · Cited by 241
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
Khot, S. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539705447037 · Cited by 236
A Survey of Algorithms for Dense Subgraph Discovery
Lee, V. E., Ruan, N., Jin, R., & Aggarwal, C. (2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0_10 · Cited by 216
Greedily Finding a Dense Subgraph
Asahiro, Y., Iwama, K., Tamaki, H., & Tokuyama, T. (2000) · Journal of Algorithms · doi:10.1006/jagm.1999.1062 · Cited by 211
Polynomial time approximation schemes for dense instances of NP-hard problems
Arora, S., Karger, D., & Karpinski, M. (1995) · Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 · doi:10.1145/225058.225140 · Cited by 199
Methods of Microarray Data Analysis V
(2007) · Springer eBooks · doi:10.1007/978-0-387-34569-7 · Cited by 168
MotifCut: regulatory motifs finding with maximum density subgraphs
Fratkin, E., Naughton, B. T., Brutlag, D. L., & Batzoglou, S. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl243 · Cited by 165
Dense subgraph maintenance under streaming edge weight updates for real-time story identification
Angel, A., Sarkas, N., Koudas, N., & Srivastava, D. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2168651.2168658 · Cited by 163
Approximating Maximum Clique by Removing Subgraphs
Feige, U. (2004) · SIAM Journal on Discrete Mathematics · doi:10.1137/s089548010240415x · Cited by 157
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
Feige, U., & Langberg, M. (2001) · Journal of Algorithms · doi:10.1006/jagm.2001.1183 · Cited by 151
Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
Kolountzakis, M. N., Miller, G. L., Peng, R., & Tsourakakis, C. E. (2012) · Internet Mathematics · doi:10.1080/15427951.2012.625260 · Cited by 148
Self-citationComplexity of finding dense subgraphs
Asahiro, Y., Hassin, R., & Iwama, K. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00243-8 · Cited by 126
Dense subgraph maintenance under streaming edge weight updates for real-time story identification
Angel, A., Koudas, N., Sarkas, N., Srivastava, D., Svendsen, M. S., & Tirthapura, S. (2013) · The VLDB Journal · doi:10.1007/s00778-013-0340-z · Cited by 119
An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem
Uno, T. (2008) · Algorithmica · doi:10.1007/s00453-008-9238-3 · Cited by 93
On Effectively Finding Maximal Quasi-cliques in Graphs
Brunato, M., Hoos, H. H., & Battiti, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92695-5_4 · Cited by 91
Cited by
Querying k-truss community in large and dynamic graphs
Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2610495 · Cited by 488
FENNEL: streaming graph partitioning for massive scale graphs
Tsourakakis, C., Gkantsidis, C., Radunovic, B., & Vojnovic, M. (2014) · Proceedings of the 7th ACM international conference on Web search and data mining · doi:10.1145/2556195.2556213 · Cited by 341
Self-citationA survey of community search over big graphs
Fang, Y., Huang, X., Qin, L., Zhang, Y., Zhang, W., Cheng, R., & Lin, X. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00556-x · Cited by 339
McCune, R. R., Weninger, T., & Madey, G. (2015) · ACM Computing Surveys · doi:10.1145/2818185 · Cited by 294
CatchSync: catching synchronized behavior in large directed graphs
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623632 · Cited by 151
Metadata
- Authors
- Tsourakakis, C., Bonchi, F., Gionis, A., Gullo, F., & Tsiarli, M.
- Venue
- Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2013-08-11
- Pages
- 104-112
- OpenAlex
- W2119757574
- Cited by
- 294
- References
- 29
- FWCI
- 14.72
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.