The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws
Abstract
How can we quickly find the number of triangles in a large graph, without actually counting them? Triangles are important for real world social networks, lying at the heart of the clustering coefficient and of the transitivity ratio. However, straight-forward and even approximate counting algorithms can be slow, trying to execute or approximate the equivalent of a 3-way database join. In this paper, we provide two algorithms, the eigentriangle for counting the total number of triangles in a graph, and the eigentrianglelocal algorithm that gives the count of triangles that contain a desired node. Additional contributions include the following: (a) We show that both algorithms achieve excellent accuracy, with up to sime 1000x faster execution time, on several, real graphs and (b) we discover two new power laws (degree-triangle and triangleparticipationlaws) with surprising properties.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Godsil, C., & Royle, G. (2001) · Graduate Texts in Mathematics · doi:10.1007/978-1-4613-0163-9 · Cited by 8,154
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
MapReduce: Simplified Data Processing on Large Cluster
Senior Software Developer, A. U., & Dayalan, M. (2018) · International Journal of Research and Engineering · doi:10.21276/ijre.2018.5.5.4 · Cited by 2,948
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Cited by
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Kronecker Graphs: An Approach to Modeling Networks
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., Faloutsos, C., & Ghahramani, Z. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0812.4905 · Cited by 697
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-citationDOULION: counting triangles in massive graphs with a coin
Tsourakakis, C. E., Kang, U., Miller, G. L., & Faloutsos, C. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557111 · Cited by 328
Self-citationWorst-case optimal join algorithms: [extended abstract]
Ngo, H. Q., Porat, E., Ré, C., & Rudra, A. (2012) · Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems · doi:10.1145/2213556.2213565 · Cited by 324
Avron, H., & Toledo, S. (2011) · Journal of the ACM · doi:10.1145/1944345.1944349 · Cited by 284
Metadata
- Authors
- Tsourakakis, C. E.
- Venue
- 2008 Eighth IEEE International Conference on Data Mining
- Publisher
- IEEE
- Published
- 2008-12
- Pages
- 608-617
- ISSN
- 1550-4786 (ISSN-L)
- OpenAlex
- W2120595041
- Cited by
- 265
- References
- 27
- FWCI
- 10.95
- 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.