Community Detection with Node2Vec
Build a Community Detection Pipeline in Python using Node2Vec & Clustering Models
This article will be a tutorial on how to identify communities within a network using node2vec and clustering models. The following highlights the structure of the article :
Table of Contents
- What is Community Detection? - Community Detection & Clustering
- Problem Statement
- Solution Architecture - Requirements
- Synthesize Network
- Apply Node2Vec
- Apply Spectral Clustering
- Identify Communities
- Concluding Remarks
- Resources
What is Community Detection?
In graph theory, a network has a community structure if you are able to group nodes (with potentially overlapping nodes) based on the node’s edge density. This would imply that the original network G, can be naturally divided into multiple subgraphs/communities where the edge connectivity within the community would be very dense. Overlapping communities are also allowed, so there can be overlapping nodes in the communities formed. This implies that nodes in separate communities have a sparse amount of edges.
The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. [1] — https://en.wikipedia.org/wiki/Community_structure
Thinking of this intuitively, it makes sense. Consider yourself in your own social networks like Instagram. You might be highly connected to many different communities related to things you’re interested in. You could have a follow / following of accounts associated with friends, memes, sports, anime, etc. Each of those categorizations could be interpreted as communities, where you as a user are a node and the edges are generated by connecting you to other users who have similar interests as yourself. Thus, within your own social network, you would have a very dense community and would be sparsely connected to other individuals outside of your community.
There are many mathematical formulations for identifying communities within a given network. Algorithms such as the Louvain, Girvan-Newman, Jaccard score, etc. All of which can be applied on a network to solve problems in community detection.
Community Detection & Clustering
There is a gray area indicating the difference between community detection and clustering, many consider them to be the same. One distinction would be that community detection refers to generating groups of nodes based on the network structure, whereas clustering focuses on generating groups based on many attributes associated with the input data. Although we’re going to use clustering models in this article, I’m referring to the approach to be more along the community detection side. This is because we’re also going to be using node2vec to generate the input embedding vectors associated with each node. Node2Vec will be the secret sauce for making this work, this algorithm aims to generate embeddings for each node while preserving the initial structure of the graph. For more information regarding Node2Vec you can refer to this article.
Problem Statement
Given a network, create a pipeline that will segment the initial network into its associated communities.
Solution Architecture
Given some tabular input data (which we will synthesize), we will begin by creating a network. Upon creating the network, we can run node2vec on it to generate node embeddings associated with each node. The embedding vectors can be passed to a clustering algorithm like Spectral Clustering to segment each node into communities.
Requirements
Python=3.8.8
networkx=2.5
pandas=1.2.4
numpy=1.20.1
node2vec=0.4.4
sklearn=0.24.1
matplotlib=3.3.4If you don’t have the node2vec package installed, here is the library documentation to install it through the command line.
Create Network
The script above will generate a random graph for us to use node2vec and later spectral clustering on. The user will specify the number of nodes and the degree distribution they want for the randomly generated network. The network will be generated through the configuration model. The configuration model essentially generates a random graph by assigning edges to match a degree sequence. Do note that since this is random, the resulting network will be different each time. Furthermore, this is just an example network to run node2vec on, just because the resulting network is a multi-graph doesn’t mean that node2vec can only run on other multi-graphs. Node2Vec can be run on directed, undirected, weighted, multi, or regular networks. When I ran the function above for n = 150 the following are the stats associated with the resulting graph.
You usually don’t want to visualize the network, especially if it's a large network. The amount of time and computing power it takes to render edges associated with networks that have 100s of thousands of edges is immense. I only visualized this so that the reader can have a visual understanding of how the nodes change color when they’re assigned to a community later on in the article.
Apply Node2Vec
Apply Spectral Clustering
For this tutorial, I’ve shown how to use the spectral clustering [2] model through sklearn. This can easily be replaced with other clustering algorithms like K-means, agglomerative clustering, etc. Because we’re currently working with synthesized data for the purposes of a tutorial, I won’t go much into detail about community evaluation or choosing the optimal number of communities. Traditional metrics in clustering evaluation like the silhouette score, elbow method, etc. can be easily applied to this scenario.
Identify Communities
Now that we’ve identified which cluster each node belongs to, we can map each cluster to color and map the colors back to our original network. This will allow us to see the network based on the communities each node belongs to.
Concluding Remarks
To recap, you can build a community detection pipeline using node2vec on networks. To do this, simply apply the node2vec algorithm on a network of your choice and then use a clustering algorithm to map the nodes into different clusters/communities. This approach works intuitively because Node2Vec aims to preserve the network structure when generating the embeddings space. Do be aware, that if you pass in an incomplete network, then the resulting communities detected might be misleading. An incomplete network is one when you create a network based on partial observations. Without a network that has all observed results, the communities generated from it can be misleading.
This concludes the overview of how to implement community detection pipelines in Python using Node2Vec. Feel free to follow along with the code in the Jupyter Notebook which you can find on my GitHub.
If you’re looking to transition into the data industry and want mentorship and guidance from seasoned mentors then you might want to check out Sharpest Minds. Sharpest Minds is a mentorship platform where mentors (who are seasoned practicing data scientists, machine learning engineers, research scientists, CTO, etc.) would aid in your development and learning to land a job in data. Check them out here.
Resources
- [1] https://en.wikipedia.org/wiki/Community_structure
- [2] https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html
If you enjoyed reading this article, here are a few others that I’ve written that you might also enjoy.
