Biological networks, social networks and the dynamic processes over them such as diffusion can be better understood by simultaneously analyzing both the network data and the diffusion data. However, data about diffusion, the network, and node attributes are all limited and often wrong. Overcoming this limited/uncertain data bottleneck is an important challenge in better estimating the network structure, better finding the correlations hidden in the network, and better tracking the diffusion dynamics over the network.

We focus on four different problems regarding the analysis of networks and diffusion dynamics over them with limited information. We first improve protein annotation prediction performance by metric labeling and associated semi-metric embedding of the annotations that integrate the similarities between annotations to protein network data. Second, we propose methods to reconstruct an unknown network from available diffusion data accurately at both micro and macro scales in both biological and social domains. Then, we formulate the diffusion history reconstruction problem to estimate the diffusion histories from incomplete snapshots of the diffusion process, and apply our methods to different diffusion types with accurate performance. Lastly, we propose novel methods to deconvolve the biological 3C interaction matrix that is an ensemble over a cell population under several assumptions about their structures. All these problems are computational, and we validate the effectiveness of our methods with both computational experiments and with theoretical bounds.

128 pages

Thesis Committee:
Carl Kingsford (Chair)
Guy Blelloch
Seyoung Kim
Russell Schwartz
Chakra Chennubhotla (University of Pittsburgh)

Robert F. Murphy, Head, Computational Biology Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu