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.
This paper proceeds from the premise that the topology of interference constrained wireless networks heavily impacts their node-to-node delay, routing energy, and capacity region. We quantitatively analyze how the discrete Ollivier-Ricci curvature of a network affects the performance metrics of several routing protocols. Since different protocols are optimal relative to different metrics under different topologies, an adaptive control system is proposed that identifies the topology curvature and selects the best protocol under current circumstances subject to user needs. Also, we analyze how sensitive the four routing protocols (Heat Diffusion, Dirichlet, Back Pressure and Shortest Path Routing) under examination are to varying topological environment, as it would commonly be encountered in wireless networks.    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. Publisher Summary This chapter describes Seifert Fibered Spaces in 3-Manifolds. There exist finitely many disjoint, non-contractible, pairwise non-parallel, embedded 2-spheres in M, whose homotopy classes generate π2 (M) as a π2 (M)-module; and modulo the Poincare conjecture, these 2-spheres are unique up to ambient homeomorphism. Thus, all singular 2-spheres in M, that is, maps of S2 into M, may be described, up to homotopy, in terms of a geometric picture in M. The strong version of the sphere theorem presented in the chapter gives a great deal of information about fundamental groups of compact 3-manifolds, for example that they are finite free products of torsion-free groups and finite groups. It also provides in a slightly refined version a reduction of the classification problem for compact, oriented 3-manifolds to the classification problem for compact, irreducible, 3-manifolds. Analysis of Internet topologies has shown that the Internet topology has negative curvature, measured by Gromov's “thin triangle condition”, which is tightly related to core congestion and route reliability. In this work we analyze the discrete Ricci curvature of the Internet, defined by Ollivier [1], [2], etc. Ricci curvature measures whether local distances diverge or converge. It is a more local measure which allows us to understand the distribution of curvatures in the network. We show by various Internet data sets that the distribution of Ricci cuvature is spread out, suggesting the network topology to be non-homogenous. We also show that the Ricci curvature has interesting connections to both local measures such as node degree and clustering coefficient, global measures such as betweenness centrality and network connectivity, as well as auxilary attributes such as geographical distances. These observations add to the richness of geometric structures in complex network theory. Statistical phylogenetic inference methods use tree rearrangement operations such as subtree–prune–regraft (SPR) to perform Markov chain Monte Carlo (MCMC) across tree topologies. The structure of the graph induced by tree rearrangement operations is an important determinant of the mixing properties of MCMC, motivating the study of the underlying SPR graph in greater detail. In this paper, we investigate the SPR graph of rooted trees (rSPR graph) in a new way: by calculating the Ricci–Ollivier curvature with respect to uniform and Metropolis–Hastings random walks. This value quantifies the degree to which a pair of random walkers from specified points move towards each other; negative curvature means that they move away from one another on average, while positive curvature means that they move towards each other. In order to calculate this curvature, we develop fast new algorithms for rSPR graph computation. We then develop formulas characterizing how the number of rSPR neighbors of a tree changes after an rSPR operation is applied to that tree. These give bounds on the curvature, as well as a flatness-in-the-limit theorem indicating that paths of small topology changes are easy to traverse. However, we find that large topology changes (i.e. moving a large subtree) give pairs of trees with negative curvature. We show using simulation that mean access time distributions depend on distance, degree, and curvature, demonstrating the relevance of these results to stochastic tree search. 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.      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.  We dene a notion of a measured length space X having nonnegative N-Ricci curvature, for N 2 [1;1), or having1-Ricci curvature bounded below byK, forK2 R. The denitions are in terms of the displacement convexity of certain functions on the associated Wasserstein metric space P2(X) of probability measures. We show that these properties are preserved under measured Gromov-Hausdor limits. We give geometric and analytic consequences. This paper has dual goals. One goal is to extend results about optimal transport from the setting of smooth Riemannian manifolds to the setting of length spaces. A second goal is to use optimal transport to give a notion for a measured length space to have Ricci curvature bounded below. We refer to [11] and [44] for background material on length spaces and optimal transport, respectively. Further bibliographic notes on optimal transport are in Appendix F. In the present introduction we motivate the questions that we address and we state the main results. To start on the geometric side, there are various reasons to try to extend notions of curvature from smooth Riemannian manifolds to more general spaces. A fairly general setting is that of length spaces, meaning metric spaces (X;d) in which the distance between two points equals the inmum of the lengths of curves joining the points. In the rest of this introduction we assume that X is a compact length space. Alexandrov gave a good notion of a length space having bounded below by K", with K a real number, in terms of the geodesic triangles in X. In the case of a Riemannian manifold M with the induced length structure, one recovers the Riemannian notion of having sectional curvature bounded below by K. Length spaces with Alexandrov curvature bounded below by K behave nicely with respect to the GromovHausdor topology on compact metric spaces (modulo isometries); they form  A new Combinatorial Ricci curvature and Laplacian oper- ators for grayscale images are introduced and tested on 2D synthetic, natural and medical images. Analogue formulae for voxels are also ob- tained. These notions are based upon more general concepts developed by R. Forman. Further applications, in particular a fltting Ricci ∞ow, are discussed.