CODEWITHSUNDEEP
algorithmnumpygraphtheano
James Atwood
James Atwood

Reputation: 4329

Number of triangles involving any two nodes

Let's say I have an adjacency matrix A that represents an unweighted, undirected graph.

I would like to compute B, where B[i][j] is the number of closed triangles that include nodes i and j.

Is there a way to compute B from A using just linear algebra? I'd like to implement this in theano.

Upvotes: 0

Views: 64

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32597

Assume that i and j are adjacent to each other. Then, the number of triangles that contain both is the number of other vertices k that are connected to both of them. I.e.

B_i,j = Sum_k (if A_i,k=1 and A_k,j=1 then 1 else 0)

This assumes that the diagonal of the adjacency matrix is 0. The boolean expression can be converted to a single product because we use only 0 and 1:

B_i,j = Sum_k A_i,k * A_k,j

This looks pretty much like matrix multiplication and indeed it is:

B = A^2

However, we are still under the assumption that i and j are connected. To integrate this assumption into the final formula, we just have to multiply each component of B by the according entry of the adjacency matrix. This sets all entries to zero where i and j are not connected. So the final formula is:

B = (A^2) * A,

where ^2 is the matrix product with itself and * is component-wise multiplication.

Upvotes: 2

Related Questions