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

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

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.