# Demystifying Louvain’s Algorithm and Its implementation in GPU

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.

# 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.

# 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.

Written by

Written by