Social Network Analysis

Worksheet 2: Graph Theory

Author

Termeh Shafie

Graph Theory in R with `igraph`

We’ll use the igraph package to explore key graph-theoretical concepts.

library(igraph)

Undirected Graph

We’ll use an undirected graph with 8 nodes.

g <- graph_from_literal(
  1 -- 2, 
  1 -- 3,
  2 -- 4,
  3 -- 5,
  4 -- 5,
  5 -- 6,
  6 -- 7,
  6 -- 8,
  7 -- 8
)

plot(g, vertex.label.cex = 1.2, vertex.size = 20)

Degree & Degree Distribution

deg <- degree(g)
deg

1 2 3 4 5 6 7 8 
2 2 2 2 3 3 2 2

# Degree distribution
dist <- degree_distribution(g)
plot(dist, type = "h", main = "Degree Distribution", xlab = "Degree", ylab = "Frequency")

Identify nodes with the highest and lowest degree. How does the distribution look?

Graph Diameter

diameter(g)

[1] 4

What is the longest shortest path in the graph?

Shortest Paths

Find shortest paths from node 1 to all others:

sp <- distances(g, v = 1)
sp

  1 2 3 4 5 6 7 8
1 0 1 1 2 2 3 4 4

Do you understand the output? What is the shortest path from node 1 to node 6?

Adjacency Matrix

adj_matrix <- as_adjacency_matrix(g, sparse = FALSE)
adj_matrix

  1 2 3 4 5 6 7 8
1 0 1 1 0 0 0 0 0
2 1 0 0 1 0 0 0 0
3 1 0 0 0 1 0 0 0
4 0 1 0 0 1 0 0 0
5 0 0 1 1 0 1 0 0
6 0 0 0 0 1 0 1 1
7 0 0 0 0 0 1 0 1
8 0 0 0 0 0 1 1 0

Use the adjacency matrix to compute the degree of each node. Compare with degree(g).

Cutpoints (Articulation Points)

articulation_points <- articulation_points(g)
articulation_points

+ 2/8 vertices, named, from be810f5:
[1] 6 5

Bridges (Critical Edges)

bridge_edges <- which(is.na(edge_connectivity(g)))
E(g)[bridge_edges]

+ 0/9 edges from be810f5 (vertex names):

# Alternatively use:
bridges(g)

+ 1/9 edge from be810f5 (vertex names):
[1] 5--6

Visualize Cutpoints and Bridges

V(g)$color <- ifelse(V(g) %in% articulation_points, "red", "skyblue")
E(g)$color <- ifelse(E(g) %in% bridges(g), "red", "black")

plot(g, vertex.size = 20, vertex.label.cex = 1.2)

Which nodes and edges are critical to keeping the graph connected?

Directed Graph

Now let’s work with a directed graph.

g_dir <- graph_from_literal(
  A -+ B, A -+ C,
  B -+ D,
  C -+ D,
  D -+ E,
  E -+ F,
  F -+ C
)

plot(g_dir, vertex.label.cex = 1.2, vertex.color = "lightcoral", edge.arrow.size = 0.5)

In-Degree and Out-Degree

degree(g_dir, mode = "in")   # incoming links

A B C D E F 
0 1 2 2 1 1

degree(g_dir, mode = "out")  # outgoing links

A B C D E F 
2 1 1 1 1 1

Strongly Connected Components

components(g_dir, mode = "strong")

$membership
A B C D E F 
1 2 3 3 3 3 

$csize
[1] 1 1 4

$no
[1] 3

Directed Paths and Diameter

diameter(g_dir, directed = TRUE)

[1] 4

Explore how cycles and direction affect path lengths.

Exercises

Create some other small unidrected and directed graphs and see how the above measure vary on them
import the Florentine marriage and business network from the networkdata package and compute the appropriate measures from above on it

library(networkdata)
data("flo_marriage")
data("flo_business")

Graph Theory in R with igraph