Fast and Scalable Complex Network Descriptor Using PageRank and Persistent Homology
This provides a fast and scalable method for graph comparison, particularly useful for analyzing large networks in domains like shape analysis, though it appears incremental as it combines existing techniques.
The authors tackled the problem of comparing graph similarities by combining PageRank and persistent homology to create a scalable graph descriptor, achieving computation in O(|E|α(|V|)) time and demonstrating effectiveness on shape mesh datasets.
The PageRank of a graph is a scalar function defined on the node set of the graph which encodes nodes centrality information of the graph. In this article, we use the PageRank function along with persistent homology to obtain a scalable graph descriptor and utilize it to compare the similarities between graphs. For a given graph $G(V,E)$, our descriptor can be computed in $O(|E|α(|V|))$, where $α$ is the inverse Ackermann function which makes it scalable and computable on massive graphs. We show the effectiveness of our method by utilizing it on multiple shape mesh datasets.