School of Information Sciences

University of Pittsburgh

TELCOM2125: Network Science and

Analysis
Konstantinos Pelechrinis
Spring 2013
Figures are taken from:
M.E.J. Newman, Networks: An Introduction

What is network science ?

It

is the interdisciplinary study of networks

Technological
Biological S
Social

Both

structure and dynamics are studied

Fairly

new field; still evolving

Developed mainly from physicist, mathematicians and computer

scientists
2

Course details
Highly

technical course

Linear algebra knowledge is a minimum requirement

Some

topics will be presented at a higher level

Grade

will be based on:

Homework (15%)
Pop-up quizzes (15%)
One

possibly analytical - question each quiz

Research project (60%)

Participation (10%)
3

http://www.sis.pitt.edu/~kpele/telcom2125.html

Textbook
There

are two main books we will be using

M.J.E. Newman, Networks: An Introduction, Oxford University

Press (2010)
D. Easley and J. Kleinberg, Networks, Crowds and Markets:
Reasoning About a Highly Interconnected World, Cambridge
University Press (2010)
Other

possible references

T.G. Lewis, Network Science: Theory and Applications, Wiley

(2009)
D.J. Watts, Six Degrees: The Science of a Connected Age,
W.W. Norton & Company (2003)
Research papers (pointers will be provided)
4

Part 1: Mathematics of Networks

The representation of networks

The

network consists of entities connected with each other

The

structure of these connections are represented through

graphs

A graph

is represented by two sets

A vertex set V of the entities participating in the network. In the rest of

the slides typically, n will be the number of vertices

Also called node or actor set

An edge set E of the connections between vertices. In the rest of the

slides typically, m will be the number of edges

Also called link or tie set

Graph terminology
A

graph whose vertices are connected by at most one link

is called simple network or simple graph
Most of the graphs we will examine will be simple

When

two nodes connect with more than one edge, we

refer to all those edges collectively as multiedge
The corresponding graph is called multigraph

Depending

on the type of connection a node might be

connected to itself
Self-edges or self-loops

we denote an edge between vertices i and j by (i,j) then the complete network can be spec
ving the value of n and a list of all the edges. For example, the network in Fig. 6.1a has n
Example
es and edges (1,2), (1,5), (2,3), (2,4), (3,4), (3,5), and (3,6). Such a specification is calle
list. Edge lists are sometimes used to store the structure of networks on computers, bu
ematical developments like those in this chapter they are rather cumbersome.

re 6.1: Two small networks. (a) A simple graph, i.e., one having no multiedges or self-ed
8
network
with both multiedges and self-edges.

The adjacency matrix

If

we label the nodes with IDs 1, 2, n we can denote

each edge as a pair (i,j)

This is an edge list specification

Good

for storing and processing networks in computers, but not for

mathematical development

The

adjacency matrix A of a simple graph is a matrix with

elements Aij such that:

Aij

1,
0,

if there is an edge between vertices i and j

otherwise

Example

10

nts to notice about the adjacency matrix are that, first, for a network with no self-e

Observations
For

the (typical) case of no self-loops, the diagonal of the

matrix is all 0

For

undirected networks, since the existence of edge (i,j)

assumes the existence of the edge (j,i), matrix A is
symmetric

If

node i has a self edge then we set Aii=2 (why?)

Multiedges

are represented by setting the corresponding

entry equal to the number of distinct edges

11

Weighted networks
Some
In

relations are not simple on/off (1/0) relations

a weighted network links can have weights

The corresponding adjacency matrix entry is equal to the weight

Weights can represent the frequency of contacts between the
actors, the capacity of a channel connecting two routers etc.
When

weights are integer it might be convenient to think

of the weight as multiedges

12

Directed networks
In

some phenomena the direction of the underlying

relation between two nodes matters relations are not
reciprocal

E.g., twitter connections, world wide web links, paper citations

etc.
These

relations
networks/graphs

The

13

are

captured

through

directed

adjacency matrix of a directed graph (or a digraph) is

A is in general not symmetric
given by:
1,
if there is an edge from j to i
Aij
Self edges are
0,
otherwise

represented by setting Aii=1

Example
ected graph, also called a digraph for short, is a network in which each

nting from one vertex to another. Such edges are themselves called
represented by lines with arrows on themsee Fig. 6.2.

(6.6)
etwork.
A small directed network with arrows indicating the directions
14

Co-citation coupling
The

co-citation of two edges i and j in a directed network

is the number of nodes that have outgoing edges pointing
to both nodes i and j

So in order for node k to contribute to the co-citation of i and j,

the following needs to be true: AikAjk=1

Hence the co-citation of nodes i and j is:

n

k1

k1

Cij Aik Ajk Aik AkjT

The

nxn adjacency matrix of the corresponding co-citation

network is:
T

C AA

15

Co-citation coupling
The

non-diagonal elements can be larger than 1

Either we consider it as a weighted undirected graph or we map

every non-diagonal entry greater than 1 to 1
The

diagonal elements of C can be non zero

Since Aik=0 or Aik=1 (assuming a simple graph no multiedges)

n

Cii A Aik
k1

2
ik

k1

Cii provides the number of nodes that point to node i

In

constructing the co-citation network we set by definition all the

diagonal elements to zero!

16

Bibliographic coupling
The

bibliographic coupling of two edges i and j in a

directed network is the number of nodes that they both
point to

So in order for node k to contribute to the bibliographic coupling

of i and j, the following needs to be true: AkiAkj=1

Hence the bibliographic coupling of nodes i and j is:

n

k1

k1

Bij Aki Akj AikT Akj

The

nxn adjacency matrix of

bibliographic coupling network
T is:

B A A

17

the

corresponding

Bibliographic coupling
The

diagonal elements of B can be non zero

Since Aki=0 or Aki=1 (assuming a simple graph no multiedges)

n

k1

k1

Bii Aki2 Aki

Bii provides the number of nodes that node i points to

Again

when considering the bibliographic coupling network, we set

by definition all the diagonal elements to zero!

The

off diagonal elements of B can again be greater than 0

and hence, we can define a weighted undirected network

We can also map any positive off diagonal element to 1

18

Notes on coupling
While

both coupling methods are similar they can give

completely different structures
Co-citation is heavily based on incoming edges, while bibliographic
coupling on outgoing edges

They

can be used for vertex similarity

E.g., the highest the co-citation of two papers in a paper citation

network, the more possible is that these papers deal with similar topics

While

these coupling methods help us convert an undirected

network to directed, we lose some structural information during
this transformation

19

Acyclic directed
networks
A cycle in a directed network.
A

cycle in a directed network is a closed loop of edges

The classic example of an acyclic directed network is a citation
with the arrows on ineach
of the edges pointing the same
Section 4.2. When writing a paper you can only cite another pap
way around the loopwhich means that all the directed edges in a citation network point

can depict
a network
as in Fig.
6.3,those
with thewith
vertices time Networks without we
cycles
are such
called
acyclic,
while
to top of the picture in this caseso that all the edges representing

cycles are called cyclic

the picture.50 There can be no closed cycles in such a network beca
Self

An

edges also count

down as
the cycles
picture and then come back up again to get back to wh
upward edges with which to achieve this.

acyclic network can be drown with all edges pointing

downward (not necessarily unique drawing)

20

Determining if a network is acyclic

A

simple algorithm for determining whether a network is

acyclic is:

Find a vertex with no outgoing edges (step 1)

If no such vertex exists, the network is cyclic. Otherwise, if such
a vertex does exist, remove it and all its incoming edges from
the network (step 2)
If all vertices have been removed, the network is acyclic.
Otherwise go back to step 1

21

Adjacency matrix of an acyclic network

If

we construct an ordering of the vertices of an acyclic

graph as per the previous algorithm, there can be an edge
from vertex i to vertex j only if j > i

Adjacency matrix is triangular (only the elements above the

diagonal have non zero entries)
More

precisely, since the acyclic graph does not have self loops,
the diagonal elements are zero strictly triangular matrix

All

of the eigenvalues of an adjacency matrix are zero if

and only if the network is acyclic

22

Bipartite networks
In

bipartite networks (aka two-mode networks) there are two

kinds of vertices
One type represents that original vertices (e.g., people) and the
other represents the groups or affiliations or foci that the first
type of vertices belong to (e.g., company)

The

edges of a bipartite network run only between nodes of

different type

bipartite network is defined by the incidence matrix B. If

there are n number of actors and g number of groups:

23

Bij

1,
0,

if vertex j belongs to group i

otherwise

One-mode projections
We

can use the bipartite network to infer connections

between nodes of the same type
Projection on the actors n-vertex network, where nodes are
the actors of the original bipartite graph and an edge between
two actors exists if they participate to at least one common
group
Projection on the groups g-vertex network, where nodes are
the groups of the original bipartite graph and an edge between
two groups exists if they include at least one common actor

One

mode projections discard a lot of the information

present in the structure of the original bipartite graph

24

ach of those four is connected to each of the others in the one-mode projection b
on membership in that group. (Such a clique of four vertices is visible in the ce
projection in Fig. 6.5.) Thus the projection is, generically, the union of a number
r each group in the original bipartite network. The same goes for the other proje
oups.

Projections

25

Mathematics of actors one-mode projection

Two

actors i and j belong to group k iff BkiBkj=1

The total number of groups Pij that i and j belong is given by:
g

k1

k1

Pij Bki Bkj BikTBkj

The

nxn matrix P=BTB is similar to the adjacency matrix

for the weighted one-mode projection onto the n vertices
(actors)

Why only similar and not the same?

26

Trees
Connected,

undirected network with no closed loops

They are usually drawn in a rooted manner

A root

node at the top and a branching structure going down

Vertices at the bottom of the tree, connected only to one other
vertex are called leaves

27

Trees
Since

there are no closed loops there is exactly one path

from every vertex to any other

This property is important because it makes some calculations

particularly simple
A

tree with n vertices has exactly n-1 edges

Reverse is also true!

28

Degree
The

degree ki of a vertex i in a graph is the number of

edges connected to it

For undirected graphs we have:

n

ki Aij
j1

n
n
And the number of 1edges
of1angraph
is given by:

k A

2
2
i

i1

Mean

29

ij

i1 j1

degree c of a vertex
n in an undirected graph is:

1
2m
c ki
n i1
n

Connectance
The

maximum number of possible edges in a simple graph is

Connectance

n 1

n(n1)
2 2

or density of a graph is the fraction of these

edges that are actually present:

2m
c

n(n1) n1

A network for which the density

2 tends to a (positive) constant as n

is called dense
A network for which the density tends to zero as n is called sparse

30

This basically means that in a sparse network c tends to a constant when n

increases arbitrarily

Degrees in directed networks

In

a directed network each vertex is associated with two

degrees

In-degree is the number of incoming edges to a vertex

Out-degree is the number of outgoing edges from a vertex
n

k Aij
in
i

j1

The

j1

total number of edges

inn a directed network is:
n

m kiin kiout Aij

i1

31

k Aji
out
i

i1

ij

Thus, mean in (cin) and out (cout) degrees are equal

1 n in 1 n out
m
cin ki ki cout c
n i1
n i1
n

Paths
A

sequence of vertices such that every consecutive pair of

vertices in the sequence is connected by an edge in the
network
For directed graphs the edges traversed from the path needs to be
traversed in the correct direction
Paths that do not intersect with themselves are called selfavoiding paths

Length

of a path is the number of edges traversed along the

path
When a path traverses the same edge e two times, e is counted
twice
32

Paths in undirected networks

The

product AikAkj is 1 iff there is a path between i and j

through k (a path of length 2)
Hence, if we want to find how many length 2 paths between i and j
exist:
(2)
ij

Aik Akj [A2 ]ij

k1

This can easily be generalized to:

[Ar]ii

Nij(r) [Ar ]ij

gives the number of length r paths that originate and

end at node i (cycles)
Hence if we want to find the number Lr of length r cycles in a graph
n

33

Lr [Ar ]ii TrAr

i1

Paths in undirected networks

A

is symmetric has n real, non-negative eigenvalues

A = UKUT
U

orthogonal matrix of eigenvectors

K diagonal matrix with eigenvalues

Ar (UKU T )r UK rU T
Lr TrAr Tr(UK rU T ) Tr(U TUK r ) TrK r ir
i

i is the i-th eigenvalue of matrix A

34

Paths in directed networks

The

adjacency matrix of a directed network is in general

non symmetric and hence not diagonalizable

We

will use the Schur decomposition

A=QTQT
Q

is orthogonal
T is upper triangular
o Its diagonal elements are its eigenvalues
*They are equal with those of A (why?)

Lr TrAr Tr(QT rQT ) Tr(QT QT r ) TrT r kir

i

35

Geodesic paths
A

geodesic path (shortest path) is a path between two vertices

such that no shorter path exists

By

The length of this path is called geodesic (or shortest) distance

If two nodes are not connected with any path their geodesic distance is
infinite

definition shortest paths are self avoiding (why?)

Diameter

of a network is the length of the longest geodesic path

between any pair of vertices in the network for which a path
actually exists

36

Other definitions are extensively used in the literature as well, such as, the
average value of all geodesic paths in the network etc.

Eulerian and Hamiltonian paths

An

Eulerian path is a path that traverses each edge in a

network exactly once

Hamiltonian path is a path that visits each vertex exactly

once

Self avoiding
Konisberg Bridge Problem

37

Components
A

network
there is no

Note, however, that the vertex labels must be chosen correctly to pro
appearance of blocks in the adjacency matrix depends on the vertice
represented by adjacent rows and columns and choices of labels t
produce non-block-diagonal matrices, even though the choice of la
of the network itself. Thus, depending on the labeling, it may
for which structure
there
pairs
thatcomp
obvious fromexists
the adjacency
matrix of
that avertices
network has separate
exist them
computer is
algorithms,
suchdisconnected
as the breadth-first search algorithm
path between
called
that can take a network with arbitrary vertex labels and quickly determi

If there exists a path between any possible pair of vertices in a

network the latter is called connected

Component

is a maximal subset of vertices of a network

such that there exists at least one path from every vertex
of the subgroup to any other
How can the adjacency matrix of a network
with more than one component be written?

38

Components in directed networks

There

are many different types of connected components that we

can define for a directed network

Assuming

no direction on the edges, we can identify connected

components as in an undirected graph

Weakly connected components

Imposing

a constrained on the direction of the edge we get the

strongly connected components

Maximal subsets of vertices such that there is a directed path in both

directions between every pair in the subset

39

Every vertex belonging to a strongly connected component with more than

one vertex must belong to at least one cycle (why?)

y if there is a directed path between them, i.e., a path in which we follow edges onl
d direction.
It would be useful to define components for directed networks based on s
Visually
ths, but this raises some problems. It is certainly possible for there to be a directed
x A to vertex B but no path back from B to A. Should we then consider A and B t
Are they in the same component or not?

13: Components in a directed network. This network has two weakly conne
s of four vertices each, and five strongly connected components (shaded).
40

Out-components
The

set of vertices that are reachable via directed paths from

node A (including A), form its out-component
Out-component is a property of both the network and the starting vertex

Hence, a vertex can belong to more than one out-components

All

members of the strongly connected component that A

belongs to, are members of its out-component

All

vertices that are reachable from A are also reachable from

any other member of its strongly connected component
Out-components really belong not to individual vertices but to strongly
connected components

41

In-components
The

in-component of a specific vertex A is the set of all

vertices (including A) from which there is a directed path
to A

All

the members of a strongly connected component have

the same in-component

As

strongly connected component is the intersection of

its out- and in-components

42

Independent paths and connectivity

Two

paths connecting a given pair of vertices are edge

(vertex)-independent if they share no edges (vertices other
2 INDEPENDENT
PATHS,
CONNECTIVITY,
than6.1
the
starting and
ending
vertices) AND CUT SETS

Two vertex-independent paths are also edge-independent (the

opposite is not true)
A pair of vertices in a network will typically be connected by many paths of many different
lengths. These paths will usually not be independent however. That is, they will share some

Theor number
of6.10independent
paths
between
pair of
vertices
edges, as in Fig.
for instance (page 140).
If we restrict
ourselves toaindependent
paths, then the number of paths between a given pair of vertices is much smaller. The number of
vertices is called connectivity of the vertices
independent paths between vertices gives a simple measure of how strongly the vertices are
connected
to one another,
and has been the topi c of much study in the graph theory literature.
Edgeand vertex-connectivity

43

Cut set
A

vertex cut set, is a set of vertices whose removal will

disconnect a specified pair of vertices

This set can be thought as the bottleneck for the connectivity of

this specific pair of nodes
An

edge cut set, is a set of edges whose removal will

disconnect a specified pair of vertices

minimum cut set is the smallest cut set that will

disconnect a specified pair of vertices

44

Mengers theorem
The

size of the minimum vertex cut set that disconnects a

given pair of vertices in a network is equal to the vertex
connectivity of the same vertices

The same holds true for edges

The

edge version of the theorem is important for the

maximum flow problem

45

Max-flow/min-cut theorem
In

the general case we have weighted networks

Minimum edge cut set is a cut set such that the sum of the
weights on the edges has the minimum possible value
The

maximum flow between a given pair of vertices in a

network is equal to the sum of the weights on the edges of
the minimum edge cut set that separates the same two
vertices

Intuitively, the low weight edges form bottlenecks that do not

allow the flow between the two vertices to increase.

46

Diffusion
Suppose

we have some commodity on the vertices of a

network (vertex i has amount i)

The

commodity moves along an edges from j to i with a

rate C(j i)

C is a constant (diffusion constant)

Hence, the rate at which i changes is:
di
C Aij ( j i )
dt
j
di
C Aij j Ci Aij C Aij j Ci ki C (Aij ij ki ) j
dt
j
j
j
j
47

Diffusion
Using

define: L = D A and hence:

d
CLequation
0
diffusion
dt

The above is similar to the ordinary

the Laplacian operator has been replaced by matrix L

48

d
C(A D)
dt

is a diagonal matrix with the vertex degrees along the diagonal

We

matrix notation we have

L is called graph Laplacian

Lij ij ki Aij

for gas, where

Solving the diffusion equation

We

write vector as a linear combination of the

eigenvectors vi of the Laplacian (why is this possible?):
n

(t) i (t)vi
i1

We

substitute at the diffusion equation and we get:

d i (t)vi

n
n d (t)v
Lvi ivi n d (t)

i
i
i
i1
CL i (t)vi 0 (
C i (t)Lvi ) 0 (
Ci i (t))vi 0
dt
dt
dt
i1
i1
i1
Since

the Laplacian is symmetric its eigenvectors are

orthogonal multiplying with any eigenvector vj we get:

49

d i (t)
Cii 0, i i (t) i (0)eCit
dt

Eigenvalues of the Laplacian

The

eigenvalues of the Laplacian are real (L is symmetric) and also

non-negative

Let

one end of an edge annotated with 1 and the other with 2. Then
we can define the mxn edge incidence matrix

BkiBkj

is non zero (actually -1) iff vertices i and j are connected

through edge k
Since we consider a simple graph, taking the sum of all the above factors
over k will be either -1 (iff vertices i and j are connected through an edge) or
0 (iff i and j are not neighbors)

50

Eigenvalues of the Laplacian

If

i=j, the previous sum is equal to the degree k i of vertex i (why?)

Hence,

L=BTB

Consider

vi being an eigenvector of L with eigenvalue i

T
T
T T
T
Lvi Hence
i vi
v
L
v

v
B
B
v

v
v

(B
v
)
(B
v
)

i
i
i
i
i
i
i
i
i
i
i
i
i
0
i

It

is easy to see that (1,1,,1) is an eigenvector of the L with

eigenvalue 0

51

Components and algebraic connectivity

Suppose

a network with c components

First component has n1 vertices, second has n2 and the c-th has nc
The Laplacian (just as the adjacent matrix) can be written in a block
diagonal form
There are c eigenvectors of L with eigenvalue
zero vectors that have ones in all positions
corresponding to vertices in single components
and zero elsewhere. E.g.,
The

number of zero eigenvalues is exactly equal to the number of

connected components

52

The second eigenvalue 2 (algebraic connectivity or spectral gap) of the

Laplacian is non-zero iff the network is connected

Random walks
A

random walk is a path across a network created by taking

repeated random steps
Start at a specific vertex
Choose uniformly at random one of the edges of this vertex and
move along the edge
Arrive at the vertex at the other end of the edge and repeat the
above steps

Let

pi(t) be the probability that after t random steps the walk

is at vertex i
If the walk is at vertex j at time t-1, the probability of taking a step
along any particular one of the kj edges of j is 1/kj

53

pi (t)
j

Aij
kj

1
pj (t1) p(t) AD p(t1)

Random walks
Since

we are interested for the steady state distribution

(i.e., t), we have:
Aij

1
pi () pj () p AD p
j kj

The

above equation can be written as:

(I AD1 ) p (D A)D1 p LD1 p 0

Hence, D-1p is an eigenvector of L with zero eigenvalue

54

Random walk on a connected graph

In

this case we know that there is only one null eigenvalue, which
corresponds to an eigenvector with all components equal:

If

D p 1 p D1 pi ki

In a connected
network the probability that a random walk will be found in a
1
vertex is proportional to its degree

we pick constant to normalize p i properly we have:

ki
ki
pi

kj 2m
55

Random walk and first passage time

The

first passage time for a random walk from a vertex u to

another vertex v is the number of steps before a walk
starting at u first reaches v
Absorbing random walk: there is one or more absorbing
states, that is, vertices that the walk can arrive but not leave
We can answer questions about the first passage time by
considering the probability pv(t) that a walk is at vertex v
(absorbing) after time t
The probability that a walk has first passage time exactly t is then
pv(t)-pv(t-1)

Then the mean first passage time is:

56

t[ pv(t) pv(t1)]
t0

Random walk and first passage time

Here

we have a semi-directed graph; the walk can get in

v (Avi is not necessarily 0) but cannot move out of it (A iv = 0
for all i)

For
In

any iv

pi (t)
j

Aij
kj

pj (t1)

Aij

j (v)

pj (t1)

the sum there are no terms Avj and hence we can write:

AD1 p(t1)

[ AD1 ]t p(0)

p(t)
p(t)

Where vector p does not include the entry for v and matrices A
and D do not include the v-th row and column

57

Random walk and first passage time

Since

p does not include the entry of pv we have:

pv(t) 1 pi (t) 1 1T p(t)

i(v)

Substituting

we get the mean passage time:

T
T

T
1 1 p(t1)]

t[ pu(t) pu(t1)] t[1 1 p(t)
t1 [ p(t1)
p(t)]

t0

t0

t0

t(M t1M t )[I M ]1

t0
T
1 t1
1 t
T
1 t1
1 t
(AD ) p(0)]
t1 p(0)[(

t1 [( AD ) p(0)
AD ) ( A D ) ]

t0

1 [I AD1 ]1 p(0)

58

t0

Random walk and first passage time

If

we further simplify:

[I AD1 ]1 I ( AD1 )1 I DA1 D( D1 A1 ) D( D A)1 DL1

We

get:

T
1

1 DL p(0)

Where L is the v-th reduced Laplacian

59