Mining Dense Overlapping Subgraphs in Weighted Protein-Protein Interaction Networks

Many high throughput experiments have been used to detect protein interactions which can be used to a protein-protein interaction network. To recognize the protein complexes in a protein-protein interaction network can help us understand the mechanisms of the biological processes. In this thesis, we proposed a novel method with four phases to mine the protein complexes in the protein-protein interaction network. First, we calculate the weighted degree for each vertex in the network and pick the vertex with the highest weighted degree as the seed vertex. Second, we find a dense subgraph based on the greedy algorithm. Third, we modify the edge weights in the network and compute the weighted degree and the ratio of weighted degree for each vertex in the network. Finally, we repeat the above phases until no more dense subgraph can be found. Our proposed method does not remove any vertex and edge as a subgraph has been found. Therefore our method can mine more overlapping subgraphs than the CODENSE method. The experiment results show that our proposed method can find more protein complexes than the CODENSE method.