Linear Algebra

def adjacency_matrix(G, nodelist=None, dtype=None, weight='weight'):
    """
    Compute adjacency matrix of graph as SciPy sparse matrix.
    
    Parameters:
    - G: NetworkX graph
    - nodelist: List of nodes in desired order
    - dtype: Data type for matrix elements
    - weight: Edge data key for weights (default: 'weight')
    
    Returns:
    SciPy sparse matrix representing graph adjacency
    """

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

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

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

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

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

def bethe_hessian_matrix(G, r=None, nodelist=None):
    """Compute Bethe Hessian matrix."""

def adjacency_spectrum(G, weight='weight'):
    """
    Compute eigenvalues of adjacency matrix.
    
    Parameters:
    - G: NetworkX graph
    - weight: Edge data key for weights
    
    Returns:
    NumPy array of eigenvalues in descending order
    """

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

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

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

def bethe_hessian_spectrum(G, r=None):
    """Compute eigenvalues of Bethe Hessian matrix."""

def algebraic_connectivity(G, weight='weight', normalized=True, tol=1e-8, method='tracemin_pcg', seed=None):
    """
    Compute algebraic connectivity of graph.
    
    Parameters:
    - G: NetworkX undirected graph
    - weight: Edge data key for weights
    - normalized: Use normalized Laplacian if True
    - tol: Tolerance for eigenvalue computation
    - method: Method for eigenvalue computation
    - seed: Random seed for iterative methods
    
    Returns:
    Algebraic connectivity (second smallest eigenvalue of Laplacian)
    """

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

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

def attr_matrix(G, edge_attr=None, node_attr=None, normalized=False, rc_order=None, dtype=None, order=None):
    """
    Create matrix from graph attributes.
    
    Parameters:
    - G: NetworkX graph
    - edge_attr: Edge attribute name for matrix values
    - node_attr: Node attribute name for diagonal values
    - normalized: Normalize matrix if True
    - rc_order: Ordering for rows and columns
    - dtype: Data type for matrix
    - order: Memory layout order
    
    Returns:
    Tuple of (matrix, node_list)
    """

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

def bethe_hessian_matrix(G, r=None, nodelist=None):
    """
    Compute Bethe Hessian matrix of graph.
    
    Parameters:
    - G: NetworkX graph
    - r: Regularization parameter (defaults to average degree)
    - nodelist: Nodes in desired order
    
    Returns:
    Bethe Hessian matrix as SciPy sparse matrix
    """

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

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

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

import networkx as nx
import numpy as np
from scipy import sparse
import matplotlib.pyplot as plt

# Create sample graph
G = nx.karate_club_graph()

# Compute different matrix representations
A = nx.adjacency_matrix(G)
L = nx.laplacian_matrix(G) 
L_norm = nx.normalized_laplacian_matrix(G)
I = nx.incidence_matrix(G)

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

# Convert to dense for visualization
A_dense = A.toarray()
L_dense = L.toarray()

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

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

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

plt.tight_layout()
plt.show()

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# Create different types of graphs
graphs = {
    'Complete': nx.complete_graph(10),
    'Path': nx.path_graph(10),
    'Cycle': nx.cycle_graph(10),
    'Star': nx.star_graph(9),
    'Random': nx.erdos_renyi_graph(10, 0.3, seed=42)
}

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

for i, (name, G) in enumerate(graphs.items()):
    # Compute eigenvalues
    adj_eigs = nx.adjacency_spectrum(G)
    lap_eigs = nx.laplacian_spectrum(G)
    
    # Plot spectra
    axes[i].stem(range(len(adj_eigs)), adj_eigs, linefmt='b-', markerfmt='bo', 
                basefmt=' ', label='Adjacency')
    axes[i].stem(range(len(lap_eigs)), lap_eigs, linefmt='r-', markerfmt='ro',
                basefmt=' ', label='Laplacian')
    axes[i].set_title(f'{name} Graph Spectrum')
    axes[i].set_xlabel('Eigenvalue Index')
    axes[i].set_ylabel('Eigenvalue')
    axes[i].legend()
    axes[i].grid(True, alpha=0.3)

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

plt.tight_layout()
plt.show()

# Print spectral properties
for name, G in graphs.items():
    adj_eigs = nx.adjacency_spectrum(G)
    lap_eigs = nx.laplacian_spectrum(G)
    
    print(f"\n{name} Graph:")
    print(f"  Largest adjacency eigenvalue: {adj_eigs[0]:.3f}")
    print(f"  Smallest Laplacian eigenvalue: {lap_eigs[0]:.3f}")
    print(f"  Second smallest Laplacian eigenvalue: {lap_eigs[1]:.3f}")

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# Create graph that becomes more connected
def create_bridged_graph(n_bridges):
    """Create two cliques connected by bridges."""
    G = nx.Graph()
    
    # Two complete graphs
    G1 = nx.complete_graph(5)
    G2 = nx.complete_graph(5)
    
    # Relabel nodes to avoid conflicts
    G2 = nx.relabel_nodes(G2, {i: i+5 for i in G2.nodes()})
    
    # Combine graphs
    G = nx.union(G1, G2)
    
    # Add bridges
    for i in range(n_bridges):
        G.add_edge(i % 5, 5 + (i % 5))
    
    return G

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

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

for i, n_bridges in enumerate(n_bridges_list):
    G = create_bridged_graph(n_bridges)
    
    # Compute algebraic connectivity
    alg_conn = nx.algebraic_connectivity(G)
    connectivities.append(alg_conn)
    
    # Compute Fiedler vector
    fiedler = nx.fiedler_vector(G)
    fiedler_vecs.append(fiedler)
    
    # Draw graph
    pos = nx.spring_layout(G, seed=42)
    node_colors = ['red' if f > 0 else 'blue' for f in fiedler]
    
    nx.draw(G, pos=pos, ax=axes[0, i], 
            node_color=node_colors, 
            node_size=300,
            with_labels=True,
            font_size=8)
    axes[0, i].set_title(f'{n_bridges} Bridges\nAlg. Conn. = {alg_conn:.3f}')
    
    # Plot Fiedler vector
    axes[1, i].bar(range(len(fiedler)), fiedler, 
                   color=['red' if f > 0 else 'blue' for f in fiedler])
    axes[1, i].set_title('Fiedler Vector')
    axes[1, i].set_xlabel('Node')
    axes[1, i].set_ylabel('Fiedler Value')
    axes[1, i].axhline(y=0, color='black', linestyle='--', alpha=0.5)

plt.tight_layout()
plt.show()

# Plot connectivity vs number of bridges
plt.figure(figsize=(8, 6))
plt.plot(n_bridges_list, connectivities, 'bo-', linewidth=2, markersize=8)
plt.xlabel('Number of Bridges')
plt.ylabel('Algebraic Connectivity')
plt.title('Algebraic Connectivity vs Graph Connectivity')
plt.grid(True, alpha=0.3)
plt.show()

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# Create weighted graph
G = nx.Graph()
edges = [
    (1, 2, 0.5), (2, 3, 1.0), (3, 4, 1.5), (4, 1, 0.8),
    (1, 3, 0.3), (2, 4, 0.6), (1, 5, 2.0), (5, 6, 1.2),
    (6, 3, 0.9), (5, 4, 0.7)
]
G.add_weighted_edges_from(edges)

# Compute weighted matrices
A_weighted = nx.adjacency_matrix(G, weight='weight')
L_weighted = nx.laplacian_matrix(G, weight='weight')
A_unweighted = nx.adjacency_matrix(G, weight=None)
L_unweighted = nx.laplacian_matrix(G, weight=None)

# Compute spectra
adj_spec_weighted = nx.adjacency_spectrum(G, weight='weight')
lap_spec_weighted = nx.laplacian_spectrum(G, weight='weight')
adj_spec_unweighted = nx.adjacency_spectrum(G, weight=None)
lap_spec_unweighted = nx.laplacian_spectrum(G, weight=None)

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

# Adjacency spectra
axes[0, 0].stem(range(len(adj_spec_weighted)), adj_spec_weighted, 
                linefmt='b-', markerfmt='bo', basefmt=' ', label='Weighted')
axes[0, 0].stem(range(len(adj_spec_unweighted)), adj_spec_unweighted,
                linefmt='r-', markerfmt='ro', basefmt=' ', label='Unweighted')
axes[0, 0].set_title('Adjacency Spectrum')
axes[0, 0].set_ylabel('Eigenvalue')
axes[0, 0].legend()
axes[0, 0].grid(True, alpha=0.3)

# Laplacian spectra
axes[0, 1].stem(range(len(lap_spec_weighted)), lap_spec_weighted,
                linefmt='b-', markerfmt='bo', basefmt=' ', label='Weighted')
axes[0, 1].stem(range(len(lap_spec_unweighted)), lap_spec_unweighted,
                linefmt='r-', markerfmt='ro', basefmt=' ', label='Unweighted')
axes[0, 1].set_title('Laplacian Spectrum')
axes[0, 1].set_ylabel('Eigenvalue')
axes[0, 1].legend()
axes[0, 1].grid(True, alpha=0.3)

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

# Weighted edges
edge_weights = [G[u][v]['weight'] for u, v in G.edges()]
nx.draw(G, pos=pos, ax=axes[1, 0],
        node_color='lightblue',
        node_size=500,
        width=[w*3 for w in edge_weights],
        edge_color=edge_weights,
        edge_cmap=plt.cm.Blues,
        with_labels=True,
        font_weight='bold')
axes[1, 0].set_title('Weighted Graph')

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

plt.tight_layout()
plt.show()

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

print(f"Algebraic connectivity (weighted): {alg_conn_weighted:.4f}")
print(f"Algebraic connectivity (unweighted): {alg_conn_unweighted:.4f}")

import networkx as nx
import numpy as np
from scipy import sparse, linalg
import matplotlib.pyplot as plt

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

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

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

# Analyze path structure
def analyze_paths(G, A_power, k):
    """Analyze k-hop paths in graph."""
    n = G.number_of_nodes()
    A_dense = A_power.toarray()
    
    # Count paths of length k
    total_paths = np.sum(A_dense)
    
    # Find nodes with most k-hop connections
    k_hop_degree = np.sum(A_dense, axis=1)
    max_node = np.argmax(k_hop_degree)
    
    return total_paths, max_node, k_hop_degree[max_node]

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

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

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

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

plt.tight_layout()
plt.show()

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

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

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

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

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

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

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

plt.tight_layout()
plt.show()

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