I'm trying to use some fragment-based measures for a network.
Given an adjacency matrix representing a (large) network how do you calculate the number of triangles that are incident to every node i? Is there an algorithm or simple formula I am missing. The network is too large to count each triangle individually.
If you compute $A^{3}$ the element on the diagonal will the be number of walks of length $3$ beginning and ending at vertex $i$. This is twice the number of triangles that include vertex $i$, since you could have $i\to j\to k\to i$ or $i\to k\to j\to i$... i.e. each triangle is counted twice.
Incidentally, if you sum the diagonal, you get 6 times the number of triangles in the whole graph.
There are a number of ways that you can do large (probably sparse) matrix multiplication in parallel (provided that your graph is not ridiculously large). If the matrix is just too large for that (talking 100s GB or several TB size for the $A$), then you could try using a parallel MapReduce method to compute triangles. There are several references (with algorithms of varying complexity). Here's one such example: http://arxiv.org/abs/1301.5887 I have not carefully read this paper, but the one I have read carefully requires a subscription to view (published in a CS journal).