Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/node_classification/lgc.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 Local and global consistency algorithm by Zhou et al. | |
2 | |
3 References | |
4 ---------- | |
5 Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2004). | |
6 Learning with local and global consistency. | |
7 Advances in neural information processing systems, 16(16), 321-328. | |
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__ = ["local_and_global_consistency"] | |
20 | |
21 | |
22 @not_implemented_for("directed") | |
23 def local_and_global_consistency(G, alpha=0.99, max_iter=30, label_name="label"): | |
24 """Node classification by Local and Global Consistency | |
25 | |
26 Parameters | |
27 ---------- | |
28 G : NetworkX Graph | |
29 alpha : float | |
30 Clamping factor | |
31 max_iter : int | |
32 Maximum number of iterations allowed | |
33 label_name : string | |
34 Name of target labels to predict | |
35 | |
36 Returns | |
37 ---------- | |
38 predicted : array, shape = [n_samples] | |
39 Array of predicted labels | |
40 | |
41 Raises | |
42 ------ | |
43 NetworkXError | |
44 If no nodes on `G` has `label_name`. | |
45 | |
46 Examples | |
47 -------- | |
48 >>> from networkx.algorithms import node_classification | |
49 >>> G = nx.path_graph(4) | |
50 >>> G.nodes[0]["label"] = "A" | |
51 >>> G.nodes[3]["label"] = "B" | |
52 >>> G.nodes(data=True) | |
53 NodeDataView({0: {'label': 'A'}, 1: {}, 2: {}, 3: {'label': 'B'}}) | |
54 >>> G.edges() | |
55 EdgeView([(0, 1), (1, 2), (2, 3)]) | |
56 >>> predicted = node_classification.local_and_global_consistency(G) | |
57 >>> predicted | |
58 ['A', 'A', 'B', 'B'] | |
59 | |
60 | |
61 References | |
62 ---------- | |
63 Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2004). | |
64 Learning with local and global consistency. | |
65 Advances in neural information processing systems, 16(16), 321-328. | |
66 """ | |
67 try: | |
68 import numpy as np | |
69 except ImportError as e: | |
70 raise ImportError( | |
71 "local_and_global_consistency() requires numpy: ", "http://numpy.org/ " | |
72 ) from e | |
73 try: | |
74 from scipy import sparse | |
75 except ImportError as e: | |
76 raise ImportError( | |
77 "local_and_global_consistensy() requires scipy: ", "http://scipy.org/ " | |
78 ) from e | |
79 | |
80 def _build_propagation_matrix(X, labels, alpha): | |
81 """Build propagation matrix of Local and global consistency | |
82 | |
83 Parameters | |
84 ---------- | |
85 X : scipy sparse matrix, shape = [n_samples, n_samples] | |
86 Adjacency matrix | |
87 labels : array, shape = [n_samples, 2] | |
88 Array of pairs of node id and label id | |
89 alpha : float | |
90 Clamping factor | |
91 | |
92 Returns | |
93 ---------- | |
94 S : scipy sparse matrix, shape = [n_samples, n_samples] | |
95 Propagation matrix | |
96 | |
97 """ | |
98 degrees = X.sum(axis=0).A[0] | |
99 degrees[degrees == 0] = 1 # Avoid division by 0 | |
100 D2 = np.sqrt(sparse.diags((1.0 / degrees), offsets=0)) | |
101 S = alpha * D2.dot(X).dot(D2) | |
102 return S | |
103 | |
104 def _build_base_matrix(X, labels, alpha, n_classes): | |
105 """Build base matrix of Local and global consistency | |
106 | |
107 Parameters | |
108 ---------- | |
109 X : scipy sparse matrix, shape = [n_samples, n_samples] | |
110 Adjacency matrix | |
111 labels : array, shape = [n_samples, 2] | |
112 Array of pairs of node id and label id | |
113 alpha : float | |
114 Clamping factor | |
115 n_classes : integer | |
116 The number of classes (distinct labels) on the input graph | |
117 | |
118 Returns | |
119 ---------- | |
120 B : array, shape = [n_samples, n_classes] | |
121 Base matrix | |
122 """ | |
123 | |
124 n_samples = X.shape[0] | |
125 B = np.zeros((n_samples, n_classes)) | |
126 B[labels[:, 0], labels[:, 1]] = 1 - alpha | |
127 return B | |
128 | |
129 X = nx.to_scipy_sparse_matrix(G) # adjacency matrix | |
130 labels, label_dict = _get_label_info(G, label_name) | |
131 | |
132 if labels.shape[0] == 0: | |
133 raise nx.NetworkXError( | |
134 "No node on the input graph is labeled by '" + label_name + "'." | |
135 ) | |
136 | |
137 n_samples = X.shape[0] | |
138 n_classes = label_dict.shape[0] | |
139 F = _init_label_matrix(n_samples, n_classes) | |
140 | |
141 P = _build_propagation_matrix(X, labels, alpha) | |
142 B = _build_base_matrix(X, labels, alpha, n_classes) | |
143 | |
144 remaining_iter = max_iter | |
145 while remaining_iter > 0: | |
146 F = _propagate(P, F, B) | |
147 remaining_iter -= 1 | |
148 | |
149 predicted = _predict(F, label_dict) | |
150 | |
151 return predicted |