1 of 40

Mathematical Foundations

MGT 780 SPRING 2022

STEVE BORGATTI

​

(C) 2022 STEPHEN P BORGATTI

1

2/8/2022

8 FEB

2 of 40

Agenda

  • Graphs
  • Trajectories
  • Relational composition
  • One-mode projections

(C) 2022 STEPHEN P BORGATTI

2

2/8/2022

3 of 40

What is a network?

(C) 2022 STEPHEN P BORGATTI

3

2/8/2022

4 of 40

Graph-theoretic terminology

  • Nodes
    • Aka vertices or points in more mathematical work
    • Actors, agents, egos, alters, contacts in more sociological work
    • Nodes can individuals or collective actors, such as countries
    • In social network analysis, nodes typically have agency – they act
  • Ties
    • Aka edges, arcs or lines in more technical work
    • Links, bonds, direct connections etc in more sociological work
    • Ties are typically binary: they link exactly two nodes
    • In SNA, the ties are (usually) thought of as the result of actor choices

(C) 2021 STEPHEN P BORGATTI

4

8 February 2022

5 of 40

A network is represented by a graph

  • A graph G(V,E) is …
    • A set of vertices V, together with …
    • A set of edges E, representing ties
  • Presence of a tie
    • (d,b) ∈ E means there is tie between b and d
  • Nodes that have a tie are “adjacent”

​

(C) 2021 STEPHEN P BORGATTI

5

8 February 2022

6 of 40

Adjacency matrix

  • 1-mode matrix representation of a network

(C) 2022 STEPHEN P BORGATTI

6

2/8/2022

​

a

b

c

d

e

f

g

a

0

1

0

0

0

0

0

b

1

0

1

0

1

0

0

c

0

1

0

1

1

0

0

d

0

0

1

0

0

0

0

e

0

1

1

0

0

1

0

f

0

0

0

0

1

0

1

g

0

0

0

0

0

1

0

7 of 40

Relations

  • A relation is a mapping of one set of items to �another
  • A graph is a relation that maps the set of nodes �to itself
  • Suppose we have a graph G(V,F) of friendship ties
    • F is relation that maps friends to each other
    • Notation bFd means that b and d are connected by relation F

(C) 2022 STEPHEN P BORGATTI

7

2/8/2022

8 of 40

Isolates and components

  • A component is a fragment of a network with no ties to any other component
    • A better definition is forthcoming …
  • An isolate is a node with no ties
    • Every isolate is a component

(C) 2022 STEPHEN P BORGATTI

8

2/8/2022

A network with 4 components, including two isolates

->c = component(padgett)

->draw padgett c

9 of 40

Matrix representation of a network

  • Adjacency matrix

(C) 2022 STEPHEN P BORGATTI

9

2/8/2022

​

a

b

c

d

e

f

g

a

0

1

0

0

0

0

0

b

1

0

1

0

1

0

0

c

0

1

0

1

1

0

0

d

0

0

1

0

0

0

0

e

0

1

1

0

0

1

0

f

0

0

0

0

1

0

1

g

0

0

0

0

0

1

0

10 of 40

Isolates and components

  • A component is a fragment of a network with no ties to any other component
    • A better definition is forthcoming …
  • An isolate is a node with no ties
    • Every isolate is a component

(C) 2022 STEPHEN P BORGATTI

10

2/8/2022

A network with 4 components, including two isolates

11 of 40

Graph traversals

(C) 2022 STEPHEN P BORGATTI

11

2/8/2022

12 of 40

Graph traversals / trajectories

  • You can trace a ‘path’ from one node to another
    • E.g., movement of object from node to node across ties
  • Walks
    • Unrestricted trajectory
    • Can double-back on itself, revisit nodes and lines
    • 1—2—1—7—2—3—1—8
    • Coin going from person to person in an economy

(C) 2022 STEPHEN P BORGATTI

12

2/8/2022

13 of 40

Graph traversals / trajectories – cont.

  • Walks
    • Unrestricted trajectory
    • Can double-back on itself, revisit nodes and lines
    • 1—2—1—7—2—3—1—8
  • Trails
    • Can revisit nodes but not lines
    • 1—8—7—1—2
    • E.g. gossip

(C) 2022 STEPHEN P BORGATTI

13

2/8/2022

14 of 40

Graph traversals / trajectories – cont.

  • Walks - unrestricted trajectory
    • 1—2—1—7—2—3—1—8 … (may be infinite)
    • Coin
  • Trails - can revisit nodes but not lines
    • 1—8—7—1—2 … etc
    • E.g. gossip
  • Paths – cannot revisit line or node
    • 1—8—7—6—4—3—2 (must stop)
    • E.g., air travel

(C) 2022 STEPHEN P BORGATTI

14

2/8/2022

15 of 40

Some possible flow processes

(C) 2022 STEPHEN P BORGATTI

15

2/8/2022

​

Paths

Trails

Walks

Move/transfer�(one place at one time)

Person driving from city to city via highways

Used book passing from person to person

Coin moving through economy

Copy�(multiple places at one time

Virus (once you get it are immune to it)

Gossip

Emotion

  • Can invent other trajectory types as well
    • A walk that can revisit lines but doesn’t go back and forth between two nodes
      • E.g., not A—B—A—C etc
    • Trails that die out over time
    • Paul Erdos

16 of 40

Flow simulation

  • Given a set of rules for how something flows, we can write a simulation. E.g.:
    • Drop info on random node and let it diffuse from there
    • Record how long it takes to reach each node
    • Calculate average time-until-arrival for each �node

​

(C) 2022 STEPHEN P BORGATTI

16

2/8/2022

repeat

On average, things reach 6 sooner than any other node

->dsp flowsim(campnet)

17 of 40

Structural asymmetry – cont.

  • In an undirected graph, geodesic distances are symmetric
  • But when flows are not restricted �to shortest paths, flow outcomes �are not necessarily symmetric

(C) 2020 STEPHEN P BORGATTI

17

8 February 2022

Expected Values of Flow Outcomes

It is faster to go from 5 to 10 �than the other way around

“Used good” process. Results are mean first passage times.

 

1

2

3

4

5

6

7

8

9

10

​

1

 

9.5

9.4

9.5

9.5

5.0

8.1

8.2

8.1

8.2

8.4

2

1.0

 

7.0

7.1

7.0

4.0

7.1

7.1

7.1

7.1

6.1

3

1.0

7.1

 

7.0

7.2

4.0

7.1

7.1

7.1

7.1

6.1

4

1.0

6.9

6.9

 

7.0

4.0

7.1

7.0

7.1

7.0

6.0

5

1.0

6.9

7.0

7.1

 

4.0

7.1

7.1

7.1

7.0

6.0

6

10.0

13.0

13.1

13.0

12.8

 

5.2

5.3

5.3

5.2

9.2

7

10.2

13.3

13.3

13.1

13.1

3.5

 

4.3

4.3

4.2

8.8

8

10.3

13.3

13.2

13.3

13.4

3.5

4.3

 

4.3

4.3

8.9

9

10.3

13.2

13.4

13.3

13.2

3.5

4.3

4.3

 

4.3

8.9

10

10.2

13.1

13.1

13.2

13.2

3.5

4.2

4.3

4.3

 

8.8

​

​

​

​

​

​

​

​

​

​

​

​

​

6.1

10.7

10.7

10.7

10.7

3.9

6.1

6.1

6.1

6.1

​

18 of 40

Length of trajectories

  • Many different ways to get from A to B
  • Some traversals are longer than others
  • The length of a traversal is the number of links in it
  • The shortest traversal btw two nodes is a geodesic
    • Can be multiple geodesics between same two nodes
  • The length of a geodesic is called the distance
    • “degrees of separation”
  • If we compute the distance between all pairs of nodes, �we have a distance matrix

(C) 2022 STEPHEN P BORGATTI

18

2/8/2022

19 of 40

Geodesic Distance Matrix

(C) 2021 STEPHEN P BORGATTI

19

8 February 2022

​

a

b

c

d

e

f

g

a

0

1

2

3

2

3

4

b

1

0

1

2

1

2

3

c

2

1

0

1

1

2

3

d

3

2

1

0

2

3

4

e

2

1

1

2

0

1

2

f

3

2

2

3

1

0

1

g

4

3

3

4

2

1

0

Distance matrix is nuanced version of the adjacency matrix – zeros replaced with gradations of separation

​

a

b

c

d

e

f

g

a

0

1

0

0

0

0

0

b

1

0

1

0

1

0

0

c

0

1

0

1

1

0

0

d

0

0

1

0

0

0

0

e

0

1

1

0

0

1

0

f

0

0

0

0

1

0

1

g

0

0

0

0

0

1

0

Avg = 1.93

->dist = geo(borg4cent)

->dsp dist

20 of 40

Component

  • A component is a maximal subgraph in which every node can reach every other by some path
    • No matter how long it is
  • Maximal means if you can add another node without violating the reachability condition, then you must

(C) 2022 STEPHEN P BORGATTI

20

2/8/2022

->unpack wiring

->c = component(rdgam)

->draw rdgam c

21 of 40

Directed graphs

(C) 2022 STEPHEN P BORGATTI

21

2/8/2022

22 of 40

Directed graphs (digraphs)

  • Graphs can be directed or undirected
  • Undirected
    • Edges don’t have direction
    • Suppose G(V,M) indicates marriage ties
      • If xMy then yMx
  • Directed
    • Ties (‘arcs’) have direction
    • Suppose G(V,A) indicates advice-seeking ties
    • Then uAv and vAu mean different things
      • uAv means that u seeks advice from v
      • vAu means that v seeks advice from u

​

(C) 2021 STEPHEN P BORGATTI

22

8 February 2022

23 of 40

Adjacency matrix of directed graph

  • Adjacency matrix is (usually) not symmetric

(C) 2021 STEPHEN P BORGATTI

23

8 February 2022

​

a

b

c

d

e

f

a

0

0

0

0

0

1

b

0

0

1

0

0

1

c

0

1

0

1

0

1

d

1

0

0

0

1

0

e

0

0

0

1

0

1

f

1

0

0

1

0

0

Consider “likes” and “seeks advice from”

Reciprocated tie – technically 2 ties, one in each direction

->dsp geo(katz)

24 of 40

Directed paths and components

  • A directed path respects the direction of the arcs
    • X 🡪 Y 🡪 Z is a directed path
    • X 🡨 Y 🡪 Z is not
  • A strong component is a maximal subgraph in which each node reach every other by a directed path
  • A weak component ignores direction of ties

(C) 2022 STEPHEN P BORGATTI

24

2/8/2022

graph with 3 �strong components

->c = component(campnet)

->draw campnet c

25 of 40

A network with 4 weak components

(C) 2021 STEPHEN P BORGATTI

25

8 February 2022

Recent acquisition

Older acquisitions

Original company

Data drawn from Cross, Borgatti & Parker 2001.

Who you go to so that you can say ‘I ran it by ____, and she says ...’

26 of 40

Transposition

  • Suppose F is the “father of” relation.
    • uFv means that u is the father of v
  • We use F’ to indicate the converse of F, which is the reciprocal role: “child of”
    • If uFv, then vF’u -- v is the child of u
  • If we represent a relation as an adjacency matrix, the converse is represented by the transpose of the matrix
    • Get the transpose by writing each row as a column, or vice-versa

(C) 2021 STEPHEN P BORGATTI

26

8 February 2022

​

A

B

C

D

E

F

A

0

0

0

0

0

1

B

0

0

1

0

0

1

C

0

1

0

1

0

1

D

1

0

0

0

1

0

E

0

0

0

1

0

1

F

1

0

0

1

0

0

matrix A

“x advises y”

​

A

B

C

D

E

F

A

0

0

0

1

0

1

B

0

0

1

0

0

0

C

0

1

0

0

0

0

D

0

0

1

0

1

1

E

0

0

0

1

0

0

F

1

1

1

0

1

0

matrix A’

“x is advised by y”

->A = copy(katz)

->At = transpose(A)

27 of 40

Matrix multiplication

(C) 2022 STEPHEN P BORGATTI

27

2/8/2022

28 of 40

Applications

  • Lengths of walks
  • 2-mode to 1-mode conversions
  • Transitivity
  • Relational composition
  • Embeddedness
  • Access to resources

​

(C) 2022 STEPHEN P BORGATTI

28

2/8/2022

29 of 40

Multiplying a matrix by a column vector

  • Multiply every number in a row by the corresponding number in the column
    • Repeat for each row
  • Suppose A is network and B is wealth of each node
    • Then C is total wealth of each person’s friends

(C) 2022 STEPHEN P BORGATTI

29

2/8/2022

A

​

B

​

🡺

 

C

0

1

0

1

​

3

​

0*3 + 1*0 + 0*2 + 1*4

4

1

0

1

0

X

0

==>

1*3 + 0*1 + 1*2 + 0*4

5

0

1

0

1

2

0*3 + 1*0 + 0*2 + 1*4

4

0

1

0

0

​

4

​

0*3 + 1*0 + 0*2 + 0*4

0

30 of 40

Row sums via matrix multiplication

  • To get the row sums of a matrix, multiply it by a column of 1s

​

​

​

​

  • If A is a network, C is the number of ties each node has

(C) 2022 STEPHEN P BORGATTI

30

2/8/2022

A

​

B

​

C

0

1

0

1

​

1

​

2

1

0

1

0

X

1

==>

2

0

1

0

1

1

2

0

1

0

0

​

1

​

1

31 of 40

Friend of a friend network

  • Multiply adjacency matrix by itself
  • L is the ‘who likes whom’ network

​

​

​

​

  • LL(a,c) = 2 means that there are two people that a likes that like c
    • Node c is the friend of a friend (actually c is the friend of two of a’s friends)

(C) 2022 STEPHEN P BORGATTI

31

2/8/2022

​

L

​

​

L

​

​

LL

​

a

b

c

d

​

​

a

b

c

d

​

​

a

b

c

d

a

0

1

0

1

​

a

0

1

0

1

​

a

1

0

2

0

b

0

0

1

0

x

b

0

0

1

0

=

b

0

1

0

0

c

0

1

0

0

​

c

0

1

0

0

​

c

0

0

1

0

d

1

0

1

0

​

d

1

0

1

0

​

d

0

2

0

1

32 of 40

Powers of the adjacency matrix

  • If you multiply an adjacency matrix X by itself, you get XX or X2
  • A given cell x2ij gives the number of walks from node i to node j of exactly length 2

​

(C) 2019 STEPHEN P BORGATTI

32

8 February 2022

​

L

​

​

L

​

​

LL

​

a

b

c

d

​

​

a

b

c

d

​

​

a

b

c

d

a

0

1

0

1

​

a

0

1

0

1

​

a

1

0

2

0

b

0

0

1

0

x

b

0

0

1

0

=

b

0

1

0

0

c

0

1

0

0

​

c

0

1

0

0

​

c

0

0

1

0

d

1

0

1

0

​

d

1

0

1

0

​

d

0

2

0

1

More generally, the cells of Xk give the number of walks of length exactly k from each node to every other

33 of 40

Matrix powers example

(C) 2019 STEPHEN P BORGATTI

33

8 February 2022

​

1

2

3

4

5

6

​

​

1

2

3

4

5

6

​

​

1

2

3

4

5

6

​

​

1

2

3

4

5

6

1

0

1

0

0

0

0

​

1

1

0

1

0

0

0

​

1

0

2

0

1

1

0

​

1

2

0

4

1

1

1

2

1

0

1

0

0

0

​

2

0

2

0

1

1

0

​

2

2

0

4

1

1

1

​

2

0

6

2

5

6

1

3

0

1

0

1

1

0

​

3

1

0

3

1

1

1

​

3

0

4

2

4

5

1

​

3

4

2

13

7

7

5

4

0

0

1

0

1

0

​

4

0

1

1

2

1

1

​

4

1

1

4

2

4

1

​

4

1

5

7

8

7

4

5

0

0

1

1

0

1

​

5

0

1

1

1

3

0

​

5

1

1

5

4

2

3

​

5

1

6

7

7

12

2

6

0

0

0

0

1

0

​

6

0

0

1

1

0

1

​

6

0

1

1

1

3

0

​

6

1

1

5

4

2

3

X

X2

X3

X4

Note that shortest path from 1 to 5 is three links, so x1,5 = 0 until we get to X3

34 of 40

Relational composition

  • Suppose B is the relation “is the brother of”
    • uBv means u is the brother of v
  • Suppose F is the relation “father of”
  • We can define compound relation FF, which is ‘father of the father of’
    • Aka grandfather
  • Define compound relation BF as “brother of the father of”
    • uBFx means u is the brother someone who is the father of x. i.e. uncle of
    • Let U = BF. Then zUx or zBFx both mean z is the uncle of x

(C) 2021 STEPHEN P BORGATTI

34

8 February 2022

35 of 40

Composition of relations

  • We represent each social relation (e.g., F= friend of, B = boss of) as a matrix
  • To create the compound relation friend of the boss of (FB), we just multiply the two matrices

​

​

​

​

  • FB(c,a) = 1 means that person c is friends with someone (namely b) who is the boss of a. i.e., c is friends with a’s boss
  • FB(a,a) = 1 means person a is friends with someone (b again) who is her boss. i.e., a is friends with her boss.

​

​

​

​

​

(C) 2019 STEPHEN P BORGATTI

35

8 February 2022

​

F

​

​

B

​

​

FB

​

a

b

c

d

​

​

a

b

c

d

​

​

a

b

c

d

a

0

1

0

1

 

a

0

0

1

1

 

a

1

0

0

0

b

1

0

1

0

x

b

1

0

0

0

=

b

0

1

1

1

c

1

1

0

1

 

c

0

1

0

0

 

c

1

0

1

1

d

1

0

1

0

 

d

0

0

0

0

 

d

0

1

1

1

->unpack padgett

->mb = prod(padgm padgb)

36 of 40

Composition of relations

  • B’ is the transpose of B. B’ is the “converse” of the B relationship. If B was boss of, then B’ is reports to or is subordinate of.
  • To create the compound relation ‘friend of the subordinate of’ (FB’), we just multiply the two matrices

​

​

​

​

  • FB’(c,a) = 1 means that person c is friend of someone (namely d) who is a subordinate of a. i.e., c is friends with a’s subordinate
  • FB’(a,a) = 1 means person a is friends with someone (d) who is her subordinate. i.e., a is friends with one of her direct reports.

​

​

​

​

​

​

(C) 2019 STEPHEN P BORGATTI

36

8 February 2022

​

F

​

​

B'

​

​

FB’

​

a

b

c

d

​

​

a

b

c

d

​

​

a

b

c

d

a

0

1

0

1

 

a

0

1

0

0

 

a

1

0

1

0

b

1

0

1

0

x

b

0

0

1

0

=

b

1

1

0

0

c

1

1

0

1

 

c

1

0

0

0

 

c

1

1

1

0

d

1

0

1

0

 

d

1

0

0

0

 

d

1

1

0

0

37 of 40

Products of matrices & their transposes

  • XX’ = product of matrix X by its transpose
  • Computes sums of products of each pair of rows (cross-products)
  • Similarities among rows

​

(C) 2019 STEPHEN P BORGATTI

37

8 February 2022

X

​

1

2

3

4

​

​

Mary

Bill

John

Larry

Tina

​

​

Mary

Bill

John

Larry

Tina

Mary

0

1

1

1

​

1

0

1

0

0

1

​

Mary

3

1

1

0

1

Bill

1

0

1

0

​

2

1

0

0

0

1

​

Bill

1

2

0

0

1

John

0

0

0

1

​

3

1

1

0

0

0

​

John

1

0

1

0

0

Larry

0

0

0

0

​

4

1

0

1

0

0

​

Larry

0

0

0

0

0

Tina

1

1

1

0

​

​

​

​

​

​

​

​

Tina

2

2

0

0

2

X’

XX’

38 of 40

Products of matrices & their transposes

  • X’X = pre-multiplying X by its transpose
  • Computes sums of products of each pair of columns (cross-products)
  • The basis for most similarity measures

​

(C) 2019 STEPHEN P BORGATTI

38

8 February 2022

​

Mary

Bill

John

Larry

Tina

​

​

1

2

3

4

​

​

1

2

3

4

1

0

1

0

0

1

​

Mary

0

1

1

1

​

1

2

1

2

0

2

1

0

0

0

1

​

Bill

1

0

1

0

​

2

1

2

2

1

3

1

1

0

0

0

​

John

0

0

0

1

​

3

1

1

2

1

4

1

0

1

0

0

​

Larry

0

0

0

0

​

4

0

1

1

2

​

​

​

​

​

​

​

Tina

1

1

1

0

​

​

​

​

​

​

X’

X

X’X

39 of 40

(C) 2019 STEPHEN P BORGATTI

39

8 February 2022

E1

E2

E3

E4

E5

E6

E7

E8

E9

E10

E11

E12

E13

E14

EVELYN

1

1

1

1

1

1

0

1

1

0

0

0

0

0

LAURA

1

1

1

0

1

1

1

1

0

0

0

0

0

0

THERESA

0

1

1

1

1

1

1

1

1

0

0

0

0

0

BRENDA

1

0

1

1

1

1

1

1

0

0

0

0

0

0

CHARLOTTE

0

0

1

1

1

0

1

0

0

0

0

0

0

0

FRANCES

0

0

1

0

1

1

0

1

0

0

0

0

0

0

ELEANOR

0

0

0

0

1

1

1

1

0

0

0

0

0

0

PEARL

0

0

0

0

0

1

0

1

1

0

0

0

0

0

RUTH

0

0

0

0

1

0

1

1

1

0

0

0

0

0

VERNE

0

0

0

0

0

0

1

1

1

0

0

1

0

0

MYRNA

0

0

0

0

0

0

0

1

1

1

0

1

0

0

KATHERINE

0

0

0

0

0

0

0

1

1

1

0

1

1

1

SYLVIA

0

0

0

0

0

0

1

1

1

1

0

1

1

1

NORA

0

0

0

0

0

1

1

0

1

1

1

1

1

1

HELEN

0

0

0

0

0

0

1

1

0

1

1

1

0

0

DOROTHY

0

0

0

0

0

0

0

1

1

0

0

0

0

0

OLIVIA

0

0

0

0

0

0

0

0

1

0

1

0

0

0

FLORA

0

0

0

0

0

0

0

0

1

0

1

0

0

0

EV

LA

TH

BR

CH

FR

EL

PE

RU

VE

MY

KA

SY

NO

HE

DO

OL

FL

E1

1

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

E2

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

E3

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

E4

1

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

E5

1

1

1

1

1

1

1

0

1

0

0

0

0

0

0

0

0

0

E6

1

1

1

1

0

1

1

1

0

0

0

0

0

1

0

0

0

0

E7

0

1

1

1

1

0

1

0

1

1

0

0

1

1

1

0

0

0

E8

1

1

1

1

0

1

1

1

1

1

1

1

1

0

1

1

0

0

E9

1

0

1

0

0

0

0

1

1

1

1

1

1

1

0

1

1

1

E10

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

0

E11

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

E12

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

E13

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

E14

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

Multiplying a matrix by its transpose

->dsp prod(davis transp(davis))�->dsp xxt(davis)

40 of 40

Alters in common

  • Consider campnet (call it C)
  • The product CC’ gives the number of outgoing choices in common
    • For any pair, it says whether they like any of the same people
  • The product C’C gives the number of incoming choices in common
    • For any pair, it says whether they are liked by any of the same people

(C) 2022 STEPHEN P BORGATTI

40

2/8/2022

->dsp xxt(campnet)�->dsp xtx(campnet)