Directed Depth-Based Complexity Traces of Hypergraphs from Directed Line Graphs

In this paper, we aim to characterize hyper graphs in terms of structural complexities. To measure the complexity of a hyper graph in a straightforward way, we transform a hyper graph into a line graph which accurately reflects the multiple relationships exhibited by the hyper graph. To locate the dominant substructure within a line graph, we identify a centroid vertex by computing the minimum variance of its shortest path lengths. A family of directed centroid expansion sub graphs of the line graph is then derived from the centroid vertex. We compute the directed depth-based complexity trace of a hyper graph by measuring directed entropies on its directed sub graphs. The novel hyper graph complexity trace provides a flexible framework that can be applied to both hyper graphs and graphs. Experiments on standard (hyper)graph datasets demonstrate the effectiveness and efficiency of the new complexity trace.