ioftools / networkxMiCe / networkxmaster / networkx / algorithms / communicability_alg.py @ 5cef0f13
History  View  Annotate  Download (5.05 KB)
1 
# * coding: utf8 *


2 
"""

3 
Communicability.

4 
"""

5 
# Copyright (C) 2011 by

6 
# Aric Hagberg <hagberg@lanl.gov>

7 
# Dan Schult <dschult@colgate.edu>

8 
# Pieter Swart <swart@lanl.gov>

9 
# Previously coded as communicability centrality

10 
# All rights reserved.

11 
# BSD license.

12 
import networkx as nx 
13 
from networkx.utils import * 
14 
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)', 
15 
'Franck Kalala (franckkalala@yahoo.fr'])

16 
__all__ = ['communicability',

17 
'communicability_exp',

18 
] 
19  
20  
21 
@not_implemented_for('directed') 
22 
@not_implemented_for('multigraph') 
23 
def communicability(G): 
24 
r"""Returns communicability between all pairs of nodes in G.

25 

26 
The communicability between pairs of nodes in G is the sum of

27 
closed walks of different lengths starting at node u and ending at node v.

28 

29 
Parameters

30 


31 
G: graph

32 

33 
Returns

34 


35 
comm: dictionary of dictionaries

36 
Dictionary of dictionaries keyed by nodes with communicability

37 
as the value.

38 

39 
Raises

40 


41 
NetworkXError

42 
If the graph is not undirected and simple.

43 

44 
See Also

45 


46 
communicability_exp:

47 
Communicability between all pairs of nodes in G using spectral

48 
decomposition.

49 
communicability_betweenness_centrality:

50 
Communicability betweeness centrality for each node in G.

51 

52 
Notes

53 


54 
This algorithm uses a spectral decomposition of the adjacency matrix.

55 
Let G=(V,E) be a simple undirected graph. Using the connection between

56 
the powers of the adjacency matrix and the number of walks in the graph,

57 
the communicability between nodes `u` and `v` based on the graph spectrum

58 
is [1]_

59 

60 
.. math::

61 
C(u,v)=\sum_{j=1}^{n}\phi_{j}(u)\phi_{j}(v)e^{\lambda_{j}},

62 

63 
where `\phi_{j}(u)` is the `u\rm{th}` element of the `j\rm{th}` orthonormal

64 
eigenvector of the adjacency matrix associated with the eigenvalue

65 
`\lambda_{j}`.

66 

67 
References

68 


69 
.. [1] Ernesto Estrada, Naomichi Hatano,

70 
"Communicability in complex networks",

71 
Phys. Rev. E 77, 036111 (2008).

72 
https://arxiv.org/abs/0707.0756

73 

74 
Examples

75 


76 
>>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])

77 
>>> c = nx.communicability(G)

78 
"""

79 
import numpy 
80 
import scipy.linalg 
81 
nodelist = list(G) # ordering of nodes in matrix 
82 
A = nx.to_numpy_matrix(G, nodelist) 
83 
# convert to 01 matrix

84 
A[A != 0.0] = 1 
85 
w, vec = numpy.linalg.eigh(A) 
86 
expw = numpy.exp(w) 
87 
mapping = dict(zip(nodelist, range(len(nodelist)))) 
88 
c = {} 
89 
# computing communicabilities

90 
for u in G: 
91 
c[u] = {} 
92 
for v in G: 
93 
s = 0

94 
p = mapping[u] 
95 
q = mapping[v] 
96 
for j in range(len(nodelist)): 
97 
s += vec[:, j][p, 0] * vec[:, j][q, 0] * expw[j] 
98 
c[u][v] = float(s)

99 
return c

100  
101  
102 
@not_implemented_for('directed') 
103 
@not_implemented_for('multigraph') 
104 
def communicability_exp(G): 
105 
r"""Returns communicability between all pairs of nodes in G.

106 

107 
Communicability between pair of node (u,v) of node in G is the sum of

108 
closed walks of different lengths starting at node u and ending at node v.

109 

110 
Parameters

111 


112 
G: graph

113 

114 
Returns

115 


116 
comm: dictionary of dictionaries

117 
Dictionary of dictionaries keyed by nodes with communicability

118 
as the value.

119 

120 
Raises

121 


122 
NetworkXError

123 
If the graph is not undirected and simple.

124 

125 
See Also

126 


127 
communicability:

128 
Communicability between pairs of nodes in G.

129 
communicability_betweenness_centrality:

130 
Communicability betweeness centrality for each node in G.

131 

132 
Notes

133 


134 
This algorithm uses matrix exponentiation of the adjacency matrix.

135 

136 
Let G=(V,E) be a simple undirected graph. Using the connection between

137 
the powers of the adjacency matrix and the number of walks in the graph,

138 
the communicability between nodes u and v is [1]_,

139 

140 
.. math::

141 
C(u,v) = (e^A)_{uv},

142 

143 
where `A` is the adjacency matrix of G.

144 

145 
References

146 


147 
.. [1] Ernesto Estrada, Naomichi Hatano,

148 
"Communicability in complex networks",

149 
Phys. Rev. E 77, 036111 (2008).

150 
https://arxiv.org/abs/0707.0756

151 

152 
Examples

153 


154 
>>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])

155 
>>> c = nx.communicability_exp(G)

156 
"""

157 
import scipy.linalg 
158 
nodelist = list(G) # ordering of nodes in matrix 
159 
A = nx.to_numpy_matrix(G, nodelist) 
160 
# convert to 01 matrix

161 
A[A != 0.0] = 1 
162 
# communicability matrix

163 
expA = scipy.linalg.expm(A.A) 
164 
mapping = dict(zip(nodelist, range(len(nodelist)))) 
165 
c = {} 
166 
for u in G: 
167 
c[u] = {} 
168 
for v in G: 
169 
c[u][v] = float(expA[mapping[u], mapping[v]])

170 
return c

171  
172 
# fixture for nose tests

173  
174  
175 
def setup_module(module): 
176 
from nose import SkipTest 
177 
try:

178 
import numpy 
179 
except:

180 
raise SkipTest("NumPy not available") 
181 
try:

182 
import scipy 
183 
except:

184 
raise SkipTest("SciPy not available") 