1
#' @title Neighborhood-inclusion preorder
2
#' @description Calculates the neighborhood-inclusion preorder of an undirected graph.
3
#' @param g An igraph object
4
#' @details Neighborhood-inclusion is defined as
5
#' \deqn{N(u)\subseteq N[v]}
6
#' where \eqn{N(u)} is the neighborhood of \eqn{u} and \eqn{N[v]=N(v)\cup \lbrace v\rbrace} is the closed neighborhood of \eqn{v}.
7
#' \eqn{N(u) \subseteq N[v]} implies that \eqn{c(u) \leq c(v)},
8
#' where \eqn{c} is a centrality index based on a specific path algebra. Indices 
9
#' falling into this category are closeness (and variants), betweenness 
10
#' (and variants) as well as many walk-based indices (eigenvector and subgraph 
11
#' centrality, total communicability,...). 
12
#' @return The neighborhood-inclusion preorder of \code{g} as matrix object. \code{P[u,v]=1} if \eqn{N(u)\subseteq N[v]}
13
#' @author David Schoch
14
#' @references Schoch, D. and Brandes, U., 2016. Re-conceptualizing centrality in social networks. 
15
#' *European Journal of Applied Mathematics* 27(6), 971-985.
16
#' 
17
#' Brandes, U. Heine, M., Müller, J. and Ortmann, M., 2017.
18
#' Positional Dominance: Concepts and Algorithms. 
19
#' *Conference on Algorithms and Discrete Applied Mathematics*, 60-71.
20
#' 
21
#' 
22
#' 
23
#' 
24
#' @seealso [positional_dominance], [exact_rank_prob]
25
#' @examples
26
#' library(igraph)
27
#' #the neighborhood inclusion preorder of a star graph is complete
28
#' g <- graph.star(5,'undirected')
29
#' P <- neighborhood_inclusion(g)
30
#' comparable_pairs(P)
31
#' 
32
#' #the same holds for threshold graphs
33
#' tg <- threshold_graph(50,0.1)
34
#' P <- neighborhood_inclusion(tg)
35
#' comparable_pairs(P)
36
#' 
37
#' #standard centrality indices preserve neighborhood-inclusion
38
#' g <- graph.empty(n=11,directed = FALSE)
39
#' g <- add_edges(g,c(1,11,2,4,3,5,3,11,4,8,5,9,5,11,6,7,6,8,
40
#'                    6,10,6,11,7,9,7,10,7,11,8,9,8,10,9,10))
41
#' P <- neighborhood_inclusion(g)
42
#' 
43
#' is_preserved(P,degree(g))
44
#' is_preserved(P,closeness(g))
45
#' is_preserved(P,betweenness(g))
46
#' @export
47
neighborhood_inclusion <- function(g) {
48 1
    adj <- lapply(igraph::get.adjlist(g), function(x) x - 1)
49 1
    deg <- igraph::degree(g)
50 1
    dom <- nialgo(adj, deg)
51 1
    if(!is.null(igraph::V(g)$name) ){
52 0
      rownames(dom) <- colnames(dom) <- igraph::V(g)$name
53
    }
54 1
    return(dom)
55
}

Read our documentation on viewing source code .

Loading