Navigating Networks with NetworkX: A Quick Information to Graphs in Python | by Diego Penilla | Nov, 2024

In a world brimming with connections — from social media friendships to complicated transportation networks — understanding relationships and patterns is essential to creating sense of the programs round us. Think about visualizing a social community the place every individual is a dot (a “node”) linked to pals by traces (or “edges”). Or image mapping a metropolis’s metro system the place every station is a node and every route is an edge connecting them.

That is the place NetworkX shines, providing a robust technique to construct, analyze, and visualize these intricate webs of relationships.

NetworkX permits us to characterize information in ways in which can be cumbersome and even impractical with conventional tables however turn out to be straightforward and pure in a graph format. Relationships that might take many rows and columns to outline in a spreadsheet could be captured in an intuitive, visible means, serving to us to grasp and interpret complicated information.

The library lets us apply a variety of strategies and algorithms to those graphs, offering recent insights every time as we reframe our information with a brand new method.

Let’s begin out by breaking down what a graph is. In community evaluation, a graph is made up of nodes (or vertices) and edges (or hyperlinks).

• Consider nodes as the principle entities, like individuals or net pages, and edges because the connections between them — like friendships in a social community or hyperlinks between web sites.
• Some edges even carry weights, representing the power, distance, or price of the connection between two nodes. This added layer of data helps us analyze not simply if two nodes are linked, however how strongly or carefully.

These graphs can be utilized to mannequin all kinds of programs, from social networks, to molecules and transportation grids.

Let’s begin by seeing how one can create a graph utilizing networkx. For those who don’t have it put in first run:

$ pip set up networkx

Making a graph

To make a community we’ll:

1. Initialize the community: by making a graph with G = nx.Graph()
2. Add Nodes with Attributes: Use G.add_node() so as to add nodes, every of which may retailer customized attributes like labels or ages.
3. Add Edges: Join nodes with G.add_edge(), the place every edge can embrace a weight attribute to characterize the power or price of the connection.
4. Visualize the Graph: Use Matplotlib features like nx.draw() and nx.draw_networkx_edge_labels() to show the graph, displaying node labels and edge weights for straightforward interpretation.

That is the code to realize this:

import networkx as nx
import matplotlib.pyplot as plt
# Create a easy graph
G = nx.Graph()
# Add nodes with attributes (e.g., 'label' and 'age')
G.add_node(1, label="A", age=25)
G.add_node(2, label="B", age=30)
G.add_node(3, label="C", age=22)
G.add_node(4, label="D", age=28)
# Add weighted edges (node1, node2, weight)
G.add_edge(1, 2, weight=4)
G.add_edge(1, 3, weight=3)
G.add_edge(2, 4, weight=5)
# Retrieve and print node attributes
node_attributes = nx.get_node_attributes(G, 'age')  # Get 'age' attribute for all nodes
print("Node Attributes (Age):", node_attributes)
# Retrieve and print edge attributes
edge_weights = nx.get_edge_attributes(G, 'weight')  # Get 'weight' attribute for all edges
print("Edge Attributes (Weight):", edge_weights)
# Draw the graph with node and edge attributes
pos = nx.spring_layout(G)  # Structure for node positions
node_labels = nx.get_node_attributes(G, 'label')  # Get node labels for visualization
edge_labels = nx.get_edge_attributes(G, 'weight')  # Get edge weights for visualization
plt.determine(figsize=(6, 6))
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=15, font_weight='daring', node_size=500)
# Draw the sting weights and node labels
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("NetworkX Graph with Node and Edge Attributes")
plt.present()

On this instance we initialise the graph after which create:

• 4 nodes (1, 2, 3, 4) by calling G.add_node(node, label, attr)
• 3 weighted edges that join these nodes: (1, 2), (1, 3), and (2, 4) by calling G.add_edge(node1, node2, attr)

Each nodes and edges in NetworkX can maintain extra attributes, making the graph richer with data.

• Node attributes (accessed through nx.get_node_attributes(G, ‘attribute’)) enable every node to retailer information, like an individual’s occupation in a social community.
• Edge attributes (accessed through nx.get_edge_attributes(G, ‘attribute’)) retailer data for every connection, akin to the space or journey time in a transportation community. These attributes add context and depth, enabling extra detailed evaluation of the community.

We then use NetworkX’s spring format pos = nx.spring_layout(G) to place the nodes for visualization, guaranteeing they’re spaced naturally inside the plot. Lastly, nx.draw() and nx.draw_networkx_edge_labels() show the graph with node labels and edge weights, creating a transparent view of the community’s construction and connections.

Whereas this was a relatively easy community, it illustrates the fundamentals of working with networks: to govern graphs we have to deal with the nodes and their connections alongside any attributes they could have.

Karate Membership Community

Some of the well-known examples in community science is the Zachary’s Karate Membership, usually used as an example social community evaluation and group detection. The dataset is public area and is included in networkx by default. You may entry as proven under:

# Load the  Karate Membership
G = nx.karate_club_graph()
# Draw the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Structure for nodes -> treats nodes as repelling objects
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=12, font_weight='daring', node_size=500)
plt.title("Zachary's Karate Membership Community")
plt.present()

This community represents the friendships amongst 34 members of a karate membership, and it’s well-known for the cut up that occurred between two factions, every centered round a central determine — Mr. Hello and Officer.

Let’s check out the attributes contained inside the node information:

# looping over nodes
for node in G.nodes():
print(f"Node: {node}, Node Attributes: {G.nodes[node]}")

Node: 0, Node Attributes: {'membership': 'Mr. Hello'}
Node: 1, Node Attributes: {'membership': 'Mr. Hello'}
Node: 2, Node Attributes: {'membership': 'Mr. Hello'}
Node: 3, Node Attributes: {'membership': 'Mr. Hello'}
Node: 4, Node Attributes: {'membership': 'Mr. Hello'}
Node: 5, Node Attributes: {'membership': 'Mr. Hello'}
Node: 6, Node Attributes: {'membership': 'Mr. Hello'}
Node: 7, Node Attributes: {'membership': 'Mr. Hello'}
Node: 8, Node Attributes: {'membership': 'Mr. Hello'}
Node: 9, Node Attributes: {'membership': 'Officer'}
Node: 10, Node Attributes: {'membership': 'Mr. Hello'}
Node: 11, Node Attributes: {'membership': 'Mr. Hello'}
Node: 12, Node Attributes: {'membership': 'Mr. Hello'}
Node: 13, Node Attributes: {'membership': 'Mr. Hello'}
Node: 14, Node Attributes: {'membership': 'Officer'}
Node: 15, Node Attributes: {'membership': 'Officer'}
Node: 16, Node Attributes: {'membership': 'Mr. Hello'}
Node: 17, Node Attributes: {'membership': 'Mr. Hello'}
Node: 18, Node Attributes: {'membership': 'Officer'}
Node: 19, Node Attributes: {'membership': 'Mr. Hello'}
Node: 20, Node Attributes: {'membership': 'Officer'}
Node: 21, Node Attributes: {'membership': 'Mr. Hello'}
Node: 22, Node Attributes: {'membership': 'Officer'}
Node: 23, Node Attributes: {'membership': 'Officer'}
Node: 24, Node Attributes: {'membership': 'Officer'}
Node: 25, Node Attributes: {'membership': 'Officer'}
Node: 26, Node Attributes: {'membership': 'Officer'}
Node: 27, Node Attributes: {'membership': 'Officer'}
Node: 28, Node Attributes: {'membership': 'Officer'}
Node: 29, Node Attributes: {'membership': 'Officer'}
Node: 30, Node Attributes: {'membership': 'Officer'}
Node: 31, Node Attributes: {'membership': 'Officer'}
Node: 32, Node Attributes: {'membership': 'Officer'}
Node: 33, Node Attributes: {'membership': 'Officer'}

The node attribute membership refers back to the group "Officer" or "Mr. Hello" that every node belongs to. Let’s use them to create coloration the nodes within the graph.

To do that we assign the blue coloration to the nodes with membership label "Mr Hello" and purple these with label "Officer" in an inventory color_map , which we are able to use to visualise the community utilizing nx.draw.

# Load the Karate Membership 
G: nx.Graph = nx.karate_club_graph()
# Get the node labels
labels = nx.get_node_attributes(G, 'membership')
# Map group labels to colours
color_map = []
for node in G.nodes():
if labels[node] == 'Mr. Hello':
# Assign blue coloration for 'Mr. Hello'
color_map.append('blue')  
else:
# Assign purple coloration for 'Officer'
color_map.append('purple')  
# Visualize the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  
nx.draw(G, pos, with_labels=True, node_color=color_map, font_size=12, font_weight='daring', node_size=500, cmap=plt.cm.rainbow)
plt.title("Zachary's Karate Membership Community with Floor Reality Communities")
plt.present()

The legend tells {that a} battle arose between the membership’s teacher, “Mr. Hello,” and the membership’s administrator, “Officer.” This division finally induced the membership to separate into two distinct teams, every centered round one among these leaders.

By representing these relationships as a community, we are able to visually seize this cut up and reveal patterns and clusters inside the information — insights which may be arduous to see having the information in conventional desk codecs.

Centrality

To know the construction and dynamics of a community, it’s important to determine essentially the most influential or strategically positioned nodes. That is the place centrality measures are available in, a key idea in community science.

It measures the place of nodes primarily based on their varieties connections, figuring out key nodes primarily based on sure standards. Widespread measures embrace:

These measures assist reveal key gamers or bottlenecks within the community, giving perception into its construction/dynamic.

import networkx as nx
import matplotlib.pyplot as plt
# Load the Karate Membership 
G = nx.karate_club_graph()
# Compute centrality measures
degree_centrality = nx.degree_centrality(G)
betweenness_centrality = nx.betweenness_centrality(G)
closeness_centrality = nx.closeness_centrality(G)
# prime 5 nodes by centrality for every measure
top_degree_nodes = sorted(degree_centrality, key=degree_centrality.get, reverse=True)[:5]
top_betweenness_nodes = sorted(betweenness_centrality, key=betweenness_centrality.get, reverse=True)[:5]
top_closeness_nodes = sorted(closeness_centrality, key=closeness_centrality.get, reverse=True)[:5]
# prime 5 nodes for every centrality measure
print("High 5 nodes by Diploma Centrality:", top_degree_nodes)
print("High 5 nodes by Betweenness Centrality:", top_betweenness_nodes)
print("High 5 nodes by Closeness Centrality:", top_closeness_nodes)
# prime 5 nodes for Diploma Centrality
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Positioning of nodes
node_color = ['red' if node in top_degree_nodes else 'skyblue' for node in G.nodes()]
# draw prime 5 nodes by diploma centrality
nx.draw(G, pos, with_labels=True, node_color=node_color, font_size=15, font_weight='daring', node_size=500)
plt.title("Karate Membership Community with High 5 Diploma Central Nodes")
plt.present()

High 5 nodes by Diploma Centrality: [33, 0, 32, 2, 1]
High 5 nodes by Betweenness Centrality: [0, 33, 32, 2, 31]
High 5 nodes by Closeness Centrality: [0, 2, 33, 31, 8]

For nodes 0 and 3 we see, that these nodes are essentially the most central within the community, with excessive diploma, betweenness, and closeness centralities.

Their central roles counsel they’re well-connected hubs, regularly appearing as bridges between different members and in a position to shortly attain others within the community. This positioning highlights them as key gamers, holding significance within the community’s circulation and construction.

A group C is a set of nodes (e.g., people in a social community, net pages linked by hyperlinks and so on.) that exhibit stronger connections amongst themselves than with the remainder of the community.

With a visible illustration of centrality in thoughts, let’s apply the Girvan-Newman Algorithm to this graph.

• The algorithm generates a collection of group splits because it progressively removes edges with the very best betweenness centrality.
• The primary time the algorithm is run, it identifies essentially the most vital group division.

from networkx.algorithms.group import girvan_newman
# Load the Karate Membership graph
G = nx.karate_club_graph()
# Apply Girvan-Newman group detection
comp = girvan_newman(G)
first_level_communities = subsequent(comp)
# Visualize the primary degree of communities
pos = nx.spring_layout(G)
plt.determine(figsize=(8, 8))
# Colour nodes by their group
node_colors = ['skyblue' if node in first_level_communities[0] else 'orange' for node in G.nodes()]
nx.draw(G, pos, with_labels=True, node_color=node_colors, font_size=12, node_size=500)
plt.title("Karate Membership Community with Girvan-Newman Communities")
plt.present()
print("Detected Communities:", first_level_communities)

• Since girvan_newman(G) returns an iterator as comp, calling subsequent(comp) permits you to retrieve the primary cut up, i.e., the primary division of the community into two communities.

Let’s examine the detected communities with the precise node label membership

print("Detected Communities:", first_level_communities)
# Print the precise communities (floor reality)
print("nActual Communities (Floor Reality):")
mr_hi_nodes = [node for node, label in labels.items() if label == 'Mr. Hi']
officer_nodes = [node for node, label in labels.items() if label == 'Officer']
print(f"Mr. Hello's Neighborhood: {mr_hi_nodes}")
print(f"Officer's Neighborhood: {officer_nodes}")

Detected Communities: (
{0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21}, 
{2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
)
Precise Communities (Floor Reality):
Mr. Hello's Neighborhood: [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 16, 17, 19, 21]
Officer's Neighborhood: [9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]

The communities detected by the Girvan-Newman algorithm are just like the precise Mr. Hello and Officer communities however not an actual match. It’s because the Girvan-Newman algorithm divides the community primarily based solely on edge betweenness centrality, with out counting on any predefined group labels.

This method is particularly helpful in unstructured datasets the place labels are absent, because it reveals significant groupings primarily based on the community’s structural properties. This highlights a key consideration in group detection: there is no such thing as a strict definition of what constitutes a group.

Consequently, there is no such thing as a single “appropriate” technique to partition a community. Totally different strategies, pushed by various metrics, can yield numerous outcomes, every offering beneficial insights relying on the context.

Cliques

A helpful idea in networks is the clique. In community science, a clique refers to a subset of nodes in a graph the place each node is linked to each different node in that subset. Because of this all members of a clique have direct relationships with one another, forming a tightly-knit group. Cliques could be significantly helpful when finding out the construction of complicated networks as a result of they usually characterize extremely linked or cohesive teams inside a bigger system.

For instance in:

• In social Networks: cliques can characterize teams of people that know one another, akin to close-knit circles of pals or skilled colleagues.
• In collaborative Networks: In a collaborative community (e.g., analysis collaborations), cliques can reveal groups of researchers who work collectively on the identical matters or initiatives.
• In organic Networks: In organic networks, cliques can point out useful teams of proteins or genes that work together carefully inside a organic course of.

Let’s discover the most important clique within the karate community. We are going to discover the most important group of those that have all hyperlinks with one another.

import networkx as nx
import matplotlib.pyplot as plt
# Load the Karate Membership graph
G = nx.karate_club_graph()
# Discover all cliques within the Karate Membership community
cliques = listing(nx.find_cliques(G))
# Discover the most important clique (the one with essentially the most nodes)
largest_clique = max(cliques, key=len)
# Print the most important clique
print("Largest Clique:", largest_clique)
# Visualize the graph with the most important clique highlighted
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Structure for node positions
nx.draw(G, pos, with_labels=True, node_color='skyblue', font_size=12, node_size=500)
# Spotlight the nodes within the largest clique
nx.draw_networkx_nodes(G, pos, nodelist=largest_clique, node_color='orange', node_size=500)
plt.title("Karate Membership Community with Largest Clique Highlighted")
plt.present()

Regardless of the challenges in defining “group” in community science, cliques provide a concrete and well-defined idea for figuring out teams which can be totally interconnected, providing significant insights into each structured and unstructured networks.

Shortest Path

One other attention-grabbing idea in community science is Shortest Path. The shortest path between two nodes in a graph refers back to the sequence of edges that connects the nodes whereas minimizing the overall distance or price, which could be interpreted in numerous methods relying on the appliance. This idea performs an important function in fields like routing algorithms, community design, transportation planning, and even social community evaluation.

NetworkX supplies a number of algorithms to compute shortest paths, akin to Dijkstra’s Algorithm for weighted graphs and Breadth-First Search (BFS) for unweighted graphs.

Let’s check out an instance, we’ll create an artificial dataset the place nodes characterize stations and the sides connections between the stations.

• We will even add weighted edge time, representing the time it takes to achieve from one station to the following.

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
# Simulate loading a CSV file (actual instance would load an precise CSV file)
# Outline a extra intensive set of stations and journey occasions between them
information = {
'station_id': ['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'E', 'E', 'F', 'F', 'G', 'G', 'H'],
'connected_station': ['B', 'C', 'A', 'C', 'A', 'D', 'C', 'E', 'B', 'F', 'D', 'G', 'E', 'H', 'F'],
'time': [10, 20, 10, 15, 20, 10, 5, 15, 10, 25, 10, 5, 15, 10, 30]  # Journey occasions in minutes
}
# Create a DataFrame
df = pd.DataFrame(information)
# Create a graph from the DataFrame
G = nx.Graph()
# Add edges to the graph (station connections with weights as journey occasions)
for index, row in df.iterrows():
G.add_edge(row['station_id'], row['connected_station'], weight=row['time'])
# Draw the graph
plt.determine(figsize=(8, 8))
pos = nx.spring_layout(G)  # Structure for node positions
nx.draw(G, pos, with_labels=True, node_size=500, node_color='skyblue', font_size=12, font_weight='daring')
# Draw edge weights (journey occasions)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("Expanded Transportation Community with Journey Instances")
plt.present()

On this instance we use Dijkstra’s algorithm to compute the shortest path from station A to station H, the place the sting weights characterize journey occasions. The shortest path and its whole journey time are printed, and the trail is highlighted in purple on the graph for visualization, with edge weights proven to point journey occasions between stations.

# Compute the shortest path utilizing Dijkstra's algorithm (contemplating the journey time as weight)
supply = 'A'
goal = 'H'
shortest_path = nx.shortest_path(G, supply=supply, goal=goal, weight='weight')
path_length = nx.shortest_path_length(G, supply=supply, goal=goal, weight='weight')
# Print the shortest path and its size
print(f"Shortest path from {supply} to {goal}: {shortest_path}")
print(f"Whole journey time from {supply} to {goal}: {path_length} minutes")
# Visualize the shortest path on the graph
plt.determine(figsize=(8, 8))
nx.draw(G, pos, with_labels=True, node_size=500, node_color='skyblue', font_size=12, font_weight='daring')
# Spotlight the shortest path in purple
edges_in_path = [(shortest_path[i], shortest_path[i + 1]) for i in vary(len(shortest_path) - 1)]
nx.draw_networkx_edges(G, pos, edgelist=edges_in_path, edge_color='purple', width=2)
# Draw edge weights (journey occasions)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title(f"Shortest Path from {supply} to {goal} with Journey Time {path_length} minutes")
plt.present()

Shortest path from A to H: ['A', 'B', 'E', 'G', 'H']
Whole journey time from A to H: 45 minutes

The algorithm calculates each the shortest route and its whole journey time, that are then displayed. The shortest path between A and H is highlighted in purple on the graph , with edge weights displaying the time between every linked station, including to a complete of 45.

Whereas this was a easy computation, shortest path algorithms have broad functions. In transportation, they optimize routes and cut back journey time; in digital communication, they route information effectively. They’re important in logistics to attenuate prices, in provide chains for well timed deliveries, and in social networks to gauge closeness between people. Understanding shortest paths permits data-driven choices throughout fields — from city planning to community infrastructure — making it a significant instrument for navigating complicated programs effectively.

Thanks for studying

We’ve explored a number of elementary ideas in Community Science utilizing NetworkX, akin to shortest path algorithms, group detection, and the facility of graph principle to mannequin and analyze complicated programs.

If you wish to proceed studying, I’ve positioned a few hyperlinks under :). In case you wish to go deeper on group detection algorithms have a look to the CDLib library.

1. Networkx Tutorial
2. CDLib, a library for group detection

NOTE: Computing superior metrics and measures on graphs can usually be ambiguous and even deceptive. With so many potential metrics out there, it’s straightforward to generate numbers that will not maintain significant worth or could misrepresent the community’s true construction. Choosing the proper metrics requires cautious consideration, as not all measures will present related insights for each kind of community evaluation. If this resonates, take a look right here for extra data: statistical inference hyperlinks information and principle in community science

References