Transcript Structural Equivalence

Victor Lee

What are Social Networks?

Role and Position Analysis

Equivalence Models for Roles

Block Modelling


Not just Facebook and MySpace…
A social network is a collection of actors who
are joined by pairwise ties.

Actors may be individual persons or organizations

Ties are any type of relationship between two actors,
such as friendship, kinship, financial exchange,
influence, or prestige.

As a Graph
 Actor  vertex or node
 Tie  edge or link
 Could be directed/undirected,
weighted/unweighted

2
1
As an Adjacency Matrix
 N x N matrix, N = number of vertices
 aij = weight of edge from i  j
3
4
0

0
1

0
1 1 0

0 1 0
0 0 0

0 1 0

Social Position = collection of actors similarly
embedded in a network
 Similar sets of ties to other actors
 Not based on adjacency, proximity, or reachability

Example: Nurses at different hospitals
occupy the position nurse, even though they
don't work with each other, or even the same
doctors or patients.

Social Role = pattern of relationships that an
actor has with other actors
 May include both direct and compound relations

Example of Kinship Relations: combinations
of relations marriage and descent.
 Direct: sister, husband, son
 Combination: sister-in-law, uncle, grandson

Position is a grouping;
Role is what characterizes the group

Positional analysis
 Separate actors into subsets of positions 
Partitioning
 Each position is a mathematical equivalence class

Role Analysis
 Discover and describe patterns of relationships 
Pattern Mining or Motif Discovery
 Global: look at the full set of edges
 Local: look at the neighborhood of an individual

Positional, then Role
a. Group actors into equivalence classes (positions)
b. Describe each position with an aggregate role
description.

Role, then Positional
a. Describe the relationships of each individual
b. Group actors that have equivalent or similar
patterns or relations

An equivalence class C is a set of ordered
pairs in which the following properties hold:
 Reflexivity: (a,a) ∈ C
 Symmetry: if (a,b) ∈ C, then (b,a) ∈ C
 Transitivity: if (a,b) and (b,c) ∈ C, then (a,c) ∈ C

An equivalence relation for set A partitions A
into equivalence classes {C1, …, Ck}


Goal: define a rule-based equivalence
relation that will partition a set of actors into
positions and roles
Three common definitions:
 Structural Equivalence
 Automorphic Equivalence
 Regular Equivalence


Two actors are structurally equivalent if they
have identical ties to and from the other
actors (Lorrain and White 1971).
Example:
 C1 = {1, 4}
 C2 = {2,5}
 C3 = {3}
1
4
2
5
3
0

0
0

0
0

1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1

0
0

1
0 

Two actors are automorphically equivalent if
they have identical ties to equivalent actors.
 Must have same number of ties
 Recursive definition

If we color the vertices by position,
 Vertices are equivalent if their neighborhoods
consist of the same number of the same colors

Example: Two families with exactly the same
number of children, parents, etc.

A graph isomorphism of graphs G and H is a
bijective mapping of vertices f(V(G))  V(H)
 such that all the edges remain the same
 That is, e(a,b) ∈ G if and only if e(f(a),f(b)) ∈ H

A graph automorphism is when the
isomorphism is to G itself
 That is, we rearrange the vertex labels of G

Example: Every possible labeling of a clique
is automorphically equivalent
 What about a ring? A binary tree?

Two actors are regularly equivalent if they
have ties to equivalent positions.
 Need not have the same number of ties
 Recursive definition

If we color the vertices by position,
 Vertices are equivalent if their neighborhoods
consist of the same set of colors
 But the quantity of each color does not matter

Example: Two families with different
numbers of children, parents, etc.

Structural: connect to
exactly the same neighbors
1
 {5,6}, {8,9}, singletons

Automorphic: connect to the
same distribution of colors
2
3
4
 {5,6,8,9}, {2,4}, singletons

Regular: connect to the
same colors
 {5,6,7,8,9}, {2,3,4}, {1}
5
6
7
8
9


Consider the matrix representations
Assume we arrange rows and columns by
equivalence class, creating blocks
 What do you notice about each block?
 What rule would each type of equivalence follow?

If we can make a simple statement about
each block:
 “Every relation within the block is (almost) always 1.”
 “Every relation within the block is (almost) always 0.”

We can form an image matrix/reduced graph

In automorphic equivalence, we expect to see
the same number of 1’s in each row and each
column within a block
 “Every relation within block Bij has a probability pij
of being present.”
 In-relations can be different from out-relations, so
Bij may be different from Bji


How would you construct a block model
based on regular equivalence?
What if we have weighted edges?

Exact equivalence is often too strict

Also want to know how similar are two actors

We can then cluster together similar actors

Euclidean distance
 Each vertex or group is a dimension in space
 Distance between row vectors & column vectors of
two actors:

Correlation (Pearson product-moment)
 If two actors are equivalent, the correlation between
their rows and columns will be +1

Hierarchical
Clustering

CONCOR


Iteratively: compute
row & column
correlations,
then split
PCA might be
superior

Relational Algebra
 Given multiple types of edges (say, Friend and Trust)
 Form an image matrix for each edge type (F and T)
 Image multiplication? Example: R = F x T
rxy means “x has a friend z who trusts y”

Optimal Partitioning?
 Exact equivalence  clear idea of “best” partition
 Using similarity  trade-off between tight variance
with a block and having a small number of blocks

Other tools and methods to compute
similarity and to partition?
These slides are based on
Wasserman and Faust (2004), Social Network Analysis:
Methods and Applications, Ch. 9 – 12.
Additional Reading


Concise online book on social network analysis:
www.faculty.ucr.edu/~hanneman/nettext/index.html
Review paper from the sociologist’s perspective:
Borgatti, S. and Everett, M., Notions of Position in Social
Network Analysis, Sociological Methodology (22), 1-35,
1992.