Social Networks

17  Equivalence and Similarity

  • Welcome
  • Introduction to Networks
  • 1  What Are Networks?
  • Graph Theory: The Basics
  • 2  Introduction to Graphs
  • 3  Graphs and their Subgraphs
  • 4  Types of Ties and Their Graphs
  • 5  Basic Graph Metrics
  • 6  Nodes and their Neighborhoods
  • 7  Nodes and their Degrees
  • 8  Degree-Based Graph Metrics
  • 9  Indirect Connections
  • 10  Directed Indirect Connections
  • 11  Graph Connectivity
  • Matrices: The Basics
  • 12  Introduction to Matrices
  • 13  The Adjacency Matrix
  • 14  Matrix Operations: Row and Column Sums
  • 15  Basic Matrix Operations
  • 16  Matrix Multiplication
  • 17  Equivalence and Similarity
  • 18  Local Node Similarities
  • 19  Blockmodeling
  • Centrality
  • 20  Centralities based on Degree
  • 21  Centralities based on the Geodesic Distance
  • 22  Centralities based on Shortest Paths
  • 23  The “Big Three” Centrality Metrics
  • Prestige
  • 24  Getting Centrality from Others
  • 25  Status
  • Two-Mode Networks
  • 26  Affiliation Networks

Table of contents

  • 17.1 The Position Approach
  • 17.2 Structural Equivalence
  • References

View source

17  Equivalence and Similarity

17.1 The Position Approach

The basic idea behind the position approach to dividing up the nodes in a graph is to come up with a measure of how similar two nodes are in terms of their patterns of connectivity with others. This measure then can be used to partition the nodes into what are called 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 is they have similar patterns of connectivity to the same 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 these are not literally the same people. 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.

17.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) is exactly the same.

Figure 17.1: An undirected graph with nodes colored by membership in the same structural equivalence class.

For instance in Figure fig-equivex, 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 17.1: Adjancency Matrix of an Undirected Graph

We can also see by looking at Table tbl-adjmat1) 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.
16  Matrix Multiplication
18  Local Node Similarities