Suppose one wants to understand the similarities between two, very large, unknown networks from an application domain, e.g., brain networks, gene expression networks, or protein networks. There are two associated problems that are far from trivial: how to quantify similarity, and how to detect it in a reasonable amount of time, considering that the networks can have millions or billions of connections. Researchers have used methods inspired by combinatorics and network theory, but so far these methods have run into many complexity-theoretic barriers and it is not clear whether they can capture true functional similarities of networks.
A more recent approach is based on spectral graph theory, which is the expertise of the investigator. In particular, the approach taken here is an original application of graph Laplacians and quantitative algorithms around real quadratic forms. There are numerous natural and unexplored algorithmic and complexity-theoretic questions in this area that the investigator will pursue. A particularly interesting aspect of this proposal is how it is related to the graph isomorphism problem, but deals with relaxations that potentially enable circumventing this venerable barrier. The investigator, with his established connections with biologists and health scientists, will also apply his work toward more practical software for network alignment.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
