Detecting Statistically Significant Subgraphs And Its Applications

Subgraph Detectionisa primaryissue in modern network science,and an important means for displaying and representing the network structure.Its objective is to find one or more subgraphs which include some kind of specific definitions.However,researchers have been focused on dense subgraph finding recently,while the study of statistically significant subgraph detection will often be ignored.Since the predicted dense subgraphs using the existing methods might not have statistical significance,it’s urgent to solve the problem of how to find the subgraph of statistical significance in the networks.This thesis proposes a novel algorithm to solve the problem of statistically significant subgraph finding.Thismethod has two main modules: statistically significant subgraph finding,and elimination of redundancy.At the former stage,a seed node should be selected to construct an initial subgraph firstly,and then a statistically significant subgraph could be found iteratively.We will iteratively loop the above procedure until there is no seed node can be selected,and all the subgraphs found are statistically significant subgraphs.Actually,the nature of a single iterative producer is multiple hypothesis testing,and FWER has been introduced to control false rate.At the latter stage,the process of elimination of redundancy for the terminal results is used to filter a lot of redundant results.A series of experiments have been carried out on the simulate networks and the real_world networks,and the experiments results demonstrate that SSF have relatively good performance on finding statistically significant subgraphs.What’s more,SSF could be successfully applied on protein complex detection in proteomic.The experimental results show that SSF can not only predict the proper results of stability in term of statistically significant subgraph detection,but also in the PPI network,SSF also has good performance on predicting protein complexes.