1
Session 4 – Network Analysis
Oleg Deev
Network Analysis2
Undirected Graphs
̶ A graph with undirected edge
interactions between variables is
an undirected graph.
̶ These graphs produce a class of
models commonly known as
undirected graphical models,
which are suitable for analyzing
similarities and correlated
behaviors
Network Analysis3
Directed Graphs
̶ A graph with directed edges between variables is a
directed graph
̶ A directed graph without cycles is a directed acyclic graph
(DAG)
Network Analysis4
Other Network Types
̶ A partially directed acyclic graph (or chain graph) is a
type of DAG that allows bi-directed edges.
e.g. A –> B –> C
̶ A weighted graph is one that has a numeric value
(weights) associated with each edge (node)
Network Analysis5
Bipartite Graphs
̶ A bipartite graph is an undirected graph in which
variables are categorized into two sets, such that nodes
in one set can only interact with those in the other set,
and no two nodes in the same set are connected
Network Analysis6
Multilayer Networks
̶ In reality, individual units belong to more than one
network (in content, in space, in time)
̶ This give rise to multilayer networks
Network Analysis7
Network Representation
̶ A graph-theoretic representation ! = ($; &; ') of
relationships & (edges, links) of strengths ' between
units $ (vertices, nodes)
̶ Nodes: individuals, companies, stocks, consumers,
industries, countries
̶ Physical links:
̶ import/export
̶ borrowing/lending
̶ common shareholdings
̶ supply chains
̶ Statistical links:
̶ correlations
̶ similarities (commercial, financial, operations)
Network Analysis8
Adjacency Matrix
!",$ = &
1 if ( and ) are connceted
0 otherwise
Example:
Network Analysis9
Adjacency List
̶ The adjacency list stores only the non-zero elements of
the adjacency matrix in a full list of all vertices.
Example:
Network Analysis10
Edge List
̶ The edge list stores only the non-zero elements of the
adjacency matrix.
Example:
Network Analysis11
Centrality Measures
̶ A common question we may ask when analyzing the structure
of a network is which vertices are more important?
̶ To answer this question depends on what we mean by
important. Define importance in terms
̶ the most connected vertex
̶ the vertex closest to all others
̶ the vertex in the middle of the network
̶ the most influential vertex
̶ The most common centrality measures
̶ degree centrality
̶ closeness centrality
̶ betweenness centrality
̶ eigenvector centrality
Network Analysis12
Degree Centrality
̶ The simplest measure of importance is the degree centrality
̶ The vertex with largest degree exerts the greatest effect on the
network
̶ Degree centrality: number of nearest neighbors
! " = $
%&'
(
)*% = $
%&'
(
)%*
̶ Sensitive to the addition of one more node
̶ We cannot compare degree centrality of vertices belonging to two
different network
̶ Normalized degree centrality (relative metric to compare degree
centrality)
+,(*) =
1
0 − 1
!(")
Network Analysis13
Degree Centrality: ExampleI
I
Network Analysis14
In-Degree and Out-Degree
In-Degree: the number of edges incoming to a vertex
!"
←
= %
&'(
)
*"&
Out-Degree: the number of edges outgoing from a vertex
!"
→
= %
&'(
)
*"&
I
I
I
Network Analysis15
Closeness Centrality
̶ Measures how close a node is to all the other nodes in
network (in terms of the shortest path)
! " =
1
∑&'(
)
*(", -)
where *(", -) is the shortest path between the nodes " and ̶
Normalized closeness centrality (relative metric to
compare closeness centrality)
/0(1) = 2 − 1 !(")
Network Analysis16
Closeness Centrality: ExampleI
I
Network Analysis17
Betweenness Centrality
̶ The number of shortest paths from all vertices to all
others that pass through a node.
! " = $
%&'&(
)%((')
)%(
where ,-(") is the number of shortest paths between , and
- that pass through ", and ,- is the total number of shortest
paths between , and -.
̶ Probability that a communication from , to - will go
through " (the frequency of " lying on the shortest path)
̶ Normalized betweenness centrality
./(') =
2
1 − 1 1 − 2
!(")
Network Analysis18
Betweenness Centrality: ExampleI
I
I
Network Analysis19
Eigenvector Centrality
̶ Eigenvector centrality measures assign an importance
score to vertices in a way that is proportional to the
importance scores of its neighbors hence the importance
of a node depends on the importance of its neighbors
̶ Shows how a well-connected vertex is connected to other
well-connected vertices
̶ This involves an eigenvector problem of the form
!" = $%&
where ! is the adjacency matrix, & is a vector containing
the eigenvector centralities, and $% is the largest
eigenvalue of !
̶ PageRank is a form of eigenvector centrality
Network Analysis20
Centrality Measures: ExampleI
I
I
I
Network Analysis21
Centrality Measures: Example
̶ Degree most central nodes: D & K
̶ Closeness most central nodes: H
̶ Betweenness most central nodes: H
̶ Eigenvector most central nodes: D & K
Network Analysis22
Network Density
̶ The density of a network is the frequency of realized
edges relative to potential edges
̶ Undirected Networks: For ! number of nodes, there are
!(! − 1)/2 possible edges
den +, =
./
0(012)/3
̶ Directed Networks: For ! number of nodes, there are
!(! − 1) possible edges
den 4, =
5,
!(! − 1)
Network Analysis23
Network Analysis
̶ Can we construct network, when we don‘t have
information on the exact links?
̶ Network reconstruction algorithms
̶ Similarity networks
̶ Complexity reductions
̶ Threshold networks
̶ Spanning trees
̶ Simulations on networks
̶ Flow analysis
̶ Community/pattern identification
Network Analysis24
Applications in Risk Management
̶ Market risk
̶ Asset correlation networks
̶ Volatility-based networks
̶ Liquidity and operational risks
̶ Payment networks
̶ Counterparty and systemic risks
̶ Exposure networks