Calculates the (normalized) majorization gap of an undirected graph. The majorization gap indicates how far the degree sequence of a graph is from a degree sequence of a threshold_graph.

majorization_gap(g, norm = TRUE)

## Arguments

g

An igraph object

norm

True (Default) if the normalized majorization gap should be returned.

## Value

Majorization gap of an undirected graph.

## Details

The distance is measured by the number of reverse unit transformations necessary to turn the degree sequence into a threshold sequence. First, the corrected conjugated degree sequence d' is calculated from the degree sequence d as follows: $$d'_k= |\{ i : i<k \land d_i\geq k-1 \} | + | \{ i : i>k \land d_i\geq k \} |.$$ the majorization gap is then defined as $$1/2 \sum_{k=1}^n \max\{d'_k - d_k,0\}$$ The higher the value, the further away is a graph to be a threshold graph.

David Schoch

## Examples

library(igraph)
g <- graph.star(5, "undirected")
majorization_gap(g) # 0 since star graphs are threshold graphs
#>  0

g <- sample_gnp(100, 0.15)
majorization_gap(g, norm = TRUE) # fraction of reverse unit transformation
#>  0.7635328
majorization_gap(g, norm = FALSE) # number of reverse unit transformation
#>  536