Random walk closeness centrality

Key takeaways

Random walk closeness centrality belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Random walk closeness centrality to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Random walk closeness centrality from memory before moving on to harder problems.

Reference excerpt

Random walk closeness centrality is a measure of centrality in a network, which describes the average speed with which randomly walking processes reach a node from other nodes of the network. It is similar to the closeness centrality except that the farness is measured by the expected length of a random walk rather than by the shortest path. The concept was first proposed by White and Smyth (2003) under the name Markov centrality.

Intuition Consider a network with a finite number of nodes and a random walk process that starts in a certain node and proceeds from node to node along the edges. From each node, it chooses randomly the edge to be followed. In an unweighted network, the probability of choosing a certain edge is equal across all available edges, while in a weighted network it is proportional to the edge weights. A node is considered to be close to other nodes, if the random walk process initiated from any node of the network arrives to this particular node in relatively few steps on average.

Definition Consider a weighted network – either directed or undirected – with n nodes denoted by j=1, …, n; and a random walk process on this network with a transition matrix M. The m i j {\displaystyle m_{ij}} element of M describes the probability of the random walker that has reached node i, proceeds directly to node j. These probabilities are defined in the following way.

m i j = a i j ∑ k = 1 n a i k {\displaystyle m_{ij}={\frac {a_{ij}}{\sum _{k=1}^{n}a_{ik}}}}

where a i j {\displaystyle a_{ij}} is the (i,j)th element of the weighting matrix A of the network. When there is no edge between two nodes, the corresponding element of the A matrix is zero. The random walk closeness centrality of a node i is the inverse of the average mean first passage time to that node:

C i R W C = n ∑ j = 1 n H ( j , i ) {\displaystyle C_{i}^{RWC}={\frac {n}{\sum _{j=1}^{n}H(j,i)}}}

where H ( j , i ) {\displaystyle H(j,i)} is the mean first passage time from node j to node i.

Mean first passage time The mean first passage time from node i to node j is the expected number of steps it takes for the process to reach node j from node i for the first time:

H ( i , j ) = ∑ r = 1 ∞ r P ( i , j , r ) {\displaystyle H(i,j)=\sum _{r=1}^{\infty }rP(i,j,r)}

where P(i,j,r) denotes the probability that it takes exactly r steps to reach j from i for the first time. To calculate these probabilities of reaching a node for the first time in r steps, it is useful to regard the target node as an absorbing one, and introduce a transformation of M by deleting its j-th row and column and denoting it by M − j {\displaystyle M_{-j}} . As the probability of a process starting at i and being in k after r-1 steps is simply given by the (i,k)th element of M − j r − 1 {\displaystyle M_{-j}^{r-1}} , P(i,j,r) can be expressed as

P ( i , j , r ) = ∑ k ≠ j ( ( M − j r − 1 ) ) i k m k j {\displaystyle P(i,j,r)=\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}}

Substituting this into the expression for mean first passage time yields

H ( i , j ) = ∑ r = 1 ∞ r ∑ k ≠ j ( ( M − j r − 1 ) ) i k m k j {\displaystyle H(i,j)=\sum _{r=1}^{\infty }r\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}}

Using the formula for the summation of geometric series for matrices yields

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Random walk closeness centrality

Start with the simplest possible case. Write down what Random walk closeness centrality claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Random walk closeness centrality before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Random walk closeness centrality ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Random walk closeness centrality

In research: Random walk closeness centrality appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Random walk closeness centrality in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Random walk closeness centrality is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph theory, so understanding it makes those chapters shorter.
In everyday life: Look for Random walk closeness centrality outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Random walk closeness centrality in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Random walk closeness centrality means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Random walk closeness centrality out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Random walk closeness centrality in simple terms?

Random walk closeness centrality is a measure of centrality in a network, which describes the average speed with which randomly walking processes reach a node from other nodes of the network. It is similar to the closeness centrality except that the farness is measured by the expected length of a r…

Why does Random walk closeness centrality matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Random walk closeness centrality?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Random walk closeness centrality.