Calculates the neighborhood-inclusion preorder of an undirected graph.

neighborhood_inclusion(g)

g | An igraph object |
---|

The neighborhood-inclusion preorder of `g`

as matrix object. `P[u,v]=1`

if \(N(u)\subseteq N[v]\)

Neighborhood-inclusion is defined as $$N(u)\subseteq N[v]$$ where \(N(u)\) is the neighborhood of \(u\) and \(N[v]=N(v)\cup \lbrace v\rbrace\) is the closed neighborhood of \(v\). \(N(u) \subseteq N[v]\) implies that \(c(u) \leq c(v)\), where \(c\) is a centrality index based on a specific path algebra. Indices falling into this category are closeness (and variants), betweenness (and variants) as well as many walk-based indices (eigenvector and subgraph centrality, total communicability,...).

Schoch, D. and Brandes, U., 2016. Re-conceptualizing centrality in social networks.
*European Journal of Applied Mathematics* 27(6), 971-985.

Brandes, U. Heine, M., Müller, J. and Ortmann, M., 2017.
Positional Dominance: Concepts and Algorithms.
*Conference on Algorithms and Discrete Applied Mathematics*, 60-71.

library(igraph) #the neighborhood inclusion preorder of a star graph is complete g <- graph.star(5,'undirected') P <- neighborhood_inclusion(g) comparable_pairs(P)#> [1] 1#the same holds for threshold graphs tg <- threshold_graph(50,0.1) P <- neighborhood_inclusion(tg) comparable_pairs(P)#> [1] 1#standard centrality indices preserve neighborhood-inclusion g <- graph.empty(n=11,directed = FALSE) g <- add_edges(g,c(1,11,2,4,3,5,3,11,4,8,5,9,5,11,6,7,6,8, 6,10,6,11,7,9,7,10,7,11,8,9,8,10,9,10)) P <- neighborhood_inclusion(g) is_preserved(P,degree(g))#> [1] TRUE#> [1] TRUE#> [1] TRUE