矩阵形式主义NxN邻接矩阵 [英] Matrix formalism NxN adjacency matrix

问题描述

让A是无向无权网络的NxN邻接矩阵，没有自环.令1为N个元素的列向量，均等于1.换句话说，1 =(1，1，...，1)T，其中上标T表示转置运算.使用矩阵形式主义(乘法常数，逐列乘法，转置和跟踪之类的矩阵运算等，但要避免总和符号Σ)来写以下表达式:

Let A be the NxN adjacency matrix of an undirected unweighted network, without self-loops. Let 1 be a column vector of N elements, all equal to 1. In other words 1 = (1, 1, ..., 1)T , where the superscript T indicates the transpose operation. Use the matrix formalism (multiplicative constants, multiplication row by column, matrix operations like transpose and trace, etc, but avoid the sum symbol Σ) to write expressions for:

a)向量k，其元素为所有节点i = 1、2，...，N的度ki.

a)The vector k whose elements are the degrees ki of all nodes i = 1, 2,..., N.

b)网络中的边缘总数L.

b)The total number of edges, L, in the network.

d)网络中存在的三角形T的数量，其中三角形表示三个节点，每个节点通过链接与其他两个节点相连(提示:您可以使用矩阵的迹线).

d)The number of triangles T present in the network, where a triangle means three nodes, each connected by links to the other two (Hint: you can use the trace of a matrix).

推荐答案

a)将邻接矩阵乘以1(您提到的向量) b)使用(1，1，…，1)*(来自a)T的向量，这将为您提供所有的总和 邻接矩阵中的元素，即所有边的数量. c)存在一个定理.设A为邻接矩阵， 然后A ^ k [i] [j]给出从节点i到节点j的长度为k的路径数. 如果然后计算A ^ 3并查看对角元素(i)，则这些元素将为您提供从节点i到长度为3的自身的路径数，即所谓的三角形. 如果然后考虑所有排列，答案是sum(trace(A ^ 3))/6.

a) multiply the adjacency matrix with the 1 (vector you mentioned) b) use (1, 1, …, 1) * (vector from a)T, which gives you the sum of all elements in the adjacency matrix, that is the number of all edges. c) There exists a theorem. Let A be an adjacency matrix, then A^k[i][j] gives you the number of paths, of length k from node i to node j. If you then calculate A^3 and look at the diagonal elements (i), those give you the number of paths from node i to itself of length 3, which are so called triangles. If you then account for all permutations, the answer is sum(trace(A^3)) / 6.

这篇关于矩阵形式主义NxN邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！