Research On Network Characterzatior And Protein-protein Interaction Network Modeling

With the rise of information technology, networks increasingly permeate many aspects of our daily life. The growing dependence of people on networks has attracted researchers from different disciplines to this emerging field:network science. In addition to the tech-nology networks, such as the Internet, World Wide Web and power grids, the networks studied also include many natural networks, such as the neuron networks, gene regulation networks and protein-protein interaction networks. These networks often involve thousands or millions of vertices and edges, and also keep changing. Faced with such a complex ob-ject, two questions arise:what a network looks like? How it was formed? This article focuses on these two basic questions and devotes to portray the topology of the network and build models to infer its underlying growth mechanisms. Here we first propose a net-work description method, and then apply it to network comparison and model assessment. We investigate the strengths and weaknesses of multiple protein-protein interaction net-work models, and obtain a more realistic model, which help infer the growth and evolution process of the network. The main results of this dissertation are as follows:1. A curve shaped description of large networks is proposed. The description ex-plores multi-scales information of a network by the use of breadth-first traversal. It serves as a bridge linking networks of different structures with a set of particular curves. To in-vestigate the hard problem that whether every network has its own unique curve, here we apply this curve shaped description to both random graphs and a set of small world networks. The analytical results show that each of these networks has a unique curve ex-pression in the limit of large network size. The curve expression possesses a number of network properties in one bag, such as the size of the giant component and the local clus-tering. Interestingly, it shows that a network which is homogeneous and small-world-like appears to have a power-law degree distribution under traceroute sampling.2. A network comparison method is proposed base on the curve mentioned above. This approach takes the curve as a feature extracted from large-scale networks and defines a graph distance to measure the structural differences between networks. The graph distance can then be used in network comparison and classification. Network comparison can help a network model find the parameters that best fit a real data, and the classification can help a real data find the best-fitting model among a pile of candidates. The effectiveness and the robustness of the comparison and classification method are validated through the numerical experiments on parameter estimation and model evaluation for a protein-protein interaction network. Additionally, compared to the network classification method based on subgraph census, the method proposed here is much faster and provides a complementary aspect of the network, which enhances the reliability of the comparison results.3. A comprehensive model considering both gene duplication and link dynamics is proposed for protein-protein interaction networks. In the study of network modeling of protein-protein interaction networks, gene duplication and link dynamics are regarded as the major mechanisms shaping network structure. Although the two mechanisms are very important, the existing models emphasis heavily only on one of the two since the lack of good evaluation methods for network models. Here we use a variety of complemen-tary evaluation methods to assess three competitive network models. The numerical results show that the gene duplication is good that reproducing the local structure of Drosophila's protein network, and the link dynamics is good at enhancing the overall connectivity of the network. In summing up, a comprehensive model considering both the two mechanisms is proposed and obtains a high rank in the evaluation methods. Experimental results show that both the gene duplication and link dynamics are critical in shaping the topology of Drosophila's network, weakening any of the two cannot reproduce the intact network.