Menu
I wrote a function that, given n, generates random nxn adjacency matrices. I was wondering if there is a way to count the number a triangles in the graph represented by the matrix.
953
Given an Undirected simple graph, We need to find how many triangles it can have. For example below graph have 2 triangles in it. Let A[][] be the adjacency matrix representation of the graph. If we calculate A3, then the number of triangles in Undirected Graph is equal to trace(A3) / 6.
A = adjacency( G ) returns the sparse adjacency matrix for graph G . If (i,j) is an edge in G , then A(i,j) = 1 . Otherwise, A(i,j) = 0 . A = adjacency( G ,'weighted') returns a weighted adjacency matrix, where for each edge (i,j) , the value A(i,j) contains the weight of the edge.
Use comma "," as separator and press "Plot Graph". Enter adjacency matrix. Press "Plot Graph". Use Ctrl + ← ↑ → ↓ keys to move between cells.
figure A = adjacency(G); H = graph(A(1:30,1:30)); h = plot(H); To visualize the adjacency matrix of this hemisphere, use the spy function to plot the silhouette of the nonzero elements in the adjacency matrix. Note that the matrix is symmetric, since if node i is connected to node j, then node j is connected to node i.
The (i, j) element in the n'th power of an adjacency matrix A counts the number of paths of length n starting at i and ending at j.
A triangle is a path of length 3 that starts and ends at the same node. Therefore the i'th diagonal element of the 3rd power of A counts the number of triangles that contain i as one of the nodes.
Each distinct triangle will be counted twice for each of the three nodes in the graph (once in each direction, clockwise and anticlockwise).
Therefore the number of distinct triangles is trace(A^3) / 6.
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
