Political Science Observations

Mathematical Models for Network Topologies

Essential equations and algorithms for mapping and analyzing network structures

Fundamental Graph Theory Equations

Adjacency Matrix Representation

The most fundamental representation of any network topology is the adjacency matrix A, where:

A[i][j] = 1 if there is an edge from node i to node j, 0 otherwise

Key Properties:

For undirected graphs: A = A^T (symmetric)

For weighted graphs: A[i][j] = weight of edge (i,j)

Laplacian Matrix

Captures both connectivity and degree information of the graph:

L = D - A

Where D is the degree matrix (diagonal matrix with D[i][i] = degree of node i)

Normalized Laplacian:

L_norm = D^-1/2 L D^-1/2 = I - D^-1/2 A D^-1/2

Graph Convolutional Network Equation

The core operation for applying convolutional filters on graph structures:

H^(l+1) = σ(Â H^(l) W^(l))

Parameters:

Â = D̃^-1/2 Ã D̃^-1/2 (normalized adjacency with self-loops)

Ã = A + I (adjacency matrix with self-connections)

D̃ = degree matrix of Ã

H^(l) = node features at layer l

W^(l) = trainable weight matrix at layer l

σ = activation function

Shortest Path Algorithms

Dijkstra's algorithm for weighted graphs with non-negative weights:

dist[v] = min(dist[v], dist[u] + weight(u, v))

Floyd-Warshall for all pairs shortest paths:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Topology-Specific Mathematical Models

Star Topology Metrics

For a star network with n nodes (1 central hub, n-1 peripheral nodes):

Diameter = 2

Average Path Length = 2 × (n-1)/n

Central Point Dominance = 1

Mesh Topology Metrics

For a full mesh network with n nodes:

Number of edges = n(n-1)/2

Diameter = 1

Average Path Length = 1

Edge Connectivity = n-1

Ring Topology Metrics

For a ring network with n nodes:

Diameter = ⌊n/2⌋

Average Path Length = (n+1)/4 for odd n, n/4 for even n

Edge Connectivity = 2

Betweenness Centrality

Measures node importance based on shortest paths passing through it:

C_B(v) = ∑_s≠v≠t σ_st(v) / σ_st

Where σ_st is the number of shortest paths from s to t, and σ_st(v) is the number of those paths passing through v.

Computational Complexity

Algorithm/Operation	Time Complexity	Space Complexity	Best Use Case
Adjacency Matrix Storage	O(1) edge lookup	O(V²)	Dense graphs
Adjacency List Storage	O(degree(v)) edge lookup	O(V+E)	Sparse graphs
Breadth-First Search (BFS)	O(V+E)	O(V)	Shortest paths in unweighted graphs
Dijkstra's Algorithm	O((V+E) log V)	O(V)	Weighted graphs with non-negative weights
Floyd-Warshall Algorithm	O(V³)	O(V²)	All pairs shortest paths
GCN Forward Pass	O(E×F) per layer	O(V×F + E)	Node classification, graph analysis

Matrix Representations Examples

Star Network (4 nodes)

Adjacency Matrix A:

[0 1 1 1]
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]

Degree Matrix D:

[3 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

Laplacian Matrix L = D - A:

[ 3 -1 -1 -1]
[-1  1  0  0]
[-1  0  1  0]
[-1  0  0  1]

Ring Network (4 nodes)

Adjacency Matrix A:

[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]

Practical Implementation Considerations

Sparse Matrix Storage

For large networks, use compressed sparse row (CSR) format to store adjacency matrices efficiently, reducing storage from O(V²) to O(V+E).

Approximation Algorithms

For massive graphs, use betweenness centrality approximations or landmark-based shortest path estimation to reduce computational complexity.

Parallel Processing

Leverage GPU acceleration for GCN operations and graph algorithms, particularly for matrix multiplications and neighborhood aggregations.

Dynamic Graphs

For evolving networks, use incremental algorithms that update metrics without recomputing from scratch, saving computational resources.