Edge Laplacian offers efficient graph community detection similar to Ricci flow
Community Detection using the Edge Laplacian Dynamics vis-a-vis Ricci Flow
Social and Information Networks
Summary
Community detection in graphs helps find groups or clusters in networks like social media or biological systems. The authors show that using the Edge Laplacian, a simpler mathematical tool, can detect these communities almost as well as a more complex method called Ricci flow. Their approach is faster because it avoids certain complicated calculations required by Ricci-based methods. This means you can analyze large networks more efficiently without losing much accuracy.
What this means in practice
- •For network analysts: Identify community structures in large graphs quickly by using Edge Laplacian driven methods instead of computationally heavier Ricci flow techniques.
- •For social media engineers: Improve clustering of users or content by deploying efficient Edge Laplacian based community detection algorithms that scale better for large social networks.
Authors
Pratibha Bhandari, Soumyendu Raha
Abstract
It has been found that utilizing the geometric properties of the graph dynamics can bring out crucial information of the data that a statistical analysis will not. The properties of Ricci flow bring out hidden dynamics of the data in the same way as decomposition of smooth manifolds. In this paper we explore an alternative to Ricci flow, where we find that we can bring out similar properties like it using a simpler and well defined Edge Laplacian to practice community detection in graphs. Moreover, the results obtained by the present approach show that a flow driven by the Edge Laplacian yields results similar to those of the Ricci flow. In contrast, computing the Forman-Ricci curvature requires looping over the adjacent edges, while computing Olivier-Ricci curvature involves the computation of Wasserstein distance and probability distribution associated with the graph nodes, making the Edge Laplacian approach computationally more efficient.