Many complex networks in the real world have community structures -- groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By considering networks as geometric objects and communities in a network as a geometric decomposition, we apply curvature and discrete Ricci flow, which have been used to decompose smooth manifolds with astonishing successes in mathematics, to break down communities in networks. We tested our method on networks with ground-truth community structures, and experimentally confirmed the effectiveness of this geometric approach.
Ricci curvature on general spaces without Riemannian structures has been recently studied, in the work of Ollivier @cite_67 @cite_12 on Markov chains, and Bakry and Emery @cite_13 , Lott, Villani @cite_24 , Bonciocat and Sturm @cite_62 @cite_3 on general metric spaces. Ricci curvature based on optimal transportation theory, proposed by Ollivier (Ollivier-Ricci curvature) @cite_67 @cite_12 , has become a popular topic and been applied in various fields -- for distinguishing cancer-related genes from normal genes @cite_37 , for studying financial market fragility @cite_19 , for understanding phylogenetic trees @cite_60 , and for detecting network backbone and congestion @cite_4 @cite_36 @cite_5 . In @cite_15 , Pal al proposed to use Jaccard coefficients for a proxy for Ollivier-Ricci Curvature. Besides, discrete Ricci curvature has also been defined on cell complexes, proposed by Forman @cite_54 (Forman curvature or Forman-Ricci curvature). Forman curvature is based on graph Laplacian. It is easier and faster to compute than Ollivier-Ricci curvature, but is less geometrical. It is more suitable for large scale network analysis @cite_46 @cite_6 @cite_59 @cite_14 and image processing @cite_51 . We have also experimented with Forman curvature for community detection. The results were less satisfying. So here we focus on Ollivier-Ricci curvature.
@cite_36 @cite_54 @cite_3 @cite_5 @cite_15 @cite_67 @cite_4 @cite_60 @cite_46 @cite_37 @cite_6 @cite_19 @cite_12 @cite_13 @cite_62 @cite_14 @cite_24 @cite_59 @cite_51
2792707137 2780222030 1970564715 1972708599
The discrete version of the Ollivier-Ricci (OR) curvature, applicable to networks, has recently found utility in diverse fields. OR curvature requires solving an optimal mass transport problem for each edge, which can be computationally expensive for large and or dense networks. We propose two alternative proxies of curvature to OR that are motivated by the Jaccard index and are demonstrably less computationally intensive. Jaccard curvature (JC) is a simple shift and scaling of the Jaccard index that captures the overlap of edge node neighborhoods. Generalized Jaccard curvature (gJC) captures the shortest path distances in a mass exchange problem. We study the goodness of approximation between the proposed curvatures and an alternative metric, Forman-Ricci curvature, with OR curvature for several network models and real networks. Our results suggest that the gJC exhibits a reasonably good fit to the OR curvature for a wide range of networks, while the JC is shown to be a good proxy only for certain scenarios. We have performed an empirical comparison of two distinct notions of discrete Ricci curvature for graphs or networks, namely, the Forman-Ricci curvature and Ollivier-Ricci curvature. Importantly, these two discretizations of the Ricci curvature were developed based on different properties of the classical smooth notion, and thus, the two notions shed light on different aspects of network structure and behavior. Nevertheless, our extensive computational analysis in a wide range of both model and real-world networks shows that the two discretizations of Ricci curvature are highly correlated in many networks. Moreover, we show that if one considers the augmented Forman-Ricci curvature which also accounts for the two-dimensional simplicial complexes arising in graphs, the observed correlation between the two discretizations is even higher, especially, in real networks. Besides the potential theoretical implications of these observations, the close relationship between the two discretizations has practical implications whereby Forman-Ricci curvature can be employed in place of Ollivier-Ricci curvature for faster computation in larger real-world networks whenever coarse analysis suffices. We present a monotonic expression for the Ricci flow, valid in all dimensions and without curvature assumptions. It is interpreted as an entropy for a certain canonical ensemble. Several geometric applications are given. In particular, (1) Ricci flow, considered on the space of riemannian metrics modulo diffeomorphism and scaling, has no nontrivial periodic orbits (that is, other than fixed points); (2) In a region, where singularity is forming in finite time, the injectivity radius is controlled by the curvature; (3) Ricci flow can not quickly turn an almost euclidean region into a very curved one, no matter what happens far away. We also verify several assertions related to Richard Hamilton's program for the proof of Thurston geometrization conjecture for closed three-manifolds, and give a sketch of an eclectic proof of this conjecture, making use of earlier results on collapsing with local lower curvature bound. Abstract We introduce and study rough (approximate) lower curvature bounds for discrete spaces and for graphs. This notion agrees with the one introduced in [J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math. 169 (2009), in press] and [K.T. Sturm, On the geometry of metric measure spaces. I, Acta Math. 196 (2006) 65–131], in the sense that the metric measure space which is approximated by a sequence of discrete spaces with rough curvature ⩾ K will have curvature ⩾ K in the sense of [J. Lott, C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math. 169 (2009), in press; K.T. Sturm, On the geometry of metric measure spaces. I, Acta Math. 196 (2006) 65–131]. Moreover, in the converse direction, discretizations of metric measure spaces with curvature ⩾ K will have rough curvature ⩾ K . We apply our results to concrete examples of homogeneous planar graphs.