In a graph, some vertex can have a higher importance than others. Importance can have a wide range
of meaning, from the type of flow through the network [Bor05], to the involvement of the cohesion in
the network [BE06], or even the topological position in the network [Bav50]. Indicators
of centrality can be used to assign a number or a ranking to vertices, according to their
position in the network, identifying the importance of the vertices in a graph [Fre78; Bor05;
Gha18].
In terms of centrality, this thesis focuses on the three following centralities based on the shortest
path:
Degree centrality: the degree centrality is defined as the number of neighbors of a
process.
Closeness centrality: the closeness centrality, or closeness, of a vertex, is the average
length of the shortest path between the vertex and all other vertices in the graph [Bav50].
The more central is a vertex, the closer it is to all other vertices. The closeness centrality
characterizes the ability of a node to spread information over the graph.
Alex Balevas [Bav50] defined in 1950 the closeness centrality of a vertex as follows [Sab66]:
where d(y,x) is the shortest path between vertex y and vertex x.
Betweenness centrality: the betweenness centrality measures the number of times a
vertex acts as a relay (router) along shortest paths between other vertices. Even if previous
authors have intuitively described centrality as being based on betweenness, betweenness
centrality was formally defined by Freeman in 1977 [Fre77].
The betweenness of a vertex x is defined as the sum, for each pair of vertices (s,t), of
the number of shortest paths from s to t that pass through x, over the total number of
shortest paths between vertices s and t,
It can be represented by the following formula [Bra01]:
where σst denotes the total number of shortest paths from vertex s to vertex t (with
σss = 1 by convention), and σst(x) is the number of those shorter paths that pass through
x.
A visual representation given in 2.8 compares the degree centrality with the closeness centrality and
the betweenness centrality of the same graph [Tap15].
Figure 2.8: Comparison between degree centrality, closeness centrality and betweenness
centrality of the same graph, by Tapiocozzo [Tap15]
The more red a vertex is, the higher its centrality. The more blue a vertex is, the lower its
centrality. In 2.8, the most central vertex for the degree centrality is different than for the closeness
and betweenness centrality. However, closeness and betweenness centrality are not always
equal.
The differences between closeness and betweenness centrality are the following: closeness is
generally regarded as a measure of access efficiency, i.e. how long it will take to spread information
from x to all other vertices sequentially; whereas betweenness is usually interpreted as a measure of the
dependence of others on a given vertex, i.e. the number of times a vertex is present on the shortest
path between two other vertices [BBF16; Du19].
