Centrality measures
Graphs.jl implements various centrality measures, which describe the importance of a vertex to the rest of the graph.
Index
Graphs.betweenness_centrality
Graphs.closeness_centrality
Graphs.degree_centrality
Graphs.eigenvector_centrality
Graphs.katz_centrality
Graphs.pagerank
Graphs.radiality_centrality
Graphs.stress_centrality
Full docs
Graphs.betweenness_centrality
— Functionbetweenness_centrality(g[, vs])
betweenness_centrality(g, k)
Calculate the betweenness centrality of a graph g
across all vertices, a specified subset of vertices vs
, or a random subset of k
vertices. Return a vector representing the centrality calculated for each node in g
.
Optional Arguments
normalize=true
: If true, normalize the betweenness values by the
total number of possible distinct paths between all pairs in the graphs. For an undirected graph, this number is $\frac{(|V|-1)(|V|-2)}{2}$ and for a directed graph, ${(|V|-1)(|V|-2)}$.
endpoints=false
: If true, include endpoints in the shortest path count.
Betweenness centrality is defined as: $bc(v) = \frac{1}{\mathcal{N}} \sum_{s \neq t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}}$.
References
- Brandes 2001 & Brandes 2008
Examples
julia> using Graphs
julia> betweenness_centrality(star_graph(3))
3-element Vector{Float64}:
1.0
0.0
0.0
julia> betweenness_centrality(path_graph(4))
4-element Vector{Float64}:
0.0
0.6666666666666666
0.6666666666666666
0.0
Graphs.closeness_centrality
— Functioncloseness_centrality(g, distmx=weights(g); normalize=true)
Calculate the closeness centrality of the graph g
. Return a vector representing the centrality calculated for each node in g
.
Optional Arguments
normalize=true
: If true, normalize the centrality value of each
node n
by $\frac{|δ_n|}{|V|-1}$, where $δ_n$ is the set of vertices reachable from node n
.
Examples
julia> using Graphs
julia> closeness_centrality(star_graph(5))
5-element Vector{Float64}:
1.0
0.5714285714285714
0.5714285714285714
0.5714285714285714
0.5714285714285714
julia> closeness_centrality(path_graph(4))
4-element Vector{Float64}:
0.5
0.75
0.75
0.5
Graphs.degree_centrality
— Methoddegree_centrality(g)
indegree_centrality(g)
outdegree_centrality(g)
Calculate the degree centrality of graph g
. Return a vector representing the centrality calculated for each node in g
.
Optional Arguments
normalize=true
: If true, normalize each centrality measure by $\frac{1}{|V|-1}$.
Examples
julia> using Graphs
julia> degree_centrality(star_graph(4))
4-element Vector{Float64}:
1.0
0.3333333333333333
0.3333333333333333
0.3333333333333333
julia> degree_centrality(path_graph(3))
3-element Vector{Float64}:
0.5
1.0
0.5
Graphs.eigenvector_centrality
— Methodeigenvector_centrality(g)
Compute the eigenvector centrality for the graph g
.
Eigenvector centrality computes the centrality for a node based on the centrality of its neighbors. The eigenvector centrality for node i
is the $i^{th}$ element of $\mathbf{x}$ in the equation $\mathbf{Ax} = λ \mathbf{x}$ where $\mathbf{A}$ is the adjacency matrix of the graph g
with eigenvalue λ.
By virtue of the Perron–Frobenius theorem, there is a unique and positive solution if λ is the largest eigenvalue associated with the eigenvector of the adjacency matrix $\mathbf{A}$.
References
- Phillip Bonacich: Power and Centrality: A Family of Measures. American Journal of Sociology 92(5):1170–1182, 1986 http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf
- Mark E. J. Newman: Networks: An Introduction. Oxford University Press, USA, 2010, pp. 169.
Graphs.katz_centrality
— Functionkatz_centrality(g, α=0.3)
Calculate the Katz centrality of the graph g
optionally parameterized by α
. Return a vector representing the centrality calculated for each node in g
.
Graphs.pagerank
— Methodpagerank(g, α=0.85, n=100, ϵ=1.0e-6)
Calculate the PageRank of the graph g
parameterized by damping factor α
, number of iterations n
, and convergence threshold ϵ
. Return a vector representing the centrality calculated for each node in g
, or an error if convergence is not reached within n
iterations.
Graphs.radiality_centrality
— Methodradiality_centrality(g)
Calculate the radiality centrality of a graph g
across all vertices. Return a vector representing the centrality calculated for each node in g
.
The radiality centrality $R_u$ of a vertex $u$ is defined as $R_u = \frac{D_g + 1 - \frac{\sum_{v∈V}d_{u,v}}{|V|-1}}{D_g}$
where $D_g$ is the diameter of the graph and $d_{u,v}$ is the length of the shortest path from $u$ to $v$.
References
- Brandes, U.: A faster algorithm for betweenness centrality. J Math Sociol 25 (2001) 163-177
Examples
julia> using Graphs
julia> radiality_centrality(star_graph(4))
4-element Vector{Float64}:
1.0
0.6666666666666666
0.6666666666666666
0.6666666666666666
julia> radiality_centrality(path_graph(3))
3-element Vector{Float64}:
0.75
1.0
0.75
Graphs.stress_centrality
— Functionstress_centrality(g[, vs])
stress_centrality(g, k)
Calculate the stress centrality of a graph g
across all vertices, a specified subset of vertices vs
, or a random subset of k
vertices. Return a vector representing the centrality calculated for each node in g
.
The stress centrality of a vertex $n$ is defined as the number of shortest paths passing through $n$.
References
- Barabási, A.L., Oltvai, Z.N.: Network biology: understanding the cell's functional organization. Nat Rev Genet 5 (2004) 101-113
- Shimbel, A.: Structural parameters of communication networks. Bull Math Biophys 15 (1953) 501-507.
Examples
julia> using Graphs
julia> stress_centrality(star_graph(3))
3-element Vector{Int64}:
2
0
0
julia> stress_centrality(cycle_graph(4))
4-element Vector{Int64}:
2
2
2
2