Demystifying Graphs: A Beginner’s Guide to Network Analysis in Python#

Nodes and Edges#

• Nodes (also referred to as vertices): The individual entities you want to represent (people, computers, airports, etc.).
• Edges: The links or connections between those entities (friendship relations, network cables, flight routes).

Directed vs. Undirected Graphs#

• Undirected Graph: Edges have no inherent direction. If A is connected to B, B is automatically connected to A.
• Directed Graph (a digraph): Each edge has a direction. If there is an edge from A to B, it doesn’t necessarily imply an edge from B to A.

Weighted vs. Unweighted#

• Unweighted Graph: Edges simply exist or do not exist.
• Weighted Graph: Each edge has an associated weight (e.g., distance, cost, capacity), reflecting the “strength�?of the relationship.

Subgraphs#

Sometimes you only want to analyze a portion of a bigger graph. A subgraph is a graph formed from a selection of vertices and edges from a larger graph.

Adjacency Matrix#

An adjacency matrix is a 2D array (or list of lists in Python) that describes whether a pair of vertices is connected. If a graph G has n vertices, an adjacency matrix is an n × n matrix M where each entry M[i][j] represents whether there is an edge from vertex i to vertex j.

• For an unweighted undirected graph:
  M[i][j] = 1 if there is an edge between i and j, else 0.
• For a weighted undirected graph:
  M[i][j] = weight of the edge between i and j, else 0 (or �?if no edge).
• For a directed graph:
  M[i][j] may differ from M[j][i] as directions matter.

Adjacency List#

An adjacency list is a dictionary (or list) where each node stores a list (or set) of its neighbors. For example:

1
{
2
    'A': ['B', 'C'],
3
    'B': ['C'],
4
    'C': []
5
}

indicates that A connects to B and C, B connects to C, and C has no outgoing edges.

Comparison Table#

Below is a quick reference for deciding which structure is best for your particular project:

For most practical situations (especially when dealing with real-world networks), adjacency lists tend to be more popular, given that most real networks are relatively sparse.

Creating a Graph#

1
import networkx as nx
2
import matplotlib.pyplot as plt
3

4
# Create an empty undirected graph
5
G = nx.Graph()
6

7
# Add nodes
8
G.add_node("Alice")
9
G.add_node("Bob")
10
G.add_node("Carol")
11

12
# Add edges
13
G.add_edge("Alice", "Bob")
14
G.add_edge("Bob", "Carol")
15
G.add_edge("Alice", "Carol")

Visualizing a Graph#

1
# Draw the graph
2
nx.draw(G, with_labels=True, node_color='lightblue', font_weight='bold')
3

4
# Display the graph
5
plt.show()

You should see a triangle connecting Alice, Bob, and Carol. To customize further, you can manipulate node sizes, colors, edge styles, layouts, and more.

Common Graph Methods#

• G.nodes(): Returns a list-like structure of all nodes in the graph.
• G.edges(): Returns all edges in the graph as (node1, node2) pairs.
• G.degree(node): Returns the degree (number of connections) of a specific node.
• G.remove_node(node): Removes a particular node.
• G.remove_edge(u, v): Removes the edge from u to v.

Depth-First Search (DFS)#

DFS starts at a designated root node (or an arbitrary node if no root is specified) and explores as far as possible along each branch before backtracking.

Pseudocode:

1
DFS(graph, start):
2
    mark start as visited
3
    for each neighbor of start:
4
        if neighbor is not visited:
5
            DFS(graph, neighbor)

1
def dfs_recursive(graph, node, visited=None):
2
    if visited is None:
3
        visited = set()
4

5
    visited.add(node)
6
    print(node)  # or store it, process it, etc.
7

8
    for neighbor in graph[node]:
9
        if neighbor not in visited:
10
            dfs_recursive(graph, neighbor, visited)
11

12
# Example adjacency list:
13
graph_example = {
14
    "A": ["B", "C"],
15
    "B": ["D", "E"],
16
    "C": ["F"],
17
    "D": [],
18
    "E": ["F"],
19
    "F": []
20
}
21

22
dfs_recursive(graph_example, "A")

Breadth-First Search (BFS)#

BFS explores the graph level by level, starting from a source node. It visits all neighbors of the source first, then moves on to the neighbors of those neighbors, and so on.

Pseudocode:

1
BFS(graph, start):
2
    create a queue
3
    enqueue start
4
    mark start as visited
5
    while queue is not empty:
6
        node = dequeue
7
        process node
8
        for each neighbor of node:
9
            if neighbor is not visited:
10
                mark neighbor as visited
11
                enqueue neighbor

1
from collections import deque
2

3
def bfs(graph, start):
4
    visited = set()
5
    queue = deque([start])
6
    visited.add(start)
7

8
    while queue:
9
        node = queue.popleft()
10
        print(node)  # or store/process
11

12
        for neighbor in graph[node]:
13
            if neighbor not in visited:
14
                visited.add(neighbor)
15
                queue.append(neighbor)
16

17
# Using the same graph_example as above
18
graph_example = {
19
    "A": ["B", "C"],
20
    "B": ["D", "E"],
21
    "C": ["F"],
22
    "D": [],
23
    "E": ["F"],
24
    "F": []
25
}
26

27
bfs(graph_example, "A")

Degree Centrality#

This is the simplest measure, defined as the number of edges connected to a node. In NetworkX:

1
import networkx as nx
2

3
G = nx.Graph()
4
G.add_edges_from([
5
    ("A", "B"), ("A", "C"), ("B", "C"),
6
    ("C", "D"), ("D", "E")
7
])
8

9
degree_centrality = nx.degree_centrality(G)
10
print(degree_centrality)
11
# e.g. {'A': 0.666..., 'B': 0.666..., 'C': 1.0, 'D': 0.666..., 'E': 0.333...}

Because there are 5 nodes, the maximum possible degree centrality in this case is 1.0 (for node C).

Betweenness Centrality#

A node with high betweenness centrality lies on many shortest paths between other nodes. It often represents a “bridge�?or “connector�?in a network.

1
betweenness_centrality = nx.betweenness_centrality(G)
2
print(betweenness_centrality)
3
# For the above G, 'C' likely scores highest because it connects A/B with D/E

Closeness Centrality#

Closeness centrality measures how close a node is to all other nodes in the network—often used to identify nodes that can quickly interact with all others.

1
closeness_centrality = nx.closeness_centrality(G)
2
print(closeness_centrality)

Eigenvector Centrality#

Eigenvector centrality goes beyond immediate neighbors, implying that a node is important if it is connected to other important nodes. This measure underlies Google’s PageRank algorithm.

1
eigenvector_centrality = nx.eigenvector_centrality(G)
2
print(eigenvector_centrality)

Each centrality measure offers a unique lens through which to interpret a network, so the choice often depends on the kind of importance you need to capture.

Why Detect Communities?#

• Social Networks: To find groups of friends.
• Biological Networks: To isolate functional modules of genes or proteins.
• Marketing: Identify clusters of customers who share similar consumer behaviors.

Modularity#

One popular method is to maximize a metric called modularity, which measures how well a division of a network into modular groups captures the density of edges within communities relative to edges between communities.

While NetworkX doesn’t provide a built-in high-level function for community detection in simple calls, you can use:

1
import networkx as nx
2
from networkx.algorithms import community
3

4
G = nx.karate_club_graph()  # a famous test graph
5
communities_generator = community.greedy_modularity_communities(G)
6
for c in communities_generator:
7
    print(c)

Here, community.greedy_modularity_communities(G) uses a greedy algorithm to find communities that (locally) maximize modularity. In real applications, you might explore other algorithms too, such as the Louvain algorithm (available in external libraries like python-louvain).

Step 1: Load and Build the Graph#

1
import csv
2
import networkx as nx
3
import matplotlib.pyplot as plt
4

5
def build_graph_from_csv(csv_path):
6
    G = nx.Graph()
7
    with open(csv_path, 'r', newline='', encoding='utf-8') as f:
8
        reader = csv.DictReader(f)
9
        for row in reader:
10
            source = row['Source']
11
            target = row['Target']
12
            G.add_node(source)
13
            G.add_node(target)
14
            G.add_edge(source, target)
15
    return G
16

17
# Example usage
18
G = build_graph_from_csv('edges.csv')

Step 2: Basic Analysis#

1
print("Number of nodes:", G.number_of_nodes())
2
print("Number of edges:", G.number_of_edges())
3

4
# Largest connected component
5
connected_components = nx.connected_components(G)
6
largest_cc = max(connected_components, key=len)
7
H = G.subgraph(largest_cc)
8

9
print("Number of nodes in largest connected component:", H.number_of_nodes())

Step 3: Centrality#

1
deg_centrality = nx.degree_centrality(G)
2
print("Top 5 nodes by degree centrality:")
3
sorted_deg = sorted(deg_centrality.items(), key=lambda x: x[1], reverse=True)
4
for node, cent in sorted_deg[:5]:
5
    print(node, cent)

Step 4: Visualization#

1
pos = nx.spring_layout(H, seed=42)
2
nx.draw(H, pos, with_labels=True, node_color='lightgreen', edge_color='gray')
3
plt.show()

1. Weighted Edges#

If you have weighted relationships (e.g., distances or interactions), NetworkX allows you to store weights:

1
G = nx.Graph()
2
G.add_edge("A", "B", weight=5)
3
G.add_edge("A", "C", weight=3)
4
G.add_edge("B", "C", weight=1)
5

6
# Retrieve weight
7
print(G["A"]["B"]["weight"])  # 5

Popular algorithms like Dijkstra’s shortest path will use these weights if available.

2. Multigraphs#

A multigraph can have multiple edges between the same pair of nodes. You might use this to model parallel or repeated interactions.

1
M = nx.MultiGraph()
2
M.add_edge("A", "B", relationship="friend")
3
M.add_edge("A", "B", relationship="colleague")

3. Directed Graphs#

For scenarios where direction matters—like hyperlink structures, one-way routes, or supply chains—you can use:

1
DG = nx.DiGraph()
2
DG.add_edge("A", "B")

Centrality algorithms or traversal can behave differently in directed graphs.

4. Bipartite Graphs#

A bipartite graph is one where nodes can be divided into two disjoint sets, such that edges only connect nodes from different sets. This is common in recommendation systems (e.g., users vs. products). NetworkX supports bipartite-specific algorithms:

1
from networkx.algorithms import bipartite
2

3
B = nx.Graph()
4
# Add nodes with bipartite sets indicated
5
B.add_nodes_from(["u1", "u2"], bipartite=0)  # user set
6
B.add_nodes_from(["p1", "p2"], bipartite=1)  # product set
7

8
# Add edges linking users to products
9
B.add_edge("u1", "p1")
10
B.add_edge("u2", "p1")
11
B.add_edge("u2", "p2")
12

13
# Check if bipartite
14
print(bipartite.is_bipartite(B))  # True or False

5. Community Detection in Weighted or Directed Graphs#

Community detection algorithms can also be adapted to weighted and directed graphs, but each approach might have different assumptions. The Louvain method can handle weighted graphs, and other specialized methods exist for directed cases.

1. Memory Considerations#

• Use adjacency lists for large sparse networks to avoid excessive memory usage.
• Look out for overhead when storing complex attributes with each edge or node.

2. Algorithmic Complexity#

• BFS and DFS both run in O(V + E) (where V = # of nodes, E = # of edges).
• More advanced algorithms like betweenness centrality can be more expensive (O(V * E)), so plan your computational resources appropriately if your network has millions of nodes.

3. Parallelization#

If you need to analyze extremely large graphs, consider methods to parallelize your computations. Libraries such as igraph or frameworks like Apache Spark’s GraphX might help with distributed processing.

4. Data Preprocessing#

Dealing with messy real-world data often involves cleaning, normalizing, and sometimes deduplicating edges or nodes before you even start analyzing.

5. Visualization Techniques#

For smaller graphs, NetworkX’s built-in visualization is enough. For bigger networks, consider specialized tools like Gephi, Cytoscape, or D3.js for interactive and more performant rendering.