Algebraic Graph Algorithms. A Practical Guide Using Python

Preface
Contents
1 Introduction
	1.1 Graphs
	1.2 Matrices
	1.3 Algebraic Graph Algorithms
	1.4 Python Language
	1.5 Challenges
	1.6 Outline of the Book
		1.6.1 Background
		1.6.2 Basic Graph Algorithms
blackPart I Background-1pt
2 A Short Review of Python
	2.1 Introduction
	2.2 Data Structures
		2.2.1 Strings
		2.2.2 Lists
		2.2.3 Tuples
		2.2.4 Arrays
		2.2.5 Dictionaries
		2.2.6 Sets
	2.3 Flow Control
		2.3.1 The if Statement
		2.3.2 Loops
	2.4 Functions
	2.5 Modules
	2.6 Chapter Notes
3 Basic Matrix Computations
	3.1 Introduction
	3.2 Matrix Operations
	3.3 Transpose of a Matrix
	3.4 Matrix Properties
	3.5 Types of Matrices
		3.5.1 Diagonal Matrix
		3.5.2 Identity Matrix
		3.5.3 Triangular Matrix
	3.6 Matrix Multiplication
		3.6.1 Vector-Vector Multiplication
		3.6.2 Matrix-Vector Multiplication
		3.6.3 Matrix-Matrix Multiplication
		3.6.4 Boolean Matrix Multiplication
	3.7 Determinant of a Matrix
	3.8 Matrix Inverse
	3.9 Rank Computation
		3.9.1 Powers of a Matrix
	3.10 Eigenvalues and Eigenvectors
	3.11 Block Matrices
	3.12 Chapter Notes
4 Graphs, Matrices and Matroids
	4.1 Introduction to Graphs
		4.1.1 Degree of a Vertex
		4.1.2 Subgraphs
	4.2 Graph Operations
	4.3 Types of Graphs
		4.3.1 Digraph
		4.3.2 Complete Graphs
		4.3.3 Weighted Graphs
		4.3.4 Bipartite Graphs
		4.3.5 Regular Graphs
		4.3.6 Graph Isomorphism
	4.4 Walks, Paths, Cycles
	4.5 Graphs and Matrices
		4.5.1 Adjacency Matrix
		4.5.2 Adjacency List
		4.5.3 Incidence Matrix
		4.5.4 Cycle Matrix
		4.5.5 Path Matrix
		4.5.6 The Laplacian
	4.6 Python Graphs
	4.7 Matroids
		4.7.1 The Basic Matroid
		4.7.2 The Graphic Matroid
		4.7.3 Weighted Matroid
		4.7.4 Graphs, Matroids and Matrices
	4.8 Chapter Notes
5 Parallel and Sparse Matrix Computations
	5.1 Parallel Processing
		5.1.1 Architectures
		5.1.2 Basic Communications
		5.1.3 Performance
		5.1.4 Parallel Matrix Computations
	5.2 Parallel Computations with Python
		5.2.1 Process-Based Model with Multiprocessing
		5.2.2 Message Passing Interface mpi4py
	5.3 Sparse Matrix Algorithms
		5.3.1 Sparsity Calculation
		5.3.2 Sparse Matrix Representations
		5.3.3 Sparse Matrix Multiplication
	5.4 Chapter Notes
blackPart II Graph Algorithms-1pt
6 Trees
	6.1 Introduction
	6.2 Spanning Tree Construction
	6.3 Minimum Spanning Trees
		6.3.1 Jarnik-Prim Algorithm
		6.3.2 Kruskal's Algorithm as a Matroid
		6.3.3 Boruvka's Algorithm
	6.4 Chapter Notes
7 Shortest Paths
	7.1 Introduction
	7.2 Breadth-First-Search
		7.2.1 The Classical Algorithm
		7.2.2 The Algebraic Algorithm
	7.3 Dijkstra's Algorithm
	7.4 Bellman-Ford Algorithm
	7.5 Floyd-Warshall Algorithm
	7.6 Transitive Closure
	7.7 Chapter Notes
8 Connectivity and Matching
	8.1 Connectivity
		8.1.1 Theory
		8.1.2 Undirected Graph Connectivity
		8.1.3 Directed Graph Connectivity
	8.2 Matching
		8.2.1 Unweighted Matching
		8.2.2 Weighted Matching
		8.2.3 Rabin-Vazirani Algorithm
	8.3 Chapter Notes
9 Subgraph Search
	9.1 Independent Sets
		9.1.1 A Greedy Algorithm
		9.1.2 Lowest Degree First Algorithm
		9.1.3 Luby's Algorithm
	9.2 Dominating Sets
	9.3 Vertex Cover
		9.3.1 A Greedy Algorithm
		9.3.2 A 2-Approximation Algorithm
	9.4 Coloring
		9.4.1 Vertex Coloring
		9.4.2 Edge Coloring
	9.5 Chapter Notes
10 Large Graph Analysis
	10.1 Introduction
	10.2 Degree Distribution
	10.3 Density
	10.4 Clustering Coefficient
	10.5 Matching Index
	10.6 Centrality
		10.6.1 Degree Centrality
		10.6.2 Closeness Centrality
		10.6.3 Vertex Betweenness Centrality
		10.6.4 Edge Betweenness Centrality
		10.6.5 Eigenvalue Centrality
	10.7 Network Models
		10.7.1 Random Networks
		10.7.2 Small-World Networks
		10.7.3 Scale-Free Networks
	10.8 Kronecker Graphs
	10.9 Chapter Notes
11 Graph Partitioning and Clustering
	11.1 Graph Partitioning
		11.1.1 BFS-Based Partitioning
		11.1.2 Spectral Bisection
		11.1.3 Multilevel Graph Partitioning
	11.2 Graph Clustering
		11.2.1 MST-Based Clustering
		11.2.2 Shared Nearest Neighbor Clustering
		11.2.3 Edge Betweenness Clustering
		11.2.4 k-Core Clustering
	11.3 Chapter Notes
Index