0
# Algorithms and Computations
1

2
Comprehensive collection of hypergraph algorithms including centrality measures, homology computations, contagion models, clustering methods, generative models, modularity functions, and matching algorithms.
3

4
## Capabilities
5

6
### Centrality Measures
7

8
S-centrality measures that generalize traditional graph centrality to hypergraphs by considering higher-order relationships through s-walks.
9

10
```python { .api }
11
def s_betweenness_centrality(
12
    H: "Hypergraph",
13
    s: int = 1,
14
    edges: bool = True,
15
    normalized: bool = True,
16
    return_singletons: bool = True
17
) -> Dict[Union[str, int], float]:
18
    """
19
    S-betweenness centrality for hypergraph nodes or edges.
20
    
21
    Parameters:
22
    - H: Input hypergraph
23
    - s: Centrality level (paths through edges of size ≥ s+1)
24
    - edges: Compute for edges (True) or nodes (False)
25
    - normalized: Normalize centrality values
26
    - return_singletons: Include singleton components
27
    
28
    Returns:
29
    Dictionary mapping node/edge UIDs to centrality values
30
    """
31

32
def s_closeness_centrality(
33
    H: "Hypergraph",
34
    s: int = 1,
35
    edges: bool = True,
36
    return_singletons: bool = True,
37
    source: Optional[Union[str, int]] = None
38
) -> Dict[Union[str, int], float]:
39
    """
40
    S-closeness centrality for hypergraph nodes or edges.
41
    
42
    Parameters:
43
    - H: Input hypergraph
44
    - s: Centrality level
45
    - edges: Compute for edges (True) or nodes (False)
46
    - return_singletons: Include singleton components
47
    - source: Compute only for specific source node/edge
48
    """
49

50
def s_harmonic_centrality(
51
    H: "Hypergraph",
52
    s: int = 1,
53
    edges: bool = True,
54
    source: Optional[Union[str, int]] = None,
55
    normalized: bool = False,
56
    return_singletons: bool = True
57
) -> Dict[Union[str, int], float]:
58
    """
59
    S-harmonic centrality for hypergraph nodes or edges.
60
    
61
    Parameters:
62
    - H: Input hypergraph
63
    - s: Centrality level
64
    - edges: Compute for edges (True) or nodes (False)
65
    - source: Compute only for specific source node/edge
66
    - normalized: Normalize centrality values
67
    - return_singletons: Include singleton components
68
    """
69

70
def s_harmonic_closeness_centrality(
71
    H: "Hypergraph",
72
    s: int = 1
73
) -> Dict[Union[str, int], float]:
74
    """S-harmonic closeness centrality for hypergraph nodes."""
75

76
def s_eccentricity(
77
    H: "Hypergraph",
78
    s: int = 1,
79
    edges: bool = True,
80
    source: Optional[Union[str, int]] = None,
81
    return_singletons: bool = True
82
) -> Dict[Union[str, int], float]:
83
    """
84
    S-eccentricity for hypergraph nodes or edges.
85
    
86
    Parameters:
87
    - H: Input hypergraph
88
    - s: Eccentricity level
89
    - edges: Compute for edges (True) or nodes (False)
90
    - source: Compute only for specific source node/edge
91
    - return_singletons: Include singleton components
92
    
93
    Returns:
94
    Dictionary mapping node/edge UIDs to eccentricity values
95
    """
96
```
97

98
### Homology and Topology
99

100
Algebraic topology computations for hypergraphs including homology, Betti numbers, and chain complexes using mod-2 arithmetic.
101

102
```python { .api }
103
def betti_numbers(
104
    h: "Hypergraph",
105
    k: Optional[int] = None
106
) -> Dict[int, int]:
107
    """
108
    Compute Betti numbers of the hypergraph.
109
    
110
    Parameters:
111
    - h: Input hypergraph
112
    - k: Specific dimension (returns all if None)
113
    
114
    Returns:
115
    Dictionary mapping dimension to Betti number
116
    """
117

118
def betti(
119
    H: "Hypergraph",
120
    k: int
121
) -> int:
122
    """Compute k-th Betti number."""
123

124
def homology_basis(
125
    H: "Hypergraph",
126
    k: int
127
) -> List:
128
    """Compute homology basis for dimension k."""
129

130
def hypergraph_homology_basis(
131
    H: "Hypergraph"
132
) -> Dict[int, List]:
133
    """Compute homology basis for all dimensions."""
134

135
def chain_complex(H: "Hypergraph") -> Dict[int, Any]:
136
    """Construct chain complex from hypergraph."""
137

138
def boundary_group(
139
    H: "Hypergraph",
140
    k: int
141
) -> Any:
142
    """Compute boundary group for dimension k."""
143

144
def kchainbasis(
145
    H: "Hypergraph",
146
    k: int
147
) -> List:
148
    """Compute k-chain basis."""
149

150
def bkMatrix(
151
    H: "Hypergraph",
152
    k: int
153
) -> Any:
154
    """Compute k-th boundary matrix."""
155

156
def smith_normal_form_mod2(matrix: Any) -> tuple:
157
    """Compute Smith normal form modulo 2."""
158

159
def reduced_row_echelon_form_mod2(matrix: Any) -> tuple:
160
    """Compute reduced row echelon form modulo 2."""
161

162
def interpret(result: Any) -> str:
163
    """Interpret homology computation results."""
164

165
# Matrix operation utilities
166
def swap_rows(matrix: Any, i: int, j: int) -> Any:
167
    """Swap two rows in matrix."""
168

169
def swap_columns(matrix: Any, i: int, j: int) -> Any:
170
    """Swap two columns in matrix."""
171

172
def add_to_row(matrix: Any, i: int, j: int) -> Any:
173
    """Add row j to row i."""
174

175
def add_to_column(matrix: Any, i: int, j: int) -> Any:
176
    """Add column j to column i."""
177

178
def logical_dot(a: Any, b: Any) -> Any:
179
    """Logical dot product."""
180

181
def logical_matmul(a: Any, b: Any) -> Any:
182
    """Logical matrix multiplication."""
183

184
def logical_matadd(a: Any, b: Any) -> Any:
185
    """Logical matrix addition."""
186

187
def matmulreduce(a: Any, b: Any) -> Any:
188
    """Matrix multiplication with reduction."""
189
```
190

191
### Contagion and Spreading Models
192

193
Epidemic and contagion models adapted for hypergraphs, supporting both individual and collective contagion mechanisms.
194

195
```python { .api }
196
def collective_contagion(
197
    H: "Hypergraph",
198
    **kwargs
199
) -> Dict:
200
    """
201
    Collective contagion model where nodes influence each other through hyperedges.
202
    
203
    Parameters:
204
    - H: Input hypergraph
205
    - **kwargs: Model parameters (initial conditions, rates, etc.)
206
    
207
    Returns:
208
    Dictionary with simulation results
209
    """
210

211
def individual_contagion(
212
    H: "Hypergraph",
213
    **kwargs
214
) -> Dict:
215
    """Individual contagion model with pairwise interactions."""
216

217
def discrete_SIR(
218
    H: "Hypergraph",
219
    **kwargs
220
) -> Dict:
221
    """
222
    Discrete-time SIR (Susceptible-Infected-Recovered) model.
223
    
224
    Parameters:
225
    - H: Input hypergraph
226
    - **kwargs: Model parameters
227
    
228
    Returns:
229
    Time series of compartment populations
230
    """
231

232
def discrete_SIS(
233
    H: "Hypergraph",
234
    **kwargs
235
) -> Dict:
236
    """Discrete-time SIS (Susceptible-Infected-Susceptible) model."""
237

238
def Gillespie_SIR(
239
    H: "Hypergraph",
240
    **kwargs
241
) -> Dict:
242
    """Continuous-time SIR model using Gillespie algorithm."""
243

244
def Gillespie_SIS(
245
    H: "Hypergraph",
246
    **kwargs
247
) -> Dict:
248
    """Continuous-time SIS model using Gillespie algorithm."""
249

250
def contagion_animation(
251
    H: "Hypergraph",
252
    **kwargs
253
) -> Any:
254
    """Create animation of contagion spreading process."""
255

256
def threshold(value: float, threshold: float) -> bool:
257
    """Threshold function for contagion models."""
258

259
def majority_vote(values: List[float]) -> bool:
260
    """Majority vote decision function."""
261
```
262

263
### Clustering and Spectral Analysis
264

265
Spectral clustering methods using hypergraph Laplacians and probability transition matrices.
266

267
```python { .api }
268
def spec_clus(
269
    H: "Hypergraph",
270
    k: int = 2
271
) -> List[int]:
272
    """
273
    Spectral clustering of hypergraph nodes.
274
    
275
    Parameters:
276
    - H: Input hypergraph
277
    - k: Number of clusters
278
    
279
    Returns:
280
    List of cluster assignments for each node
281
    """
282

283
def norm_lap(H: "Hypergraph") -> Any:
284
    """
285
    Compute normalized Laplacian matrix.
286
    
287
    Parameters:
288
    - H: Input hypergraph
289
    
290
    Returns:
291
    Normalized Laplacian matrix
292
    """
293

294
def prob_trans(H: "Hypergraph") -> Any:
295
    """Compute probability transition matrix."""
296

297
def get_pi(H: "Hypergraph") -> Any:
298
    """Compute stationary distribution."""
299
```
300

301
### Generative Models
302

303
Random hypergraph generation models including Erdős-Rényi, Chung-Lu, and degree-corrected stochastic block models.
304

305
```python { .api }
306
def erdos_renyi_hypergraph(
307
    n: int,
308
    m: int,
309
    k: Union[int, List[int]] = 2,
310
    **kwargs
311
) -> "Hypergraph":
312
    """
313
    Generate Erdős-Rényi random hypergraph.
314
    
315
    Parameters:
316
    - n: Number of nodes
317
    - m: Number of edges
318
    - k: Edge size (fixed or distribution)
319
    - **kwargs: Additional parameters
320
    
321
    Returns:
322
    Random hypergraph
323
    """
324

325
def chung_lu_hypergraph(
326
    degree_seq: List[int],
327
    edge_size_seq: List[int],
328
    **kwargs
329
) -> "Hypergraph":
330
    """
331
    Generate Chung-Lu random hypergraph.
332
    
333
    Parameters:
334
    - degree_seq: Node degree sequence
335
    - edge_size_seq: Edge size sequence
336
    - **kwargs: Additional parameters
337
    
338
    Returns:
339
    Random hypergraph matching degree and edge size sequences
340
    """
341

342
def dcsbm_hypergraph(
343
    degree_seq: List[int],
344
    communities: List[int],
345
    **kwargs
346
) -> "Hypergraph":
347
    """
348
    Generate degree-corrected stochastic block model hypergraph.
349
    
350
    Parameters:
351
    - degree_seq: Node degree sequence
352
    - communities: Community assignments
353
    - **kwargs: Model parameters
354
    
355
    Returns:
356
    Random hypergraph with community structure
357
    """
358
```
359

360
### Modularity and Community Detection
361

362
Modularity functions and community detection methods for hypergraphs.
363

364
```python { .api }
365
def modularity(
366
    H: "Hypergraph",
367
    partition: Union[Dict, List],
368
    wdc: callable = None
369
) -> float:
370
    """
371
    Compute hypergraph modularity for a given partition.
372
    
373
    Parameters:
374
    - H: Input hypergraph
375
    - partition: Node partition (dict or list of communities)
376
    - wdc: Weight distribution function
377
    
378
    Returns:
379
    Modularity value
380
    """
381

382
def dict2part(partition_dict: Dict) -> List[set]:
383
    """Convert partition dictionary to list of communities."""
384

385
def part2dict(partition_list: List[set]) -> Dict:
386
    """Convert partition list to dictionary."""
387

388
def linear(H: "Hypergraph", partition: Union[Dict, List]) -> float:
389
    """Linear modularity function."""
390

391
def majority(H: "Hypergraph", partition: Union[Dict, List]) -> float:
392
    """Majority modularity function."""
393

394
def strict(H: "Hypergraph", partition: Union[Dict, List]) -> float:
395
    """Strict modularity function."""
396

397
def two_section(H: "Hypergraph") -> Any:
398
    """Two-section graph construction."""
399

400
def kumar(H: "Hypergraph", **kwargs) -> Any:
401
    """Kumar's modularity optimization method."""
402

403
def last_step(H: "Hypergraph", **kwargs) -> Any:
404
    """Last step modularity optimization."""
405
```
406

407
### Matching Algorithms
408

409
Various matching algorithms for hypergraphs including greedy, maximal, and approximation methods.
410

411
```python { .api }
412
def greedy_matching(
413
    hypergraph: "Hypergraph",
414
    k: int
415
) -> list:
416
    """
417
    Greedy matching algorithm for hypergraphs.
418
    
419
    Parameters:
420
    - hypergraph: Input hypergraph
421
    - k: Matching parameter
422
    
423
    Returns:
424
    List of matched edge UIDs
425
    """
426

427
def maximal_matching(H: "Hypergraph") -> List[Union[str, int]]:
428
    """
429
    Maximal matching algorithm.
430
    
431
    Parameters:
432
    - H: Input hypergraph
433
    
434
    Returns:
435
    List of edges forming maximal matching
436
    """
437

438
def iterated_sampling(
439
    hypergraph: "Hypergraph",
440
    s: int,
441
    max_iterations: int = 100
442
) -> list:
443
    """
444
    Iterated sampling matching method.
445
    
446
    Parameters:
447
    - hypergraph: Input hypergraph
448
    - s: Sampling parameter
449
    - max_iterations: Maximum number of sampling iterations
450
    
451
    Returns:
452
    Best matching found
453
    """
454

455
def HEDCS_matching(
456
    hypergraph: "Hypergraph",
457
    s: int
458
) -> list:
459
    """
460
    HEDCS (Hypergraph Edge Disjoint Cover Set) matching algorithm.
461
    
462
    Parameters:
463
    - hypergraph: Input hypergraph  
464
    - s: HEDCS parameter
465
    
466
    Returns:
467
    HEDCS matching
468
    """
469

470
def approximation_matching_checking(
471
    H: "Hypergraph",
472
    matching: List[Union[str, int]]
473
) -> float:
474
    """
475
    Check approximation quality of a matching.
476
    
477
    Parameters:
478
    - H: Input hypergraph
479
    - matching: Candidate matching
480
    
481
    Returns:
482
    Approximation ratio
483
    """
484
```