32 Equivalence and Similarity
32.1 The Position Approach
The basic idea behind the position approach to dividing up the nodes in a graph is to define a measure of how similar two nodes are in terms of their patterns of connectivity with others. This measure can then be used to partition the nodes into equivalence or similarity classes. Nodes in the same equivalence class are said to occupy the same position in the social structure described by the network.
There are two main ways to partition nodes into equivalence classes. The first is based on the idea that two nodes occupy the same position if they have the same connectivity patterns to other nodes in the graph. This is called structural equivalence (Lorrain and White 1971).
The second is based on the idea that two nodes are equivalent if they are connected to people who are themselves equivalent, even if those people are not literally the same. This is called regular equivalence (White and Reitz 1983).
This and the following lessons will deal mainly with various ways of partitioning the nodes in a network based on structural equivalence and its more relaxed cousin, structural similarity.
32.2 Structural Equivalence
Two nodes are structurally equivalent if they are connected to the same others. Thus, their patterns of connectivity (e.g., their row in the adjacency matrix) are exactly the same.
For instance, in Figure 32.1, nodes C and D are structurally equivalent because they are connected to the same neighbors \(\{A, B, E\}\). In the same way, nodes A and B are structurally equivalent because they are connected to the same neighbors \(\{C, D\}\). Finally, nodes E and F occupy unique positions in the network because their neighborhoods are not equivalent to that of any other nodes. Node E is the only node that has a neighborhood composed of nodes \(\{C, D, F\}\), and node F is the only node that has a neighborhood composed of node \(\{E\}\) only. Perhaps F is the main boss, and E is the second in command.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 0 | 1 | 1 | 0 | 0 |
| B | 0 | 0 | 1 | 1 | 0 | 0 |
| C | 1 | 1 | 0 | 0 | 1 | 0 |
| D | 1 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
Table 32.1: Adjancency Matrix of an Undirected Graph.
We can also see by looking at Table 32.1) that, indeed, the rows corresponding to the structurally equivalent nodes \(\{A, B\}\) and \(\{C, D\}\) in the corresponding adjacency matrix are indistinguishable from one another. The nodes that have unique positions in the network \(\{E, F\}\) also have a unique pattern of 0s and 1s across the rows of the adjacency matrix.
References
Lorrain, Francois, and Harrison C White. 1971. “Structural Equivalence of Individuals in Social Networks.” The Journal of Mathematical Sociology 1 (1): 49–80.
White, Douglas R, and Karl P Reitz. 1983. “Graph and Semigroup Homomorphisms on Networks of Relations.” Social Networks 5 (2): 193–234.