Is this betweenness centrality?

No. Betweenness concerns paths through a node, while this measure concerns variation in random-walk return times.

Can the documented NetworkX function accept a disconnected graph?

Its stated requirements call for a connected graph, and disconnected input raises an exception.

Does a low score guarantee frequent real-world visits?

No. The score describes variability under a specified mathematical walk, not measured visitor frequency.

AI Glossary / Graphs and symbolic AI / Advanced

Second Order Centrality

Definition

Second order centrality is a network measure based on the standard deviation of the time between successive visits to a node by a specified random walk. In the NetworkX formulation, lower values indicate greater centrality, and the walk operates on a balanced transformation of the input graph.

What it means

Many centrality measures ask how many neighbors a node has or how often shortest paths pass through it. Second order centrality instead examines the regularity of return times under a random-walk model. The spread of those times, rather than merely their average, distinguishes nodes.

The word second refers to variability and second-moment information, not simply to counting friends of friends. A node with relatively regular returns receives a smaller score in this convention.

The walk definition is essential. NetworkX balances the graph by adding self-loops before computing the measure. Its output should not be described as the return-time variation of an ordinary unmodified walk on the original graph, because that can be a different process.

How it works

Begin with an appropriate connected, undirected network and meaningful edge weights. In the documented NetworkX procedure, balancing adds self-loop weight where necessary so that the transformed graph has equal total incoming weight at each node.

Normalize the resulting weights into transition probabilities. A self-loop means that a walk step can remain at the same node. The return-time random variable counts steps until the walk next visits the node in question, including the effect of these possible stays.

The implementation calculates the required quantities analytically through linear algebra rather than estimating them from a simulated walk. It returns a score for each node; sorting in ascending order places more central nodes first under this definition.

The documented implementation has cubic time complexity in the number of nodes, so computational suitability should be assessed before using it on a large network. Disconnected graphs and negative weights are outside its documented input conditions.

Three practical examples

A network researcher compares nodes using return-time variability alongside degree and shortest-path-based measures.
A team studying an undirected collaboration graph examines whether apparently well-connected nodes also have relatively regular returns under this model.
An analyst tests how removing or changing an edge affects centrality rankings, while reporting that the result describes a model rather than actual traffic.

Think of it this way

Think of repeatedly returning to a familiar meeting point during a random journey. Two places might have similar average revisit intervals but differ greatly in how irregular those intervals are.

The analogy concerns the spread of return times. It does not mean a business has measured actual visitors or that the modeled walk matches real human travel. The graph transformation also introduces stays that may not represent physical movement.

Worked example

Consider the three-node path A - B - C with unit edge weights. The middle node B has total weight two, while each endpoint has weight one. Balancing adds a self-loop of weight one at A and C.

The transformed walk stays at A with probability one-half or moves to B with probability one-half. From B it moves to either endpoint with probability one-half. C behaves symmetrically to A.

For returns to B, the first step goes to an endpoint. Each subsequent step there has probability one-half of returning to B. The return time is therefore one plus a geometric waiting time with success probability one-half. Its mean is three steps and its variance is two, giving standard deviation sqrt(2), approximately 1.414.

The corresponding analytical calculation gives each endpoint standard deviation sqrt(14), approximately 3.742. Thus B has the lower score and is more central by this measure. These values describe the balanced walk; using the original path without self-loops would be a different calculation.

Illustrative case study

In a fictional project, Cedar Networks adds a second order centrality column to an analysis dashboard. The default descending sort puts the largest values at the top, and the display calls those nodes “most central.”

A reviewer checks the definition and reverses that interpretation. The team also documents the balancing step and compares the result with other centrality measures rather than presenting one ranking as a universal importance score.

The case illustrates how an otherwise correct calculation can be miscommunicated through an assumed score direction. It does not establish actual operational criticality.

Common misconceptions and mistakes

Larger scores always mean more central nodes. The documented convention here is the opposite.
Second order centrality counts two-hop neighbors. It concerns return-time variability.
The average return time alone defines the measure. The standard deviation is central to the definition.
NetworkX simulates many random walks to obtain the score. Its documented implementation uses analytical computation.
The transformed walk is identical to the original graph's simple walk. Added self-loops can change return behavior.
A structural ranking proves business importance. That interpretation requires evidence about the network's meaning and use.

Business use

Use this measure when return regularity under a graph-based movement model is relevant to the analysis. Explain what nodes and edges represent and why an undirected model is appropriate.

Do not apply a familiar interpretation to weights without checking the walk. A distance or cost may not have the same meaning as a transition strength. The chosen representation affects the resulting scores.

For reporting, state that lower values indicate greater centrality and identify the implementation's transformation. Treat comparisons across differently sized or constructed networks cautiously; raw scores are not automatically normalized measures of organizational importance.

Check your understanding

Two nodes have second order centrality scores 2.1 and 4.8 under the same documented convention. Which is more central, and what quantity do the scores represent?

Answer: The node scoring 2.1 is more central. The scores are standard deviations of return times for the specified transformed random walk.

Related terms

Random walk
Standard deviation
return time
graph centrality
self-loop
transition matrix
betweenness centrality
network analysis

Learn next

Write the three-by-three transition matrix for the worked path after balancing. Compare it with the matrix before self-loops are added. Explain why a change in the walk can change return-time statistics even when the original node labels stay the same.

Sources

NetworkX second order centrality documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.second_order_centrality.html

Developer implementation: https://networkx.org/documentation/stable/_modules/networkx/algorithms/centrality/second_order.html

The documentation and relevant implementation were reviewed. The path example was independently checked with the displayed linear-algebra formula; Cedar Networks is fictional.

Previous: Second normal form (2NF) Next: Second-order co-occurrence pointwise mutual information