Fast and Scalable Complex Network Descriptor Using PageRank and Persistent Homology
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|\alpha(|V|))$, where $\alpha$ 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph SimilaritySimilar Papers 제목 키워드 기반
A Framework for Fast and Stable Representations of Multiparameter Persistent Homology Decompositions
Topological data analysis (TDA) is an area of data science that focuses on using invariants from algebraic topology to provide multiscale shape descriptors for geometric data sets such as point clouds. One of the most im…
Topological Data AnalysisFast Incremental and Personalized PageRank
In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evol…
Fast Geometric Embedding for Node Influence Maximization
Computing classical centrality measures such as betweenness and closeness is computationally expensive on large-scale graphs. In this work, we introduce an efficient force layout algorithm that embeds a graph into a low-…
Data-Driven Controllability Analysis and Stabilization for Linear Descriptor Systems
For a parameter-unknown linear descriptor system, this paper proposes data-driven methods to testify the system's type and controllability and then to stabilize it. First, a data-based condition is developed to identify …
Topologically Persistent Features-based Object Recognition in Cluttered Indoor Environments
Recognition of occluded objects in unseen indoor environments is a challenging problem for mobile robots. This work proposes a new slicing-based topological descriptor that captures the 3D shape of object point clouds to…
Object RecognitionPoint Cloud ClassificationUnity