Loading...
Please wait, while we are loading the content...
Similar Documents
Lecturer: daniel a. Spielman lecture 7 7.1 random walks on weighted graphs (2004).
| Content Provider | CiteSeerX |
|---|---|
| Abstract | We now define random walks on weighted graphs. We will let A denote the adjacency matrix of a weighted graph. We will also the graph to have self-loops, which will correspond to diagonal entries in A. Thus, the only restriction on A is that is be symmetric and non-negative. When our random walk is at a vertex u, it will go to node v with probability proportional to au,v: def au,v mu,v = �. w au,w So that mu,v can be the probability of moving from v to w, I am going to have to do something I hate: multiplying by vectors from the right. In matrix notation, we can form the matrix of probabiliites, M, by setting def du = w au,w def D = diag(d1,..., dn) def M = D −1 A. I will call M the walk matrix of the weighted graph. We must be careful when dealing with M because it is not symmetric, and so its eigenvectors are not necessarily orthogonal, or might not even exist. However, M is very close to symmetric. If we define the normalized adjacency matrix def N = D −1/2 AD −1/2, we can see that M and N have the same eigenvalues and related eigenvectors. To make this more precise, let v be an eigenvector of N with eigenvalue λ. Setting w = vD 1/2, we find λv = vN λv = vD 1/2 MD −1/2 λwD −1/2 = wD −1/2 D 1/2 MD −1/2 λwD −1/2 = wMD −1/2 λw = wM. |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Content Type | Text |
