/
to_hypergraph.py
286 lines (236 loc) · 7.62 KB
/
to_hypergraph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
"""Convert complexes to hypergraphs."""
__all__ = [
"simplicial_subcomplex_2_hypergraph_incidence_matrix",
"simplicial_complex_2_hypergraph",
"graph_2_neighborhood_hypergraph",
"point_cloud_2_knn_graph",
"graph_2_k_hop_hypergraph",
"graph_2_k_hop_hypergraph",
"simplicial_complex_closure_of_hypergraph",
"distance_matrix_2_knn_hypergraph",
"distance_matrix_2_knn_graph",
"distance_matrix_2_eps_neighborhood_hypergraph",
]
import hypernetx as hnx
import networkx as nx
import numpy as np
from scipy.sparse import coo_matrix
from sklearn.neighbors import kneighbors_graph, radius_neighbors_graph
from toponetx import SimplicialComplex
def simplicial_subcomplex_2_hypergraph_incidence_matrix(
simplicial_complex, nodes_dim, edges_dim
):
"""Convert a simplicial subcomplex to a hypergraph incidence matrix.
Parameters
----------
simplicial_complex : SimplicialComplex
Simplicial complex.
nodes_dim : int
Dimension of the simplicies in the simplicial complex that we
consider as being the the nodes of the output hypergraph.
edges_dim : int
Dimension of the simplicies in the simplicial complex that we
consider as being the the edges of the output hypergraph.
Returns
-------
_ : np.array
Indicence matrix of a hypergraph whose nodes are
simplices of dimension nodes_dim and whose edges are simplices of dimension edges_dim.
A node i is a part of the edge j if the intersection of i and j is not empty.
"""
assert isinstance(nodes_dim, int)
assert isinstance(edges_dim, int)
assert isinstance(simplicial_complex, SimplicialComplex)
max_dim = simplicial_complex.maxdim
assert nodes_dim <= max_dim
assert edges_dim <= max_dim
_nodes = simplicial_complex.dic_order_faces(
nodes_dim
) # maintain the same order stored in the SC
_edges = simplicial_complex.dic_order_faces(
edges_dim
) # maintain the same order stored in the SC
graph = []
for i in range(0, len(_edges)):
edge = []
for j in range(0, len(_nodes)):
if _nodes[j] & _edges[i]:
edge.append(1)
else:
edge.append(0)
graph.append(edge)
return np.array(graph).T
def simplicial_complex_closure_of_hypergraph(H):
"""Compute the simplicial complex closure of a hypergraph.
Parameters
----------
H : hyernetx hypergraph
Hypergraph.
Returns
-------
_ : SimplicialComplex
Simplicial complex closure of the hypergraph.
"""
edges = H.edges
lst = []
for e in edges:
lst.append(edges[e])
return SimplicialComplex(lst)
def simplicial_complex_2_hypergraph(simplicial_complex):
"""Convert a simplicial complex to a hypergraph.
Parameters
----------
simplicial_complex : SimplicialComplex
Simplicial complex.
Returns
-------
_ : hypernetx hypergraph
Hypergraph whose edges are all sets in the simplicial complex
that have cardinalties larger than or equal to 2.
"""
assert isinstance(simplicial_complex, SimplicialComplex)
max_dim = simplicial_complex.maxdim
graph = []
for i in range(1, max_dim + 1):
edge = [list(j) for j in simplicial_complex.n_faces(i)]
graph = graph + edge
return hnx.Hypergraph(graph, static=True)
def graph_2_neighborhood_hypergraph(G):
"""Convert a graph to a hypergraph.
Parameters
----------
G : networkx graph
Graph.
Returns
-------
_ : hypernetx hypergraph
Hypergraph.
"""
edges = [sorted(list(G.neighbors(v)) + [v]) for v in G.nodes]
return hnx.Hypergraph(edges, static=True)
def graph_2_k_hop_hypergraph(G, k_hop=1):
"""Convert a graph to a hypergraph.
Parameters
----------
G : networkx graph
Graph.
Returns
-------
_ : hypernetx hypergraph
Hypergraph.
"""
edges = [sorted(list(nx.ego_graph(G, v, k_hop).nodes())) for v in G.nodes]
return hnx.Hypergraph(edges, static=True)
def point_cloud_2_knn_graph(point_cloud, n_neighbors):
"""Convert a point cloud to a knn graph.
Parameters
----------
point_cloud : np.array
Collection of Euclidean points in R^n
n_neighbors : int
Number of neighbors.
Returns
-------
G : networkx graph
The knn weighted graph obtained from the point cloud.
The weight is the distance between the points.
"""
A = kneighbors_graph(point_cloud, n_neighbors, mode="distance")
G = nx.Graph()
cx = coo_matrix(A)
for i, j, v in zip(cx.row, cx.col, cx.data):
G.add_edge(i, j, weight=v)
return G
def point_cloud_2_knn_hypergraph(point_cloud, n_neighbors):
"""Convert a point cloud to a knn hypergraph.
Parameters
----------
point_cloud : np.array
Collection of Euclidean points in R^n.
n_neighbors : int
Number of neighbors.
Returns
-------
_ : hypenetx hypergraph
Hypergraph.
"""
A = kneighbors_graph(point_cloud, n_neighbors, mode="distance")
G = nx.Graph()
cx = coo_matrix(A)
for i, j, v in zip(cx.row, cx.col, cx.data):
G.add_edge(i, j, weight=v)
return graph_2_neighborhood_hypergraph(G)
def point_cloud_2_eps_neighborhood_hypergraph(point_cloud, eps):
"""Convert a point cloud to a eps neighborhood hypergraph.
Parameters
----------
point_cloud : np.array
Collection of Euclidean points in R^n.
eps : float
Real number representing the thinkness around each point
in the metric space.
Returns
-------
_ : hypenetx hypergraph
Hypergraph.
"""
A = radius_neighbors_graph(point_cloud, eps, mode="connectivity")
G = nx.Graph()
cx = coo_matrix(A)
for i, j, v in zip(cx.row, cx.col, cx.data):
G.add_edge(i, j, weight=v)
return graph_2_neighborhood_hypergraph(G)
def distance_matrix_2_eps_neighborhood_hypergraph(distance_matrix, eps):
"""Convert a distance matrix to a eps neighborhood hypergraph.
Parameters
----------
distance_matrix : array-like
Sparse coo_matrix distance matrix.
eps : float
Real number representing the thinkness around each point
in the metric space.
Returns
-------
_ : hypenetx hypergraph
Hypergraph.
"""
G = nx.Graph()
for i, j, v in zip(distance_matrix.row, distance_matrix.col, distance_matrix.data):
if v <= eps:
G.add_edge(i, j, weight=v)
return graph_2_neighborhood_hypergraph(G)
def distance_matrix_2_knn_graph(distance_matrix, n_neighbors):
"""Convert a distance matrix to a knn graph.
Parameters
----------
distance_matrix : array-like
Sparse coo_matrix distance matrix.
n_neighbors : int
Number of neighbors.
Returns
-------
G : networkx graph
Graph.
"""
knn = kneighbors_graph(distance_matrix, n_neighbors, metric="precomputed")
G = nx.Graph()
cx = coo_matrix(knn)
for i, j, v in zip(cx.row, cx.col, cx.data):
G.add_edge(i, j, weight=v)
return G
def distance_matrix_2_knn_hypergraph(distance_matrix, n_neighbors):
"""Convert a distance matrix to a knn hypergraph.
Parameters
----------
distance_matrix : array-like
Sparse coo_matrix distance matrix.
eps : float,
real number representing the thinkness around each point
in the metric space
Returns
-------
G : hypenetx hypergraph
Hypergraph.
"""
G = distance_matrix_2_knn_graph(distance_matrix, n_neighbors)
return graph_2_neighborhood_hypergraph(G)