给定一个nxn的邻接矩阵，如何计算图形中的三角形数量(Matlab)? [英] Given an nxn Adjacency matrix, how can one compute the number of triangles in the graph (Matlab)?

问题描述

我编写了一个函数，给定n，它会生成随机的nxn邻接矩阵.我想知道是否有一种方法可以计算矩阵所代表的图中三角形的数量.

解决方案

第 n 个元素中的( i ， j )元素邻接矩阵 A 的幂计算从 i 到 j 的长度为 n 的路径数.

三角形是一条长度为3的路径，该路径在同一节点处开始和结束.因此， A 的三次方的 i 个对角元素计算包含 i 作为节点之一的三角形的数量.

对于图中的三个节点，每个不同的三角形将被计数两次(每个方向分别为顺时针和逆时针).

因此，不同个三角形的数量为trace(A^3) / 6.

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.

解决方案

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.

这篇关于给定一个nxn的邻接矩阵，如何计算图形中的三角形数量(Matlab)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！