The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Graph mining: Laws, generators, and algorithms
Abstract
How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M:N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: “How can we generate synthetic but realistic graphs?” To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Burt, R. S. (1992) · doi:10.4159/9780674029095 · Cited by 9,093
Error and attack tolerance of complex networks
Albert, R., Jeong, H., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35019019 · Cited by 7,534
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Estimating the Number of Clusters in a Data Set Via the Gap Statistic
Tibshirani, R., Walther, G., & Hastie, T. (2001) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/1467-9868.00293 · Cited by 6,205
Classes of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Graphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281
Self-citationDorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Cited by
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Relational learning via latent social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557109 · Cited by 799
Leveraging social media networks for classification
Tang, L., & Liu, H. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0210-x · Cited by 360
A classification for community discovery methods in complex networks
Coscia, M., Giannotti, F., & Pedreschi, D. (2011) · Statistical Analysis and Data Mining: The ASA Data Science Journal · doi:10.1002/sam.10133 · Cited by 353
Topic-link LDA: joint models of topic and author community
Liu, Y., Niculescu-Mizil, A., & Gryc, W. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553460 · Cited by 288
Metadata
- Authors
- Chakrabarti, D., & Faloutsos, C.
- Venue
- ACM Computing Surveys
- Published
- 2006-06-29
- Volume
- 38
- Issue
- 1
- Pages
- 2
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2085761620
- Cited by
- 609
- References
- 12
- FWCI
- 18.91
- Type
- journal article
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Graph mining: Laws, generators, and algorithms. https://app.cochat.ai/papers/10.1145/1132952.1132954
- The paper
- Chakrabarti, D., & Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM Computing Surveys. https://doi.org/10.1145/1132952.1132954
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.
