notesum.ai

Published at December 10

A Spectral Framework for Tracking Communities in Evolving Networks

cs.SI

cs.LG

stat.ML

Released Date: December 10, 2024

Authors: Jacob Hume¹, Laura Balzano²

Aff.: ¹University of Cambridge; ²University of Michigan, Ann Arbor

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

Notation	Description
$G$	A (simple, directed, multiview…) graph with $d$ nodes, suitably connected
$\boldsymbol{A}$	The (possibly weighted) adjacency matrix of $G$
$\operatorname{deg}(\ell)$	The degree of a node $\ell$ of $G$ defined as $\operatorname{deg}(\ell)=\sum_{j\neq\ell}A_{\ell j}$
$\operatorname{vol}(S)$	The volume of a node subset $S$ , defined as $\operatorname{vol}(S)=\sum_{v\in S}\operatorname{deg}(v)$
$\boldsymbol{D}$	The degree matrix $\operatorname{diag}(\operatorname{deg}(1),\dots,\operatorname{deg}(d))$ of $G$ .
$\lambda(\boldsymbol{H});\lambda_{i}(\boldsymbol{H})$	The spectrum of a matrix $\boldsymbol{H}$ ; the $i$ th largest eigenvalue of $\boldsymbol{H}$ .
$\sigma(\boldsymbol{H});\sigma_{i}(\boldsymbol{H})$	The singular values of a matrix $\boldsymbol{H}$ ; the $i$ th largest singular value of $\boldsymbol{H}$ .
$\langle\boldsymbol{H}\rangle$	The span of a matrix or vector $\boldsymbol{H}$
$\text{St}(d,k)$	The Stiefel manifold of matrices in $\mathbb{R}^{d\times k}$ with orthonormal columns
$\mathrm{O}_{k}$	The orthogonal group of matrices in $\mathbb{R}^{k\times k}$ with orthonormal columns
$\text{Gr}(d,k)$	The Grassmann manifold of $k$ -dimensional linear subspaces of $\mathbb{R}^{d}$
$\mathscr{A}$	An algorithm which clusters $d$ nodes with Euclidean embeddings into $\mathbb{R}^{k}$ derived from the extreme of a matrix spectrum (a static spectral method)
$\boldsymbol{M}_{k}=\boldsymbol{U}_{k}\boldsymbol{\Sigma}_{k}\boldsymbol{V}_{k}% ^{\top}$	The rank- $k$ singular value decomposition $\boldsymbol{U}_{k}(\boldsymbol{M})\boldsymbol{\Sigma}_{k}(\boldsymbol{M})% \boldsymbol{V}_{k}(\boldsymbol{M})^{\top}$ of $\boldsymbol{M}$
MCM of $\mathscr{A}$	A matrix $\boldsymbol{M}$ satisfying $\langle\boldsymbol{U}_{k}(\boldsymbol{M})\rangle=\langle\boldsymbol{C}\rangle$ , where $\boldsymbol{C}$ ’s rows are the spectral embeddings from $\mathscr{A}$ into $\mathbb{R}^{k}$ . Called a modeled clustering matrix (MCM)