Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products
Counting triangles in graphs is a fundamental operation in network analysis, underpinning metrics such as clustering coefficients and serving as a signal for community detection, link prediction, and anomaly detection. The standard approach computes the trace of the cube of the adjacency matrix, but explicitly forming $\mathbf{A}^3$ is infeasible for large graphs. Hutchinson randomized trace estimator offers an efficient alternative by approximating the trace through stochastic averaging of quadratic forms, requiring only matrix vector products with $\mathbf{A}$. However, in distributed and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.22629
curl -X POST /api/v1/records/arxiv/2606.22629/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.22629/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'