Curvature Analysis in Complex Networks: Theory and Application

Useful insights for many complex systems are often obtained by representing them as net- works and analyzing them using algorithmic tools and network measures (i.e., ”network curva- ture”). In this thesis, we will use (a) Gromov-hyperbolic combinatorial curvature δ based on the properties of exact and aproximate geodesics distributions and higher-order connectivities and (b) Geometric curvatures C based on identifying network motifs with geometric complexes (”geometric motifs” in systems biology jargon). Gromov-hyperbolic curvature in graphs occur often in many network applications. When the curvature is fixed, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of ”non-expander” graphs. In this thesis we investigate the effect of δ on expansion and cut-size bounds on graphs (here δ need not be a constant), and the asymptotic ranges of δ for which these results provide improved approx- imation algorithms for related combinatorial problems, minimizing bottleneck edges problem and Small-set expansion problem. To this effect, we provide constructive bounds on node ex- pansions for δ-hyperbolic graphs as a function of δ, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently. We also formulate and analyze ge- ometric curvature based on defining k-complex-based Formans combinatorial Ricci curvature for elementary components, and using Euler characteristic of the complex that is topologically associated with the given graph. Since, C depends on non-trivial global properties, we formulate several computational problems related to anomaly detection in static networks, and provide non-trivial computational complexity results for these problems.