III: CCF: Medium: Collaborative Research: Combinatorial Analysis of Biological and Social Networks

III：CCF：媒介：协作研究：生物和社交网络的组合分析

• 批准号: 1161007
• 负责人: Reka Albert
• 金额: $ 27.28万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161007&HistoricalAwards=false
• 关键词: III; CCF; Medium; Collaborative; Research

In this collaborative interdisciplinary proposal involving a researcher at the University of Illinois at Chicago (UIC) and one at the Pennsylvania State University (Penn State), the investigators will design and apply novel algorithmic tools to explore several fundamental graph-theoretic problems that have significant applications in biological and social interaction networks. The research problems addressed in the proposal can be broadly classified into graph partitioning type of problems and graph sparsification type of problems. For example, one such problem in the context of social interaction networks is to partition the nodes into so-called "communities of statistically significant interactions" to study the behavioral patterns of a group of individuals in a society. The PIs will formulate 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 proposed research will leverage further development of novel combinatorial tools previously developed by the PIs, in addition to developing new techniques, to design efficient algorithms for complex optimization problems. 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 life science and social science communities.On a broader level, since this proposal deals with fundamental combinatorial optimization problems that arise in diverse scientific fields, the proposed research will have a strong impact on research areas beyond the primary research area, such as in stability analysis of computer networks and in social network visualization. A central component of the proposal is the creation of meaningful educational activities that leverage the proposed interdisciplinary research and build on the PIs' substantial past experience in teaching, mentoring and outreach and on the diverse communities in Chicago . Additionally, the PIs plan to integrate 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 research and educational activities.The outcomes of the project will be made freely available through the following websites of the investigators and their labs: http://www.cs.uic.edu/~dasgupta; http://www.cs.uic.edu/~dasgupta/professional/algo-lab.html; and http://www.phys.psu.edu/~ralbert.

在这项涉及伊利诺伊大学芝加哥分校 (UIC) 的一名研究人员和宾夕法尼亚州立大学 (宾夕法尼亚州立大学) 的一名研究人员的跨学科合作提案中，研究人员将设计和应用新颖的算法工具来探索在生物和社会交互网络中具有重要应用的几个基本图论问题。该提案中解决的研究问题可以大致分为图划分类型的问题和图稀疏类型的问题。例如，社交互动网络背景下的一个此类问题是将节点划分为所谓的“具有统计显着性互动的社区”，以研究社会中一组个体的行为模式。 PI 将提出精确的计算问题，研究其性质，使用新颖的算法工具设计高效的算法，并实施所得算法以测试其准确性和效率。除了开发新技术之外，拟议的研究还将利用 PI 先前开发的新型组合工具的进一步开发，为复杂的优化问题设计有效的算法。该项目过程中开发的算法将用于对模拟和真实数据进行验证，并将为生命科学和社会科学界带来开源软件。在更广泛的层面上，由于该提案涉及不同科学领域中出现的基本组合优化问题，因此拟议的研究将对主要研究领域之外的研究领域产生重大影响，例如计算机网络的稳定性分析和社交网络可视化。该提案的一个核心组成部分是创建有意义的教育活动，这些活动利用拟议的跨学科研究，并以 PI 过去在教学、指导和推广以及芝加哥多元化社区方面的丰富经验为基础。此外，PI 计划通过课程和课程开发、本科生、少数族裔和代表性不足群体的参与、有效传播研究、指导本科生和研究生、外展和社区参与以及促进研究和教育活动的多样性来整合研究和教育。该项目的成果将通过研究人员及其实验室的以下网站免费提供： http://www.cs.uic.edu/~dasgupta； http://www.cs.uic.edu/~dasgupta/professional/algo-lab.html；和 http://www.phys.psu.edu/~ralbert。