notesum.ai

Published at December 4

Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs

cs.SI

cs.DS

cs.LG

Released Date: December 4, 2024

Authors: Zihao Li¹, Dongqi Fu¹, Hengyu Liu¹, Jingrui He¹

Aff.: ¹University of Illinois Urbana-Champaign

Arxiv: http://arxiv.org/pdf/2412.03008v1

Refer to caption

Symbol	Definition and Description
$\mathcal{G}=(\mathcal{V},W,\varphi)$	graph being investigated, with vertex set $\mathcal{V}$ , adjacency matrix $W$ , vertex weight mapping $\varphi$
$\mathcal{H}=(\mathcal{V},\mathcal{E},\omega,\gamma)$	hypergraph being investigated, with vertex set $\mathcal{V}$ , hyperedge set $\mathcal{E}$ , edge weight mapping $\omega$ and edge-dependent vertex weight mapping $\gamma$
$n=\|\mathcal{V}\|$	number of vertices
$m$	number of hyperedge-vertex connections in Hypergraph $\mathcal{H}$ , $m=\sum_{e\in\mathcal{E}}\|e\|$
$d(v)$	degree of vertex $v$ , $d(v)=\sum_{e\in E(v)}w(e)$
$\delta(e)$	degree of hyperedge $e$ , $\delta(e)=\sum_{v\in e}\gamma_{e}(v)$
$R$	$\|\mathcal{E}\|\times\|\mathcal{V}\|$ vertex-weight matrix
$W$	$\|\mathcal{V}\|\times\|\mathcal{E}\|$ hyperedge-weight matrix
$D_{\mathcal{V}}$	$\|\mathcal{V}\|\times\|\mathcal{V}\|$ vertex-degree matrix
$D_{\mathcal{E}}$	$\|\mathcal{E}\|\times\|\mathcal{E}\|$ hyperedge-degree matrix
$P$	$\|\mathcal{V}\|\times\|\mathcal{V}\|$ transition matrix of random walk on $\mathcal{H}$
$\phi$	$1\times\|\mathcal{V}\|$ stationary distribution of random walk
$\Pi$	$\|\mathcal{V}\|\times\|\mathcal{V}\|$ diagonal stationary distribution matrix
$p$	$1\times\|\mathcal{V}\|$ probability distribution on $\mathcal{V}$
$\alpha$	restart probability of random walks
$\partial$	boundary notation
$vol$	volume notation
$pr(\alpha,s)$	lazy personalized PageRank vector with restart probability $\alpha$ and stochastic vector $s$