Network Analysis and Graph Statistics

Network science provides the mathematical language for studying complex systems of interacting entities. From social networks and biological pathways to communication infrastructure and financial systems, the statistical analysis of networks reveals structural patterns, identifies influential nodes, and detects latent community organization. This lesson develops the theoretical foundations and computational methods for rigorous network analysis.

Graph Fundamentals

Centrality Measures

Centrality quantifies the relative importance of nodes within a network. Different measures capture different notions of "importance" — popularity, brokerage, proximity, or influence.

Community Detection

Communities (modules, clusters) are groups of nodes that are more densely connected internally than with the rest of the network. Quantifying community structure requires a modularity function.

Network Generative Models

Generative models specify probability distributions over graphs, enabling hypothesis testing and simulation.

Exponential Random Graph Models

ERGMs provide a principled statistical framework for modeling network structure as a function of network statistics.

Python Implementation

import numpy as np
import networkx as nx
from networkx.algorithms.community import louvain_communities, modularity
from scipy import stats
import matplotlib.pyplot as plt

np.random.seed(42)

# --- Generate Network Models ---
n = 500

# Erdos-Renyi
G_er = nx.erdos_renyi_graph(n, p=0.01, seed=42)
degrees_er = [d for _, d in G_er.degree()]

# Barabasi-Albert
G_ba = nx.barabasi_albert_graph(n, m=3, seed=42)
degrees_ba = [d for _, d in G_ba.degree()]

# Watts-Strogatz
G_ws = nx.watts_strogatz_graph(n, k=6, p=0.1, seed=42)
degrees_ws = [d for _, d in G_ws.degree()]

# --- Centrality Measures ---
G = G_ba  # Use BA model for centrality analysis
degree_cent = nx.degree_centrality(G)
between_cent = nx.betweenness_centrality(G, k=100)  # sampled
closeness_cent = nx.closeness_centrality(G)
eigen_cent = nx.eigenvector_centrality(G, max_iter=1000)

# Top nodes by different centrality measures
top_degree = sorted(degree_cent.items(), key=lambda x: -x[1])[:5]
top_between = sorted(between_cent.items(), key=lambda x: -x[1])[:5]
top_eigen = sorted(eigen_cent.items(), key=lambda x: -x[1])[:5]

print("=== Top 5 Nodes by Centrality ===")
print(f"{'Node':<8} {'Degree':<12} {'Betweenness':<14} {'Eigenvector':<12}")
print("-" * 46)
for i in range(5):
    print(f"{top_degree[i][0]:<8} {top_degree[i][1]:<12.4f} "
          f"{top_between[i][1]:<14.4f} {top_eigen[i][1]:<12.4f}")

# --- Community Detection ---
communities = louvain_communities(G, seed=42)
Q = modularity(G, communities)
print(f"\n=== Community Detection (Louvain) ===")
print(f"Number of communities: {len(communities)}")
print(f"Modularity: {Q:.4f}")
print(f"Community sizes: {[len(c) for c in sorted(communities, key=len, reverse=True)]}")

# --- Degree Distribution Analysis ---
fig, axes = plt.subplots(1, 3, figsize=(15, 5))

for ax, degs, title in zip(axes, 
                            [degrees_er, degrees_ba, degrees_ws],
                            ['Erdos-Renyi', 'Barabasi-Albert', 'Watts-Strogatz']):
    ax.hist(degs, bins=max(degs) - min(degs) + 1, density=True, 
            alpha=0.7, edgecolor='black', linewidth=0.5)
    ax.set_xlabel('Degree k')
    ax.set_ylabel('P(k)')
    ax.set_title(f'{title} (n={n})')

plt.tight_layout()
plt.savefig("network_degree_distributions.png", dpi=150, bbox_inches="tight")
plt.show()

# --- Network Statistics ---
print(f"\n=== Network Statistics ===")
for name, G_model in [('ER', G_er), ('BA', G_ba), ('WS', G_ws)]:
    print(f"\n{name}:")
    print(f"  Edges: {G_model.number_of_edges()}")
    print(f"  Avg degree: {2 * G_model.number_of_edges() / n:.2f}")
    print(f"  Clustering coeff: {nx.average_clustering(G_model):.4f}")
    print(f"  Avg path length: {nx.average_shortest_path_length(G_model) if nx.is_connected(G_model) else 'N/A (disconnected)'}")
    print(f"  Diameter: {nx.diameter(G_model) if nx.is_connected(G_model) else 'N/A (disconnected)'}")

Summary