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: www.cs.uic.edu/~dasgupta; www.cs.uic.edu/~dasgupta/professional/algo-lab.html; and www.phys.psu.edu/~ralbert.
