Random Walks Flashcards
What is Heaps Law?
An empirical law describing the number of distinct words in a document or a book as a function of the document length.
S(t) = ~t^beta
What are Random Walks?
They are a fundamental type of dynamical processes on networks.
A random walk on a graph is a process
that begins at some vertex, and at each time step moves to another vertex.
What is the probability for the walk to be found at node i?
The probability should be proportional to the nodal degree.
What is the “node staying” probability?
p(t) = (p1(t), p2(t), ... pn(t))^T T = transpose
What is the mean first-passage time?
The average time for the walk to go from one node to another.
When calculating the mean first-passage from node u to node v. Why do we assume that the adjacency matrix of Aiv = 0?
Because we assume the walk ends at node v. Therefore v is an absorbing node.
What is the benefit of a reduced Laplacian matrix?
L’ no longer has a zero eigenvalue (as 1 is no longer an eigenvector) and is thus invertible.
What is an edge-reinforced random walk? (ERRW)
Every time an edge is utilized, the weight of the edge increases. For example, a link between two concepts is reinforced every time it’s recalled in a cognitive process.
ERRW networks tend to be what due to their long term memory?
Non-Markovian
