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 : ik \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 .