Real World: Adjacency Matrices in Networks

Linear Algebra for Machine Learning · Axiom Academy

Graph Theory & Adjacency Matrices An adjacency matrix represents a graph. For a graph with n vertices, the adjacency matrix A is an n×n matrix where entry aᵢⱼ = 1 if there's an edge from vertex i to vertex j, and 0 otherwise. Consider a network with connections: 1→2, 1→3, 2→3, 2→4, 3→4 Each row represents outgoing connections. Each column represents incoming connections. Path Counting with Matrix Powers The entry (Aᵏ)ᵢⱼ gives the number of paths of length k from vertex i to vertex j. Example: (A²)₁₄ = 1 means there's exactly 1 path of length 2 from vertex 1 to vertex 4 (via vertex 3). Applications in Social Networks Model social networks where aᵢⱼ = 1 if persons i and j are friends. A² tells us mutual friends in common A³ gives second-degree connections Determinant and eigenvalues reveal network properties Google's PageRank uses matrices! The web is a directed graph where pages are vertices and links are edges. The adjacency matrix encodes the link structure, and eigenvalues determine page importance. Pages with high eigenvector centrality rank higher in search results. Properties of Adjacency Matrices Symmetric for undirected graphs: aᵢⱼ = aⱼᵢ Diagonal is zero: No self-loops typically Row sums: Out-degree of each vertex Column sums: In-degree of each vertex Eigenvalues: Reveal network structure and properties LinkedIn: Connection graph with millions of vertices Facebook: Friendship graph, used for recommendations Web Graph: Pages and hyperlinks (billions of vertices)

This is the written version of the interactive lesson above. See the full Linear Algebra for Machine Learning course.