Small: New Directions in Community Detection

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

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.