Project web site for NSF grant IIS-1814931 (Link to NSF award site)

                          Project title:     III: Small: Collaborative Research: Network analysis and anomaly detection via global curvatures
                          PI:     Bhaskar DasGupta
                          Collaborative PI:     Réka Albert (Pennsylvania State University)
Project abstract
Curvatures of geometric shapes and topological spaces in higher dimension are natural and powerful generalizations of their simpler counter-parts, in planes and other two-dimensional spaces, to higher dimensions and play a fundamental role in physics, mathematics and many other areas. In this collaborative interdisciplinary proposal involving one investigator each from the University of Illinois at Chicago and the Pennsylvania State University, the investigators will use powerful higher-dimensional curvature analysis methods to provide the foundations of systematic and computationally efficient approaches to find critical components, measure redundancies and detect anomaly in biological and social networks. There is a pressing need for this, as identification of critical components are crucial to the analysis of networks, and curvature-based analysis methods provide a principled way of satisfying this need using a systematic and rigorous theoretical framework to achieve a clear understanding. The proposed research will leverage further development of novel combinatorial tools previously developed by the investigators, in addition to developing new algorithmic and approximability techniques. The algorithms developed in the course of this project will be implemented for validation on simulated and real data and will lead to open-source software for the relevant research communities. In addition to substantial impacts in network analysis, the proposed research will have strong impacts on many other research areas in computational biology, neuroscience and social network analysis. Other broader impacts will include integration of research and education via course and curriculum development, involvement of undergraduates, minorities and under-represented groups, effective dissemination of research, mentoring of undergraduate and graduate students, outreach and community involvement, and promoting diversity in related research and educational activities. The two investigators have a proven track record of extremely successful past collaboration via joint research publications and grants and are therefore confident that this grant will extend their past successful collaboration.

To achieve the goals of this project, the investigators will explore two notions of curvature, namely Gromov-hyperbolic curvature based on the properties of geodesics and higher-order connectivities, and geometric curvatures based on identifying networks with geometric complexes and using combinatorialization of Ricci type curvatures. These curvature measures depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network as opposed to many other measures that are local in nature. The investigators will use these notions to identify non-trivial critical components of the network whose removal affects the change the network topology or dynamics in a significant manner. The investigators will formulate mathematically precise computational problems, study their properties, use novel algorithmic tools to design efficient algorithms, and implement the resulting algorithms to test their accuracy and efficiency. The complementary backgrounds of the two investigators, namely combinatorial optimization in computer science and computational biology (DasGupta) and modelling and analysis of biological and social networks (Albert), will make the two investigators a perfect team for the interdisciplinary applications in this proposal.

Publications

  1. Bhaskar DasGupta, Elena Grigorescu and Tamalika Mukherjee, On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, arXiv:2208.09535, 2022.

  2. Tanima Chatterjee, Réka Albert, Stuti Thapliyal, Nazanin Azarhooshang and Bhaskar DasGupta, Detecting Network Anomalies Using Forman-Ricci Curvature and A Case Study for Human Brain Networks, (Nature) Scientific Reports, 11, 8121, 2021.

  3. Tanima Chatterjee, Bhaskar DasGupta and Réka Albert, A review of two network curvature measures, in Nonlinear Analysis and Global Optimization, Th. M. Rassias, and P. M. Pardalos (eds.), Springer Optimization and Its Applications series 167, 51-69, Springer, 2021.

  4. Nazanin Azarhooshang, Prithviraj Sengupta and Bhaskar DasGupta, A Review of and Some Results for Ollivier-Ricci Network Curvature, Mathematics, 8, 1416, 2020.

  5. Bhaskar DasGupta, Mano Vikash Janardhanan and Farzane Yahyanejad, How did the shape of your network change? (On detecting network anomalies via non-local curvatures), Algorithmica, 82(7), 1741-1783, 2020.

  6. Farzane Yahyanejad, Bhaskar DasGupta and Réka Albert, A survey of some tensor analysis techniques for biological systems, Quantitative Biology, 7(4), 266-277, 2019.

  7. Bhaskar DasGupta, Topological implications of negative curvature for biological networks, 2018 IEEE 8th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS 2018), p. 54, ©IEEE, 2018.

Publication related software

Collaborating researchers (outside UIC)

Graduate students (Past and Present)