Image for post
Image for post
Photo Credit : Community Detection

Demystifying Louvain’s Algorithm and Its implementation in GPU

Abhishek Mishra
Nov 21, 2019 · 10 min read

1. Introduction:

Most of the systems running businesses today can be represented in the form of a network. In this digital age, networks are an appropriate way of representing entities because all the systems today are well connected. Data represented in the form of a network is also known as Graph. Graphs are a much better way of studying multilevel relationships networks in social media, organised crime links, geographical links, etc compared to relational databases which would need a much larger space to store these relationships. Moreover, the computational complexity of searching for the linked entities would also increase due to the redundant storage of linked elements. In this blog, I will try to explain the basic terminologies of Graph Theory and Community Detection using Louvain’s Algorithm in GPU. Happy reading!!

2. Applications of Graphs :

  • Social Media Network: Users are considered as vertices and the friendship between them is treated as an existence of edge between the vertices ( users ). This is useful in friend recommendations.
  • Retail Product Recommendations in Retail: Representing the products as nodes and the volume of purchases in the same invoice as edges can unfold new multilevel relationships between the products. These relationships drive the products recommendation for the customers.
  • Retail Fraud Networks: Analysis of customers using same credit cards, phone numbers, IP Addresses, devices can be done using graphs to identify the frauds related to collusion among customers involved in stock shrinkage, payments fraud, etc.
  • Geographical Maps : Every map application uses graphs to calculate the shortest path between two locations( vertices ) based on the traffic congestion and actual road distance( edges ).
  • Unsupervised Machine Learning algorithms like K-Means clustering stores the elements in the form of graphs for calculating the pair wise distances faster.

3. Graph Terminologies Required For Understanding Louvain’s Algorithm

In this section, I will walk you through the graph terminologies which are pre- requisites for understanding Louvain’s Algorithm.

Image for post
Image for post
Basic Graph Example
Image for post
Image for post
Adjacency Matrix Example
Image for post
Image for post
Community Detection Example

4. Louvain’s Algorithm for Community Detection:

Louvain’s algorithm was proposed by Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte and Etienne Lefebvre in this paper in 2008. It was named after the city in Belgium where one of the proposers Etienne Lefebvre first developed this algorithm during his Master thesis at UCL( Louvain-la-Neuve ) in March,2007.

Image for post
Image for post
Modularity Definition
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Communities Initialisation represented by dotted rings
Image for post
Image for post
Nodes 1 and 2 merged into one community
Image for post
Image for post
Node 3 also got merged with 2 and 3
Image for post
Image for post
Nodes 5 and 7 gets merged into same community and process continues
Image for post
Image for post
Final community assignments for nodes

5. Implementation in GPU

In this section, I will walk you through the implementation steps of Louvain’s Algorithm in CUDA RAPIDS GPU installed on Microsoft Azure.

Image for post
Image for post
Sample Data Used for Implementation
Image for post
Image for post
Intermediate Data after removing character “P” from nodes
Image for post
Image for post
Sample Data with Nodes starting from 0
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Sample data showing communities and its members

6. References:

  1. https://arxiv.org/pdf/0803.0476.pdf
  2. https://docs.rapids.ai/
  3. https://github.com/rapidsai/cudf
  4. https://github.com/rapidsai/cugraph
  5. https://github.com/rapidsai/notebooks/blob/branch-0.11/cugraph/Louvain.ipynb
  6. https://www.researchgate.net/post/Can_anyone_provide_a_short_example_of_how_the_modularity_is_being_calculated_in_networks
  7. https://en.wikipedia.org/wiki/Graph_theory
  8. http://mathworld.wolfram.com/Graph.html
  9. https://azure.microsoft.com/en-us/pricing/details/virtual-machines/series/
  10. https://developer.nvidia.com/how-to-cuda-python
  11. https://blogs.nvidia.com/blog/2019/03/18/cuda-x-ai-microsoft-azure/
  12. https://azure.microsoft.com/en-in/blog/azure-machine-learning-service-now-supports-nvidia-s-rapids/

Walmart Global Tech Blog

We’re powering the next great retail disruption.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store