Interpretation Power of weighted Graph's Adjacency Matrix

1.1k Views Asked by At

Consider a graph with two notes $\{1,2\}$ with loops at 1 and 2 and an edge $(1,2)$. For a parameter $\mu\in(0,\frac{1}{2})$ the weighted adjacency matrix $A$ of $G$ takes the form

$$A = \begin{pmatrix}1-\mu & \mu \\ \mu & 1-\mu\end{pmatrix}.$$

First question: Is there an interpretation of $A^k$ for some positive integer $k$?

Second question: Direct calculations of the eigenvalues and vectors show that
$$\lim_{k\to\infty} A^k = \dfrac{1}{2}\begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix}$$ where the limit is taken for each component of $A^k$. Is there an interpretation in the context of weighted graphs for that behavior?

1

There are 1 best solutions below

0
On BEST ANSWER

The entry at position $(i,j)$ of $A^k$ is the sum of the products of all weights of all paths from node $i$ to node $j$ of length exactly $k$. So for every path of length $k$, you multiply all weights to get a weight of the whole path, and then you sum over all paths. That is especially important in unweighted graphs (where the entries of the matrix $A$ are only zeroes and ones), as you can count the number of paths of a certain length in this way and solve multiple problems in combinatorics.
It also has applications in stochastics, where the product of weights is the product of probabilities to find a joined probability.

Your limit now tells you the value of $$\sum_{x_i \in \{\mu, 1-\mu\}} \prod_{i=1}^{\infty} x_i = \frac{1}{2},$$ where the sum runs over all possible choices of $x_i$, and if you require an even/odd number of $\mu$ (to get from one vertex to the other or not) it doesn't change the result.