Centrality Measures

betweenness_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 LightGraphs

julia> betweenness_centrality(StarGraph(3))
3-element Array{Float64,1}:
 1.0
 0.0
 0.0

julia> betweenness_centrality(PathGraph(4))
4-element Array{Float64,1}:
 0.0
 0.6666666666666666
 0.6666666666666666
 0.0

closeness_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 LightGraphs

julia> closeness_centrality(StarGraph(5))
5-element Array{Float64,1}:
 1.0
 0.5714285714285714
 0.5714285714285714
 0.5714285714285714
 0.5714285714285714

julia> closeness_centrality(PathGraph(4))
4-element Array{Float64,1}:
 0.5
 0.75
 0.75
 0.5

degree_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 LightGraphs

julia> degree_centrality(StarGraph(4))
4-element Array{Float64,1}:
 1.0               
 0.3333333333333333
 0.3333333333333333
 0.3333333333333333

julia> degree_centrality(PathGraph(3))
3-element Array{Float64,1}:
 0.5
 1.0
 0.5

eigenvector_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.

katz_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.

pagerank(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.

stress_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 LightGraphs

julia> stress_centrality(StarGraph(3))
3-element Array{Int64,1}:
 2
 0
 0

julia> stress_centrality(CycleGraph(4))
4-element Array{Int64,1}:
 2
 2
 2
 2

radiality_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 LightGraphs

julia> radiality_centrality(StarGraph(4))
4-element Array{Float64,1}:
 1.0               
 0.6666666666666666
 0.6666666666666666
 0.6666666666666666

julia> radiality_centrality(PathGraph(3))
3-element Array{Float64,1}:
 0.75
 1.0 
 0.75