Network Description

In the Network Description chapter of the Social Network Analysis for Crime Analysts textbook, we learned four basic ways to describe a network (i.e. size, density, components, diameter). In this tutorial, we will review how we can do this in R.

Simple Network Summary

So you have your network data, now what? The next step is to summarize its most critical features, which can guide your analysis. First, consider the size: How big is the network? This is the number of nodes involved, giving a sense of its scale. Next, think about how tightly connected the network is—this is the density, or the proportion of actual connections relative to all possible ones. Another key question is separation: How fragmented or divided is the network? Understanding its components or subgraphs can highlight isolated clusters. Finally, consider the network’s compactness, or its diameter, how far do nodes have to travel through connections to reach others? These four basic measures lay the groundwork for describing and understanding the structure of any network you encounter in your analysis.

As a refresher:

The size of the network is just the number of nodes in the network, which we represent with $g$;
The density the number of edges compared to how many ties there could be;
Disconnected subgraphs are referred to as components;
The diameter is the longest of all the shortest paths in the network, where a shortest path is the fewest number of steps node $A$ has to take to reach node $B$.

Let’s take a look at these in R.

Setup

First, let’s set up our undirected graph and our directed graph from the Network Description chapter:

# first, clear the workspace
rm( list = ls() )


# then, build the undirected network using the matrix function
u_mat <- matrix(
  c( 0,1,0,0,0,
     1,0,1,0,0,
     0,1,0,1,1,
     0,0,1,0,1,
     0,0,1,1,0 ),
  nrow = 5,
  byrow = TRUE 
  )

# assign the names to the object
rownames( u_mat ) <- c( "Jen","Tom","Bob","Leaf","Jim" )
colnames( u_mat ) <- c( "Jen","Tom","Bob","Leaf","Jim" )

# take a look at what we made
u_mat

     Jen Tom Bob Leaf Jim
Jen    0   1   0    0   0
Tom    1   0   1    0   0
Bob    0   1   0    1   1
Leaf   0   0   1    0   1
Jim    0   0   1    1   0

# now, let's build the directed network
d_mat <- matrix(
  c( 0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0 ),
  nrow = 5,
  byrow = TRUE )
  
# assign the names to the object
rownames( d_mat ) <- c( "Jen","Tom","Bob","Leaf","Jim" )
colnames( d_mat ) <- c( "Jen","Tom","Bob","Leaf","Jim" )

# take a look at what we made
d_mat

     Jen Tom Bob Leaf Jim
Jen    0   1   0    0   0
Tom    0   0   1    0   0
Bob    0   0   0    1   1
Leaf   0   0   1    0   1
Jim    0   0   1    1   0

Size

To get the size of the network we can examine the dimensions, or order, using the dim() function.

# get the dimensions
dim( u_mat )

[1] 5 5

This shows that the object u_mat has 5 rows and 5 columns. Since this is an object, we can use indexing to refer to each element in the object.

# set the number of rows as the size of the network
u_g <- dim( u_mat )[1]

u_g

[1] 5

# set the number of rows as the size of the network
d_g <- dim( d_mat )[1]

d_g

[1] 5

Density

Recall that the density of an undirected graph is given by: $\frac{2L}{g(g-1)}$ and the density of a directed graph is given by: $\frac{L}{g(g-1)}$. This means that for both networks we need to find $L$ and $g$.

We already have $g$ from our use of the dim() function above.

Now, we just need to count how many edges are in the network. To do this, we can use the sum() function, which adds up all the values in an object. Since the adjacency matrix is 0s and 1s, we can just sum the matrix to get $L$.

However, for the undirected network, the sum() function is going to double count our edges. As a result, we have to divide that one by 2.

# sum up the undirected network and then divide by 2
u_L <- sum( u_mat ) / 2

u_L

[1] 5

# sum up the directed network
d_L <- sum( d_mat )

d_L

[1] 8

Now that we have L and g for each network, we can find the density:

# for the undirected network
u_density <- ( 2 * u_L ) / ( u_g * ( u_g - 1 ) )

u_density

[1] 0.5

# for the directed network (note the difference)
d_density <- ( d_L ) / ( d_g * ( d_g - 1 ) )

d_density

[1] 0.4

Components

Disconnected subgraphs are referred to as components. In each of our example networks, there is only a single component because there are no subgraphs. In other words, all of the nodes are correctly either directly or indirectly.

In the sna package, there is a function called component.dist() which finds the distribution of components in a graph. Let’s take a look at it:

# first, load the sna library
library( sna )

# now, calculate the component distributionsfor the undirected graph
u_comp <- component.dist( u_mat )

u_comp

$membership
[1] 1 1 1 1 1

$csize
[1] 5

$cdist
[1] 0 0 0 0 1

The u_comp object shows three “pieces”. This is because it is a special class of object called a “list”. We can reference the “pieces” of a list using the $ operator and the name of the piece. For example, if we type u_comp$membership, it will show us which component each node is a member of:

u_comp$membership

[1] 1 1 1 1 1

These values show that all the nodes are in the first component. That makes sense because there are no subgraphs.

To illustrate, let’s disconnect the graph by removing Jen’s tie (sorry Jen) and take a look:

disconnected_u_mat <- matrix(
  c( 0,0,0,0,0,
     0,0,1,0,0,
     0,1,0,1,1,
     0,0,1,0,1,
     0,0,1,1,0 ),
  nrow = 5,
  byrow = TRUE 
  )

disconnected_u_mat

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    0    0
[2,]    0    0    1    0    0
[3,]    0    1    0    1    1
[4,]    0    0    1    0    1
[5,]    0    0    1    1    0

disconnected_u_comp <- component.dist( disconnected_u_mat )

disconnected_u_comp$membership

[1] 1 2 2 2 2

Now, we see that there are two components: the first node (Jen) is in component 1 and the other nodes are in component 2. Note that these are ids and not indicators for the first and second components.

If we had a large graph and wanted to know how many components we had, we could use the unique() and length() functions like this:

length( unique( disconnected_u_comp$membership ) )

[1] 2

Now let’s do it for the directed graph. Because there is directionality, we have to use the connected = weak argument to tell the function to ignore the direction (we will discuss this more later).

# calculate the component distribution for the directed graph and ignore the directionality
d_comp <- component.dist( d_mat, connected = "weak" )

d_comp

$membership
[1] 1 1 1 1 1

$csize
[1] 5

$cdist
[1] 0 0 0 0 1

Diameter

Recall that the diameter is the longest of all the shortest paths in the network, where a shortest path is the fewest number of steps node $A$ has to take to reach node $B$.

In the sna package, there is a function called geodist() that calculates the geodesics of a network. A geodesic is the number of edges that must be traversed for two nodes to connect. We will discuss this at greater length in the Closeness Centrality chapter of the Social Network Analysis for Crime Analysts textbook. For now, let’s just take a quick look:

# get the table of distances (geodesics)
u_gd <- geodist( u_mat )

# take a look at the them
u_gd$gdist

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    2    3    3
[2,]    1    0    1    2    2
[3,]    2    1    0    1    1
[4,]    3    2    1    0    1
[5,]    3    2    1    1    0

# find the maximum value
max( u_gd$gdist )

[1] 3

The diameter is 3. As for the directed graph:

# get the table of distances (geodesics)
d_gd <- geodist( d_mat,  )

# take a look at the them
d_gd$gdist

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    2    3    3
[2,]  Inf    0    1    2    2
[3,]  Inf  Inf    0    1    1
[4,]  Inf  Inf    1    0    1
[5,]  Inf  Inf    1    1    0

# find the maximum value
max( d_gd$gdist )

[1] Inf

Hold up?! We get the value of Inf. Why?

Think about the issue of direction here. Jen cannot be reached by the other nodes because of the directionality of the edges.

We need to tell R to ingore the Inf values using the is.finite() function:

max( d_gd$gdist[is.finite( d_gd$gdist )] )

[1] 3

Test your Knowledge

What are the four basic measures used to describe a network, and what does each one tell you about the network’s structure?
How do the formulas for network density differ between undirected and directed networks, and why?
How can you use the component.dist() function to determine whether a network contains multiple components?
How does the geodist() function help you calculate the network diameter, and why might a network return Inf values?
If a directed network contains unreachable nodes, what are two ways you can handle this when calculating the diameter?

Summary

In this tutorial we reviewed how to describe a network in R using four basic measures: size, density, components, and diameter. We reviewed simple undirected and directed adjacency matrices, then computed size from the matrix dimensions and density from the number of edges relative to possible ties. We also used the component.dist() function to identify disconnected subgraphs and geodist() function to find the network diameter from shortest-path distances, noting that directed graphs may produce Inf values unless you ignore unreachable pairs or treat the network as weakly connected. Disconnected graphs (i.e. graphs with multiple components) will also generate Inf values because of our use of the distance matrix (we will discuss this more later).