Description Usage Arguments Details Value Author(s) References Examples
View source: R/majorization.gap.R
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.
1  majorization_gap(g, norm = TRUE)

g 
An igraph object 
norm 

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≥q k1 \}  +  \{ i : i>k \land d_i≥q k \} .
the majorization gap is then defined as
1/2 ∑_{k=1}^n \max\{d'_k  d_k,0\}
The higher the value, the further away is a graph to be a threshold graph.
Majorization gap of an undirected graph.
David Schoch
Schoch, D., Valente, T. W. and Brandes, U., 2017. Correlations among centrality indices and a class of uniquely ranked graphs. Social Networks 50, 46–54.
Arikati, S.R. and Peled, U.N., 1994. Degree sequences and majorization. Linear Algebra and its Applications, 199, 179211.
1 2 3 4 5 6 7  library(igraph)
g < graph.star(5, "undirected")
majorization_gap(g) # 0 since star graphs are threshold graphs
g < sample_gnp(100, 0.15)
majorization_gap(g, norm = TRUE) # fraction of reverse unit transformation
majorization_gap(g, norm = FALSE) # number of reverse unit transformation

Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.