A modified Ricci flow on arbitrary weighted graph

Abstract

In this paper, we propose a modified Ricci flow, as well as a quasi-normalized Ricci flow, on arbitrary weighted graph. Each of these two flows has a unique global solution. In particular, these global existence and uniqueness results do not require an exit condition proposed by Bai et al in a recent work [2]. As applications, these two Ricci flows are applied to community detection for complex networks, including Karate Club, American football games, Facebook, as well as artificial networks. In our algorithms, unlike in [5,15], there is no need to perform surgery at every iteration, only one surgery needs to be performed after the last iteration. From three commonly used criteria for evaluating community detection algorithms, ARI, NMI and Q, we conclude that our algorithms outperform existing algorithms, including Ollivier's Ricci flow [5], normalized Ollivier's Ricci flow and normalized Lin-Lu-Yau's Ricci flow [15]. The codes for our algorithms are available at https://github.com/mjc191812/Modified-Ricci-Flow.

References in corpus (9)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks