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
#
LightGraphs.betweenness_centrality — Function
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#
LightGraphs.closeness_centrality — Function
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#
LightGraphs.degree_centrality — Method
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#
LightGraphs.eigenvector_centrality — Method
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
-
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.
#
LightGraphs.katz_centrality — Function
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.
#
LightGraphs.pagerank — Method
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.
#
LightGraphs.stress_centrality — Function
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#
LightGraphs.radiality_centrality — Method
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