An O(m) Algorithm for Cores Decomposition of Undirected Hypergraph
Leng Min · Journal of Chinese Computer Systems · 2013
The core notion of graph and its application in matching schemes is introduced,which can be extended to hypergraph. Firstly,the core notion of hypergraph is proposed and its formal description is presented. Secondly,we analyze the constructive property of p-core at level k and give the solution steps of cores decomposition for hypergraph. We also discuss the improvement of its time complexity and propose the outline of the rapid algorithm for cores decomposition based on the vertex property function of hypergraph. Thirdly,we describe the improved compressed storage format( ICSF) of undirected hypergraph and promote the cores decomposition from the degree of vertex to the property function of vertex. Furthermore,we present the pseudocode of cores decomposition algorithm of vertex property functions p5( v,U) based on the ICSF of undirected hypergraph,whose time complexity is O( m) and space complexity is O( n + m + z). Finally,we carry out the comparative experiment between degree and core of vertex based on 18 hypergraphs of ISPD98 benchmark. The experiment and analysis showthe core of vertex can more nearly reflect the importance of nodes in the hypergraph than the degree of vertex.