ATD: Algorithms and Geometric Methods for Community and Anomaly Detection and Robust Learning in Complex Networks

Complex networks arise in many natural systems, such as social networks, opinion networks, and biological networks, as well as in engineered systems like communication networks such as the Internet. Detecting communities, that is, clusters of nodes with dense interconnections, is a crucial problem with numerous applications. In real-world complex networks, community structures change over time. Dynamic networks, where nodes and network topology have mutually dependent (co-evolving) dynamics, are actively studied in physics, control theory, and robotics. The primary objectives of this project are to establish mathematical tools and algorithms for community detection, using geometric techniques, and to develop a mathematical model for dynamic networks. The applications of this project include security and threat detection. Some of the research will involve graduate and undergraduate students, and the software developed will be made freely available to other researchers. Communities in networks can be viewed as discrete counterparts of thick-thin decompositions in Riemannian geometry. Drawing inspiration from geometry and the success of Hamilton-Perelman's Ricci flow program, the investigators recently proposed discrete Ricci flows for community detection in networks. Experimental investigations have demonstrated that the proposed method can accurately detect communities. However, several theoretical problems, such as the long-term convergence of the flow, remain open. Resolving these issues will be the main focus of the first project. The second project aims to find models that explain the emergence of communities in social and opinion networks. By considering a social network as a graph with specific attributes at nodes (e.g., opinions) and edges (e.g., tie relations), the investigators plan to understand how opinions influence tie relations and vice versa over an extended period. They also seek to determine if the network will become polarized or decomposed into communities with different opinions. For threat detection, particular emphasis will be placed on identifying small clusters of extreme. Two mathematical models are proposed to monitor the dynamic changes in opinion networks. The main goals are understanding the long-term behavior of these models and mathematically establishing the existence of the asymptotic limit. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.