0
# Centrality Measures
1

2
Comprehensive collection of node and edge centrality algorithms for identifying important vertices and edges in networks. rustworkx provides efficient implementations of major centrality measures with parallel processing support for large graphs.
3

4
## Capabilities
5

6
### Betweenness Centrality
7

8
Measures the extent to which a node lies on paths between other nodes, identifying nodes that serve as bridges in the network.
9

10
```python { .api }
11
def betweenness_centrality(graph, normalized: bool = True, endpoints: bool = False, parallel_threshold: int = 50) -> dict:
12
    """
13
    Compute betweenness centrality for all nodes.
14
    
15
    Betweenness centrality measures the fraction of all-pairs shortest
16
    paths that pass through each node.
17
    
18
    Parameters:
19
    - graph: Input graph (PyGraph or PyDiGraph)
20
    - normalized (bool): Normalize by number of node pairs
21
    - endpoints (bool): Include endpoints in path length calculation
22
    - parallel_threshold (int): Node count for parallel execution
23
    
24
    Returns:
25
    dict: Mapping of node indices to betweenness centrality scores
26
    """
27

28
def edge_betweenness_centrality(graph, normalized: bool = True, parallel_threshold: int = 50):
29
    """
30
    Compute betweenness centrality for all edges.
31
    
32
    Edge betweenness centrality measures the fraction of all-pairs
33
    shortest paths that pass through each edge.
34
    
35
    Parameters:
36
    - graph: Input graph
37
    - normalized (bool): Normalize by number of node pairs  
38
    - parallel_threshold (int): Node count for parallel execution
39
    
40
    Returns:
41
    EdgeCentralityMapping: Mapping of edge indices to centrality scores
42
    """
43
```
44

45
### Closeness Centrality
46

47
Measures how close a node is to all other nodes in the graph based on shortest path distances.
48

49
```python { .api }
50
def closeness_centrality(graph, wf_improved: bool = True, parallel_threshold: int = 50) -> dict:
51
    """
52
    Compute closeness centrality for all nodes.
53
    
54
    Closeness centrality is the reciprocal of the average shortest
55
    path distance to all other reachable nodes.
56
    
57
    Parameters:
58
    - graph: Input graph (PyGraph or PyDiGraph)
59
    - wf_improved (bool): Use Wasserman-Faust improved formula for disconnected graphs
60
    - parallel_threshold (int): Node count for parallel execution
61
    
62
    Returns:
63
    dict: Mapping of node indices to closeness centrality scores
64
    """
65

66
def newman_weighted_closeness_centrality(graph, weight_fn = None, wf_improved: bool = True, default_weight: float = 1.0, parallel_threshold: int = 50):
67
    """
68
    Compute weighted closeness centrality using Newman's method.
69
    
70
    Extends standard closeness centrality to weighted graphs where
71
    edge weights represent connection strength (higher = stronger).
72
    
73
    Parameters:
74
    - graph: Input graph (PyGraph or PyDiGraph)
75
    - weight_fn (callable, optional): Function to extract connection strength
76
    - wf_improved (bool): Use improved formula for disconnected components
77
    - default_weight (float): Default edge weight
78
    - parallel_threshold (int): Node count for parallel execution
79
    
80
    Returns:
81
    CentralityMapping: Mapping of node indices to weighted closeness scores
82
    """
83
```
84

85
### Degree Centrality
86

87
Measures the fraction of nodes that a particular node is connected to, normalized by the maximum possible degree.
88

89
```python { .api }
90
def degree_centrality(graph):
91
    """
92
    Compute degree centrality for all nodes.
93
    
94
    Degree centrality is the fraction of nodes that each node is
95
    connected to, providing a measure of local connectivity.
96
    
97
    Parameters:
98
    - graph: Input graph (PyGraph or PyDiGraph)
99
    
100
    Returns:
101
    CentralityMapping: Mapping of node indices to degree centrality scores
102
    """
103
```
104

105
### Eigenvector Centrality
106

107
Measures the influence of a node in the network based on the principle that connections to high-scoring nodes contribute more to the score.
108

109
```python { .api }
110
def eigenvector_centrality(graph, weight_fn = None, default_weight: float = 1.0, max_iter: int = 100, tol: float = 1e-6):
111
    """
112
    Compute eigenvector centrality using power iteration method.
113
    
114
    Eigenvector centrality assigns higher scores to nodes connected
115
    to other high-scoring nodes, measuring recursive importance.
116
    
117
    Parameters:
118
    - graph: Input graph (PyGraph or PyDiGraph)
119
    - weight_fn (callable, optional): Function to extract edge weight
120
    - default_weight (float): Default edge weight
121
    - max_iter (int): Maximum iterations for convergence
122
    - tol (float): Convergence tolerance
123
    
124
    Returns:
125
    CentralityMapping: Mapping of node indices to eigenvector centrality scores
126
    
127
    Note: Convergence is not guaranteed. May raise FailedToConverge.
128
    """
129
```
130

131
### Katz Centrality
132

133
Generalization of eigenvector centrality that includes a constant bias term, ensuring all nodes have some base importance.
134

135
```python { .api }  
136
def katz_centrality(graph, alpha: float = 0.1, beta = 1.0, weight_fn = None, default_weight: float = 1.0, max_iter: int = 100, tol: float = 1e-6):
137
    """
138
    Compute Katz centrality with attenuation factor and bias term.
139
    
140
    Katz centrality extends eigenvector centrality by adding immediate
141
    neighborhood weights, ensuring all nodes have base importance.
142
    
143
    Parameters:
144
    - graph: Input graph (PyGraph or PyDiGraph)
145
    - alpha (float): Attenuation factor controlling recursive influence
146
    - beta (float or dict): Immediate neighborhood weights (bias term)
147
    - weight_fn (callable, optional): Function to extract edge weight
148
    - default_weight (float): Default edge weight  
149
    - max_iter (int): Maximum iterations for convergence
150
    - tol (float): Convergence tolerance
151
    
152
    Returns:
153
    CentralityMapping: Mapping of node indices to Katz centrality scores
154
    
155
    Note: If beta is dict, must contain all node indices as keys.
156
    """
157
```
158

159
## Usage Examples
160

161
### Basic Centrality Analysis
162

163
```python
164
import rustworkx as rx
165

166
# Create sample network
167
graph = rx.PyGraph()
168
nodes = graph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
169
graph.add_edges_from([
170
    (nodes[0], nodes[1], 1),  # A-B
171
    (nodes[1], nodes[2], 1),  # B-C  
172
    (nodes[1], nodes[3], 1),  # B-D
173
    (nodes[2], nodes[4], 1),  # C-E
174
    (nodes[3], nodes[4], 1),  # D-E
175
])
176

177
# Compute various centrality measures
178
betweenness = rx.betweenness_centrality(graph)
179
closeness = rx.closeness_centrality(graph)
180
degree = rx.degree_centrality(graph)
181
eigenvector = rx.eigenvector_centrality(graph)
182

183
print("Betweenness centrality:", betweenness)
184
print("Closeness centrality:", closeness)
185
print("Degree centrality:", degree)
186
print("Eigenvector centrality:", eigenvector)
187
```
188

189
### Weighted Centrality Analysis
190

191
```python
192
# Weighted graph analysis
193
weighted_graph = rx.PyGraph()
194
nodes = weighted_graph.add_nodes_from(['Hub', 'A', 'B', 'C'])
195
weighted_graph.add_edges_from([
196
    (nodes[0], nodes[1], 0.8),  # Strong connection
197
    (nodes[0], nodes[2], 0.9),  # Very strong
198
    (nodes[0], nodes[3], 0.3),  # Weak connection
199
    (nodes[1], nodes[2], 0.1),  # Very weak
200
])
201

202
# Weighted closeness using Newman's method
203
weighted_closeness = rx.newman_weighted_closeness_centrality(
204
    weighted_graph,
205
    weight_fn=lambda x: x  # Use edge weight as connection strength
206
)
207

208
# Weighted eigenvector centrality
209
weighted_eigenvector = rx.eigenvector_centrality(
210
    weighted_graph,
211
    weight_fn=lambda x: x
212
)
213

214
print("Weighted closeness:", weighted_closeness)
215
print("Weighted eigenvector:", weighted_eigenvector)
216
```
217

218
### Edge Centrality Analysis
219

220
```python
221
# Identify critical edges in network
222
edge_centrality = rx.edge_betweenness_centrality(graph)
223

224
# Get edge list for interpretation
225
edges = graph.edge_list()
226
for i, (source, target) in enumerate(edges):
227
    if i in edge_centrality:
228
        print(f"Edge {source}-{target}: {edge_centrality[i]:.3f}")
229
```
230

231
### Katz Centrality with Custom Parameters
232

233
```python
234
# Katz centrality with different node importance
235
node_importance = {
236
    nodes[0]: 2.0,  # A has higher base importance
237
    nodes[1]: 1.5,  # B has moderate importance
238
    nodes[2]: 1.0,  # C has standard importance
239
    nodes[3]: 1.0,  # D has standard importance
240
    nodes[4]: 0.5,  # E has lower importance
241
}
242

243
katz_scores = rx.katz_centrality(
244
    graph,
245
    alpha=0.2,  # Higher attenuation factor
246
    beta=node_importance,  # Custom bias terms
247
    weight_fn=lambda x: 1.0
248
)
249

250
print("Katz centrality with custom bias:", katz_scores)
251
```
252

253
### Centrality-Based Node Ranking
254

255
```python
256
# Rank nodes by different centrality measures
257
import operator
258

259
def rank_nodes_by_centrality(centrality_scores, node_names):
260
    """Rank nodes by centrality scores."""
261
    sorted_items = sorted(centrality_scores.items(), 
262
                         key=operator.itemgetter(1), 
263
                         reverse=True)
264
    return [(node_names[idx], score) for idx, score in sorted_items]
265

266
node_names = {i: name for i, name in enumerate(['A', 'B', 'C', 'D', 'E'])}
267

268
print("Ranking by betweenness:")
269
for name, score in rank_nodes_by_centrality(betweenness, node_names):
270
    print(f"  {name}: {score:.3f}")
271

272
print("Ranking by degree:")  
273
for name, score in rank_nodes_by_centrality(degree, node_names):
274
    print(f"  {name}: {score:.3f}")
275
```
276

277
### Parallel Processing for Large Graphs
278

279
```python
280
# For large graphs, adjust parallel processing threshold
281
large_graph = rx.generators.erdos_renyi_gnp_random_graph(1000, 0.01)
282

283
# Use lower threshold to enable parallelization
284
centrality_parallel = rx.betweenness_centrality(
285
    large_graph, 
286
    parallel_threshold=100  # Enable parallel processing
287
)
288

289
# Compare with different settings using environment variable
290
import os
291
os.environ['RAYON_NUM_THREADS'] = '4'  # Limit to 4 threads
292

293
centrality_limited = rx.closeness_centrality(
294
    large_graph,
295
    parallel_threshold=100
296
)
297
```
298

299
### Handling Disconnected Graphs
300

301
```python
302
# Create disconnected graph
303
disconnected = rx.PyGraph()
304
# Component 1
305
comp1_nodes = disconnected.add_nodes_from(['A1', 'B1', 'C1'])
306
disconnected.add_edges_from([
307
    (comp1_nodes[0], comp1_nodes[1], 1),
308
    (comp1_nodes[1], comp1_nodes[2], 1)
309
])
310

311
# Component 2 (isolated)
312
comp2_nodes = disconnected.add_nodes_from(['A2', 'B2'])
313
disconnected.add_edges_from([
314
    (comp2_nodes[0], comp2_nodes[1], 1)
315
])
316

317
# Use improved formula for disconnected graphs
318
closeness_improved = rx.closeness_centrality(
319
    disconnected, 
320
    wf_improved=True  # Wasserman-Faust improved formula
321
)
322

323
closeness_standard = rx.closeness_centrality(
324
    disconnected,
325
    wf_improved=False  # Standard formula
326
)
327

328
print("Improved formula:", closeness_improved)
329
print("Standard formula:", closeness_standard)
330
```