A Tutorial on NetworkX: Network Analysis in Python (Part-III) (2024)

A Tutorial on NetworkX: Network Analysis in Python (Part-III) (1)

In this tutorial, we will cover four graph algorithms in NetworkX: Bellman-Ford Algorithm, Girvan-Newman Algorithm, Louvain Algorithm, and Label Propagation Algorithm.

Part-I and Part-II of this tutorial series are available on the following links:

A Tutorial on NetworkX: Network Analysis in Python (Part-I) In this tutorial, we will learn about the NetworkX package of Python. NetworkX stands for network analysis in Python… medium.com

Interested readers can also read the following introductory tutorial which discusses in detail the basics of graph analysis in Python:

Now, we will start discussing the four graph algorithms supported by NetworkX.

The Bellman-Ford algorithm is a shortest-path algorithm that is used to find the shortest path between two nodes in a weighted graph. In NetworkX, we can use the bellman_ford_path() function to find the shortest path between two nodes using the Bellman-Ford algorithm.

Here’s an example of how to use the Bellman-Ford algorithm to find the shortest path between two nodes in a graph. To get started, we first need to create a weighted graph. In NetworkX, we can create a graph using the Graph() function. We can then add nodes to the graph using the add_node() function, and edges using the add_edge() function. Here’s an example of how to create a simple undirected graph with 10 nodes and 27 edges with weights:

import networkx as nx# create a graph object G2G2 = nx.Graph()# add nodes to the graph G2 G2.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])# add edges to the graph G2 G2.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (1, 4, 1), (2, 4, 2), (2, 5, 1), (2, 8, 2), (3, 6, 3), (3, 7, 2), (3, 10, 2), (4, 5, 1), (4, 8, 3), (4, 9, 3), (5, 3, 2), (5, 6, 2), (5, 9, 4), (6, 1, 4), (6, 7, 2), (6, 8, 2), (7, 2, 3), (7, 4, 1), (7, 10, 3), (8, 7, 2), (8, 9, 1), (9, 1, 3), (9, 2, 2), (10, 2, 1), (10, 6, 2) ])

We can visualize the above graph G2 using the following code:

import matplotlib.pyplot as pltpos= nx.circular_layout(G2)nx.draw(G2, pos, with_labels=True, font_weight='bold') edge_weight = nx.get_edge_attributes(G2,'weight')nx.draw_networkx_edge_labels(G2, pos, edge_labels = edge_weight)plt.show(G2) 

This will produce the following graph:

A Tutorial on NetworkX: Network Analysis in Python (Part-III) (2)

In NetworkX, we can use the bellman_ford_path() function to find the shortest path between two nodes using the Bellman-Ford algorithm.

# find the shortest path between nodes 1 and 7 using the Bellman-Ford algorithmshortest_path = nx.bellman_ford_path(G2, 1, 7)# print the shortest pathprint(shortest_path) 

This will produce the following output:

[1, 4, 7]

The Girvan-Newman algorithm is a community detection algorithm that works by iteratively removing edges from a graph until the graph is split into multiple connected components. At each step, the algorithm calculates the betweenness centrality of each edge in the graph, which measures how often an edge appears on the shortest path between any two nodes. The edge with the highest betweenness centrality is removed, and the process is repeated until the graph is split into multiple connected components.

Here, we use the Karate club graph that can be generated using the following code:

The above code snippet creates a NetworkX graph object called G3 representing the famous "karate club" social network. The karate club graph is a small, undirected graph that represents the friendships between members of a karate club in the 1970s.

A Tutorial on NetworkX: Network Analysis in Python (Part-III) (3)

To use the Girvan-Newman algorithm in NetworkX, you can call the girvan_newman() function, which takes a graph as input and returns a generator of sets of nodes, where each set represents a community:

communities = nx.algorithms.community.girvan_newman(G3)for community in next(communities): print(community)

The above code snippet applies the Girvan-Newman algorithm to G3, prints out the nodes in the first set of communities generated by the algorithm, and then exits. The Girvan-Newman algorithm is a popular community detection algorithm that can help identify cohesive groups of nodes in a graph based on their connectivity patterns.

The above print statement will generate the following output:

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

The Louvain algorithm is another community detection algorithm that works by optimizing a modularity score, which measures the density of edges within communities relative to the density of edges between communities. The algorithm starts by assigning each node to its own community, and then iteratively merges communities that increase the modularity score. This process is repeated until the modularity score can no longer be improved.

To use the Louvain algorithm in NetworkX, you can call the greedy_modularity_communities() function, which takes a graph as input and returns a list of sets of nodes, where each set represents a community:

communities = nx.algorithms.community.greedy_modularity_communities(G)for community in communities: print(community)

This will produce the following output:

frozenset({32, 33, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31})frozenset({1, 2, 3, 7, 9, 12, 13, 17, 21})frozenset({0, 4, 5, 6, 10, 11, 16, 19})

The Label Propagation algorithm is a community detection algorithm that works by iteratively updating the labels of each node to the label that is most common among its neighbors. The algorithm starts by assigning a unique label to each node, and then iteratively updates the labels until the labels converge.

To use the Label Propagation algorithm in NetworkX, you can call the label_propagation_communities() function, which takes a graph as input and returns a list of sets of nodes, where each set represents a community:

communities = nx.algorithms.community.label_propagation_communities(G)for community in communities: print(community)

The above print statement will produce the following output:

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

By using these community detection algorithms in NetworkX, you can identify groups of nodes that are densely connected and potentially meaningful in the context of your graph. This can be useful for a wide range of applications, from social network analysis to recommendation systems to targeted advertising.

This is the end of Part-III of this tutorial series.

A Tutorial on NetworkX: Network Analysis in Python (Part-III) (2024)
Top Articles
Latest Posts
Recommended Articles
Article information

Author: Annamae Dooley

Last Updated:

Views: 5355

Rating: 4.4 / 5 (65 voted)

Reviews: 80% of readers found this page helpful

Author information

Name: Annamae Dooley

Birthday: 2001-07-26

Address: 9687 Tambra Meadow, Bradleyhaven, TN 53219

Phone: +9316045904039

Job: Future Coordinator

Hobby: Archery, Couponing, Poi, Kite flying, Knitting, Rappelling, Baseball

Introduction: My name is Annamae Dooley, I am a witty, quaint, lovely, clever, rich, sparkling, powerful person who loves writing and wants to share my knowledge and understanding with you.