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.展开更多
基金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.
