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

复杂网络出现在许多自然系统中，如社会网络、意见网络和生物网络，以及在工程系统中，如通信网络，如互联网。检测社区，即具有密集互连的节点集群，对于许多应用来说是一个关键问题。在现实世界的复杂网络中，社区结构会随着时间的推移而变化。动态网络，其中节点和网络拓扑具有相互依赖(共同进化)的动力学，是物理学、控制理论和机器人学中的活跃研究对象。这个项目的主要目标是利用几何技术建立社区探测的数学工具和算法，并开发动态网络的数学模型。该项目的应用包括安全和威胁检测。一些研究将涉及研究生和本科生，开发的软件将免费提供给其他研究人员。网络中的群落可以被视为黎曼几何中粗细分解的离散对应物。从几何学和汉密尔顿-佩雷尔曼的Ricci流计划的成功中获得灵感，研究人员最近提出了用于网络中社区检测的离散Ricci流。实验研究表明，该方法能够准确地检测出社区。然而，一些理论问题，如流动的长期收敛，仍然是悬而未决的。解决这些问题将是第一个项目的主要重点。第二个项目旨在寻找模型来解释社会和舆论网络中社区的出现。通过将社交网络视为在节点(例如，意见)和边上具有特定属性(例如，平局关系)的图，调查者计划在较长时间内理解意见如何影响平局关系，反之亦然。他们还试图确定这个网络是否会两极分化，或者分解成有不同观点的社区。对于威胁检测，将特别强调识别极端的小集群。提出了两个用于监测意见网络动态变化的数学模型。主要目标是了解这些模型的长期行为，并从数学上确定渐近极限的存在。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.