Engee documentation

Centrality Measures

Centrality measures describe the importance of a vertex to the rest of the graph using some set of criteria. Centrality measures implemented in LightGraphs.jl include the following:

Full docs

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 and for a directed graph, .

  • endpoints=false: If true, include endpoints in the shortest path count.

Betweenness centrality is defined as: .

References

  • Brandes 2001 & Brandes 2008

Examples

julia> using LightGraphs

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

julia> betweenness_centrality(path_graph(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 , where is the set of vertices reachable from node n.

Examples

julia> using LightGraphs

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

julia> closeness_centrality(path_graph(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 .

Examples

julia> using LightGraphs

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

julia> degree_centrality(path_graph(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 element of in the equation where 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 .

References

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 is defined as the number of shortest paths passing through .

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(star_graph(3))
3-element Array{Int64,1}:
 2
 0
 0

julia> stress_centrality(cycle_graph(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 of a vertex is defined as

where is the diameter of the graph and is the length of the shortest path from to .

References

  • Brandes, U.: A faster algorithm for betweenness centrality. J Math Sociol 25 (2001) 163-177

Examples

julia> using LightGraphs

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

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