Persistent homology with k-nearest-neighbor filtrations reveals topological convergence of PageRank

Figure 1.  Visualizations of simplicial complexes and graphs resulting from (A) a Vietoris-Rips (VR) filtration and (B) our proposed k-nearest-neighbor (kNN) filtration. As shown in the second column, VR filtrations are parameterized by the radius $ \epsilon $ of $ \epsilon $-balls that are centered at the points, whereas kNN filtrations are parameterized by the number $ k $ of nearest neighbors. (Dotted lines depict the nearest-neighbor orderings for node $ i = 4 $.) The third column depicts simplicial complexes that are obtained at some $ \epsilon $ and $ k $. The fourth columns shows their 1-skeletons, which are graphs in which $ k $-simplices of $ k>1 $ are discarded

Figure 2.  (left) An example graph. (right) Convergence of approximate PageRank values $ x_i(t)\to\pi_i $ with $ t $ iterations

Figure 3.  Example of stability for persistence diagrams resulting from Vietoris-Rips filtrations. (left) Two point-cloud sets $ \mathcal{Y}{ = \{{\bf y}^{(i)}\}_{i = 1}^N} $ and $ \mathcal{Z}{ = \{{\bf z}^{(i)}\}_{i = 1}^N} $ are close with respect to the $ \mathsf{L}_\infty $ norm. The center and right panels depict their associated persistence diagrams $ D_{\mathcal{Y}} $ and $ D_{\mathcal{Z}} $, which are also close with respect to the bottleneck distance

Figure 4.  Visualization of kNN-filtered simplicial complexes for a point cloud using the three types of symmetrization given by Definition 3.4. Comparing across the columns, observe the nestedness property given by Corollary 2

Figure 5.  Comparison of persistent homology for an example point cloud using two different filtrations: (left) our proposed kNN, min filtration; and (right) a VR filtration. The red and blue persistence barcodes indicate 0-dimensional and 1-dimensional cycles, respectively. Observe that the kNN filtration reveals a 1-cycle that was born at $ k = 2 $ and die at $ k = 3 $, whereas the VR filtration does not

Figure 6.  Example with 3 points $ \mathcal{Y} = \{x_a, x_b, x_c\} $ with $ x_a = -1 $, $ x_c = 1 $ and either (A) $ x_b = -\epsilon $ or (B) $ x_b = \epsilon $. Note that the perturbation can be made arbitrarily small for any $ \epsilon>0 $, and the nearest-neighbor orderings are different. (See Tables 2 and 3.)

Figure 7.  (left) A social network of interactions among $ N = 62 $ dolphins in New Zealand. (right) node colors indicate the nodes' respective PageRank values. In both panels, nodes with larger/smaller size have more/fewer connecting edges

Figure 8.  (left) Convergence of nodes' rank orderings $ R_i({\bf x}(t))\to {R}_i(\mathit{\boldsymbol{\pi}}) $ versus time step $ t $. (right) Scatter plot comparing $ t^*_i $ and $ \pi_i $ across the nodes $ i $

Figure 9.  Homological convergence of an iterative algorithm for PageRank for the dolphin social network. (left) Convergence of persistent homology for VR filtrations coincides with a geometrical notion of convergence $ ||{\bf x}(t)-\mathit{\boldsymbol{\pi}}|| \to 0 $ due to the stability theorem. Both asymptotically approach 0 with exponential decay. (right) In contrast, convergence of persistent homology for kNN filtrations more closely resembles the convergence of the rank ordering, which exactly converges after $ t = 14 $ time steps in this case. Observe the kNN persistence diagrams for the max and min methods of symmetrization for kNN sets converge at around the same number of iterations

Figure 10.  Impact of teleportation parameter $ \alpha $ on the geometrical and (discrete) topological convergence of PageRank for the dolphin network. The top and bottom rows are similar to the left and right columns of Fig. 9, respectively, except now different columns depict different choices for $ \alpha $

Figure 11.  $ \mathcal{U} $-local topological convergence for the following subset of nodes: $ \mathcal{U}_1 = \{ $Ripplefluke, Zig, Feather, Gallatin, SN90, DN16, Wave, DN21, Web, Upbang$ \} $. Similar to Fig. 9, the left and right panels depict convergence of persistence diagrams for VR and kNN filtrations, respectively

Figure 12.  Same information as in Fig. 11, except we consider the subset $ \mathcal{U}_1 $ of nodes that have the largest PageRank values

Figure 13.  kNN homological convergence of PageRank for Erdős-Rényi random graphs [22]

Figure 14.  kNN homological convergence of PageRank for small-world networks generated using the Watts-Strogatz model [70]

Figure 15.  kNN homological convergence of PageRank for scale-free networks generated using the Barabasi-Albert model [4]