Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/communicability_alg.py: 27%
41 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Communicability.
3"""
4import networkx as nx
5from networkx.utils import not_implemented_for
7__all__ = ["communicability", "communicability_exp"]
10@not_implemented_for("directed")
11@not_implemented_for("multigraph")
12@nx._dispatch
13def communicability(G):
14 r"""Returns communicability between all pairs of nodes in G.
16 The communicability between pairs of nodes in G is the sum of
17 walks of different lengths starting at node u and ending at node v.
19 Parameters
20 ----------
21 G: graph
23 Returns
24 -------
25 comm: dictionary of dictionaries
26 Dictionary of dictionaries keyed by nodes with communicability
27 as the value.
29 Raises
30 ------
31 NetworkXError
32 If the graph is not undirected and simple.
34 See Also
35 --------
36 communicability_exp:
37 Communicability between all pairs of nodes in G using spectral
38 decomposition.
39 communicability_betweenness_centrality:
40 Communicability betweenness centrality for each node in G.
42 Notes
43 -----
44 This algorithm uses a spectral decomposition of the adjacency matrix.
45 Let G=(V,E) be a simple undirected graph. Using the connection between
46 the powers of the adjacency matrix and the number of walks in the graph,
47 the communicability between nodes `u` and `v` based on the graph spectrum
48 is [1]_
50 .. math::
51 C(u,v)=\sum_{j=1}^{n}\phi_{j}(u)\phi_{j}(v)e^{\lambda_{j}},
53 where `\phi_{j}(u)` is the `u\rm{th}` element of the `j\rm{th}` orthonormal
54 eigenvector of the adjacency matrix associated with the eigenvalue
55 `\lambda_{j}`.
57 References
58 ----------
59 .. [1] Ernesto Estrada, Naomichi Hatano,
60 "Communicability in complex networks",
61 Phys. Rev. E 77, 036111 (2008).
62 https://arxiv.org/abs/0707.0756
64 Examples
65 --------
66 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
67 >>> c = nx.communicability(G)
68 """
69 import numpy as np
71 nodelist = list(G) # ordering of nodes in matrix
72 A = nx.to_numpy_array(G, nodelist)
73 # convert to 0-1 matrix
74 A[A != 0.0] = 1
75 w, vec = np.linalg.eigh(A)
76 expw = np.exp(w)
77 mapping = dict(zip(nodelist, range(len(nodelist))))
78 c = {}
79 # computing communicabilities
80 for u in G:
81 c[u] = {}
82 for v in G:
83 s = 0
84 p = mapping[u]
85 q = mapping[v]
86 for j in range(len(nodelist)):
87 s += vec[:, j][p] * vec[:, j][q] * expw[j]
88 c[u][v] = float(s)
89 return c
92@not_implemented_for("directed")
93@not_implemented_for("multigraph")
94@nx._dispatch
95def communicability_exp(G):
96 r"""Returns communicability between all pairs of nodes in G.
98 Communicability between pair of node (u,v) of node in G is the sum of
99 walks of different lengths starting at node u and ending at node v.
101 Parameters
102 ----------
103 G: graph
105 Returns
106 -------
107 comm: dictionary of dictionaries
108 Dictionary of dictionaries keyed by nodes with communicability
109 as the value.
111 Raises
112 ------
113 NetworkXError
114 If the graph is not undirected and simple.
116 See Also
117 --------
118 communicability:
119 Communicability between pairs of nodes in G.
120 communicability_betweenness_centrality:
121 Communicability betweenness centrality for each node in G.
123 Notes
124 -----
125 This algorithm uses matrix exponentiation of the adjacency matrix.
127 Let G=(V,E) be a simple undirected graph. Using the connection between
128 the powers of the adjacency matrix and the number of walks in the graph,
129 the communicability between nodes u and v is [1]_,
131 .. math::
132 C(u,v) = (e^A)_{uv},
134 where `A` is the adjacency matrix of G.
136 References
137 ----------
138 .. [1] Ernesto Estrada, Naomichi Hatano,
139 "Communicability in complex networks",
140 Phys. Rev. E 77, 036111 (2008).
141 https://arxiv.org/abs/0707.0756
143 Examples
144 --------
145 >>> G = nx.Graph([(0, 1), (1, 2), (1, 5), (5, 4), (2, 4), (2, 3), (4, 3), (3, 6)])
146 >>> c = nx.communicability_exp(G)
147 """
148 import scipy as sp
150 nodelist = list(G) # ordering of nodes in matrix
151 A = nx.to_numpy_array(G, nodelist)
152 # convert to 0-1 matrix
153 A[A != 0.0] = 1
154 # communicability matrix
155 expA = sp.linalg.expm(A)
156 mapping = dict(zip(nodelist, range(len(nodelist))))
157 c = {}
158 for u in G:
159 c[u] = {}
160 for v in G:
161 c[u][v] = float(expA[mapping[u], mapping[v]])
162 return c