0
# Graph Analysis
1

2
Comprehensive analysis algorithms including centrality measures, shortest paths, connectivity analysis, and structural properties. These methods enable deep understanding of network structure and vertex/edge importance.
3

4
## Capabilities
5

6
### Centrality Measures
7

8
Compute various centrality metrics to identify important vertices in the network.
9

10
```python { .api }
11
class Graph:
12
    def betweenness(self, vertices=None, directed=True, weights=None):
13
        """
14
        Calculate betweenness centrality.
15
        
16
        Parameters:
17
        - vertices: list/VertexSeq, vertices to compute (None for all)
18
        - directed: bool, whether to respect edge directions
19
        - weights: str/list, edge weights or attribute name
20
        
21
        Returns:
22
        list of float, betweenness centrality values
23
        """
24

25
    def closeness(self, vertices=None, mode=ALL, weights=None, normalized=True):
26
        """
27
        Calculate closeness centrality.
28
        
29
        Parameters:
30
        - vertices: vertex selection (None for all)
31
        - mode: path direction (ALL, IN, OUT)
32
        - weights: edge weights
33
        - normalized: bool, whether to normalize by (n-1)
34
        
35
        Returns:
36
        list of float, closeness centrality values
37
        """
38

39
    def eigenvector_centrality(self, directed=True, scale=True, weights=None, return_eigenvalue=False):
40
        """
41
        Calculate eigenvector centrality.
42
        
43
        Parameters:
44
        - directed: bool, respect edge directions
45
        - scale: bool, scale values to unit length
46
        - weights: edge weights
47
        - return_eigenvalue: bool, also return dominant eigenvalue
48
        
49
        Returns:
50
        list of float (+ eigenvalue if requested)
51
        """
52

53
    def pagerank(self, vertices=None, directed=True, damping=0.85, weights=None, arpack_options=None):
54
        """
55
        Calculate PageRank centrality.
56
        
57
        Parameters:
58
        - vertices: vertex selection (None for all)
59
        - directed: bool, respect edge directions
60
        - damping: float, damping parameter (0-1)
61
        - weights: edge weights
62
        - arpack_options: ARPACKOptions, solver configuration
63
        
64
        Returns:
65
        list of float, PageRank values
66
        """
67

68
    def authority_score(self, scale=True, weights=None, return_eigenvalue=False):
69
        """
70
        Calculate HITS authority scores.
71
        
72
        Parameters:
73
        - scale: bool, scale to unit length
74
        - weights: edge weights  
75
        - return_eigenvalue: bool, return eigenvalue
76
        
77
        Returns:
78
        list of float, authority scores
79
        """
80

81
    def hub_score(self, scale=True, weights=None, return_eigenvalue=False):
82
        """
83
        Calculate HITS hub scores.
84
        
85
        Parameters:
86
        - scale: bool, scale to unit length
87
        - weights: edge weights
88
        - return_eigenvalue: bool, return eigenvalue
89
        
90
        Returns:
91
        list of float, hub scores
92
        """
93
```
94

95
**Usage Examples:**
96

97
```python
98
import igraph as ig
99

100
# Create sample network
101
g = ig.Graph.Famous("Zachary")  # Karate club network
102

103
# Betweenness centrality
104
betw = g.betweenness()
105
print("Top betweenness:", sorted(enumerate(betw), key=lambda x: x[1], reverse=True)[:3])
106

107
# Closeness centrality
108
close = g.closeness()
109
print("Top closeness:", sorted(enumerate(close), key=lambda x: x[1], reverse=True)[:3])
110

111
# Eigenvector centrality
112
eigen = g.eigenvector_centrality()
113
print("Top eigenvector:", sorted(enumerate(eigen), key=lambda x: x[1], reverse=True)[:3])
114

115
# PageRank
116
pr = g.pagerank(damping=0.85)
117
print("Top PageRank:", sorted(enumerate(pr), key=lambda x: x[1], reverse=True)[:3])
118

119
# For directed graphs
120
g_dir = ig.Graph.Erdos_Renyi(20, 30, directed=True)
121
auth = g_dir.authority_score()
122
hubs = g_dir.hub_score()
123
```
124

125
### Shortest Paths
126

127
Compute shortest paths and distances between vertices.
128

129
```python { .api }
130
class Graph:
131
    def shortest_paths(self, source=None, target=None, weights=None, mode=OUT):
132
        """
133
        Calculate shortest path distances.
134
        
135
        Parameters:
136
        - source: int/list, source vertices (None for all)
137
        - target: int/list, target vertices (None for all)  
138
        - weights: str/list, edge weights or attribute name
139
        - mode: path direction (OUT, IN, ALL)
140
        
141
        Returns:
142
        list/matrix, shortest path distances
143
        """
144

145
    def shortest_paths_dijkstra(self, source=None, target=None, weights=None, mode=OUT):
146
        """
147
        Dijkstra's algorithm for shortest paths (non-negative weights).
148
        
149
        Parameters:
150
        - source: source vertices (None for all)
151
        - target: target vertices (None for all)
152
        - weights: edge weights (must be non-negative)
153
        - mode: path direction
154
        
155
        Returns:
156
        Distance matrix
157
        """
158

159
    def get_shortest_paths(self, v, to=None, weights=None, mode=OUT, predecessors=False, inbound_edges=False):
160
        """
161
        Get actual shortest paths as vertex sequences.
162
        
163
        Parameters:
164
        - v: int, source vertex
165
        - to: int/list, target vertices (None for all)
166
        - weights: edge weights
167
        - mode: path direction
168
        - predecessors: bool, return predecessor info
169
        - inbound_edges: bool, return edge sequences
170
        
171
        Returns:
172
        list of paths (vertex lists)
173
        """
174

175
    def diameter(self, directed=True, unconn=True, weights=None):
176
        """
177
        Calculate graph diameter (longest shortest path).
178
        
179
        Parameters:
180
        - directed: bool, respect edge directions
181
        - unconn: bool, return infinity for unconnected graphs
182
        - weights: edge weights
183
        
184
        Returns:
185
        float, diameter length
186
        """
187

188
    def average_path_length(self, directed=True, unconn=True):
189
        """
190
        Calculate average shortest path length.
191
        
192
        Parameters:
193
        - directed: bool, respect edge directions  
194
        - unconn: bool, how to handle unconnected pairs
195
        
196
        Returns:
197
        float, average path length
198
        """
199
```
200

201
**Usage Examples:**
202

203
```python
204
# Create weighted graph
205
g = ig.Graph([(0,1), (1,2), (2,3), (0,3), (1,3)], directed=False)
206
g.es["weight"] = [1, 2, 1, 4, 1]
207

208
# All shortest distances
209
distances = g.shortest_paths(weights="weight")
210
print("Distance matrix:", distances)
211

212
# Specific source
213
dist_from_0 = g.shortest_paths(source=[0], weights="weight")[0]
214
print("Distances from vertex 0:", dist_from_0)
215

216
# Get actual paths
217
paths = g.get_shortest_paths(0, to=[2, 3], weights="weight")
218
print("Paths from 0 to 2,3:", paths)
219

220
# Graph diameter
221
diam = g.diameter(weights="weight")
222
print("Diameter:", diam)
223

224
# Average path length
225
avg_path = g.average_path_length()
226
print("Average path length:", avg_path)
227
```
228

229
### Connectivity Analysis
230

231
Analyze graph connectivity and identify components.
232

233
```python { .api }
234
class Graph:
235
    def is_connected(self, mode=WEAK):
236
        """
237
        Check if graph is connected.
238
        
239
        Parameters:
240
        - mode: connectivity type (WEAK, STRONG for directed graphs)
241
        
242
        Returns:
243
        bool, True if connected
244
        """
245

246
    def components(self, mode=WEAK):
247
        """
248
        Find connected components.
249
        
250
        Parameters:
251
        - mode: component type (WEAK, STRONG)
252
        
253
        Returns:
254
        VertexClustering, component membership
255
        """
256

257
    def articulation_points(self):
258
        """
259
        Find articulation points (cut vertices).
260
        
261
        Returns:
262
        list of int, articulation point indices
263
        """
264

265
    def bridges(self):
266
        """
267
        Find bridge edges (cut edges).
268
        
269
        Returns:
270
        list of int, bridge edge indices
271
        """
272

273
    def vertex_connectivity(self, source=None, target=None, checks=True):
274
        """
275
        Calculate vertex connectivity.
276
        
277
        Parameters:
278
        - source: int, source vertex (None for overall connectivity)
279
        - target: int, target vertex
280
        - checks: bool, perform input validation
281
        
282
        Returns:
283
        int, minimum vertex cuts needed to disconnect
284
        """
285

286
    def edge_connectivity(self, source=None, target=None, checks=True):
287
        """
288
        Calculate edge connectivity.
289
        
290
        Parameters:
291
        - source: source vertex (None for overall)
292
        - target: target vertex  
293
        - checks: bool, input validation
294
        
295
        Returns:
296
        int, minimum edge cuts needed to disconnect
297
        """
298

299
    def st_mincut(self, source, target, capacity=None):
300
        """
301
        Calculate minimum s-t cut.
302
        
303
        Parameters:
304
        - source: int, source vertex
305
        - target: int, target vertex
306
        - capacity: str/list, edge capacities
307
        
308
        Returns:
309
        Cut object with value, partition, and cut edges
310
        """
311
```
312

313
**Usage Examples:**
314

315
```python
316
# Create graph with components
317
g1 = ig.Graph([(0,1), (1,2), (3,4), (4,5)])  # Two components
318

319
# Check connectivity
320
print("Connected:", g1.is_connected())  # False
321

322
# Find components  
323
comp = g1.components()
324
print("Components:", comp.membership)   # [0, 0, 0, 1, 1, 1]
325
print("Component sizes:", comp.sizes()) # [3, 3]
326

327
# Create connected graph for further analysis
328
g2 = ig.Graph.Ring(8)  # 8-vertex cycle
329

330
# Find articulation points and bridges
331
g2.add_edge(0, 4)  # Add chord
332
arts = g2.articulation_points()
333
bridges = g2.bridges()
334
print("Articulation points:", arts)
335
print("Bridge edges:", bridges)
336

337
# Connectivity measures
338
v_conn = g2.vertex_connectivity()
339
e_conn = g2.edge_connectivity()
340
print(f"Vertex connectivity: {v_conn}")
341
print(f"Edge connectivity: {e_conn}")
342

343
# Minimum cut
344
cut = g2.st_mincut(0, 4)
345
print(f"Min cut value: {cut.value}")
346
print(f"Cut partition: {cut.partition}")
347
```
348

349
### Structural Properties
350

351
Analyze various structural characteristics of the graph.
352

353
```python { .api }
354
class Graph:
355
    def transitivity_undirected(self, mode="nan", weights=None):
356
        """
357
        Calculate global clustering coefficient.
358
        
359
        Parameters:
360
        - mode: how to handle undefined cases ("nan", "zero")
361
        - weights: edge weights for weighted transitivity
362
        
363
        Returns:
364
        float, global transitivity
365
        """
366

367
    def transitivity_local_undirected(self, vertices=None, mode="nan", weights=None):
368
        """
369
        Calculate local clustering coefficients.
370
        
371
        Parameters:
372
        - vertices: vertex selection (None for all)
373
        - mode: undefined case handling
374
        - weights: edge weights
375
        
376
        Returns:
377
        list of float, local clustering coefficients
378
        """
379

380
    def assortativity_degree(self, directed=True, mode1=OUT, mode2=IN):
381
        """
382
        Calculate degree assortativity.
383
        
384
        Parameters:
385
        - directed: bool, respect edge directions
386
        - mode1: source vertex degree type
387
        - mode2: target vertex degree type
388
        
389
        Returns:
390
        float, degree assortativity coefficient
391
        """
392

393
    def assortativity(self, types1, types2=None, directed=True):
394
        """
395
        Calculate attribute assortativity.
396
        
397
        Parameters:
398
        - types1: list, vertex attributes for source vertices
399
        - types2: list, vertex attributes for target vertices (None = same as types1)
400
        - directed: bool, respect directions
401
        
402
        Returns:
403
        float, assortativity coefficient
404
        """
405

406
    def reciprocity(self, ignore_loops=True, mode="default"):
407
        """
408
        Calculate edge reciprocity.
409
        
410
        Parameters:
411
        - ignore_loops: bool, exclude self-loops
412
        - mode: reciprocity definition ("default", "ratio")
413
        
414
        Returns:
415
        float, reciprocity measure
416
        """
417

418
    def motifs_randesu(self, size=3, cut_prob=None):
419
        """
420
        Count network motifs using RANDESU algorithm.
421
        
422
        Parameters:
423
        - size: int, motif size (3 or 4)
424
        - cut_prob: list, cutting probabilities for sampling
425
        
426
        Returns:
427
        list of int, motif counts
428
        """
429
```
430

431
**Usage Examples:**
432

433
```python
434
# Create social network-like graph
435
g = ig.Graph.Barabasi(100, m=3, directed=False)
436

437
# Clustering coefficients
438
global_cc = g.transitivity_undirected()
439
local_cc = g.transitivity_local_undirected()
440
print(f"Global clustering: {global_cc:.3f}")
441
print(f"Average local clustering: {sum(local_cc)/len(local_cc):.3f}")
442

443
# Degree assortativity
444
deg_assort = g.assortativity_degree()
445
print(f"Degree assortativity: {deg_assort:.3f}")
446

447
# Attribute assortativity
448
import random
449
g.vs["type"] = [random.choice([0, 1]) for _ in range(g.vcount())]
450
attr_assort = g.assortativity("type")
451
print(f"Type assortativity: {attr_assort:.3f}")
452

453
# For directed networks
454
g_dir = ig.Graph.Erdos_Renyi(50, 100, directed=True)
455
recip = g_dir.reciprocity()
456
print(f"Reciprocity: {recip:.3f}")
457

458
# Motif analysis
459
motifs = g_dir.motifs_randesu(size=3)
460
print("Triad counts:", motifs)
461
```
462

463
### Special Graph Measures
464

465
Additional structural measures for specific types of analysis.
466

467
```python { .api }
468
class Graph:
469
    def girth(self):
470
        """
471
        Calculate graph girth (shortest cycle length).
472
        
473
        Returns:
474
        int, girth (0 if acyclic)
475
        """
476

477
    def radius(self, mode=OUT):
478
        """
479
        Calculate graph radius.
480
        
481
        Parameters:
482
        - mode: path direction (OUT, IN, ALL)
483
        
484
        Returns:
485
        float, radius (maximum eccentricity)
486
        """
487

488
    def cohesion(self, checks=True):
489
        """
490
        Calculate graph cohesion (vertex connectivity).
491
        
492
        Parameters:
493
        - checks: bool, perform input validation
494
        
495
        Returns:
496
        int, cohesion value
497
        """
498

499
    def adhesion(self, checks=True):
500
        """
501
        Calculate graph adhesion (edge connectivity).
502
        
503
        Parameters:
504
        - checks: bool, input validation
505
        
506
        Returns:  
507
        int, adhesion value
508
        """
509

510
    def dyad_census(self):
511
        """
512
        Perform dyad census for directed graphs.
513
        
514
        Returns:
515
        DyadCensus object with mutual, asymmetric, null counts
516
        """
517

518
    def triad_census(self):
519
        """
520
        Perform triad census for directed graphs.
521
        
522
        Returns:
523
        TriadCensus object with counts for all 16 triad types
524
        """
525
```
526

527
**Usage Examples:**
528

529
```python
530
# Structural measures
531
g = ig.Graph.Ring(10)
532
g.add_edges([(0, 5), (2, 7)])  # Add chords
533

534
girth = g.girth()
535
radius = g.radius()
536
cohesion = g.cohesion()
537
adhesion = g.adhesion()
538

539
print(f"Girth: {girth}")      # Shortest cycle
540
print(f"Radius: {radius}")    # Maximum eccentricity  
541
print(f"Cohesion: {cohesion}")   # Vertex connectivity
542
print(f"Adhesion: {adhesion}")   # Edge connectivity
543

544
# For directed graphs
545
g_dir = ig.Graph.Erdos_Renyi(20, 40, directed=True)
546

547
# Dyad census
548
dyads = g_dir.dyad_census()
549
print(f"Mutual: {dyads.mutual}, Asymmetric: {dyads.asymmetric}, Null: {dyads.null}")
550

551
# Triad census
552
triads = g_dir.triad_census()
553
print("Triad type 003 count:", getattr(triads, "003"))  # Empty triad
554
print("Triad type 300 count:", getattr(triads, "300"))  # Complete triad
555
```