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 Erdos.jl include the following:
Erdos.betweenness_centrality
Erdos.closeness_centrality
Erdos.cores
Erdos.degree_centrality
Erdos.in_degree_centrality
Erdos.katz_centrality
Erdos.kcore
Erdos.out_degree_centrality
Erdos.pagerank
Erdos.betweenness_centrality
— Methodbetweenness_centrality(g; normalize=true, endpoints=false, approx=-1)
Calculates the betweenness centrality of the vertices of graph g
.
Betweenness centrality for vertex v
is defined as:
\[bc(v) = \frac{1}{\mathcal{N}} \sum_{s \neq t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}},\]
where $\sigma _{st}} \sigma_{st}$ is the total number of shortest paths from node s
to node t
and $\sigma_{st}(v)$ is the number of those paths that pass through v
.
If endpoints=true
, endpoints are included in the shortest path count.
If normalize=true
, the betweenness values are normalized by the total number of possible distinct paths between all pairs in the graph. For an undirected graph, this number if ((n-1)*(n-2))/2
and for a directed graph, (n-1)*(n-2)
where n
is the number of vertices in the graph.
If an integer argument approx > 0
is given, returns an approximation of the betweenness centrality of each vertex of the graph involving approx
randomly chosen vertices.
References
[1] Brandes 2001 & Brandes 2008
Erdos.closeness_centrality
— MethodCalculates the closeness centrality of the graph g
.
Erdos.degree_centrality
— MethodCalculates the degree centrality of the graph g
, with optional (default) normalization.
Erdos.in_degree_centrality
— MethodCalculates the degree centrality of the graph g
, with optional (default) normalization.
Erdos.out_degree_centrality
— MethodCalculates the degree centrality of the graph g
, with optional (default) normalization.
Erdos.katz_centrality
— FunctionCalculates the Katz centrality of the graph g
.
Erdos.pagerank
— Functionpagerank(g::ADiGraph, α=0.85, n=100, ϵ = 1.0e-6)
Calculates the PageRank of the graph g
. Can optionally specify a different damping factor (α
), number of iterations (n
), and convergence threshold (ϵ
). If convergence is not reached within n
iterations, an error will be returned.
Erdos.cores
— Methodcores(g)
Returns a vector deg
such that if deg[v]=k
then the vertex v
belongs to the k
-core of g
and not to the k+1
-core.
See also kcore
.
Erdos.kcore
— Methodkcore(g, k) -> (gnew, vmap)
Returns the k
-core of g
along with a vertex map associating the mutated vertex indexes to the old ones (as in rem_vertices!
).
See also cores