Edge weights are constrained to be non-negative, which allows us to define the transition matrix P with The distance of two vertices is measured in terms of the average time of a random walk be-tween the two.
we adopt the notion of T-truncated hitting time (Sarkar and Moore, 2007) defined as the expected number of steps it takes until a random walk of at most T steps starting at v i reaches v j for the first time: The truncated hitting time h T (v j |v i ) can be approximately computed by sampling M independent random walks starting at v i of length T and computinĝ where {t 1 .