The extension nctx provides functionality to analyze attributed networks. Unique feature of this extension is the ability to enforce contextual constraints via user-defined functions during shortest path discovery and centrality calculation. More info and full documentation can be found here
The source code is accessible on github.
You can install the released version of nctx from github with:
library(devtools)
install_github("nctx/rnctx")
This is a basic example of how to process attributed networks. For the creation of the graph, there are three choices: create the graph from scratch, load it from a file (in the GraphML format), or copy it from igraph.
This example shows how to do things from scratch.
require(nctx)
g <- create_graph(directed=FALSE)
# This instantiates the network proposed in
# Ulrik Brandes, Jan Hildebrand: Smallest graphs with distinct singleton centers,
# Network Science 2 (2014), 3., S. 416-418
sapply(1:10,function(x){add_vertex(g)})
add_edge(g, 1, 2)
add_edge(g, 2, 3)
add_edge(g, 3, 4)
add_edge(g, 4, 5)
add_edge(g, 3, 5)
add_edge(g, 5, 9)
add_edge(g, 6, 4)
add_edge(g, 7, 4)
add_edge(g, 2, 6)
add_edge(g, 8, 2)
add_edge(g, 9, 4)
add_edge(g, 3, 10)
add_edge(g, 10, 5)
add_edge(g, 10, 9)
Next to our graph we create a list of attributes or context information
context <- c(1,1,0,1,1,1,1,0,1,0)This is a very simple example of a bool-attriute associated with each node (the third entry in this list yields the attribute of the third vertex in g and so on).
The unique feature of nctx comes here: Define a function that is evaluated at each node during shortest path discovery. Therefore, the function has to accept three parameters: the start vertex, the current, and the next vertex. It must evaluate to bool in order to guide edge traversal.
decision_fct <- function(strt, crnt, nxt){
context[crnt] == context[nxt]
}Here, we use an edge only if its source and end vertex have the same context information assigned:
path <- find_path_ctx(g, 1, 7, decision_fct)
The shortest path from 1 to 7 is:
[1] 1 2 6 4 7
The edge 2 -> 3 was not visited because of contextual constraints: context[2] != context[3].
For this example of shortest path discovery from start to target, passing the start vertex to the decision function is unnecessary. However, the signature of this function is consistent for all shortest-path- and centrality-related functionality. It becomes clear for the discovery of all shortest paths in the network. Here, we need the start vertex to know the vertex for which shortest paths are discovered:
distances <- all_pairs_shortest_paths_ctx(g, decision_fct)The result is a distance matrix:
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 0 1 Inf 3 4 2 4 Inf 4 Inf
[2,] 1 0 Inf 2 3 1 3 Inf 3 Inf
[3,] Inf Inf 0 Inf Inf Inf Inf Inf Inf 1
[4,] 3 2 Inf 0 1 1 1 Inf 1 Inf
[5,] 4 3 Inf 1 0 2 2 Inf 1 Inf
[6,] 2 1 Inf 1 2 0 2 Inf 2 Inf
[7,] 4 3 Inf 1 2 2 0 Inf 2 Inf
[8,] Inf Inf Inf Inf Inf Inf Inf 0 Inf Inf
[9,] 4 3 Inf 1 1 2 2 Inf 0 Inf
[10,] Inf Inf 1 Inf Inf Inf Inf Inf Inf 0
Since the decision function receives IDs of vertices, we can complicate our attribute data structure to contain vectors for each vertex:
set.seed(42)
context <- list("1" = rnorm(100),
"2" = rnorm(100),
"3" = rnorm(100),
"4" = rnorm(100),
"5" = rnorm(100),
"6" = rnorm(100),
"7" = rnorm(100),
"8" = rnorm(100),
"9" = rnorm(100),
"10"= rnorm(100))Then, the decision function needs to be adapted to this new data structure:
decision_fct <- function(strt, crnt, nxt){
dist_angular_distance(context[[crnt]], context[[nxt]]) <=
dist_angular_distance(context[[strt]], context[[nxt]])
}This decision function makes use of built-in distance functions for numeric vectors. Using this, we could evaluate the betweenness centrality, for example:
betw <- betweenness_ctx(g,decision_fct)It results in the following betweenness values for the vertices:
[1] 0.0000000 3.3750000 4.3333333 3.9583333 1.0416667 0.5000000 0.0000000 0.0000000 0.5833333 0.4583333
More examples can be found in the documentation of the functions - see https://nctx.mircoschoenfeld.de/R/
If you use the nctx package, please cite this paper:
Schönfeld, Mirco ; Pfeffer, Jürgen:
Shortest path-based centrality metrics in attributed graphs with node-individual context constraints.
In: Social Networks. (2 November 2021) .
@article{SCHOENFELD2021,
title = {Shortest path-based centrality metrics in attributed graphs with node-individual context constraints},
journal = {Social Networks},
year = {2021},
issn = {0378-8733},
doi = {https://doi.org/10.1016/j.socnet.2021.10.004},
url = {https://www.sciencedirect.com/science/article/pii/S037887332100085X},
author = {Mirco Schoenfeld and Jürgen Pfeffer},
keywords = {Attributed network, Betweenness centrality, Closeness centrality, Contextual embeddedness},
abstract = {Centrality measurements are a well-known method to assess the importance of actors in networks. They are easy to obtain and provide a versatile interpretability adaptable to the meaning of nodes and edges. The current centrality measurements use structural information alone. In real-world situations, however, actors and the connections between them are subject to contextual settings and can be significantly influenced by these settings. In fact, such real-world observations are often modeled using attributed networks in which contextual information can be associated as attributes to nodes and edges. However, this information is disregarded when evaluating the importance of actors in terms of network centrality measurements. Hence, this paper proposes a method for obtaining shortest path-based centrality measurements for attributed networks that exploit attribute information on nodes for shortest path calculations. We add abstracts of scientific publications to a co-publishing network and use topic models to create node-individual context constraints for shortest path calculations. This creates additional analytic opportunities and can aid in gaining a detailed understanding of complex social networks.}
}