1
#' @title Random threshold graphs
2
#' @description  Constructs a random threshold graph. 
3
#' A threshold graph is a graph where the neighborhood inclusion preorder is complete.
4
#' @param n The number of vertices in the graph.
5
#' @param p The probability of inserting dominating vertices. Equates approximately 
6
#'     to the density of the graph. See Details.
7
#' @param bseq (0,1)-vector a binary sequence that produces a threshold grah. See details
8
#' @details Either `n` and `p` must be specified or `bseq`.
9
#' Threshold graphs can be constructed with a binary sequence. For each 0, an isolated 
10
#' vertex is inserted and for each 1, a vertex is inserted that connects to all previously inserted 
11
#' vertices. The probability of inserting a dominating vertices is controlled with parameter `p`.
12
#' If `bseq` is gicen instead, a threshold graph is constructed from that sequence.
13
#' An important property of threshold graphs is, that all centrality indices induce the same ranking.
14
#' @return A threshold graph as igraph object
15
#' @author David Schoch
16
#' @references Mahadev, N. and Peled, U. N. , 1995. Threshold graphs and related topics.
17
#' 
18
#' 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
#' @seealso [neighborhood_inclusion], [positional_dominance]
22
#' @examples
23
#' library(igraph)
24
#' g <- threshold_graph(10,0.3)
25
#' \dontrun{
26
#' plot(g)
27
#' 
28
#' # star graphs and complete graphs are threshold graphs
29
#' complete <- threshold_graph(10,1) #complete graph
30
#' plot(complete)
31
#' 
32
#' star <- threshold_graph(10,0) #star graph
33
#' plot(star)
34
#' }
35
#' 
36
#' # centrality scores are perfectly rank correlated
37
#' cor(degree(g),closeness(g),method = "kendall")
38
#' @export
39
threshold_graph <- function(n, p,bseq) {
40 2
  if(missing(n) & missing(bseq)){
41 2
    stop('Either specify both n and p, or bseq ')
42
  }
43 2
  if(missing(p) & missing(bseq)){
44 2
    stop('Either specify both n and p, or bseq ')
45
  }
46
  
47 2
  if(!missing(n) & !missing(p)){
48 2
    vschedule <- rep(0, n)
49 2
    pvals <- stats::runif(n)
50
    
51 2
    vschedule[pvals <= p] <- 1
52 2
    vschedule[n] <- 1
53 2
    vschedule[1] <- 0
54 0
  } else if(!missing(bseq)){
55 0
    n <- length(bseq)
56 0
    if(bseq[n]==0){
57 0
      warning("bseq[n]=0 produces unconnected graphs. using bseq[n]=1 instead")
58 0
      bseq[n] <- 1
59
    }
60 0
    vschedule <- bseq
61 0
    vschedule[1] <- 0
62
    
63
  }
64 2
  dom_vertices <- which(vschedule == 1)
65 2
  if (length(dom_vertices) != 1) {
66 2
      edgelist <- do.call(rbind, sapply(dom_vertices, function(v) cbind(rep(v, (v - 1)), seq(1, (v - 1)))))
67
      
68
  } else {
69 2
      edgelist <- cbind(rep(n, (n - 1)), seq(1, (n - 1)))
70
  }
71 2
  g <- igraph::graph_from_edgelist(edgelist, directed = FALSE)
72 2
  g$sequence <- vschedule
73 2
  return(g)
74
}

Read our documentation on viewing source code .

Loading