0
# Linear Algebra
1

2
Graph matrix operations and spectral analysis including adjacency matrices, Laplacian matrices, and eigenvalue computations. NetworkX provides comprehensive linear algebra functionality for analyzing graph structure through matrix representations.
3

4
## Capabilities
5

6
### Graph Matrices
7

8
Functions to compute various matrix representations of graphs.
9

10
```python { .api }
11
def adjacency_matrix(G, nodelist=None, dtype=None, weight='weight'):
12
    """
13
    Compute adjacency matrix of graph as SciPy sparse matrix.
14
    
15
    Parameters:
16
    - G: NetworkX graph
17
    - nodelist: List of nodes in desired order
18
    - dtype: Data type for matrix elements
19
    - weight: Edge data key for weights (default: 'weight')
20
    
21
    Returns:
22
    SciPy sparse matrix representing graph adjacency
23
    """
24

25
def incidence_matrix(G, nodelist=None, edgelist=None, oriented=False, weight=None):
26
    """Compute incidence matrix of graph."""
27

28
def laplacian_matrix(G, nodelist=None, weight='weight'):
29
    """Compute Laplacian matrix of graph."""
30

31
def normalized_laplacian_matrix(G, nodelist=None, weight='weight'):
32
    """Compute normalized Laplacian matrix."""
33

34
def directed_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95):
35
    """Compute directed Laplacian matrix."""
36

37
def modularity_matrix(G, nodelist=None, weight='weight'):
38
    """Compute modularity matrix of graph."""
39

40
def bethe_hessian_matrix(G, r=None, nodelist=None):
41
    """Compute Bethe Hessian matrix."""
42
```
43

44
### Spectrum and Eigenvalues
45

46
Functions to compute eigenvalues and eigenvectors of graph matrices.
47

48
```python { .api }
49
def adjacency_spectrum(G, weight='weight'):
50
    """
51
    Compute eigenvalues of adjacency matrix.
52
    
53
    Parameters:
54
    - G: NetworkX graph
55
    - weight: Edge data key for weights
56
    
57
    Returns:
58
    NumPy array of eigenvalues in descending order
59
    """
60

61
def laplacian_spectrum(G, weight='weight'):
62
    """Compute eigenvalues of Laplacian matrix."""
63

64
def normalized_laplacian_spectrum(G, weight='weight'):
65
    """Compute eigenvalues of normalized Laplacian matrix."""
66

67
def modularity_spectrum(G, weight='weight'):
68
    """Compute eigenvalues of modularity matrix."""
69

70
def bethe_hessian_spectrum(G, r=None):
71
    """Compute eigenvalues of Bethe Hessian matrix."""
72
```
73

74
### Algebraic Connectivity
75

76
Functions related to algebraic connectivity and Fiedler vectors.
77

78
```python { .api }
79
def algebraic_connectivity(G, weight='weight', normalized=True, tol=1e-8, method='tracemin_pcg', seed=None):
80
    """
81
    Compute algebraic connectivity of graph.
82
    
83
    Parameters:
84
    - G: NetworkX undirected graph
85
    - weight: Edge data key for weights
86
    - normalized: Use normalized Laplacian if True
87
    - tol: Tolerance for eigenvalue computation
88
    - method: Method for eigenvalue computation
89
    - seed: Random seed for iterative methods
90
    
91
    Returns:
92
    Algebraic connectivity (second smallest eigenvalue of Laplacian)
93
    """
94

95
def fiedler_vector(G, weight='weight', normalized=True, tol=1e-8, method='tracemin_pcg', seed=None):
96
    """Compute Fiedler vector (eigenvector of algebraic connectivity)."""
97

98
def spectral_ordering(G, weight='weight', normalized=True, tol=1e-8, method='tracemin_pcg', seed=None):
99
    """Compute spectral ordering of nodes."""
100
```
101

102
### Matrix Utilities
103

104
Helper functions for working with graph matrices.
105

106
```python { .api }
107
def attr_matrix(G, edge_attr=None, node_attr=None, normalized=False, rc_order=None, dtype=None, order=None):
108
    """
109
    Create matrix from graph attributes.
110
    
111
    Parameters:
112
    - G: NetworkX graph
113
    - edge_attr: Edge attribute name for matrix values
114
    - node_attr: Node attribute name for diagonal values
115
    - normalized: Normalize matrix if True
116
    - rc_order: Ordering for rows and columns
117
    - dtype: Data type for matrix
118
    - order: Memory layout order
119
    
120
    Returns:
121
    Tuple of (matrix, node_list)
122
    """
123

124
def attr_sparse_matrix(G, edge_attr=None, node_attr=None, normalized=False, rc_order=None, dtype=None):
125
    """Create sparse matrix from graph attributes."""
126
```
127

128
### Specialized Matrices
129

130
Additional matrix representations for specific graph analysis tasks.
131

132
```python { .api }
133
def bethe_hessian_matrix(G, r=None, nodelist=None):
134
    """
135
    Compute Bethe Hessian matrix of graph.
136
    
137
    Parameters:
138
    - G: NetworkX graph
139
    - r: Regularization parameter (defaults to average degree)
140
    - nodelist: Nodes in desired order
141
    
142
    Returns:
143
    Bethe Hessian matrix as SciPy sparse matrix
144
    """
145

146
def modularity_matrix(G, nodelist=None, weight=None):
147
    """Compute modularity matrix of graph."""
148

149
def directed_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95):
150
    """Compute directed Laplacian matrix."""
151

152
def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight', walk_type=None, alpha=0.95):
153
    """Compute directed combinatorial Laplacian matrix."""
154
```
155

156
## Usage Examples
157

158
### Basic Matrix Operations
159

160
```python
161
import networkx as nx
162
import numpy as np
163
from scipy import sparse
164
import matplotlib.pyplot as plt
165

166
# Create sample graph
167
G = nx.karate_club_graph()
168

169
# Compute different matrix representations
170
A = nx.adjacency_matrix(G)
171
L = nx.laplacian_matrix(G) 
172
L_norm = nx.normalized_laplacian_matrix(G)
173
I = nx.incidence_matrix(G)
174

175
print(f"Adjacency matrix shape: {A.shape}")
176
print(f"Laplacian matrix shape: {L.shape}")
177
print(f"Incidence matrix shape: {I.shape}")
178

179
# Convert to dense for visualization
180
A_dense = A.toarray()
181
L_dense = L.toarray()
182

183
# Visualize matrices
184
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
185

186
# Adjacency matrix
187
im1 = axes[0].imshow(A_dense, cmap='Blues', interpolation='nearest')
188
axes[0].set_title('Adjacency Matrix')
189
axes[0].set_xlabel('Node')
190
axes[0].set_ylabel('Node')
191
plt.colorbar(im1, ax=axes[0])
192

193
# Laplacian matrix
194
im2 = axes[1].imshow(L_dense, cmap='RdBu', interpolation='nearest')
195
axes[1].set_title('Laplacian Matrix')
196
axes[1].set_xlabel('Node')
197
axes[1].set_ylabel('Node')
198
plt.colorbar(im2, ax=axes[1])
199

200
plt.tight_layout()
201
plt.show()
202
```
203

204
### Spectral Analysis
205

206
```python
207
import networkx as nx
208
import numpy as np
209
import matplotlib.pyplot as plt
210

211
# Create different types of graphs
212
graphs = {
213
    'Complete': nx.complete_graph(10),
214
    'Path': nx.path_graph(10),
215
    'Cycle': nx.cycle_graph(10),
216
    'Star': nx.star_graph(9),
217
    'Random': nx.erdos_renyi_graph(10, 0.3, seed=42)
218
}
219

220
# Compute spectra
221
fig, axes = plt.subplots(2, 3, figsize=(15, 10))
222
axes = axes.flatten()
223

224
for i, (name, G) in enumerate(graphs.items()):
225
    # Compute eigenvalues
226
    adj_eigs = nx.adjacency_spectrum(G)
227
    lap_eigs = nx.laplacian_spectrum(G)
228
    
229
    # Plot spectra
230
    axes[i].stem(range(len(adj_eigs)), adj_eigs, linefmt='b-', markerfmt='bo', 
231
                basefmt=' ', label='Adjacency')
232
    axes[i].stem(range(len(lap_eigs)), lap_eigs, linefmt='r-', markerfmt='ro',
233
                basefmt=' ', label='Laplacian')
234
    axes[i].set_title(f'{name} Graph Spectrum')
235
    axes[i].set_xlabel('Eigenvalue Index')
236
    axes[i].set_ylabel('Eigenvalue')
237
    axes[i].legend()
238
    axes[i].grid(True, alpha=0.3)
239

240
# Remove empty subplot
241
axes[-1].remove()
242

243
plt.tight_layout()
244
plt.show()
245

246
# Print spectral properties
247
for name, G in graphs.items():
248
    adj_eigs = nx.adjacency_spectrum(G)
249
    lap_eigs = nx.laplacian_spectrum(G)
250
    
251
    print(f"\n{name} Graph:")
252
    print(f"  Largest adjacency eigenvalue: {adj_eigs[0]:.3f}")
253
    print(f"  Smallest Laplacian eigenvalue: {lap_eigs[0]:.3f}")
254
    print(f"  Second smallest Laplacian eigenvalue: {lap_eigs[1]:.3f}")
255
```
256

257
### Algebraic Connectivity
258

259
```python
260
import networkx as nx
261
import numpy as np
262
import matplotlib.pyplot as plt
263

264
# Create graph that becomes more connected
265
def create_bridged_graph(n_bridges):
266
    """Create two cliques connected by bridges."""
267
    G = nx.Graph()
268
    
269
    # Two complete graphs
270
    G1 = nx.complete_graph(5)
271
    G2 = nx.complete_graph(5)
272
    
273
    # Relabel nodes to avoid conflicts
274
    G2 = nx.relabel_nodes(G2, {i: i+5 for i in G2.nodes()})
275
    
276
    # Combine graphs
277
    G = nx.union(G1, G2)
278
    
279
    # Add bridges
280
    for i in range(n_bridges):
281
        G.add_edge(i % 5, 5 + (i % 5))
282
    
283
    return G
284

285
# Test algebraic connectivity for different numbers of bridges
286
n_bridges_list = range(1, 6)
287
connectivities = []
288
fiedler_vecs = []
289

290
fig, axes = plt.subplots(2, len(n_bridges_list), figsize=(20, 8))
291

292
for i, n_bridges in enumerate(n_bridges_list):
293
    G = create_bridged_graph(n_bridges)
294
    
295
    # Compute algebraic connectivity
296
    alg_conn = nx.algebraic_connectivity(G)
297
    connectivities.append(alg_conn)
298
    
299
    # Compute Fiedler vector
300
    fiedler = nx.fiedler_vector(G)
301
    fiedler_vecs.append(fiedler)
302
    
303
    # Draw graph
304
    pos = nx.spring_layout(G, seed=42)
305
    node_colors = ['red' if f > 0 else 'blue' for f in fiedler]
306
    
307
    nx.draw(G, pos=pos, ax=axes[0, i], 
308
            node_color=node_colors, 
309
            node_size=300,
310
            with_labels=True,
311
            font_size=8)
312
    axes[0, i].set_title(f'{n_bridges} Bridges\nAlg. Conn. = {alg_conn:.3f}')
313
    
314
    # Plot Fiedler vector
315
    axes[1, i].bar(range(len(fiedler)), fiedler, 
316
                   color=['red' if f > 0 else 'blue' for f in fiedler])
317
    axes[1, i].set_title('Fiedler Vector')
318
    axes[1, i].set_xlabel('Node')
319
    axes[1, i].set_ylabel('Fiedler Value')
320
    axes[1, i].axhline(y=0, color='black', linestyle='--', alpha=0.5)
321

322
plt.tight_layout()
323
plt.show()
324

325
# Plot connectivity vs number of bridges
326
plt.figure(figsize=(8, 6))
327
plt.plot(n_bridges_list, connectivities, 'bo-', linewidth=2, markersize=8)
328
plt.xlabel('Number of Bridges')
329
plt.ylabel('Algebraic Connectivity')
330
plt.title('Algebraic Connectivity vs Graph Connectivity')
331
plt.grid(True, alpha=0.3)
332
plt.show()
333
```
334

335
### Weighted Graph Spectral Analysis
336

337
```python
338
import networkx as nx
339
import numpy as np
340
import matplotlib.pyplot as plt
341

342
# Create weighted graph
343
G = nx.Graph()
344
edges = [
345
    (1, 2, 0.5), (2, 3, 1.0), (3, 4, 1.5), (4, 1, 0.8),
346
    (1, 3, 0.3), (2, 4, 0.6), (1, 5, 2.0), (5, 6, 1.2),
347
    (6, 3, 0.9), (5, 4, 0.7)
348
]
349
G.add_weighted_edges_from(edges)
350

351
# Compute weighted matrices
352
A_weighted = nx.adjacency_matrix(G, weight='weight')
353
L_weighted = nx.laplacian_matrix(G, weight='weight')
354
A_unweighted = nx.adjacency_matrix(G, weight=None)
355
L_unweighted = nx.laplacian_matrix(G, weight=None)
356

357
# Compute spectra
358
adj_spec_weighted = nx.adjacency_spectrum(G, weight='weight')
359
lap_spec_weighted = nx.laplacian_spectrum(G, weight='weight')
360
adj_spec_unweighted = nx.adjacency_spectrum(G, weight=None)
361
lap_spec_unweighted = nx.laplacian_spectrum(G, weight=None)
362

363
# Visualize comparison
364
fig, axes = plt.subplots(2, 2, figsize=(12, 10))
365

366
# Adjacency spectra
367
axes[0, 0].stem(range(len(adj_spec_weighted)), adj_spec_weighted, 
368
                linefmt='b-', markerfmt='bo', basefmt=' ', label='Weighted')
369
axes[0, 0].stem(range(len(adj_spec_unweighted)), adj_spec_unweighted,
370
                linefmt='r-', markerfmt='ro', basefmt=' ', label='Unweighted')
371
axes[0, 0].set_title('Adjacency Spectrum')
372
axes[0, 0].set_ylabel('Eigenvalue')
373
axes[0, 0].legend()
374
axes[0, 0].grid(True, alpha=0.3)
375

376
# Laplacian spectra
377
axes[0, 1].stem(range(len(lap_spec_weighted)), lap_spec_weighted,
378
                linefmt='b-', markerfmt='bo', basefmt=' ', label='Weighted')
379
axes[0, 1].stem(range(len(lap_spec_unweighted)), lap_spec_unweighted,
380
                linefmt='r-', markerfmt='ro', basefmt=' ', label='Unweighted')
381
axes[0, 1].set_title('Laplacian Spectrum')
382
axes[0, 1].set_ylabel('Eigenvalue')
383
axes[0, 1].legend()
384
axes[0, 1].grid(True, alpha=0.3)
385

386
# Graph visualization
387
pos = nx.spring_layout(G, seed=42)
388

389
# Weighted edges
390
edge_weights = [G[u][v]['weight'] for u, v in G.edges()]
391
nx.draw(G, pos=pos, ax=axes[1, 0],
392
        node_color='lightblue',
393
        node_size=500,
394
        width=[w*3 for w in edge_weights],
395
        edge_color=edge_weights,
396
        edge_cmap=plt.cm.Blues,
397
        with_labels=True,
398
        font_weight='bold')
399
axes[1, 0].set_title('Weighted Graph')
400

401
# Edge labels showing weights
402
edge_labels = {(u, v): f"{d['weight']:.1f}" for u, v, d in G.edges(data=True)}
403
nx.draw_networkx_edge_labels(G, pos, edge_labels, ax=axes[1, 1], font_size=10)
404
nx.draw(G, pos=pos, ax=axes[1, 1],
405
        node_color='lightcoral',
406
        node_size=500,
407
        with_labels=True,
408
        font_weight='bold',
409
        edge_color='gray')
410
axes[1, 1].set_title('Edge Weights')
411

412
plt.tight_layout()
413
plt.show()
414

415
# Compare algebraic connectivity
416
alg_conn_weighted = nx.algebraic_connectivity(G, weight='weight')
417
alg_conn_unweighted = nx.algebraic_connectivity(G, weight=None)
418

419
print(f"Algebraic connectivity (weighted): {alg_conn_weighted:.4f}")
420
print(f"Algebraic connectivity (unweighted): {alg_conn_unweighted:.4f}")
421
```
422

423
### Matrix-based Graph Analysis
424

425
```python
426
import networkx as nx
427
import numpy as np
428
from scipy import sparse, linalg
429
import matplotlib.pyplot as plt
430

431
# Create graph
432
G = nx.erdos_renyi_graph(50, 0.1, seed=42)
433

434
# Get adjacency matrix
435
A = nx.adjacency_matrix(G, dtype=float)
436

437
# Compute powers of adjacency matrix
438
A2 = A @ A  # A^2 gives 2-hop connections
439
A3 = A2 @ A  # A^3 gives 3-hop connections
440

441
# Analyze path structure
442
def analyze_paths(G, A_power, k):
443
    """Analyze k-hop paths in graph."""
444
    n = G.number_of_nodes()
445
    A_dense = A_power.toarray()
446
    
447
    # Count paths of length k
448
    total_paths = np.sum(A_dense)
449
    
450
    # Find nodes with most k-hop connections
451
    k_hop_degree = np.sum(A_dense, axis=1)
452
    max_node = np.argmax(k_hop_degree)
453
    
454
    return total_paths, max_node, k_hop_degree[max_node]
455

456
# Analyze 1, 2, 3-hop connections
457
results = []
458
for k, A_k in enumerate([A, A2, A3], 1):
459
    total, max_node, max_degree = analyze_paths(G, A_k, k)
460
    results.append((k, total, max_node, max_degree))
461
    print(f"{k}-hop paths: {int(total)} total, node {max_node} has {int(max_degree)}")
462

463
# Visualize matrix powers
464
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
465

466
matrices = [('A (1-hop)', A), ('A² (2-hop)', A2), ('A³ (3-hop)', A3)]
467

468
for i, (title, matrix) in enumerate(matrices):
469
    # Convert to dense for visualization (only for small matrices)
470
    if matrix.shape[0] <= 50:
471
        dense_matrix = matrix.toarray()
472
        im = axes[i].imshow(dense_matrix, cmap='Blues', interpolation='nearest')
473
        axes[i].set_title(title)
474
        axes[i].set_xlabel('Node')
475
        axes[i].set_ylabel('Node')
476
        plt.colorbar(im, ax=axes[i])
477

478
plt.tight_layout()
479
plt.show()
480

481
# Spectral clustering using Laplacian
482
L = nx.normalized_laplacian_matrix(G, dtype=float)
483

484
# Compute eigenvectors
485
eigenvals, eigenvecs = sparse.linalg.eigsh(L, k=3, which='SM')
486

487
# Use second eigenvector (Fiedler vector) for 2-way clustering
488
fiedler = eigenvecs[:, 1]
489
cluster_assignment = (fiedler > 0).astype(int)
490

491
# Visualize clustering
492
pos = nx.spring_layout(G, seed=42)
493
node_colors = ['red' if c == 0 else 'blue' for c in cluster_assignment]
494

495
plt.figure(figsize=(12, 5))
496

497
plt.subplot(121)
498
nx.draw(G, pos=pos, node_color=node_colors, node_size=100, 
499
        with_labels=False, edge_color='gray', alpha=0.7)
500
plt.title('Spectral Clustering (2 clusters)')
501

502
plt.subplot(122)
503
plt.plot(fiedler, 'o-', alpha=0.7)
504
plt.axhline(y=0, color='red', linestyle='--', alpha=0.5)
505
plt.xlabel('Node Index')
506
plt.ylabel('Fiedler Vector Value')
507
plt.title('Fiedler Vector Values')
508
plt.grid(True, alpha=0.3)
509

510
plt.tight_layout()
511
plt.show()
512

513
print(f"Cluster 0: {np.sum(cluster_assignment == 0)} nodes")
514
print(f"Cluster 1: {np.sum(cluster_assignment == 1)} nodes")
515
```