Flow Complexity: Fast Polytopal Graph Complexity and 3D Object Clustering

摘要

In this paper, we introduce a novel descriptor of graph complexity which can be computed in real time and has the same qualitative behavior of polytopal (Birkhoff) complexity, which has been successfully tested in the context of Bioinformatics. We also show how the phase-change point may be characterized in terms of the Laplacian spectrum, by analyzing the derivatives of the complexity function. In addition, the new complexity notion (flow complexity) is applied to cluster a database of Reeb graphs coming from analyzing 3D objects.