Adjacency Matrix

====================

The Adjacency Matrix is a square matrix used to represent a graph or network. It is a fundamental concept in Graph Theory and has numerous applications in Computer Science, Social Networks, and other fields.

Definition

An Adjacency Matrix is a square matrix of size n x n, where n is the number of vertices (or nodes) in the graph. The entry at row i and column j represents the presence or absence of an edge between vertex i and vertex j.

Construction

The Adjacency Matrix is constructed by adding a vector of all ones to each row of the matrix, resulting in a square matrix with n rows and columns. Each entry at position (i, j) represents the number of edges from vertex i to vertex j. If there is no edge between vertices i and j, the corresponding entry will be zero.

Properties

Non-zero entries

• The Adjacency Matrix has non-zero entries only for the edges that exist in the graph.
• The number of non-zero entries in each row represents the degree of vertex i.

Zero entries

• All other entries in the matrix are zero.
• There is at most one zero entry per row.

Applications

1. Graph Traversal: Adjacency matrices can be used to implement graph traversal Algorithms, such as Breadth-First Search (BFS) and Depth-First Search (DFS).
2. Shortest Paths: The Adjacency Matrix can be used to find the shortest path between two vertices in a weighted graph.
3. Closeness Centrality: The sum of non-zero entries in each row can be used to calculate Closeness Centrality, which measures how similar an element is to other elements in the network.

Example

Consider a graph with four vertices: A, B, C, and D.

In this example, the Adjacency Matrix represents a simple graph with four vertices. The non-zero entries indicate that there is an edge between each pair of vertices.

Code

Here is an example implementation in Python:

def create_adjacency_matrix(graph):
    """
    Create an [Adjacency Matrix](/Adjacency_Matrix) for a given graph.

    Args:
        graph (dict): A dictionary representing the graph, where each key is a vertex and its value is another dictionary.
                        The inner dictionary's keys represent the neighboring vertices and its values are their respective edges.

    Returns:
        list: An [Adjacency Matrix](/Adjacency_Matrix) as a 2D list.
    """
    n = len(graph)
    adj_matrix = [[0 for _ in range(n)] for _ in range(n)]

    # Populate the [Adjacency Matrix](/Adjacency_Matrix)
    for i in range(n):
        for j in range(n):
            if graph[i].get(j, None) is not None:
                adj_matrix[i][j] = 1

    return adj_matrix


# Example usage:
graph = {
    'A': {'B': True, 'C': False},
    'B': {'A': True, 'D': True},
    'C': {'A': False, 'D': True},
    'D': {'B': True, 'C': False}
}

adj_matrix = create_adjacency_matrix(graph)

print(adj_matrix)

Advantages

• The Adjacency Matrix provides a compact representation of the graph, making it efficient for large graphs.
• It is widely used in graph Algorithms and Network Analysis.

Disadvantages

• The Adjacency Matrix can be difficult to interpret, especially for complex graphs with many edges.
• It may require manual calculation or conversion to other representations (e.g., adjacency lists).