Implement Louvain Community Detection Algorithm using Python and Gephi with visualization
Louvain Community Detection Algorithm
The Louvain method for community detection is a method to extract communities from large networks created by Blondel et al. from the University of Louvain (the source of this method’s name). The method is a greedy optimization method that appears to run in time O(n log2n) in the number of nodes in the network. You can have access to the paper here.
I’m here to introduce two ways to implement the Louvain community detection algorithm and visualize the clustered graph.
Python Code
import networkx as nx
import community as community_louvain
import matplotlib.pyplot as plt
import matplotlib.cm as cm# define the graph
edge = [(1,2),(1,3),(1,4),(1,5),(1,6),(2,7),(2,8),(2,9)]
G = nx.Graph()
G.add_edges_from(edge)# retrun partition as a dict
partition = community_louvain.best_partition(G)# visualization
pos = nx.spring_layout(G)
cmap = cm.get_cmap('viridis', max(partition.values()) + 1)
nx.draw_networkx_nodes(G, pos, partition.keys(), node_size=100,cmap=cmap, node_color=list(partition.values()))
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.show()
And the results are as follows:
Gephi
Gephi is the leading visualization and exploration software for all kinds of graphs and networks. You can use it on Linux, Windows, macOS.
I’m here to introduce a simple way to import graphs with CSV format, implement the Louvain community detection algorithm, and cluster the nodes. Credit to Gephi tutorials, click to have more details.
Firstly, create a file containing edges of the graph with CSV or excel format.
Secondly, you need to find the Import Spreadsheet button in the Data Laboratory panel. And import this CSV or excel file.
Turn to the Overview panel, you can see the visualization of the graph imported. You can select the proper layout for beautiful visualization.
The ability to detect and study communities is central in network analysis. We would like to colorize clusters in our example. Gephi implements the Louvain method, available from the Statistics panel. Click on Run near the Modularity line.
The community detection algorithm created a “Modularity Class” value for each node. The partition module can use this new data to colorize communities. Locate the Partition module on the left panel. Choose Modularity Class and click Apply.
Then you can see the following clustered graph with corresponding colors.
