Mercurial > repos > shellac > guppy_basecaller
annotate env/lib/python3.7/site-packages/networkx/linalg/laplacianmatrix.py @ 2:6af9afd405e9 draft
"planemo upload commit 0a63dd5f4d38a1f6944587f52a8cd79874177fc1"
author | shellac |
---|---|
date | Thu, 14 May 2020 14:56:58 -0400 |
parents | 26e78fe6e8c4 |
children |
rev | line source |
---|---|
0
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
1 """Laplacian matrix of graphs. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
2 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
3 # Copyright (C) 2004-2019 by |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
4 # Aric Hagberg <hagberg@lanl.gov> |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
5 # Dan Schult <dschult@colgate.edu> |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
6 # Pieter Swart <swart@lanl.gov> |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
7 # All rights reserved. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
8 # BSD license. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
9 import networkx as nx |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
10 from networkx.utils import not_implemented_for |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
11 __author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
12 'Pieter Swart (swart@lanl.gov)', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
13 'Dan Schult (dschult@colgate.edu)', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
14 'Alejandro Weinstein <alejandro.weinstein@gmail.com>']) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
15 __all__ = ['laplacian_matrix', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
16 'normalized_laplacian_matrix', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
17 'directed_laplacian_matrix', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
18 'directed_combinatorial_laplacian_matrix'] |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
19 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
20 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
21 @not_implemented_for('directed') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
22 def laplacian_matrix(G, nodelist=None, weight='weight'): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
23 """Returns the Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
24 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
25 The graph Laplacian is the matrix L = D - A, where |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
26 A is the adjacency matrix and D is the diagonal matrix of node degrees. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
27 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
28 Parameters |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
29 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
30 G : graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
31 A NetworkX graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
32 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
33 nodelist : list, optional |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
34 The rows and columns are ordered according to the nodes in nodelist. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
35 If nodelist is None, then the ordering is produced by G.nodes(). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
36 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
37 weight : string or None, optional (default='weight') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
38 The edge data key used to compute each value in the matrix. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
39 If None, then each edge has weight 1. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
40 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
41 Returns |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
42 ------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
43 L : SciPy sparse matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
44 The Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
45 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
46 Notes |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
47 ----- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
48 For MultiGraph/MultiDiGraph, the edges weights are summed. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
49 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
50 See Also |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
51 -------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
52 to_numpy_matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
53 normalized_laplacian_matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
54 laplacian_spectrum |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
55 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
56 import scipy.sparse |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
57 if nodelist is None: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
58 nodelist = list(G) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
59 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
60 format='csr') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
61 n, m = A.shape |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
62 diags = A.sum(axis=1) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
63 D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
64 return D - A |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
65 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
66 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
67 @not_implemented_for('directed') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
68 def normalized_laplacian_matrix(G, nodelist=None, weight='weight'): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
69 r"""Returns the normalized Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
70 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
71 The normalized graph Laplacian is the matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
72 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
73 .. math:: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
74 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
75 N = D^{-1/2} L D^{-1/2} |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
76 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
77 where `L` is the graph Laplacian and `D` is the diagonal matrix of |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
78 node degrees. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
79 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
80 Parameters |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
81 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
82 G : graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
83 A NetworkX graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
84 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
85 nodelist : list, optional |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
86 The rows and columns are ordered according to the nodes in nodelist. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
87 If nodelist is None, then the ordering is produced by G.nodes(). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
88 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
89 weight : string or None, optional (default='weight') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
90 The edge data key used to compute each value in the matrix. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
91 If None, then each edge has weight 1. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
92 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
93 Returns |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
94 ------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
95 N : NumPy matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
96 The normalized Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
97 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
98 Notes |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
99 ----- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
100 For MultiGraph/MultiDiGraph, the edges weights are summed. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
101 See to_numpy_matrix for other options. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
102 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
103 If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
104 the adjacency matrix [2]_. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
105 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
106 See Also |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
107 -------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
108 laplacian_matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
109 normalized_laplacian_spectrum |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
110 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
111 References |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
112 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
113 .. [1] Fan Chung-Graham, Spectral Graph Theory, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
114 CBMS Regional Conference Series in Mathematics, Number 92, 1997. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
115 .. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
116 Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
117 March 2007. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
118 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
119 import scipy |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
120 import scipy.sparse |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
121 if nodelist is None: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
122 nodelist = list(G) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
123 A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
124 format='csr') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
125 n, m = A.shape |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
126 diags = A.sum(axis=1).flatten() |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
127 D = scipy.sparse.spdiags(diags, [0], m, n, format='csr') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
128 L = D - A |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
129 with scipy.errstate(divide='ignore'): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
130 diags_sqrt = 1.0 / scipy.sqrt(diags) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
131 diags_sqrt[scipy.isinf(diags_sqrt)] = 0 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
132 DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format='csr') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
133 return DH.dot(L.dot(DH)) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
134 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
135 ############################################################################### |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
136 # Code based on |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
137 # https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
138 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
139 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
140 @not_implemented_for('undirected') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
141 @not_implemented_for('multigraph') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
142 def directed_laplacian_matrix(G, nodelist=None, weight='weight', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
143 walk_type=None, alpha=0.95): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
144 r"""Returns the directed Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
145 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
146 The graph directed Laplacian is the matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
147 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
148 .. math:: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
149 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
150 L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
151 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
152 where `I` is the identity matrix, `P` is the transition matrix of the |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
153 graph, and `\Phi` a matrix with the Perron vector of `P` in the diagonal and |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
154 zeros elsewhere. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
155 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
156 Depending on the value of walk_type, `P` can be the transition matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
157 induced by a random walk, a lazy random walk, or a random walk with |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
158 teleportation (PageRank). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
159 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
160 Parameters |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
161 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
162 G : DiGraph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
163 A NetworkX graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
164 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
165 nodelist : list, optional |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
166 The rows and columns are ordered according to the nodes in nodelist. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
167 If nodelist is None, then the ordering is produced by G.nodes(). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
168 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
169 weight : string or None, optional (default='weight') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
170 The edge data key used to compute each value in the matrix. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
171 If None, then each edge has weight 1. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
172 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
173 walk_type : string or None, optional (default=None) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
174 If None, `P` is selected depending on the properties of the |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
175 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
176 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
177 alpha : real |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
178 (1 - alpha) is the teleportation probability used with pagerank |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
179 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
180 Returns |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
181 ------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
182 L : NumPy array |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
183 Normalized Laplacian of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
184 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
185 Notes |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
186 ----- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
187 Only implemented for DiGraphs |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
188 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
189 See Also |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
190 -------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
191 laplacian_matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
192 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
193 References |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
194 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
195 .. [1] Fan Chung (2005). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
196 Laplacians and the Cheeger inequality for directed graphs. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
197 Annals of Combinatorics, 9(1), 2005 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
198 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
199 import scipy as sp |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
200 from scipy.sparse import spdiags, linalg |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
201 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
202 P = _transition_matrix(G, nodelist=nodelist, weight=weight, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
203 walk_type=walk_type, alpha=alpha) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
204 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
205 n, m = P.shape |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
206 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
207 evals, evecs = linalg.eigs(P.T, k=1) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
208 v = evecs.flatten().real |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
209 p = v / v.sum() |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
210 sqrtp = sp.sqrt(p) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
211 Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
212 I = sp.identity(len(G)) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
213 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
214 return I - (Q + Q.T) / 2.0 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
215 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
216 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
217 @not_implemented_for('undirected') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
218 @not_implemented_for('multigraph') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
219 def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
220 walk_type=None, alpha=0.95): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
221 r"""Return the directed combinatorial Laplacian matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
222 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
223 The graph directed combinatorial Laplacian is the matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
224 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
225 .. math:: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
226 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
227 L = \Phi - (\Phi P + P^T \Phi) / 2 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
228 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
229 where `P` is the transition matrix of the graph and and `\Phi` a matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
230 with the Perron vector of `P` in the diagonal and zeros elsewhere. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
231 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
232 Depending on the value of walk_type, `P` can be the transition matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
233 induced by a random walk, a lazy random walk, or a random walk with |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
234 teleportation (PageRank). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
235 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
236 Parameters |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
237 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
238 G : DiGraph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
239 A NetworkX graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
240 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
241 nodelist : list, optional |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
242 The rows and columns are ordered according to the nodes in nodelist. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
243 If nodelist is None, then the ordering is produced by G.nodes(). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
244 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
245 weight : string or None, optional (default='weight') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
246 The edge data key used to compute each value in the matrix. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
247 If None, then each edge has weight 1. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
248 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
249 walk_type : string or None, optional (default=None) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
250 If None, `P` is selected depending on the properties of the |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
251 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
252 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
253 alpha : real |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
254 (1 - alpha) is the teleportation probability used with pagerank |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
255 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
256 Returns |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
257 ------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
258 L : NumPy array |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
259 Combinatorial Laplacian of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
260 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
261 Notes |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
262 ----- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
263 Only implemented for DiGraphs |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
264 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
265 See Also |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
266 -------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
267 laplacian_matrix |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
268 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
269 References |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
270 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
271 .. [1] Fan Chung (2005). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
272 Laplacians and the Cheeger inequality for directed graphs. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
273 Annals of Combinatorics, 9(1), 2005 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
274 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
275 from scipy.sparse import spdiags, linalg |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
276 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
277 P = _transition_matrix(G, nodelist=nodelist, weight=weight, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
278 walk_type=walk_type, alpha=alpha) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
279 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
280 n, m = P.shape |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
281 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
282 evals, evecs = linalg.eigs(P.T, k=1) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
283 v = evecs.flatten().real |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
284 p = v / v.sum() |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
285 Phi = spdiags(p, [0], n, n) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
286 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
287 Phi = Phi.todense() |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
288 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
289 return Phi - (Phi*P + P.T*Phi) / 2.0 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
290 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
291 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
292 def _transition_matrix(G, nodelist=None, weight='weight', |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
293 walk_type=None, alpha=0.95): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
294 """Returns the transition matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
295 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
296 This is a row stochastic giving the transition probabilities while |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
297 performing a random walk on the graph. Depending on the value of walk_type, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
298 P can be the transition matrix induced by a random walk, a lazy random walk, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
299 or a random walk with teleportation (PageRank). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
300 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
301 Parameters |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
302 ---------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
303 G : DiGraph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
304 A NetworkX graph |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
305 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
306 nodelist : list, optional |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
307 The rows and columns are ordered according to the nodes in nodelist. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
308 If nodelist is None, then the ordering is produced by G.nodes(). |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
309 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
310 weight : string or None, optional (default='weight') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
311 The edge data key used to compute each value in the matrix. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
312 If None, then each edge has weight 1. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
313 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
314 walk_type : string or None, optional (default=None) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
315 If None, `P` is selected depending on the properties of the |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
316 graph. Otherwise is one of 'random', 'lazy', or 'pagerank' |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
317 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
318 alpha : real |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
319 (1 - alpha) is the teleportation probability used with pagerank |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
320 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
321 Returns |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
322 ------- |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
323 P : NumPy array |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
324 transition matrix of G. |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
325 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
326 Raises |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
327 ------ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
328 NetworkXError |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
329 If walk_type not specified or alpha not in valid range |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
330 """ |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
331 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
332 import scipy as sp |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
333 from scipy.sparse import identity, spdiags |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
334 if walk_type is None: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
335 if nx.is_strongly_connected(G): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
336 if nx.is_aperiodic(G): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
337 walk_type = "random" |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
338 else: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
339 walk_type = "lazy" |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
340 else: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
341 walk_type = "pagerank" |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
342 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
343 M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight, |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
344 dtype=float) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
345 n, m = M.shape |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
346 if walk_type in ["random", "lazy"]: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
347 DI = spdiags(1.0 / sp.array(M.sum(axis=1).flat), [0], n, n) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
348 if walk_type == "random": |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
349 P = DI * M |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
350 else: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
351 I = identity(n) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
352 P = (I + DI * M) / 2.0 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
353 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
354 elif walk_type == "pagerank": |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
355 if not (0 < alpha < 1): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
356 raise nx.NetworkXError('alpha must be between 0 and 1') |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
357 # this is using a dense representation |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
358 M = M.todense() |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
359 # add constant to dangling nodes' row |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
360 dangling = sp.where(M.sum(axis=1) == 0) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
361 for d in dangling[0]: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
362 M[d] = 1.0 / n |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
363 # normalize |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
364 M = M / M.sum(axis=1) |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
365 P = alpha * M + (1 - alpha) / n |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
366 else: |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
367 raise nx.NetworkXError("walk_type must be random, lazy, or pagerank") |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
368 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
369 return P |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
370 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
371 |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
372 # fixture for pytest |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
373 def setup_module(module): |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
374 import pytest |
26e78fe6e8c4
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
shellac
parents:
diff
changeset
|
375 numpy = pytest.importorskip('numpy') |