Network Science

Class 2: Graph Theory

Ganesh Bagler
— Adapted from —
Albert-László Barabási
(With Roberta Sinatra)
Section 1

The Bridges of Konigsberg

Köningsberg, 1726
 Köningsberg Problem:
Origin of Graph Theory

Can one walk across the seven bridges and never

cross the same one twice?
1735: Euler’s theorem:

(a) If a graph has more than two nodes of odd degree, there is no path.

(b) If a graph is connected and has no odd degree nodes, it has at least one path.
Section 2

Networks and graphs

COMPONENTS OF A COMPLEX SYSTEM

 components: nodes, vertices N

 interactions: links, edges L

 system: network, graph (N,L)

Network Science: Graph Theory
NETWORKS OR GRAPHS?

network often refers to real systems

•www,
•social network
•metabolic network.

Language: (Network, node, link)

graph: mathematical representation of a network

•web graph,
•social graph (a Facebook term)

Language: (Graph, vertex, edge)

We will try to make this distinction whenever it is appropriate,

but in most cases we will use the two terms interchangeably.

Network Science: Graph Theory

A COMMON LANGUAGE

N=4
L=4
Network Science: Graph Theory
CHOOSING A PROPER REPRESENTATION

The choice of the proper network representation determines our

ability to use network theory successfully.

In some cases there is a unique, unambiguous representation.

In other cases, the representation is by no means unique.

For example, the way we assign the links between a group of

individuals will determine the nature of the question we can study.

Network Science: Graph Theory

CHOOSING A PROPER REPRESENTATION

If you connect individuals

that work with each other,
you will explore
the professional network.

Network Science: Graph Theory

CHOOSING A PROPER REPRESENTATION

If you connect those that

have a romantic and
sexual relationship, you
will be exploring the
sexual networks.

Network Science: Graph Theory

CHOOSING A PROPER REPRESENTATION

If you connect individuals based on their first name

(all Peters connected to each other), what will you will
be exploring?

It is a network, nevertheless.

Network Science: Graph Theory

UNDIRECTED VS. DIRECTED NETWORKS

Undirected Directed
Links: undirected (symmetrical) Links: directed (arcs).

Graph: Digraph = directed graph:

L
A
D
M B An undirected
F
C link is the
I superposition of
D two opposite
B G directed links.
E
G
H A
C
F
Undirected links : Directed links :
coauthorship links URLs on the www
Actor network phone calls
protein interactions metabolic reactions

Network Science: Graph Theory

Section 2.2 Reference Networks
Section 2.3

Degree, Average Degree and

Degree Distribution
NODE DEGREES

Node degree: the number of links connected to the node.

Undirected

kA =1 kB = 4
B

In directed networks we can define an in-degree and out-degree.

B D
Directed

C The (total) degree is the sum of in- and out-degree.

G
E k Cin  2 k Cout  1 kC  3
A

Source: a node with kin= 0; Sink: a node with kout= 0.

A BIT OF STATISTICS

Network Science: Graph Theory

AVERAGE DEGREE
Undirected

1 N
2L
j k   ki k º
N i 1 N
i

N – the number of nodes in the graph

N N
1 1
k k
D
B
k in
 in
, k out
 out
, k in  k out
Directed

C i i
N i 1 N i 1

E
A
L
F
k º
N

Network Science: Graph Theory

Average Degree

Network Science: Graph Theory

DEGREE DISTRIBUTION

Degree distribution
P(k): probability that a
randomly chosen node
has degree k

Nk = # nodes with degree k

P(k) = Nk / N  plot
DEGREE DISTRIBUTION
DEGREE DISTRIBUTION
DEGREE DISTRIBUTION
DEGREE DISTRIBUTION
DEGREE DISTRIBUTION
 Role of Degree Distributions
• Degree distributions dictate the topological and dynamical
properties of the network.

• Scale-free networks
- Heterogeneous degree distributions
- Importance of ‘hubs’
- Hubs as control elements
- Structural integrity vs. dynamic integrity

• Scale-free distributions and averages

“Don’t cross the river if it on an average only 5 feet deep.”

• Mediocristan vs. Extremistan (NN Taleb)

- How to become fat by eating heavily on one day?
- How to get rich in one day?
DEGREE DISTRIBUTION

Discrete Representation: pk is the probability that a node has degree k.

Continuum Description: p(k) is the pdf of the degrees, where

k2

ò p(k)dk
k1

represents the probability that a node’s degree is between k1 and k2.

Normalization condition:
¥ ¥

åp k =1 ò p(k)dk = 1
0 K min

where Kmin is the minimal degree in the network.

Network Science: Graph Theory

Section 2.4

Adjacency matrix
ADJACENCY MATRIX

4 4

3 3
2 2
1 1

Aij=1 if there is a link between node i and j

Aij=0 if nodes i and j are not connected to each other.

Note that for a directed graph (right) the matrix is not symmetric.

if there is a link pointing from node j and i

if there is no link pointing from j to i. Network Science: Graph Theory
ADJACENCY MATRIX AND NODE DEGREES
æ0 1 0 1ö N

ç ÷ ki = åA
Undirected

4 ij
1 0 0 1÷
Aij = ç
j =1

ç0 0 0 1÷ N

3 ç ÷ k j = å Aij
1
2
è1 1 1 0ø i=1

Aij = A ji N N

L = å ki = å Aij
1 1
Aii = 0 2 i=1 2 ij

æ 0 0 0 0 ö
ç ÷
Directed

Aij = ç ÷
4 1 0 0 1
ç 0 0 0 1 ÷ N

ç ÷ k out
= å Aij
3 è 1 0 0 0 ø j
i=1
2
1 N N N
L = åk = åk = å Aij
Aij ¹ A ji
in out
i j
i=1 j=1 i, j

Aii = 0
ADJACENCY MATRIX

a e
a b c d e f g h
a 0 1 0 0 1 0 1 0
b 1 0 1 0 0 0 0 1
c 0 1 0 1 0 1 1 0
h b d
d 0 0 1 0 1 0 0 0
e 1 0 0 1 0 0 0 0
f 0 0 1 0 0 0 1 0
g 1 0 1 0 0 0 0 0
f
h 0 1 0 0 0 0 0 0
g c

Network Science: Graph Theory

 Numerical Representation of a Graph
Adjacency matrix and edge list are two of the important numerical (computational)
representations of a graph/network.
A B

D
C E

A B C D E F G G node(i) node(j)

A A B

B A C

C B C

D B D

B F
E
C E
F
F G
G
Metcalfe’s Law
Section 4

Real networks are sparse

COMPLETE GRAPH

The maximum number of links a network

of N nodes can have is: Lmax = æç N ö÷ = N(N -1)
è2ø 2

A graph with degree L=Lmax is called a complete graph,

and its average degree is <k>=N-1

Network Science: Graph Theory

REAL NETWORKS ARE SPARSE

Most networks observed in real systems are sparse:

L << Lmax
or
<k> <<N-1.

WWW (ND Sample): N=325,729; L=1.4 106 Lmax=1012 <k>=4.51

Protein (S. Cerevisiae): N= 1,870; L=4,470 Lmax=107 <k>=2.39
Coauthorship (Math): N= 70,975; L=2 105 Lmax=3 1010 <k>=3.9
Movie Actors: N=212,250; L=6 106 Lmax=1.8 1013 <k>=28.78

(Source: Albert, Barabasi, RMP2002)

Network Science: Graph Theory

ADJACENCY MATRICES ARE SPARSE

Network Science: Graph Theory

Bipartite Graphs
PATHS

A path is a sequence of nodes in which each node is adjacent to the next one

Pi0,in of length n between nodes i0 and in is an ordered collection of n+1 nodes and n links

Pn = {i0,i1,i2,...,in } Pn = {(i0 ,i1),(i1,i2 ),(i2 ,i3 ),...,(in-1,in )}

• In a directed network, the path can follow only the direction of an arrow.
Network Science: Graph Theory
DISTANCE IN A GRAPH Shortest Path, Geodesic Path

B The distance (shortest path, geodesic path) between two

A nodes is defined as the number of edges along the shortest
path connecting them.

C
D *If the two nodes are disconnected, the distance is infinity.

B In directed graphs each path needs to follow the direction of

A the arrows.
Thus in a digraph the distance from node A to B (on an AB
path) is generally different from the distance from node B to A
C
D (on a BCA path).

Network Science: Graph Theory

NUMBER OF PATHS BETWEEN TWO NODES Adjacency Matrix

Nij,number of paths between any two nodes i and j:

Length n=1: If there is a link between i and j, then Aij=1 and Aij=0 otherwise.

Length n=2: If there is a path of length two between i and j, then AikAkj=1, and AikAkj=0
otherwise.
The number N
of paths of length 2:
N (2)
ij
= åA ik Akj = [A 2 ]ij
k =1

Length n: In general, if there is a path of length n between i and j, then Aik…Alj=1

and Aik…Alj=0 otherwise.
The number of paths of length n between i and j is*

N (n)
ij
= [A n
]ij

*holds for both directed and undirected networks.

Network Science: Graph Theory

FINDING DISTANCES: BREADTH FIRST SEARCH

Distance between node 0 and node 4:

[Link] at 0.

3 4
3
2
4 3 2 1 01 1 3 4

2
3 3
4 1 4

4 3
4 4
2 2

Network Science: Graph Theory

FINDING DISTANCES: BREADTH FIRST SEARCH

Distance between node 0 and node 4:

[Link] at 0.
[Link] the nodes adjacent to 1. Mark them as at distance 1. Put them in a queue.

3 4
3
2
4 3 2 1 1
0 1 3 4

2
3 3
4 1 4

4 3
4 4
2 2

Network Science: Graph Theory

FINDING DISTANCES: BREADTH FIRST SEARCH
Distance between node 0 and node 4:
[Link] at 0.
[Link] the nodes adjacent to 0. Mark them as at distance 1. Put them in a queue.
[Link] the first node out of the queue. Find the unmarked nodes adjacent to it in the
graph. Mark them with the label of 2. Put them in the queue.

3 4
3
2
4 3 1 1 3 4
2 0 1

2
3 3
4 1 4

4 3
4 4
2 2

Network Science: Graph Theory

FINDING DISTANCES: BREADTH FIRST SEARCH

Distance between node 0 and node 4:

[Link] until you find node 4 or there are no more nodes in the queue.
[Link] distance between 0 and 4 is the label of 4 or, if 4 does not have a label, infinity.

3 4
3
2
4 3 2 1 0 1 3 4

2
3 3
4 1 4

4 3
4 4
2 2

Network Science: Graph Theory

Connectedness & Components
Connectedness & Components
CONNECTIVITY OF UNDIRECTED GRAPHS

Connected (undirected) graph: any two vertices can be joined by a path.

A disconnected graph is made up by two or more connected components.

B
B
A
A Largest Component:
Giant Component

C
D F C
D F
F
F The rest: Isolates
G
G

Bridge: if we erase it, the graph becomes disconnected.

Network Science: Graph Theory

CONNECTIVITY OF DIRECTED GRAPHS

Strongly connected directed graph: has a path from each node to

every other node and vice versa (e.g. AB path and BA path).
Weakly connected directed graph: it is connected if we disregard the
edge directions.

Strongly connected components can be identified, but not every node is part
of a nontrivial strongly connected component.
B
E
A F
B

D E C
D C G
F
G

In-component: nodes that can reach the scc,

Out-component: nodes that can be reached from the scc.
Network Science: Graph Theory
Graph Theoretical Parameters
COMPUTATION OF NETWORK PARAMETERS: Adjacency Matrix
“Network Biology, Understanding the Cell’s Functional Organization”, Barabasi and Oltvai, Nature Reviews Genetics (2004).
COMPUTATION OF NETWORK PARAMETERS: <k>
“Network Biology, Understanding the Cell’s Functional Organization”, Barabasi and Oltvai, Nature Reviews Genetics (2004).
COMPUTATION OF NETWORK PARAMETERS: Shortest Path Lengths
COMPUTATION OF NETWORK PARAMETERS: Diameter and L
“Network Biology, Understanding the Cell’s Functional Organization”, Barabasi and Oltvai, Nature Reviews Genetics (2004).
Clustering Coefficient

where Li represents the number of links between the

ki neighbors of node i.
CLUSTERING COEFFICIENT

Clustering coefficient:
what fraction of your neighbors are connected?

Node i with degree ki

Ci in [0,1]

Watts & Strogatz, Nature 1998. Network Science: Graph Theory

COMPUTATION OF NETWORK PARAMETERS: Clustering Coefficient

Compute clustering coefficient of each of the node.

 EXERCISE: Study the following network concepts
• Adjacency and incidence (directed and undirected)
• Isomorphism
• Subgraphs
• Cliques
• Walk
• Path
• Cycle
• Connected components
• Connectivity
• Cutsets
• Strongly connected component
• Tree
• Spanning Tree
• Complement of a network
• Regular network
• Empty network
• Cycle networks
• Network coloring
• Bipartite network
• k-partite network
• Planar networks
 EXERCISE
Let 𝐴 be the 𝑁 × 𝑁 adjacency matrix of an undirected unweighted
network, without self-loops. Let 1 be a column vector of 𝑁 elements, all
equal to 1 . In other words 1 = (1, 1, ..., 1)T , where the
superscript T indicates the transpose operation. Use the matrix
formalism (multiplicative constants, multiplication row by column,
matrix operations like transpose and trace, etc., but avoid the sum
symbol Σ) to write expressions for:
a. The vector k whose elements are the degrees ki of all nodes i = 1,
2,..., N.
b. The total number of links, L, in the network.
c. The number of triangles T present in the network, where a triangle
means three nodes, each connected by links to the other two (Hint:
you can use the trace of a matrix).
d. The vector knn whose element i is the sum of the degrees of node i's
neighbors.
e. The vector knnn whose element i is the sum of the degrees of node i's
second neighbors.
 NetworkX Tutorial
• NetworkX Tutorial
[Link]
workx-1.10/tutorial/[Link]