Computationally tractable graph clustering algorithms for reducing large scale dynamic network models

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The world today is replete with examples of engineering systems, health care systems, scientific results and biomedical problems that can be described using graphs; examples include network routing, image processing, statistical learning, networked dynamic systems, modeling of human contact networks, bioinformatics for the interpretation of microarray gene expression data, and neuroscience studies of functional relationships in the brain. Such graphs frequently have complex structures and may be time-varying. Combined with recent rapid advances in data-collection technology, such as in cyber networks, data search engines, geo-positioning and wireless sensor networks, geographic information systems, and bioinformatics, this has resulted in the need for the development of a comprehensive and systematic framework that allows for the simple analysis and use of such large graph models. As graph-based models for these systems are typically complex and high dimensional, the resulting analysis of their fundamental system behavior is often intractable. We propose an algorithmic framework that addresses a common requirement in the study of these systems - to find simplified graph models that are representative of the original graphs. In parallel with the technical research efforts, educational programs will be developed having a unique interdisciplinary nature with a computational core as the unifying thread. Undergraduates will be involved in simulations that will introduce them to the underlying research fields in a natural and intuitive manner. Targeted activities focused on the emerging prevalence of computational data analysis and optimization in physical and health sciences will be included, with one goal being to attract students from underrepresented groups. This research program addresses the need for reducing the complexity of graph models by uniting concepts from information and optimization theories, network analysis, control and dynamic system theory, and graph theory. The development and application of a general computational framework addressing network and graph-centric aggregation problems will be undertaken. This framework will incorporate domain-specific constraints on network structure; variability in interactions, interdependencies and cost functions; and allow for dynamics in constituent elements and network topologies. The resulting algorithms will be scalable and capable of handling exceptionally large data sets. Conceptually, the proposed framework is based on a stochastic approach where a probability density function is ascribed on the space of decision variables such that the most probable value for the decision variable is an approximate solution to the combinatorial problem under the given constraints. This probability density function is derived using the maximum entropy principle, which is motivated by the law of minimum free energy in physical chemistry; a similar mechanism is employed by nature in solving analogous combinatorial problems. In this project, we will develop a maximum entropy framework that will transcend standard approaches to large-scale graph-reduction problems derived from varied application domains, while exploiting their commonalities. The immediate application domains include neuroscience and epidemic control, with expected long-range potential impacts in biological, chemical and health sciences. The work in this proposal will be apt for the analysis and simplification of human contact networks that lead toward advanced epidemic analysis and control, and projects that incorporate networks of generative models, such as classification of brain-activity data from brain machine interfaces to predict motor intent for the purpose of guiding prosthetic devices. The proposed framework facilitates the inclusion of information and constraints that are unique to these applications and not adequately covered in existing methods.