1
#' @title Majorization gap 
2
#' @description  Calculates the (normalized) majorization gap of an undirected graph. 
3
#' The majorization gap indicates how far the degree sequence of a graph is 
4
#' from a degree sequence of a [threshold_graph]. 
5
#'
6
#' @param g An igraph object
7
#' @param norm `True` (Default) if the normalized majorization gap should be returned.
8
#' @details The distance is measured by the number of \emph{reverse unit
9
#' transformations} necessary to turn the degree sequence into a threshold sequence.
10
#' First, the \emph{corrected conjugated degree sequence} d' is calculated from the degree sequence d as follows:
11
#' \deqn{d'_k= |\{ i : i<k \land d_i\geq k-1 \} | + 
12
#' | \{ i : i>k \land d_i\geq k \} |.} 
13
#' the majorization gap is then defined as
14
#' \deqn{1/2 \sum_{k=1}^n \max\{d'_k - d_k,0\}}
15
#' The higher the value, the further away is a graph to be a threshold graph.
16
#' @return Majorization gap of an undirected graph.
17
#' @author David Schoch
18
#' @references Schoch, D., Valente, T. W. and Brandes, U., 2017. Correlations among centrality
19
#' indices and a class of uniquely ranked graphs. *Social Networks* **50**, 46–54.
20
#' 
21
#' Arikati, S.R. and Peled, U.N., 1994. Degree sequences and majorization. 
22
#' *Linear Algebra and its Applications*, **199**, 179-211.
23
#' 
24
#' @examples
25
#' library(igraph)
26
#' g <- graph.star(5,'undirected')
27
#' majorization_gap(g) #0 since star graphs are threshold graphs
28
#'
29
#' g <- sample_gnp(100,0.15)
30
#' majorization_gap(g,norm=TRUE) #fraction of reverse unit transformation
31
#' majorization_gap(g,norm=FALSE) #number of reverse unit transformation
32
#' @export
33
majorization_gap <- function(g, norm = TRUE) {
34 2
    if(!igraph::is_connected(g)){
35 0
        warning("graph is not connected. Computing for each component separately and returning sum.")
36
    }
37 2
    comps <- igraph::components(g)
38 2
    if(comps$no>1){
39 0
        gap <- 0
40 0
        for(i in 1:comps$no){
41 0
            g1 <- igraph::induced_subgraph(g,which(comps$membership==i))
42 0
            if(igraph::ecount(g1)!=0){
43 0
                n <- igraph::vcount(g)
44 0
                deg.sorted <- sort(igraph::degree(g1), decreasing = TRUE)
45 0
                deg.cor <- sapply(1:n, function(k) {
46 0
                    length(which(deg.sorted[which((1:n) < k)] >= (k - 1))) + length(which(deg.sorted[which((1:n) > k)] >= k))
47
                })
48 0
                gap1 <- deg.cor - deg.sorted
49 0
                if (!norm) {
50 0
                    gap1 <- 0.5 * sum(gap1[gap1 >= 0])
51
                } else {
52 0
                    gap1 <- 0.5 * sum(gap1[gap1 >= 0])/igraph::ecount(g1)
53
                }
54 0
                gap <- gap+gap1
55
            }
56
        }
57
    } else{
58 2
        n <- igraph::vcount(g)
59 2
        deg.sorted <- sort(igraph::degree(g), decreasing = TRUE)
60 2
        deg.cor <- sapply(1:n, function(k) {
61 2
            length(which(deg.sorted[which((1:n) < k)] >= (k - 1))) + length(which(deg.sorted[which((1:n) > k)] >= k))
62
        })
63 2
        gap <- deg.cor - deg.sorted
64 2
        if (!norm) {
65 2
            gap <- 0.5 * sum(gap[gap >= 0])
66
        } else {
67 2
            gap <- 0.5 * sum(gap[gap >= 0])/igraph::ecount(g)
68
        }
69
    }
70 2
    return(gap)
71
}

Read our documentation on viewing source code .

Loading