High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA...High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA,has been put forward to predict protein complexes via dense subgraph because the proteins among a protein complex have a much tighter relation among them than with others. This method chooses a node with its neighbors to form the initial subgraph,and chooses a node which has the tightest relation with the subgraph according to greedy strategy,then the chosen node is added into the initial subgraph until the subgraph density is below the threshold value. The ob-tained subgraph is then removed from the network and the process continues until no subgraph can be detected. Compared with other algorithms,DSDA can predict not only non-overlap protein com-plexes but also overlap protein complexes. The experiment results show that DSDA predict as many protein complexes as possible. And in Y78K network the accuracy of DSDA is as twice times as that of RNSC and MCL.展开更多
The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few inde...The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.展开更多
基金Supported by the National Natural Science Foundation of China (60803025)
文摘High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA,has been put forward to predict protein complexes via dense subgraph because the proteins among a protein complex have a much tighter relation among them than with others. This method chooses a node with its neighbors to form the initial subgraph,and chooses a node which has the tightest relation with the subgraph according to greedy strategy,then the chosen node is added into the initial subgraph until the subgraph density is below the threshold value. The ob-tained subgraph is then removed from the network and the process continues until no subgraph can be detected. Compared with other algorithms,DSDA can predict not only non-overlap protein com-plexes but also overlap protein complexes. The experiment results show that DSDA predict as many protein complexes as possible. And in Y78K network the accuracy of DSDA is as twice times as that of RNSC and MCL.
基金This work was supported by the National Key Research and Development Program of China(No.2019YFB2102600)the National Natural Science Foundation of China(Nos.62122042 and 61971269)the Blockchain Core Technology Strategic Research Program of Ministry of Education of China(No.2020KJ010301)fund。
文摘The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.
