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

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