A shortest path is a path that connects two nodes in a network with a minimal number of edges. The length of a shortest path is called the distance between two nodes.
In empirical networks, we often observe a tendency towards high transitivity (“the friend of a friend is a friend”)
Degree distribution
The degree of a node in a network is the number of connections it has to other nodes.
The degree distribution is the probability distribution of the degrees over the whole network.
Empirical degree distributions are generally right skewed.
(Many nodes have a few conncetions and few have many) “preferential attachment”, “matthew effect”, “the rich get richer”
Degree distribution
er <-sample_gnp(n =5000, p =0.01)pa <-sample_pa(n =5000, power =1.5, m =2, directed =FALSE)
plot(degree_distribution(er))
plot(degree_distribution(pa),log ="xy")
Centrality
A measure of centrality is an index that assigns a numeric values to the nodes of the network. The higher the value, the more central the node.
“Being central” is a very ambiguous term hence there exists a large variety of indices that assess centrality with very different structural properties.
Standard indices
Degree
Number of direct neighbors (“popularity”)
Closeness
Reciprocal of the sum of the length of the shortest paths
Betweenness
Number of shortest paths that pass through a node (“brokerage”)
Eigenvector
Being central means being connected to other central nodes
PageRank
Similar to eigenvector, just for directed networks
Implemented indices
igraph contains the following 10 indices:
degree (degree())
weighted degree (strength())
betweenness (betweenness())
closeness (closeness())
eigenvector (eigen_centrality())
alpha centrality (alpha_centrality())
power centrality (power_centrality())
PageRank (page_rank())
eccentricity (eccentricity())
hubs and authorities (authority_score() and hub_score())
subgraph centrality (subgraph_centrality())
Indices in the sna package
The sna package implements roughly the same indices as but adds:
Signed networks include two types of relations:
positive (“friends”) and negative (“foes”)
typical research questions involve (implemented in signnet):
structural balance
blockmodeling
(centrality)
Structural balance theory
Beyond triangles
A network is balanced if it can be partitioned into two groups such that all intra group edges are positive and all inter group edges are negiative
Extended form of balance (Davis 1960s)
A network is balanced if it can be partitioned into k groups …
Toy example
library(signnet)data("tribes")
ggsigned(tribes)
ggsigned(tribes,weights =TRUE)
Measuring structural balance
triangles: Fraction of balanced triangles.
walks: fraction of signed to unsigned walks
frustration: optimal partition such that the sum of intra group negative and inter group positive edges is minimized
balance_score(tribes,method ="triangles")
[1] 0.867647
balance_score(tribes,method ="walk")
[1] 0.357576
balance_score(tribes,method ="frustration")
[1] 0.758621
Blockmodeling
In signed blockmodeling, the goal is to determine \(k\) blocks of nodes such that all intra-block edges are positive and inter-block edges are negative
general <-signed_blockmodel_general(g,blockmat,alpha =0.5)traditional <-signed_blockmodel(g,k =3,alpha =0.5,annealing =TRUE)c(general$criterion,traditional$criterion)
[1] 0 6
Generalized blockmodeling
Is there a “tidyverse” for networks?
tidygraph I
This package provides a tidy API for graph/network manipulation. While network data itself is not tidy, it can be envisioned as two tidy tables, one for node data and one for edge data. tidygraph provides a way to switch between the two tables and provides dplyr verbs for manipulating them.
tidygraph II
It more or less wraps the full functionality of igraph in a tidy API giving you access to almost all of the dplyr verbs plus a few more, developed for use with relational data.
Network Visualization
Visualizing networks is hard(er)
ordinary data
clear data format (rows: observations, columns: variables)
plot style dependent on variable scale (barchart, scatterplot, boxplot,…)
illustrate relations between variables
given relative positions
network data
different data formats (adjacency matrix, edgelist, adjaceny list, …)
global: all edges have the same appearance (e.g. edge_colour = "grey25")
via attributes: appearance depends on attribute (e.g. aes(edge_width = weight))
available aesthetics
edge_colo(u)r, edge_width, edge_linetype, edge_alpha
2) edges: aesthetics examples
# create a simple graph of three nodes where all nodes are connectedg <-graph.full(3) E(g)$weight <-c(1, 2, 0.5)ggraph(g, "stress") +geom_edge_link0(edge_linetype ="dotted")
2) edges: aesthetics examples
# create a simple graph of three nodes where all nodes are connectedg <-graph.full(3) E(g)$weight <-c(1, 2, 0.5)ggraph(g, "stress") +geom_edge_link0(edge_alpha =0.5)
2) edges: aesthetics examples
# create a simple graph of three nodes where all nodes are connectedg <-graph.full(3) E(g)$weight <-c(1, 2, 0.5)ggraph(g, "stress") +geom_edge_link0(aes(edge_alpha = weight, edge_width = weight))
2) edges: misc
g <-graph.full(3,directed =TRUE)ggraph(g, "stress") +geom_edge_parallel0(edge_width =0.5,arrow =arrow(angle =15, length =unit(0.15, "inches"),ends ="last", type ="closed"))
mapping aesthetics
- global: specify font properties
- via attributes: set label to name attribute of node
- filter: only display for nodes (or edges!) that fulfil a given criterion
available aesthetics
many! but most important: label, colour, family, size, and repel
4) labels: aesthetics examples
g <-graph.full(3)V(g)$name <-c("David", "Termeh", "Luna")ggraph(g, "stress") +geom_edge_link0() +geom_node_point(size =5, color ="grey66")+geom_node_text(aes(label = name), color ="black") +coord_fixed(clip ="off")
4) labels: aesthetics examples
g <-graph.full(3)V(g)$name <-c("David", "Termeh", "Luna")ggraph(g, "stress") +geom_edge_link0() +geom_node_point(size =5, color ="grey66")+geom_node_label(aes(label = name), color ="black") +coord_fixed(clip ="off")
facebook friendships of a university. Node colour corresponds to dormitory of students
