Louvain clustering is an algorithm for community detection that serves as an unsupervised, agglomerative, bottom-up clustering method for undirected graphs.
It was developed at Belgium’s University of Louvain, and it is designed to sort unstructured data into the most efficient groups so that it can be analyzed. It does this by analyzing the density of nodes using a recursive process that, by ranking the results of similarity computations, groups the nodes into clusters. Small communities are detected first by optimizing modularity locally on all nodes, after which the small communities are each grouped into one node and the first step is repeated.
Louvain is an unsupervised algorithm. It does not require specification of the number of communities to detect or the expected community size for calculation.
Louvain randomly orders all the nodes in a graph in the modularity-optimization phase. Then, it removes and inserts each node in a different community until no significant increase in modularity results. A modularity score has been maximized once relationships among nodes have been minimized by aggregating the weights (or quantities) of the edges connecting them into the highest possible density. Achieving high modularity lets you make modifications or add new nodes without causing cascading impacts in the overall graph by decoupling generalized clusters, allowing them to be manipulated separately.
The algorithm groups together similar nodes based on edge weights. The criteria used to determine similarity is up to the person running the algorithm and can take into account combinations of properties or a single property. If edges are unweighted, the algorithm determines similarity by comparing the number of edges coming out of a node.
Community structure is a vital feature of complex networks. Due to its speed, effectiveness, and simplicity, the Louvain algorithm is widely used to detect community structures in the network topology. Speeding up the Louvain algorithm, enabling the analysis of larger graphs in a shorter time, and maintaining the accuracy of the result can benefit the research of networks in many fields.
An ideal use of the Louvain algorithm is segmenting customer profiles for targeted sales and marketing efforts. It is particularly adept at identifying dynamic communities quickly, and is therefore applicable to partitioning communities onto different machines or in security operations involving evolving communities.
Louvain clustering is just one of many sophisticated analytic algorithms that Katana Graph supports. Learn more about Katana Graph’s High Performance Graph Analytics Library.
Katana Graph Intelligence Platform is used to solve problems. Speak to a Graph expert to learn how Katana Graph’s Intelligence Platform will help your organization.
Get to Know Katana Graph
We thrive on testing new and diverse ideas.
Katana Graph was born of cutting-edge research and scientific rigor, and these beginnings have a powerful effect on who we are to this day. We’re devoted to problem solving, and are relentless in our pursuit of more effective and more efficient solutions to real-world challenges. Continuous improvement is the very foundation of our success.
