Measuring Influence With Degree And Betweenness

Two Ways to Measure a Vertex’s Position

In a social network, a person with many direct contacts may occupy a different position from someone who connects otherwise distant groups. Degree measures the first feature: how many neighbors a vertex has. Betweenness measures a particular kind of intermediary position: how often a vertex lies inside shortest paths between other vertices. These measures describe the graph that has been modeled; neither one, on its own, establishes a person’s actual influence.

Throughout, a network is a finite, simple, undirected, unweighted graph $G=(V,E)$. An edge represents a direct connection, and path length is the number of edges. A shortest path between two vertices is a path of minimum length. For distinct vertices $s,t$, let $\sigma_{st}$ be the number of shortest $s$-$t$ paths. For a third vertex $v$, let $\sigma_{st}(v)$ count those shortest paths on which $v$ occurs as an internal vertex—that is, not as either endpoint.

Definition: The degree centrality of $v$ is its degree $d(v)=\deg(v)$, the number of vertices adjacent to it. For a graph of order $n\ge2$, its normalized degree centrality is $C_D(v)=d(v)/(n-1)$. The betweenness centrality of $v$ is $$ C_B(v)=\sum_{\substack{\{s,t\}\subseteq V\setminus\{v\}\\s\ne t,\ \sigma_{st}>0}}\frac{\sigma_{st}(v)}{\sigma_{st}}. $$ The sum is over unordered pairs of distinct vertices other than $v$ that are connected by a path. A disconnected pair contributes zero. When $n\ge3$, normalized betweenness is $C_B(v)/\binom{n-1}{2}$.

The fraction in the betweenness formula shares credit among tied shortest paths. If two shortest paths connect $s$ to $t$, and exactly one passes through $v$ internally, that pair contributes $1/2$ to $v$. A vertex that is an endpoint of a pair is never counted as lying internally on a path for that pair. We will use this distinction explicitly in the calculations.

What the Measures Guarantee

Proposition: For $n\ge2$, $0\le C_D(v)\le1$, and $C_D(v)=1$ if and only if $v$ is adjacent to every other vertex.

Proof. There are exactly $n-1$ other vertices, and $d(v)$ counts how many of them are adjacent to $v$. Thus $0\le d(v)\le n-1$, and division by the positive number $n-1$ gives $0\le C_D(v)\le1$. The equality $C_D(v)=1$ holds exactly when $d(v)=n-1$, which holds exactly when all other vertices are adjacent to $v$. $\square$

Proposition: For $n\ge2$, $0\le C_B(v)\le\binom{n-1}{2}$. For $n\ge3$, the normalized betweenness lies between $0$ and $1$.

Proof. There are $\binom{n-1}{2}$ unordered pairs of distinct vertices other than $v$. For any such pair that is connected, every shortest path either contains $v$ internally or does not. Therefore $0\le\sigma_{st}(v)\le\sigma_{st}$, so its contribution $\sigma_{st}(v)/\sigma_{st}$ lies between $0$ and $1$. A disconnected pair contributes zero by convention. Summing at most one for each of the $\binom{n-1}{2}$ pairs proves the bound. When $n\ge3$, the normalizing denominator is positive, so dividing the bound by it gives a value between $0$ and $1$. $\square$

Degree is local: it uses only the edges incident with $v$. Betweenness depends on paths throughout the graph, and it can be fractional even though the graph itself has no fractional edges. In both measures, a larger score means a larger value under that chosen definition, not an automatic conclusion about authority, trust, or the ability to affect other people.

Calculating Both Measures

Worked Example: A Bridge Between Two Parts of a Network

Let $G=(V,E)$, where $V=\{A,B,C,D,E\}$ and $E=\{AB,AC,BC,CD,DE\}$. Compute degree and betweenness for every vertex, then compare the rankings.

The degrees are $d(A)=2$, from $AB,AC$; $d(B)=2$, from $AB,BC$; $d(C)=3$, from $AC,BC,CD$; $d(D)=2$, from $CD,DE$; and $d(E)=1$, from $DE$. Since $n-1=4$, their normalized degree centralities are $2/4=1/2$, $2/4=1/2$, $3/4$, $2/4=1/2$, and $1/4$, respectively.

To compute betweenness, list all ten unordered vertex pairs and their shortest paths. The paths are unique in this graph. The pairs $AB,AC,BC,CD,DE$ are adjacent pairs, so their shortest paths have no internal vertices. For the other pairs, the paths are $A-C-D$ for $AD$, $A-C-D-E$ for $AE$, $B-C-D$ for $BD$, $B-C-D-E$ for $BE$, and $C-D-E$ for $CE$.

Thus $C$ is internal on exactly $AD,AE,BD,BE$, giving $C_B(C)=1+1+1+1=4$. Vertex $D$ is internal on $AE,BE,CE$, giving $C_B(D)=1+1+1=3$. None of the listed shortest paths has $A$, $B$, or $E$ internally, so $C_B(A)=C_B(B)=C_B(E)=0$.

Check: The degree sum is $2+2+3+2+1=10$, which equals $2|E|=2\cdot5=10$. For betweenness, the full list of ten pairs shows that the internal-vertex counts are four for $C$, three for $D$, and zero for the others. The rankings differ: $C$ has the largest degree and betweenness, but $A,B,D$ tie in degree while $D$ has positive betweenness and $A,B$ have none.

In this example, the bridge-like position of $C$ is reflected in both measures, while $D$ has fewer neighbors but still lies on several shortest paths. The calculation uses shortest paths in the whole network, not just the edges incident with the vertex being scored.

Worked Example: Sharing Credit Across Tied Shortest Paths

Let $G=(V,E)$, where $V=\{P,Q,R,S\}$ and $E=\{PQ,PR,QS,RS\}$. This is a four-cycle. Compute both measures, taking account of the fact that some pairs have more than one shortest path.

Each vertex has degree $2$, so every normalized degree centrality is $2/(4-1)=2/3$. There are six unordered pairs. The adjacent pairs $PQ,PR,QS,RS$ have a unique shortest path of length $1$. The pair $P,S$ has two shortest paths of length $2$, namely $P-Q-S$ and $P-R-S$. The pair $Q,R$ also has two shortest paths of length $2$, namely $Q-P-R$ and $Q-S-R$.

For $P$, only the pair $Q,R$ contributes: one of its two shortest paths has $P$ internally, so $C_B(P)=1/2$. For $S$, only $Q,R$ contributes, again by $1/2$, so $C_B(S)=1/2$. For $Q$, the pair $P,S$ contributes $1/2$, and no other pair has $Q$ internally, so $C_B(Q)=1/2$. For $R$, the pair $P,S$ contributes $1/2$, giving $C_B(R)=1/2$. Since $\binom{3}{2}=3$, each normalized betweenness is $(1/2)/3=1/6$.

Check: The two nonadjacent pairs each have two internal vertices across their two shortest paths: for $P,S$, the paths have internal vertices $Q$ and $R$; for $Q,R$, they have internal vertices $P$ and $S$. Each pair therefore contributes a total of $1$ across all vertices, giving total betweenness $2$. The four individual scores sum to $1/2+1/2+1/2+1/2=2$, as required by that count.

Worked Example: A Disconnected Network

Let $G=(V,E)$, where $V=\{1,2,3,4,5\}$ and $E=\{12,13,23,45\}$. Compute the degree and betweenness scores, using the convention that disconnected pairs contribute zero.

Vertices $1,2,3$ each have degree $2$, and vertices $4,5$ each have degree $1$. Because $n-1=4$, the normalized degree centralities are $2/4=1/2$ for each of $1,2,3$, and $1/4$ for each of $4,5$.

The connected pairs are $12,13,23,45$. Each is an edge, so its unique shortest path has no internal vertex. The six pairs with one endpoint in $\{1,2,3\}$ and one in $\{4,5\}$ are disconnected, so each contributes zero. Therefore every vertex has betweenness zero. There are $\binom{4}{2}=6$ possible pairs of other vertices for each vertex, so normalized betweenness is also zero for every vertex.

Check: The degree sum is $2+2+2+1+1=8$, equal to $2|E|=2\cdot4=8$. The only connected pairs have direct shortest paths, and the remaining pairs are assigned zero; hence no shortest path counted in the formula has an internal vertex.

Interpreting the Rankings Carefully

Degree and betweenness answer different questions. Degree asks, “How many direct neighbors does this vertex have?” Betweenness asks, “For how many other pairs does a shortest path pass through this vertex, with ties sharing the credit?” In the first example, $D$ has degree $2$, tied with $A$ and $B$, but its betweenness is $3$, while theirs is $0$. In the four-cycle, all vertices tie under both measures; fractional contributions prevent an arbitrary choice between equally short routes.

Normalization makes scores easier to compare across graphs of different orders, but only when the definition is stated. Here, normalized degree divides by $n-1$, and normalized betweenness divides by $\binom{n-1}{2}$. The betweenness denominator counts all possible pairs of other vertices, including disconnected pairs. Other conventions may normalize using only connected pairs, so a reported score should be interpreted with its convention in view. For $n=1$, normalized degree is undefined under the stated formula because $n-1=0$; for $n<3$, we do not define normalized betweenness by the displayed denominator.

Most importantly, a graph records a chosen representation of relationships. If edges mean “has exchanged a message with,” the scores measure positions in that exchange network. They do not show how important the messages were, whether the relationship is reciprocal, or whether changing one person’s position would cause a real-world outcome. A person can have many recorded contacts without being persuasive, and a person with high betweenness may not control or even know about the paths counted. The measures are useful summaries for a specified graph, not complete models of human influence.

Common Mistakes

Counting an endpoint as an intermediary. In the first example, $A$ is an endpoint of the pair $AC$, so $AC$ cannot contribute to $C_B(C)$. The correct pairs on whose shortest paths $C$ is internal are $AD,AE,BD,BE$, giving $C_B(C)=4$, not $5$. Always remove the vertex being scored from the set of possible pair endpoints before counting paths.

Choosing just one of several shortest paths. In the four-cycle, assigning the whole $P,S$ contribution to $Q$ would depend on an arbitrary choice between $P-Q-S$ and $P-R-S$. The definition instead assigns $1/2$ to each internal vertex for that pair.

Treating disconnected pairs as if a path existed. In the third example, a pair with one vertex in each component has no shortest path. Its contribution is zero; it is not counted as a path through any vertex.

Check Your Understanding

Use the definitions and conventions in this tutorial. Show your pair counts when computing betweenness.

In the graph with $V=\{a,b,c,d\}$ and $E=\{ab,bc,cd\}$, calculate every vertex’s degree and betweenness.
For the four-cycle in the second example, what fraction does each of its two shortest paths contribute to betweenness for the pair $P,S$?
Explain why the pair $AC$ in the first example does not contribute to $C_B(C)$.
Give the normalized degree centrality of a vertex of degree $3$ in a graph of order $7$.
Why does a zero betweenness score in the disconnected-network example not imply that the vertex has no direct connections?