Hitting Time

We run random-walk models on the graph with the new transition probability matrix P′ = D′⁻¹A′ to calculate the hitting-time matrix H = [h_ij]. The hitting time from node i to node j, h_ij, is the expected number of hops to visit node j for the first time, for a random walk started at node i.

Hitting time is an asymmetric measure, meaning that h_ij and h_ji might be different. For example, for a lollipop graph, the hitting times from the nodes on the complete component to nodes on the chain are much larger than the reverse direction, because a random walker spends more time in the complete component. We compute the hitting times between pairs of nodes using the graph Laplacian method introduced in spectral graph theory (Aldous & Fill, 2002). This method is advantageous as it does not require the exact knowledge of the adjacency matrix, instead using a probabilistic approximation of the adjacency matrix of the network. Following Lovász and Simonovits (1993), we calculated the normalized graph Laplacian as

where, D′ is the degree matrix and A′ is the adjacency matrix of the graph after normalization as defined in the main text. We used the eigenvalues and eigenvectors of ℒ to calculate the hitting-time matrix H = [h_ij] (Lovász & Simonovits, 1993);

where, di′ is the degree of node i, i = 1, …, N, and d′ is the sum of all degrees (after normalization; see main text). 0 = λ₁ < λ₂ < ⋯ < λ_n are the n eigenvalues of ℒ, and μ_kj is the jth element of kth eigenvector of ℒ (Lovász & Simonovits, 1993).

Adding the self loops in the normalization step does not make the graphs reducible or periodic, meeting the requirements of the hitting-time calculation we use here (Norris, 1997). Code for analysis in this project can be found under the first author’s name on GitHub: https://github.com/SNaGLab: Hitting-time-analysis (Rezaeinia, 2018).