MATH347

MATH347 L27: SVD applications

New concepts:
- Graph representation of social networks
- Clustering through SVD

Graph representation of networks

A Social Network consists of:
- Actors (e.g., individuals, organizations)
- Interactions (e.g., communication, transactions)
A mathematical Graph contains a set of vertices and edges, $G = (V, E)$
For a graph with $m$ edges and $n$ vertices, define edge-vertex incidence matrix
$𝑩 \in ℝ^{m \times n}, 𝑩 = [b_{i j}], i = 1, \dots, m, j = 1, \dots, n$ $Interaction i between actor p and actor q : b_{i p} = 1, b_{i q} = - 1$
Connectivity matrix $𝑪 \in ℝ^{n \times n}$ , $𝑪 = [c_{i j}]$ , $c_{i j} = c_{j i} = 1$ for $i, j$ on an edge
Construct a graph of $n = 2 N$ actors with two types of interactions:
- $m_{Far}$ interactions between $p ⩽ n / 2$ and $q > n / 2$
- $m_{Near}$ interactions between $p ⩽ n / 2$ and $q ⩽ n / 2$
- $m_{Near}$ interactions between $p > n / 2$ and $q > n / 2$
Suppose the interaction groups were not known initially.

Could the interaction groups be found from the incidence matrix?

Construct incidence matrix

Far interactions

matlab>>

mFar=100; mNear=30; m=mFar+mNear; n=50;
B=zeros(m,n); C=zeros(n,n); E=[];
for r=1:mFar
  p=randi(n/2); q=randi([n/2+1 n]);
  B(r,p)= 1; B(r,q)=-1; E=[E [p; q]]; C(p,q)=1; C(q,p)=1;
end

>>

Near interactions

matlab>>

for r=mFar+1:mFar+mNear
  p=randi(n/2); q=randi(n/2);
  B(r,p)=1; B(r,q)=-1; E=[E [p; q]]; C(p,q)=1; C(q,p)=1;
end

>>

matlab>>

for r=mFar+mNear+1:mFar+2*mNear
  p=randi([n/2+1 n]); q=randi([n/2+1 n]);
  B(r,p)=1; B(r,q)=-1; E=[E [p; q]]; C(p,q)=1; C(q,p)=1;
end

>>

matlab>>

Examples

Figure 1. From left to right: networks with more, less, equal far, near interactions

SVD clustering

SVD of $𝑩$

matlab>>

[U S V]=svd(B);
plot(V(1:n/2,1),V(1:n/2,2),'o'); hold;
plot(V(n/2+1:n,1),V(n/2+1;n,2),'o')

>>

matlab>>

Graphical representation of network