Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/node_classification/hmn.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Function for computing Harmonic function algorithm by Zhu et al. | |
2 | |
3 References | |
4 ---------- | |
5 Zhu, X., Ghahramani, Z., & Lafferty, J. (2003, August). | |
6 Semi-supervised learning using gaussian fields and harmonic functions. | |
7 In ICML (Vol. 3, pp. 912-919). | |
8 """ | |
9 import networkx as nx | |
10 | |
11 from networkx.utils.decorators import not_implemented_for | |
12 from networkx.algorithms.node_classification.utils import ( | |
13 _get_label_info, | |
14 _init_label_matrix, | |
15 _propagate, | |
16 _predict, | |
17 ) | |
18 | |
19 __all__ = ["harmonic_function"] | |
20 | |
21 | |
22 @not_implemented_for("directed") | |
23 def harmonic_function(G, max_iter=30, label_name="label"): | |
24 """Node classification by Harmonic function | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX Graph | |
29 max_iter : int | |
30 maximum number of iterations allowed | |
31 label_name : string | |
32 name of target labels to predict | |
33 | |
34 Returns | |
35 ---------- | |
36 predicted : array, shape = [n_samples] | |
37 Array of predicted labels | |
38 | |
39 Raises | |
40 ---------- | |
41 NetworkXError | |
42 If no nodes on `G` has `label_name`. | |
43 | |
44 Examples | |
45 -------- | |
46 >>> from networkx.algorithms import node_classification | |
47 >>> G = nx.path_graph(4) | |
48 >>> G.nodes[0]["label"] = "A" | |
49 >>> G.nodes[3]["label"] = "B" | |
50 >>> G.nodes(data=True) | |
51 NodeDataView({0: {'label': 'A'}, 1: {}, 2: {}, 3: {'label': 'B'}}) | |
52 >>> G.edges() | |
53 EdgeView([(0, 1), (1, 2), (2, 3)]) | |
54 >>> predicted = node_classification.harmonic_function(G) | |
55 >>> predicted | |
56 ['A', 'A', 'B', 'B'] | |
57 | |
58 References | |
59 ---------- | |
60 Zhu, X., Ghahramani, Z., & Lafferty, J. (2003, August). | |
61 Semi-supervised learning using gaussian fields and harmonic functions. | |
62 In ICML (Vol. 3, pp. 912-919). | |
63 """ | |
64 try: | |
65 import numpy as np | |
66 except ImportError as e: | |
67 raise ImportError( | |
68 "harmonic_function() requires numpy: http://numpy.org/ " | |
69 ) from e | |
70 try: | |
71 from scipy import sparse | |
72 except ImportError as e: | |
73 raise ImportError( | |
74 "harmonic_function() requires scipy: http://scipy.org/ " | |
75 ) from e | |
76 | |
77 def _build_propagation_matrix(X, labels): | |
78 """Build propagation matrix of Harmonic function | |
79 | |
80 Parameters | |
81 ---------- | |
82 X : scipy sparse matrix, shape = [n_samples, n_samples] | |
83 Adjacency matrix | |
84 labels : array, shape = [n_samples, 2] | |
85 Array of pairs of node id and label id | |
86 | |
87 Returns | |
88 ---------- | |
89 P : scipy sparse matrix, shape = [n_samples, n_samples] | |
90 Propagation matrix | |
91 | |
92 """ | |
93 degrees = X.sum(axis=0).A[0] | |
94 degrees[degrees == 0] = 1 # Avoid division by 0 | |
95 D = sparse.diags((1.0 / degrees), offsets=0) | |
96 P = D.dot(X).tolil() | |
97 P[labels[:, 0]] = 0 # labels[:, 0] indicates IDs of labeled nodes | |
98 return P | |
99 | |
100 def _build_base_matrix(X, labels, n_classes): | |
101 """Build base matrix of Harmonic function | |
102 | |
103 Parameters | |
104 ---------- | |
105 X : scipy sparse matrix, shape = [n_samples, n_samples] | |
106 Adjacency matrix | |
107 labels : array, shape = [n_samples, 2] | |
108 Array of pairs of node id and label id | |
109 n_classes : integer | |
110 The number of classes (distinct labels) on the input graph | |
111 | |
112 Returns | |
113 ---------- | |
114 B : array, shape = [n_samples, n_classes] | |
115 Base matrix | |
116 """ | |
117 n_samples = X.shape[0] | |
118 B = np.zeros((n_samples, n_classes)) | |
119 B[labels[:, 0], labels[:, 1]] = 1 | |
120 return B | |
121 | |
122 X = nx.to_scipy_sparse_matrix(G) # adjacency matrix | |
123 labels, label_dict = _get_label_info(G, label_name) | |
124 | |
125 if labels.shape[0] == 0: | |
126 raise nx.NetworkXError( | |
127 "No node on the input graph is labeled by '" + label_name + "'." | |
128 ) | |
129 | |
130 n_samples = X.shape[0] | |
131 n_classes = label_dict.shape[0] | |
132 | |
133 F = _init_label_matrix(n_samples, n_classes) | |
134 | |
135 P = _build_propagation_matrix(X, labels) | |
136 B = _build_base_matrix(X, labels, n_classes) | |
137 | |
138 remaining_iter = max_iter | |
139 while remaining_iter > 0: | |
140 F = _propagate(P, F, B) | |
141 remaining_iter -= 1 | |
142 | |
143 predicted = _predict(F, label_dict) | |
144 | |
145 return predicted |