Small: New Directions in Community Detection

小：社区检测的新方向

• 批准号: 2154100
• 负责人: Julia Gaudio
• 金额: $ 40.06万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154100&HistoricalAwards=false
• 关键词: Small; New; Directions; Community; Detection

Community detection is the problem of identifying community structure in a network. With applications to fields such as biology, sociology, telecommunications, and transportation, community detection is an important question in network science. Community detection is a well-studied problem in probability, statistics, and theoretical computer science, where the network is typically assumed to be random. While there has been much research on community detection in random networks, the standard probabilistic model is too restrictive to model many network-science applications and cannot effectively capture certain features of real-world networks: higher order interactions, overlapping communities, and hierarchical structure. The project will advance the understanding of network science and network inference, by studying richer, more expressive, and realistic formulations of community detection that move beyond the standard Stochastic Block Model (SBM). Broad goals include community detection in the hypergraph generalization of the SBM, using tensor methods to find overlapping communities in hypergraphs, recovering hierarchical community structure, and understanding the capabilities and limits of simple spectral algorithms for many community-detection problems. Tackling the above questions will involve developing new mathematical and algorithmic techniques related to random matrices and random tensors, and bringing them to bear upon problems in community detection. The project will involve graduate student training and co-mentorship by the PIs across computer science and mathematics, as well as outreach to middle- and high-school students.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.

社区检测是识别网络中社区结构的问题。社区检测是网络科学中的一个重要问题，在生物学、社会学、电信、交通等领域都有广泛的应用。社区检测是概率论、统计学和理论计算机科学中一个研究得很好的问题，其中网络通常被假设为随机的。虽然在随机网络中的社区检测方面已经有了很多研究，但标准概率模型对许多网络科学应用的建模限制太大，并且不能有效地捕捉现实世界网络的某些特征：高阶交互、重叠社区和分层结构。该项目将通过研究超越标准随机块模型（SBM）的更丰富、更具表现力和更现实的社区检测公式，促进对网络科学和网络推理的理解。广泛的目标包括在SBM的超图泛化中的社区检测，使用张量方法在超图中找到重叠的社区，恢复分层社区结构，以及理解简单谱算法在许多社区检测问题中的能力和局限性。解决上述问题需要开发与随机矩阵和随机张量相关的新数学和算法技术，并将其应用于社区检测问题。该项目将包括研究生培训和计算机科学和数学领域的pi共同指导，以及向中学生和高中生推广。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。