Network Analysis Fundamentals

Introduction

Network analysis is a useful tool for statisticians and data scientists who want to explore relationships and interactions within data. From social networks to transportation systems and biological pathways, network analysis provides a structured approach to studying these interconnected systems.

This tutorial covers the fundamentals of network analysis, focusing on core concepts and practical implementation using Python.

Key Concepts of Network Analysis

Graph Basics

A graph is a collection of nodes — also referred to as vertices — which are connected to one another by edges. Graphs can be directed — in which the edges have direction — or they can be undirected — in which the edges do not have direction. Edges can optionally be weighted, representing the strength or capacity of the connection.

Types of Graphs

A simple graph contains no loops or multiple edges. A multigraph allows multiple edges between nodes. In a bipartite graph, nodes are divided into two disjoint sets, and edges only connect nodes from different sets.

Important Metrics

Degree: Number of connections a node has
Path: Sequence of nodes connected by edges
Centrality: Measures the importance of a node within the network
- Degree Centrality: Based on the number of connections
- Betweenness Centrality: Based on the number of shortest paths passing through a node
- Closeness Centrality: Inverse of the sum of distances to all other nodes
Clustering Coefficient: Measures how interconnected a node’s neighbors are

Getting Started with Python for Network Analysis

In this article, we will use the popular networkx library for introductory network analysis, a Python tool for creating, analyzing, and visualizing graphs.

First, we install the library using pip:

pip install networkx

Then we can create a graph:

import networkx as nx
import matplotlib.pyplot as plt

# Create an undirected graph (G is often used by convention)
G = nx.Graph()

# Add nodes
G.add_nodes_from([1, 2, 3, 4])

# Add edges
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])

# Visualize the graph
nx.draw(G, with_labels=True, node_color='lightblue', edge_color='gray')
plt.show()

Calculating Basic Metrics

As we revisit our key concepts from above, let’s look at how to calculate some of those metrics. The first is degree centrality. Degree centrality measures how many direct connections a node has relative to the most possible connections in the network. It reflects the influence or activity of a node, with higher centrality indicating more immediate ties to other nodes.

degree_centrality = nx.degree_centrality(G)
print("Degree Centrality:", degree_centrality)

Degree Centrality: {1: 1.0, 2: 0.6666666666666666, 3: 1.0, 4: 0.6666666666666666}

In the above degree centrality values, nodes 1 and 3 each have a centrality of 1.0, meaning they are maximally connected within this network, while nodes 2 and 4 have a centrality of approximately 0.67, indicating they have fewer direct connections compared to nodes 1 and 3.

Next, we look at betweenness centrality. Betweenness centrality quantifies how often a node lies on the shortest paths between other nodes in the network. It highlights nodes that serve as bridges or critical connectors, with higher values indicating greater control over information flow or connectivity.

betweenness_centrality = nx.betweenness_centrality(G)
print("Betweenness Centrality:", betweenness_centrality)

Betweenness Centrality: {1: 0.16666666666666666, 2: 0.0, 3: 0.16666666666666666, 4: 0.0}

Given the above betweenness centrality values, nodes 1 and 3 have moderate roles (≈0.167 each) as intermediaries on some shortest paths between other nodes, while nodes 2 and 4 do not serve as bridges in this network.

And finally, lets have a look at our graph’s clustering coefficient. Clustering coefficient measures how close a node’s neighbors are to being a complete clique, meaning how likely it is that two neighbors of a node are also directly connected. A higher clustering coefficient indicates a tightly knit neighborhood around that node.

clustering_coeff = nx.clustering(G)
print("Clustering Coefficient:", clustering_coeff)

Clustering Coefficient: {1: 0.6666666666666666, 2: 1.0, 3: 0.6666666666666666, 4: 1.0}

Given the above output, nodes 2 and 4 each have a clustering coefficient of 1.0, meaning all of their neighbors are interconnected, while nodes 1 and 3 have a coefficient of approximately 0.667, indicating that most—but not all—of their neighbors form connections with each other.

Graph Analysis

Let’s preform shortest path analysis, from node 1 to node 4. The shortest path is self-explanatory, and exactly what you think it is.

# Shortest path between two nodes
shortest_path = nx.shortest_path(G, source=1, target=4)
print("Shortest Path from 1 to 4:", shortest_path)

Shortest Path from 1 to 4: [1, 4]

The shortest path from node 2 to node 4 in our graph is the connection between nodes 1 and 4, unsurprisingly.

Now let’s visualize the graph with attributes. Here we have our graph visualized with some weights we have added to a pair of edges.

# Adding edge weights
G.add_edge(1, 2, weight=4)
G.add_edge(3, 4, weight=2)

# Draw graph with weights
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()

Finally, let’s perform community detection analysis on the graph. Greedy modularity communities is a method for detecting communities in a network by greedily optimizing the modularity score, which measures the density of connections inside communities compared to connections between communities. It starts with each node as its own community and iteratively merges communities that result in the greatest increase in overall modularity until no further improvement is possible.

from networkx.algorithms.community import greedy_modularity_communities

# Detect communities
communities = list(greedy_modularity_communities(G))
print("Communities:", communities)

Communities: [frozenset({1, 2, 3, 4})]

The above output indicates that all nodes in the network belong to a single community. This suggests that the network is highly interconnected without distinct clusters or sub-groups separating it into smaller communities.

Conclusion

Network analysis is a versatile and powerful set of tools and techniques used for analyzing relationships and interactions within data that can be modeled as a graph. Using a library such as networkx, you can model complex systems, calculate important metrics, and uncover insights that might not be evident otherwise. By mastering these fundamentals, you are well on your way to tackling advanced network analysis challenges.