| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| A | – | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| B | 1 | – | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| C | 1 | 1 | – | 1 | 1 | 0 | 0 | 0 | 0 |
| D | 1 | 1 | 1 | – | 1 | 1 | 0 | 0 | 0 |
| E | 1 | 0 | 1 | 1 | – | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 1 | 0 | – | 1 | 1 | 1 |
| G | 0 | 0 | 0 | 0 | 0 | 1 | – | 1 | 1 |
| H | 0 | 0 | 0 | 0 | 0 | 1 | 1 | – | 1 |
| I | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | – |
15 The Social Network Matrices
15.1 The Adjacency Matrix
As we saw in the Chapter 14, a matrix is a two-dimensional array of numbers. A matrix is two-dimensional because it arranges numbers according to the intersection of a row dimension and a column dimension.
Matrices, therefore, are perfect for storing network information, because we can put the nodes in the row and column dimensions and then record characteristics of each dyad in the network (like whether they are adjacent in the corresponding graph) in the corresponding cell of the matrix.
Recall that each ij cell of a matrix corresponds to the intersection of a particular row object i and a particular column object j, so they are perfect for recording dyadic information, like adjacency. A matrix that stores adjacency relations between pairs of nodes in a graph is called an adjacency matrix.
As we will see later, we can, of course, record all kinds of relationships between dyads in matrix form beyond adjacency. These include the length of the shortest paths linking two nodes, the number of shortest paths, the number of common neighbors, whether two nodes are reachable from one another, and so forth.
Regardless, the adjacency matrix is the most important, most commonly used way of representing graphs in network analysis. As we saw in Chapter 6, two actors are connected in the network if they share an edge (are adjacent) in the graph; otherwise, they are not connected (are non-adjacent).
The adjacency matrix indicates whether two nodes are directly connected, and thus, as its name implies, it records the adjacency relations between every pair of nodes in the network.
15.2 Symmetric Adjacency Matrices for Undirected Graphs
The first step in building the adjacency matrix that represents the graph is to list all the nodes \(\{A, B, C, D, E, F, G, H, I\}\) as both a row and a column entry for each node. Next, one goes sequentially across the rows and columns, asking the question “does actor i have the relationship I am examining with actor j?” If the question asks about the presence or absence of a relationship, 0s and 1s are used. If A has a relationship with B, the value 1 is marked. Otherwise, 0.
As we can see in Table 15.1, A indeed has a relationship with B, so the corresponding cell for the row corresponding to A and the column corresponding to B is marked 1. In fact, A has a relationship with B, C, D, and E, and has 1’s in each of the cells corresponding to these actors, but not with F, G, H, or I, and so 0’s are in these cells.
But what do we do about the cells where we are theoretically supposed to ask if A has a relationship with A? As we have seen, for most sociological applications, it makes sense to just put a dash there, thus blocking the diagonals. It’s not sociologically meaningful for A to have a relationship with itself.
For example, asking “Is A friends with A?” does not make much sense, but there are rare cases when it does, such as when A is a group rather than a single person, and the relationship we are looking at might occur both within and between groups. As we saw in Chapter 6, these are called reflexive-ties or loops. But if the network is represented as a simple graph, it should contain no loops.
After completing the first row, we ask whether actor B has a relationship with actor A? Well, yes, it does. In fact, we can know this without even looking, because, if you recall, this network is defined ahead of time as reciprocal: if A is friends with B, then B is friends with A. We can remember this because the graph we are using is undirected. This means the resulting matrix will be symmetric. Symmetric matrices are those that, when flipped along the diagonal (as shown in Figure Table 15.1), the two sides of the matrix will be mirror images of each other.
15.3 Asymmetric Adjacency Matrices for Directed Graphs
Conversely, a directed graph describing a network of asymmetric or anti-symmetric ties will create an asymmetric matrix. Saying a matrix is asymmetric means that the values contained in the upper and lower triangles of the matrix do not mirror each other. In other words, in an asymmetric matrix, the cell values are not necessarily the same (the relationship is not necessarily equivalent) between every pair of cases.
Figure 10.1 shows an example directed graph. The corresponding asymmetric adjacency matrix is shown in Table 15.2. Note that while some relationships (such as between node A and B) are reciprocated, not all connections in the network are reciprocated. Node G sends ties to D and F but receives none in return.
In the resulting matrix, A to B and B to A each have a 1, while G to D and G to F also have a 1. However, the cells corresponding to F to G and D to G each have a value of 0 because the ties are unreciprocated. These unreciprocated ties make the resulting matrix asymmetric. The two halves across the diagonal are no longer mirror images, but contain different entries.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | -- | 1 | 0 | 0 | 0 | 1 | 0 |
| B | 1 | -- | 0 | 1 | 0 | 0 | 0 |
| C | 0 | 1 | -- | 0 | 0 | 0 | 0 |
| D | 0 | 1 | 0 | -- | 0 | 0 | 0 |
| E | 0 | 0 | 1 | 1 | -- | 0 | 0 |
| F | 1 | 0 | 0 | 0 | 0 | -- | 0 |
| G | 0 | 0 | 0 | 1 | 0 | 1 | -- |
Why are the ties not reciprocated? You might remember from our lessons on types of ties and types of graphs, but it is because of the type of data that the graph and matrix are representing. For example, the matrix in Table 15.2 and the graph shown in Figure 10.1 could represent an intramural basketball club in which members ask one another who they would like to have as a teammate. Not everyone would agree that they like having one another as teammates, and the matrix and graph in Figure 10.1 would represent that.
In this case, a node like G or E looks really lonely since no one wants to play with them. However, if the tie were to be about advice, such that actually G gives advice to D and F, but does not take their advice back, G (and E) now look like respected figures in the network.
15.4 The Reachability Matrix
Consider the directed graph shown in Figure 10.1. Earlier, we derived an asymmetric adjacency matrix from a graph similar to this one. But directed graphs do not only encode information about adjacency relations between nodes. As we saw in the graph theory lesson, in directed graphs (and as we will later, in disconnected undirected graphs), there is another pairwise relationship between nodes we may be interested in; namely, reachability (Krackhardt 1994):
In a graph, node B is said to be reachable by node A if there is path (of any length) that has A as the origin node and B as the destination node. In that case, we say that A can reach B.
Sometimes, it is useful to encode reachability relations between nodes in order to compute some important graph metrics. This is done using the reachability matrix, written \(D^r\). The reachability matrix is just like the adjacency matrix, except that instead of putting a one in the corresponding matrix cell if the node in the row sends a tie to the node in the respective column, we put a one in the corresponding matrix cell if the node in the row can reach the node in the column via a path. Table 15.3 shows the reachability matrix corresponding to the directed graph shown in Figure 10.1.
Note that if a node sends a regular old directed edge (a path of length one!) that counts for reachability too. This means that if the cell corresponding to the relationship between two nodes has a one in the adjacency matrix, then it should also have a one in the reachability matrix.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | – | 1 | 0 | 1 | 0 | 1 | 1 |
| B | 1 | – | 0 | 1 | 0 | 1 | 1 |
| C | 1 | 1 | – | 1 | 0 | 1 | 1 |
| D | 1 | 1 | 0 | – | 0 | 1 | 1 |
| E | 1 | 1 | 1 | 1 | – | 1 | 1 |
| F | 1 | 1 | 0 | 1 | 0 | – | 1 |
| G | 1 | 1 | 0 | 1 | 0 | 1 | – |
So show does this work? Let us take a look at how the first row (corresponding to whether node A can reach the other nodes in the graph) was filled out. First we ask, can node A reach node B? The answer is yes, because they are is a direct link between them! Node A sends a tie to node B, so the corresponding cell \(d^r_{12} = 1\).
Then we ask, can node A reach node C? The answer is no. Note that there is no directed path we can trace that would start from node A and end in node C. So we put a zero in the corresponding cell (row 1, column 3) of the reachability matrix (\(d^r_{13} = 0\)).
Further, we can ask, can node A reach node D? Note that here the answer is yes! While node A is not directly connected to node D, they are indirectly connected, so node A can reach node D in two ways: First, via a path of length two that goes: \(A \rightarrow B, B \rightarrow D\), and via path of length three that goes: \(A \rightarrow F, F \rightarrow G, G \rightarrow D\).1 So \(d^r_{13} = 1\).
1 Because nodes can be indirectly connected by more than one path, it is possible to come up with a weighted version of the reachability matrix, that encodes the number of paths of any length via which the row node can reach the column node.
We can continue like this and finish the row for node A and the rows for all the other nodes. If we do, we end up with the numbers shown in Table 15.3. There are some interesting things about this matrix. Reading across the rows for each node, we can figure out the number of other nodes that that particular node can reach.
Note than an interesting feature of the graph shown in Figure 10.1 is that while some nodes (like node A) cannot reach all the nodes in the graph, other nodes (like node E) can! It seems like E has access to everyone in the network, whether directly or indirectly. Maybe they are pretty important (Krackhardt 1994). Node C is almost like node E. They can reach almost everyone in the network, except for E. Maybe they are the second in command.
In the same way, note that reading across the columns, tell us whether a particular node is reachable by the other nodes. So we see that some nodes, like A, B, D, F, and G are reachable by everyone. Other nodes like E are reachable by no one. Finally, a node like C is not reachable by almost anyone else, except node E. It seems like reachability can encode some interesting properties, and can be used to develop some graph metrics related to power and hierarchy.
15.4.1 Measuring Graph Connectedness (\(C\))
Sometimes, we are not just interested in whether a particular individual node can reach another. We want to measure the overall capacity of a network to facilitate connections. We want to answer the question: To what extent can actors in this system reach one another directly or indirectly?
To quantify this, the sociologist David Krackhardt (1994) introduced the concept of graph connectedness (\(C\)). Connectedness is defined as the proportion of all possible directed pairs of nodes that are actually reachable from one another.
Krackhardt, David. 1994. “Graph Theoretical Dimensions of Informal Organizations.” Computational Organization Theory 89 (112): 123–40.
In the language of matrix algebra, graph connectedness is equivalent to the density of the directed reachability matrix (excluding the main diagonal cells, which represent self-reachability). The formula to calculate connectedness is:
\[C = \frac{\sum_{i \neq j} D^r_{ij}}{N(N-1)}\]
Where \(\sum_{i \neq j} D^r_{ij}\) is the sum of all cells containing a \(1\) in the off-diagonal cells of the reachability matrix, and \(N(N-1)\) is the maximum possible number of directed pairs in a network of size \(N\). Graph connectedness ranges from \(0\) (a completely disconnected network where no node can reach any other node) to \(1.0\) (a strongly connected network where every node can reach every other node, and the reachability matrix is the all-ones matrix).
To see this in action, let’s calculate the connectedness of the directed graph shown in Figure 10.1 using its reachability matrix in Table 15.3.
- First, we sum all the cell values in Table 15.3 (excluding the blocked diagonal dashes). By counting the number of cells containing a \(1\), we find that there are exactly 17 directed reachability relations in this network.
- Second, we calculate the total number of possible directed pairs. Since there are \(N = 6\) nodes, this is: \[N(N-1) = 6 \times (6 - 1) = 30\]
- Third, we divide the sum of reachable pairs by the total possible pairs: \[C = \frac{17}{30} \approx 0.57\]
This tells us that about \(57\%\) of all directed pairs in this network are connected via some directed path of any length. Connectedness is an invaluable tool for comparing network systems, such as measuring whether information propagates more efficiently through a highly integrated, flat cooperative (\(C \approx 1.0\)) than through a rigid, top-down bureaucratic tree (\(C \approx 0.3\)).
| A | B | C | D | E | F | G | H | I | J | K | L | M | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | – | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| B | 0 | – | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | – | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| E | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 | 0 | 0 |
| H | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 | 0 |
| I | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 | 0 |
| J | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 | 0 |
| K | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 | 0 |
| L | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – | 0 |
| M | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | – |
For instance, the reachability matrix corresponding to a perfectly hierarchical directed tree graph containing only antisymmetric relations, such as the one shown in Figure 13.1, has an interesting property. This is shown in Table 15.4. If you look at the reachability matrix’s lower-triangle, it is full of zeroes! The only ones present in the matrix are contained in the matrix’s upper-triangle. This means that when looking at a reachability matrix of any directed graph, we can get a sense of how much they approximate a pure antisymmetric hierarchy by counting the number of ones that appear in the reachability matrix’s lower-triangle.
15.4.2 Graph Connectivity Levels and Reachability Matrix Zeros
Beyond measuring the overall density of the reachability matrix through graph connectedness, we can use the pattern of zeros and ones in the matrix to diagnose the specific qualitative “flavor” of connectivity that a directed network exhibits. As introduced in our discussion of graph connectivity, directed networks can be strongly, unilaterally, or weakly connected. In matrix algebra, these three structural conditions correspond to highly specific mathematical patterns in the off-diagonal cells of the reachability matrix:
- Strongly Connected (The All-Ones Matrix): A directed network is strongly connected if there is a directed path from every node to every other node in the graph (representing mutual reachability). In terms of the reachability matrix, this means there are absolutely no zeros in the off-diagonal cells. The entire matrix (excluding the blocked diagonal dashes
--) is completely filled with ones. This indicates that information, advice, or influence can flow from any starting point to any destination in the system, with zero structural bottlenecks or isolates. - Unilaterally Connected (No Symmetric Zeros): A directed network is unilaterally connected if, for every pair of nodes \(\{u, v\}\), there is at least one directed path connecting them (meaning either \(u\) can reach \(v\), or \(v\) can reach \(u\), or both). In the reachability matrix, a unilaterally connected graph will contain some zeros, representing unreciprocated reachability. For example, if node \(2\) is a transmitter node (a source), it can reach everyone else, but nobody can reach it, which creates several zeros in Column 2 of the matrix. However, because at least one direction is always reachable for any pair, we will never observe a symmetric zero where both \(D^r_{uv} = 0\) and \(D^r_{vu} = 0\). For any off-diagonal cell pair, at least one of the cells must hold a \(1\).
- Weakly Connected (Symmetric Zeros Exist): A directed network is only weakly connected if some nodes are connected solely when ignoring the directions of the arrows (via semipaths). In a weakly connected network, there is at least one mutually unreachable pair \(\{u, v\}\) where neither node can reach the other via any directed pathway. In the reachability matrix, this structural condition is immediately diagnosed by the presence of a symmetric zero in the off-diagonal cells: both \(D^r_{uv} = 0\) and \(D^r_{vu} = 0\).
By scanning the reachability matrix for these symmetric zeros, network analysts can immediately detect structural divides and communication barriers where two actors are completely cut off from one another, despite being embedded in the same larger, weakly connected system.
15.5 The Geodesic Distance Matrix
Consider the directed graph shown in Figure 7.1 again. In Table 15.1 we derived an symmetric adjacency matrix from the same graph. However, as noted in the graph theory lesson and our previous discussion of indirect connections, adjacency is only one way (the direct way) in which nodes can be connected in graph. A particularly important way in which two nodes can be connected is via shortest paths. The length of shortest path between two nodes is called the geodesic distance between them. So it is possible to create a matrix D in which each cell d\(_{ij}\) contains the length of the shortest path between the row node i and the column node j. This is called the distance matrix for the corresponding graph. The D matrix corresponding to the graph shown in Figure 7.1, is shown in Table 15.5.
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 1 | 2 | 3 | 3 | 3 |
| B | 1 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| C | 1 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
| D | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 2 | 2 |
| E | 1 | 2 | 1 | 1 | 0 | 2 | 3 | 3 | 3 |
| F | 2 | 2 | 2 | 1 | 2 | 0 | 1 | 1 | 1 |
| G | 3 | 3 | 3 | 2 | 3 | 1 | 0 | 1 | 1 |
| H | 3 | 3 | 3 | 2 | 3 | 1 | 1 | 0 | 1 |
| I | 3 | 3 | 3 | 2 | 3 | 1 | 1 | 1 | 0 |
The distance matrix reveals a number of things about the network. First, note that nodes that are adjacent in Figure 7.1 have a geodesic distance of 1.0 by definition. In addition, nodes are at a minimum distance from themselves, so we put a value of 0 in the diagonal cells; d\(_{ij} = 0\) for all \(i=j\). Second, note that the maximum geodesic distance between any two nodes in the graph is 3.0. As we saw in the lesson on indirect connections, this is an important graph metric, called the graph diameter. Finally, note that just like an undirected graph yields a symmetric adjacency matrix, it also yields a symmetric distance matrix. If the geodesic distance between nodes A and G in an undirected graph is 3.0, then the geodesic distance between G and A is also 3.0: d\(_{ij}\) = d\(_{ji}\) for all \(i\) and \(j\).
We can also generate geodesic distance matrices for directed graphs, such as the one shown in Figure 10.1. The corresponding distance matrix for this graph is shown in Table 15.6.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 0 | 1 | Inf | 2 | Inf | 1 | Inf |
| B | 1 | 0 | Inf | 1 | Inf | 2 | Inf |
| C | 2 | 1 | 0 | 2 | Inf | 3 | Inf |
| D | 2 | 1 | Inf | 0 | Inf | 3 | Inf |
| E | 3 | 2 | 1 | 1 | 0 | 4 | Inf |
| F | 1 | 2 | Inf | 3 | Inf | 0 | Inf |
| G | 2 | 2 | Inf | 1 | Inf | 1 | 0 |
This distance matrix is very different from the one corresponding to the undirected graph. First note that some shortest paths are not defined, because some pairs of nodes are disconnected in the directed graph; that is there is directed path linking them. So the corresponding cells are noted with Inf in the matrix.2 For instance, node A cannot reach nodes C, E or G. Note also that now the matrix is asymmetric, so the numbers above the diagonal do not have to match the numbers below the diagonal. Thus, while node A cannot reach node G via a shortest path, node G can reach node A via shortest path of length 2.
2 If the shortest path between a pair of nodes does not exist, then technically their geodesic distance is infinity! (\(\infty\))
15.5.1 Node Eccentricity and Graph Diameter
The Geodesic Distance Matrix is a treasure trove of structural metrics. In particular, we can use it to calculate how “remote” or “central” each individual actor is, as well as the overall “width” of the network, using two classical metrics: node eccentricity and graph diameter.
15.5.1.1 Node Eccentricity (\(e(v)\))
The eccentricity of a node \(v\)—written \(e(v)\)—is the maximum geodesic distance between that node and any other reachable node in the network:
\[e(v) = \max_{j \neq v} D^g_{vj}\]
In other words, we look at the row corresponding to node \(v\) in our geodesic distance matrix (excluding the diagonal \(0\) cell) and find the maximum value. Eccentricity represents the “worst-case scenario” for communication originating at node \(v\): it is the maximum number of steps required for a message sent from \(v\) to reach the most distant, remote actor in the graph. Nodes with low eccentricity are highly central because they are relatively close to everyone, whereas nodes with high eccentricity are remote and marginal.
If we look at our distance matrix in Table 15.5: - The row for node \(C\) is \((1, 2, 0, 1, 1, 2, 2, 2, 2)\). The maximum value is \(2\). Therefore, the eccentricity of node \(C\) is \(e(C) = 2\). - The row for node \(A\) is \((0, 1, 1, 1, 1, 2, 3, 3, 3)\). The maximum value is \(3\) (it takes 3 steps for \(A\) to reach \(G\), \(H\), or \(I\)). Therefore, the eccentricity of node \(A\) is \(e(A) = 3\).
15.5.1.2 Graph Diameter (\(d\))
The diameter of a graph (\(d\)) is the maximum geodesic distance between any pair of nodes in the network. In terms of our matrix metrics, the diameter is simply the maximum eccentricity of all nodes in the graph:
\[d = \max_v e(v)\]
To find the diameter of a network, we simply search for the maximum value in the entire geodesic distance matrix. - In our 9-node undirected distance matrix (Table 15.5), the maximum value is \(3.0\). Thus, the diameter of this network is \(d = 3\). - In our directed distance matrix (Table 15.6), the maximum distance (excluding infinity) is \(3.0\) (representing the path \(C \rightarrow E \rightarrow D\) or others), so the diameter of the connected component is \(3\).
Analyzing eccentricities and diameter helps us understand how quickly information can diffuse across a network. A network with a very small diameter (like a “Small World” network where \(d \le 6\)) can propagate innovations, news, or diseases almost instantaneously, whereas a network with a large, sprawling diameter will have slow, localized, and fragmented communication flows.
15.6 The Shortest Paths Matrix
Recall that in our discussion of shortest paths in the indirect connectivity lesson, we noted that nodes can be connected by more than one shortest path at the same time. So sometimes it is useful to create a matrix that records this number for each pair of nodes. This is called the shortest paths matrix (S). Each cell in the matrix s\(_{ij}\) gives us the number of shortest paths connecting the row node i with the column node j. The shortest path matrix corresponding to the graph in Figure 7.1, is shown in Table 15.7.
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 1 | 2 | 3 | 3 | 3 |
| B | 1 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| C | 1 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
| D | 1 | 1 | 1 | 0 | 1 | 1 | 2 | 2 | 2 |
| E | 1 | 2 | 1 | 1 | 0 | 2 | 3 | 3 | 3 |
| F | 2 | 2 | 2 | 1 | 2 | 0 | 1 | 1 | 1 |
| G | 3 | 3 | 3 | 2 | 3 | 1 | 0 | 1 | 1 |
| H | 3 | 3 | 3 | 2 | 3 | 1 | 1 | 0 | 1 |
| I | 3 | 3 | 3 | 2 | 3 | 1 | 1 | 1 | 0 |
The S matrix contains useful information. For instance, it tell us that some pairs of nodes in the graph, have multiple ways of reaching other nodes to which they are not directly connected using shortest paths. For instance, actor A can get to actor G via three distinct shortest paths. So this gives us a sense of the capacity of that actor to reach the other one in an efficient way; if one of those shortest paths were to be compromised, A would still be able to send something to G via the other non-compromised paths.
15.7 The Neighborhood Overlap Matrix
As we noted in the original graph theory lesson, it is possible for the neighborhood of two nodes in a graph to overlap. Recall that for each node, we define its neighborhood as the set of other nodes that they are adjacent to. That means the neighborhood between two nodes can have members in common.
This can be used as a measure of the overlap of the neighborhood between two nodes. For instance, imagine you have a friend and that friend knows all your friends and you know all their friends. In which case we would say that the overlap between your node neighborhoods is pretty high; in fact the two neighborhoods overlap completely.
Now imagine you just met a new person online who lives in a far away country, and as far as you know, they know none of your friends and you know none of their friends. In which case, we would say that the overlap of the two neighborhoods is nil or as close to zero as it can get.
\[ o_{ij} = \frac{|\mathcal{N}(i) \cap \mathcal{N}(j)|}{|\mathcal{N}(i) \cup \mathcal{N}(j)|} \tag{15.1}\]
Given a graph, we can construct the neighborhood overlap matrix for the graph O, containing such overlap scores between the neighborhood sets of each pair of nodes in the graph. The overlap score ranges from 0 (not overlap), to 1.0 (complete overlap), with values in-between for partial overlap (which is the more common case). Each cell in the matrix is filled in using equation Equation 30.2.
This equation says that the overlap between node i and node j, written \(o_{ij}\), is equivalent to the cardinality (||) of the set defined by the intersection (\(\cap\)) of i’s neighborhood (\(\mathcal{N}(i)\)) and j’s neighborhood (\(\mathcal{N}(j)\)), or the number of common neighbors, divided by the cardinality of the set defined by the union (\(\cup\)) of i’s neighborhood (\(\mathcal{N}(i)\)) and j’s neighborhood (\(\mathcal{N}(j)\)), or the total number of neighbors.
Thus, the overlap is the number of common neighbors, divided by the number of total neighbors. For instance, the neighborhood overlap for the undirected graph shown in Figure 7.1 is shown in Table 15.8.
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| A | 1.00 | 0.40 | 0.60 | 0.50 | 0.40 | 0.14 | 0.00 | 0.00 | 0.00 |
| B | 0.40 | 1.00 | 0.40 | 0.33 | 1.00 | 0.17 | 0.00 | 0.00 | 0.00 |
| C | 0.60 | 0.40 | 1.00 | 0.50 | 0.40 | 0.14 | 0.00 | 0.00 | 0.00 |
| D | 0.50 | 0.33 | 0.50 | 1.00 | 0.33 | 0.00 | 0.14 | 0.14 | 0.14 |
| E | 0.40 | 1.00 | 0.40 | 0.33 | 1.00 | 0.17 | 0.00 | 0.00 | 0.00 |
| F | 0.14 | 0.17 | 0.14 | 0.00 | 0.17 | 1.00 | 0.40 | 0.40 | 0.40 |
| G | 0.00 | 0.00 | 0.00 | 0.14 | 0.00 | 0.40 | 1.00 | 0.50 | 0.50 |
| H | 0.00 | 0.00 | 0.00 | 0.14 | 0.00 | 0.40 | 0.50 | 1.00 | 0.50 |
| I | 0.00 | 0.00 | 0.00 | 0.14 | 0.00 | 0.40 | 0.50 | 0.50 | 1.00 |
Looking at the first row of the matrix, we can see that nodes A and C have a pretty high neighborhood overlap score \(o_{AC} = 0.60\). But the node neighborhood A has no overlap with that of nodes G, H and I, as is evident by looking at Figure 7.1.
We can examine the overlap pattern of each node in Figure 7.1 by going down each row of the matrix. Note that the common neighbors matrix is symmetric: If A has an overlap of o with B, then B necessarily has the same overlap score with A. So all the information in the neighborhood overlap matrix is contained in either the lower or upper triangle.
We can think of neighborhood overlap as a measure of structural similarity of two nodes in a graph based on their pattern of social connections. In fact, the formula shown in equation Equation 30.2 is called Jaccard’s Coefficient (named after the French Botanist Paul Jaccard, who introduced it) and it is generally used (along with many variations) as a measure of similarity between two sets (Jaccard 1901).
Jaccard, Paul. 1901. “Distribution of the Alpine Flora in the Dranse’s Basin and Some Neighbouring Regions.” Bulletin de La Societe Vaudoise Des Sciences Naturelles 37 (1): 241–72.
So looking at Table 15.8, we can see node F is most similar to nodes G, H and I in the graph shown in Figure 7.1, and least similar to node D.
Can you think of which of your friends you are most similar to in terms of neighborhood overlap?
As we noted in the lesson on graph theory, common neighbors are defined for all the dyads in the network, whether they are connected or null. So that means that two nodes can have overlapping neighborhoods even if they do not have tie between them! Sometimes it happens that you meet someone new and then you realize that you had friends in common. This is such a common occurrence that it has a name: the small world phenomenon (Milgram 1967).
Milgram, Stanley. 1967. “The Small World Problem.” Psychology Today 2 (1): 60–67.