Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says:

Walks: which allow both nodes and edges to be used more than once. For example, in Figure 1, Mary-Bob-Sue-Ramona-Bob-Mary-Joe is a walk, but not a trail or a path. A particular dollar bill flows through the person-person network along walks. Mary might give the bill to Bob in one transaction, and Bob might return it to Mary in another.

A trail is when a node i may be visited multiple times, but a particular edge connecting it with a node j, can be visited no more than 1 time.


An identity from linear algebra is used which I cannot find is used Suppose an undirected network has an adjacency matrix A, where $a_{i,j}=1$ if nodes i and j are connected, and $a_{i,j}=0$ otherwise. Then the basic identity

$(A^{n})_{ij} = \sum^{n}_{k_{1} = 1}\sum^{n}_{k_{2}=1}\ldots\sum^{n}_{k_{n-1}=1}a_{i,k_{1}}a_{k_{1},k_{2}}\ldots a_{k_{n-1},j}$

shows that $(A^{n})_{ij}$ counts the total number of walks of length n from node i to node j.


The indice k is not explicitly defined in the text or given more description. What makes it hard to understand is that the index k is not being summed over the possible nodes the matrix since n is the walk length as it is written, unless there is a mistake.

I want to see if I can be bold and say that the equation should have been better written as (making N be the node set or square matrix dimension):

$(A^{n})_{ij} = \sum^{N}_{k_{1}=1}(\sum^{N}_{k_{2}=1}\ldots(\sum^{N}_{k_{n-1}=1}a_{i,k_{1}}a_{k_{1},k_{2}}\ldots a_{k_{n-1},j}))$

Because I read the equation as a brute force summation over the total set of combinations of length n.

Is this interpretation correct?

and is $(A^{n})_{ij}$ the result of the entry for ij in doing the matrix exponentiation of the adjacency matrix n times because in simple examples I tried with small graphs I did not get the correct answer (tried simple fully connected graph with n=2,3,4)?

Best,

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Yes, you're right (the $k$'s should run from 1 to $N$, the size of the matrix), and yes, $(A^n)_{ij}$ is the $(i,j)$ entry in $A^n=AA\dots A$ ($n$ factors).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.