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 — Method.

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

source

# Erdos.closeness_centrality — Method.

Calculates the closeness centrality of the graph g.

source

# Erdos.degree_centrality — Method.

Calculates the degree centrality of the graph g, with optional (default) normalization.

source

# Erdos.in_degree_centrality — Method.

Calculates the degree centrality of the graph g, with optional (default) normalization.

source

# Erdos.out_degree_centrality — Method.

Calculates the degree centrality of the graph g, with optional (default) normalization.

source

# Erdos.katz_centrality — Function.

Calculates the Katz centrality of the graph g.

source

# Erdos.pagerank — Function.

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

source

# Erdos.cores — Method.

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