majorization_gap: Majorization gap

In netrankr: Analyzing Partial Rankings in Networks

Majorization gap

Description

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.

Usage

majorization_gap(g, norm = TRUE)

Arguments

g	An igraph object
norm	True (Default) if the normalized majorization gap should be returned.

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.

Value

Majorization gap of an undirected graph.

Author(s)

David Schoch

References

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, 179-211.

Examples

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

netrankr documentation built on May 29, 2024, 4:19 a.m.