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
Applied numerical linear algebra
(1998) · Choice Reviews Online · doi:10.5860/choice.35-3919 · Cited by 2,170
Rivlin, T. J. (1974) · International Linear Collider · Cited by 1,988
Introduction to linear algebra
(2016) · Cybersecurity and Applied Mathematics · doi:10.1016/b978-0-12-804452-0.09998-x · Cited by 1,646
Mason, J. C., & Handscomb, D. C. (2002) · Chapman & Hall/CRC eBooks · doi:10.1201/9781420036114 · Cited by 1,402
Lanczos Algorithms for Large Symmetric Eigenvalue Computations: Vol. I: Theory
Cullum, J. K., & Willoughby, R. A. (2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719192 · Cited by 1,291
The eigenvalues of random symmetric matrices
Füredi, Z., & Komlós, J. (1981) · Combinatorica · doi:10.1007/bf02579329 · Cited by 633
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28396 · Cited by 632
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
Spectra of “real-world” graphs: Beyond the semicircle law
Farkas, I. J., Derényi, I., Barabási, A.-L., & Vicsek, T. (2001) · Physical Review E · doi:10.1103/physreve.64.026704 · Cited by 499
Introduction to Linear Algebra
Lesk, A. M. (2004) · Introduction to Symmetry and Group Theory for Chemists · doi:10.1007/1-4020-2151-8_5 · Cited by 361
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
Leskovec, J., Chakrabarti, D., Kleinberg, J., & Faloutsos, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11564126_17 · Cited by 356
Curvature of co-links uncovers hidden thematic layers in the World Wide Web
Eckmann, J.-P., & Moses, E. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.032093399 · Cited by 346
Efficient semi-streaming algorithms for local triangle counting in massive graphs
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401898 · Cited by 319
Counting triangles in data streams
Buriol, L. S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., & Sohler, C. (2006) · Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1142351.1142388 · Cited by 252
Eigenvalues of Random Power law Graphs
Chung, F., Lu, L., & Vu, V. (2003) · Annals of Combinatorics · doi:10.1007/s000260300002 · Cited by 161
Spectral scaling and good expansion properties in complex networks
Estrada, E. (2006) · Europhysics Letters (EPL) · doi:10.1209/epl/i2005-10441-3 · Cited by 107
Ye, P., Peyser, B. D., Spencer, F. A., & Bader, J. S. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-270 · Cited by 22
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
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.