This is a summary of the course Massive Graph Management and Analytics taught at the Université Paris Saclay - CentraleSupélec by Professor Nacéra Seghouani in the academic year 23/24. Most of the content of this document is adapted from the course notes by Seghouani, [4], so I won’t be citing it all the time. Other references will be provided when used.

Contents

1 Introduction

Graph-structured data is at the heart of complex systems and plays a major role in our daily life, science and economy. Examples of this data are the cooperation between billions of individuals, or communication infraestructures with billions of cell phones, computers and satellites, the interactions between thousands of genes and metabolites within our cells, and so on.

Therefore, understanding its mathematical foundations, description, prediction, and eventually being able to control them is one of the major scientific challenges of the 21st century.

2 Preliminaries

2.1 Graph Theory Preliminaries

A graph is a pair G = , where V is the set of vertices and E ⊂ V × V is the set of edges. Usually, we denote = n and = m.

There are different types of graphs:

• Undirected: ∈ E ∈ E. That is, the edges goes in both directions.

• Directed: ∈ E ⁄ ∈ E. That is, the edges have direction, and it is possible that an edge goes from u to v, but not the other way.

• Weigthed vertices: the vertices have a weight. That is, there is a function w_v : V → ℝ.

• Weigthed edges: the edges have a weight. That is, there is a function w_e : E → ℝ.

• Labeled vertices: the vertices have a label, L_v : V →, where is the set of labels.

• Labeled edges: the edges have a label, L_e : E →.

• Bipartite: a graph G = is bipartite if there is a partition of the vertices, V = V ₁ ∪ V ₂, such that V ₁ ∩ V ₂ = ∅ and E = . That is, the vertices in V ₁ only connect to vertices in V ₂, and viceversa.

• k-Partite: a graph G = is k-partite if there is a k-partition of the vertices, V = V ₁ ∪V ₂ ∪...∪V _k, such that V _i ∩ V _j = ∅,∀i≠j and the is no edge e = such that u,v ∈ V _i, for the same i.

• Multigraph or multidigraph: in this case, there can be several edges between two vertices. For this, we define the edges as a separate set E, and a function r : E → V × V , that assigns the vertices related by that edge.

• Hypergraph: in this case, E ⊂ 2^V . That it, the edges can relate 0 or more vertices. In this case, it is more appropriate to interpret E as a set of classes or hierarchies, rather than edges.

• Complete: a graph is complete if E = V × V .

Some examples are:

Continuing with definitions, let G = be a graph (directed or undirected). Let d_i⁺ and d_i^- denote the number of edges coming out and coming to v_i, respectively. The degree of v_i is

Note that it counts double for undirected graphs.

Now, let N_i⁺ and N_i^- the set of successors and predecessors of v_i, respectively. Then, the set of neighbors of v_i is

A path between two vertices, u,v ∈ V , denoted u ⇝ v, is a sequence of vertices , where ∈ E,∀i = 1,...,k. The length of a path, L, is the number of edges in the cycle, that is, k.

A cycle is a path from a vertex to itself, u ⇝ u.

The distance between two nodes, d, is the shortest path length between them:

The eccentricity of a node, ecc, is the greatest distance between u and any other vertex in the graph:

Note that this could be infinity if we cannot reach some node from u. Usually, we consider only reachable nodes, because this can give us information about the graph, but a value of infinity is not very informative.

The diameter of a graph, diam, is the greatest distance between two nodes in the graph:

The radius of a graph, rad, is the minimum eccentricity of any vertex in the graph:

The center of a graph, C, is the set of all vertices of minimum eccentricity, i.e., the graph radius:

A partial graph of G = is a graph G′ = , where E′⊂ E.

A subgraph of G = is a graph G′ = where V ′⊂ V and E′⊂ E. Note that partial graphs are also subgraphs.

A graph G = is said to be connected if, and only if, ∀u,v ∈ V,∃u ⇝ v.

A (strongly) connected component of G = is a subgraph G_cc = , where ∀u,v ∈ V _cc,∃u ⇝ v ∈ V _cc. That it, a connected subgraph. It is called strongly when the paths are directed.

A graph G = is a tree if, and only if, G is a connected graph without cycles. In this case, the graph has m = n - 1 edges.

A graph G = is a forest if, and only if, all connected components of G are trees.

2.1.1 Breadth First Search (BFS)

BFS is a method to traverse the nodes of a graph, by starting at one node and traversing all its neighbours. Then, all neighbours of its neighbours, and so on.

For this, we use a FIFO queue. The algorithm is:

2.1.2 Depth First Search (DFS)

In the case of DFS, the objective is also to traverse the whole graph. The difference is that in this case we try to go as deep as we can in the graph before visiting more neighbours.

It can be implemented with a stack, let it be a explicit stack, or an implicit one.

The implementation with an explicit stack is the following:

The implementation with an implicit stack is recursive, and is as follows:

2.1.3 Greaph Representations

A graph, G = , with n vertices and m edges can be encoded using different structures:

• Adjacency matrix: a matrix A ∈_n×n, defined by

  

  The adjacency matrix is symmetric for undirected graphs.

• Adjacency list: a list L of length n in which each vertex holds a list of its neighbours:

  

  If G is directed, the choice of the direction depends on the analytic needs.

• Incidence matrix: a matrix B ∈_n×m, defined by

  

2.1.4 Exercises

1. Using graph traversal algorithms, propose an algorithm that computes the number of edges between a given vertex and all other vertices.

   1procedure n_edges(G=(V,E), r) 
   2  Q <- emptyset 
   3  enqueue(Q,r) 
   4  r.n_edges = 0 
   5 
   6  while Q is not empty do 
   7    v <- dequeue(Q) 
   8    for neig in neighbours(v) do 
   9      if not neig.n_edges then 
   10        enqueue(Q,neig) 
   11        neig.n_edges = v.n_edges + 1 
   12      end if 
   13    end for 
   14  end while  
   15end procedure

2. Given the following cycles with even and odd lengths (with the distances or depths from the grey vertex), what do you think about the case of graphs with an odd cycle (in number of edges)? Is this a characteristic property? State the general case.

   

   Proposition: a graph contains a cycle C with an odd number of edges if, and only if, ∃ ∈ E|depth = depth.

   Proof : first, we know that all edges connect vertices of ’neighbouring’ depths. That it, ∀ ∈ E, it holds ≤ 1.

   By reduction ad absurdum, seeking a contradiction, suppose that ∀ ∈ C, with depth≠depth. This means that depth = depth ± 1. Therefore, there is, along the cycle, a node of even depth, followed by a node of odd lenght, and so on. When we close the cycle, the final node is the inicial one, so its depth is 0 (even). Therefore, we need an even number of edges, to conserve the parity.

   If there is an edge ∈ E with depth = depth, then we can consider the path tree that was used to annotate the depths. In this tree, x and y have a first ancestor z in common, from which we can form an odd cycle of size 2 ⋅ + 1 by adding the edge to this subtree starting at z.

3. Propose an algorithm that determines if a graph contains an odd cycle.

   1procedure hasOddCycle(G=(V,E)) 
   2  v <- a vertex from V 
   3  depths <- n_edges(G,v) #from the first exercise 
   4   
   5  for (u,v) in E do 
   6    if depth[u] == depth[v] then 
   7      return True 
   8    end if 
   9  end for  
   10end procedure

4. In a bipartite graph, can there be a cycle with an odd number of edges? Is this a characteristic property?

   No, it is not possible!

   Proposition: A graph is bipartite if, and only if, all cycles are of even size.

   If the graph is bipartite, any path alternates between each vertex of each partition to create a cycle ending by the initial vertex. Therefore, all cycles must be of even size.

   Consider the partition of vertices with even depth V ₁, and the partition of vertices with odd depth V ₂.

   Since there is no odd cycle, then, from question 2, we know that ∀ ∈ E it is depth = depth ± 1. Therefore, the graph is bipartite.

5. Propose an algorithm that allows to determine if a graph is bipartite. Test your algorithm in the following graph. Is it bipartite? Justify your answer.

   

   The algorithm is the same as in exercise 3, because of exercise 4.

   The proposed graph is clearly not bipartite, because there are several odd cycles.

6. Graph coloring is a way of coloring the vertices of a graph in such a way that no two adjacent vertices share the same color. A 2-colorable graph is a graph that can be colored with only 2 colors.

   1. What is the link with the previous exercise? Justify your answer.

      Proposition: a graph is 2-colorable if, and only if, it is bipartite.

      Proof : If it is 2-colorable, with colors red and blue. Then we take V ₁ = and V ₂ = . G is clearly bipartite with this partition.

      If it is bipartite, with partition V ₁ and V ₂, then we can color all nodes in V ₁ in blue, and all nodes in V ₂ in red. The graph is 2-colorable.

   2. We want to write an algorithm, inspired by DFS search, which takes as input a graph, G = , and which returns a pair where result is True if the graph is colorable, False otherwise, and color is a dictionary associating a color 0 or 1 to each vertex. This algorithm should stop as soon as possible when the graph is not 2-colorable.

      1procedure coloring(G=(V,E), r) 
      2  color <- {r: 0} 
      3  stack <- emptyset 
      4  push(stack, r) 
      5   
      6  while stack is not empty do 
      7    v <- pop(stack) 
      8    for neig in neighbours(v) do 
      9      if neigh is not in color.keys then 
      10        push(stack, neigh) 
      11        color[neig] = 1 - color[v] 
      12      elif color[neig] = color[v] then 
      13        return False, color 
      14      end if 
      15    end for 
      16  end while 
      17  return True, color 
      18end procedure

7. Compute the shortest path in the following graph using Dijkstra’s algorithm, starting at A:

   1procedure dijkstra(G=(V,E), r) 
   2  dist <- {r:0} 
   3  P <- emptyset 
   4   
   5  for v in V-{r} do 
   6    dist[v] = infinity 
   7  end for 
   8 
   9  while V-P is not empty do 
   10    w <- select(v in V-P and dist[v]=min_u dist[u]) 
   11    P <- P union {w} 
   12    for neig in neighbours(w)-P do 
   13      if dist[w]+weight(neig,w) < dist[neig] then 
   14        dist[neig] <- dist[w]+wight(neig,w) 
   15      end if 
   16    end for 
   17  end while  
   18end procedure

   

   We start with: dist =

   A	B	C	D	E	F	G
   0	∞	∞	∞	∞	∞	∞

   , and P = ∅.

   Now, w = A and P = . We update dist =

   A	B	C	D	E	F	G
   0	∞	∞	∞	∞	3	1

   .

   Now, w = G and P = . We update dist =

   A	B	C	D	E	F	G
   0	∞	∞	∞	3	2	1

   .

   Now, w = F and P = . We update dist =

   A	B	C	D	E	F	G
   0	6	∞	∞	3	2	1

   .

   Now, w = E and P = . We update dist =

   A	B	C	D	E	F	G
   0	6	4	8	3	2	1

   .

   Now, w = C and P = . We update dist =

   A	B	C	D	E	F	G
   0	6	4	6	3	2	1

   .

   Now, w = B and P = . dist does not change.

   Finally, w = D and P = . dist does not change.

8. Given the following graphs:

   

   1. Give the different representations of these graphs.

      A₁ =

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

      ,L₁ =

      0 :

      1 :

      2 :

      3 :

      4 :

      5 :

      B₁ =

      	01 04 05 12 13 15 23 25 35 45
      0 1 2 3 4 5

      A₂ =

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

      , L₂ =

      0 :

      1 :

      2 :

      3 :

      4 :

      5 :

      ,

      B₁ =

      	01 04 15 23 25 33 40 41 54
      0 1 2 3 4 5

   2. Compute A²,A³. What does A_ij^r represents?

      A_ij^r represents the number of paths of length r from node i to node j.

   3. What is the complexity of A^r? Is it possible to reduce it?

      Computing A^r is O, since it requires r products of complexity O.

      However, we can reuse some results to reduce the complexity:

      • If r is even, we can do A^r = ².

      • If r is odd, we can do A^r = A².

      Therefore, we can obtain A^r in O.

2.2 Linear Algebra Preliminaries

A norm is a function f that measures the size of a vector. It must satisfy the following properties:

• f = 0 ⇐⇒ x = 0.

• Linear on scale factors:

  

• Triangle inequality:

  

A widely use family of norms are the p-norms:

with the most common one being the Euclidean norm, for p = 2:

The determinant of a square matrix is equal to the hypervolume of the parallelotope defined by the vectors of the matrix. It is 0 if, and only if, the set of vectors is colinear.

The determinant can be used for many things:

• We can represents linear systems with matrices as Y = AX, and there are many methods to solve this efficiently.

• With the determinant we can compute the characteristic polynomial of A, whose roots are the eigenvalues of A.

Some properties of the determinant are:

• = 1, where I is the identity matrix.

• = 0 if A is singular (not invertible).

• = .

• = .

• = cⁿ, where n is the dimension of A.

A square matrix, A, is invertible (non-singular, non-degenerate), with inverse denoetd A^-1, if ∃B such that

in this case, A^-1 = B.

Properties of the inverse:

• ^-1 = A.

• ^-1 = ^T.

• ^-1 = B^-1A^-1.

• ^-1 = A^-1 for c≠0.

• = .

An eigenvector or characteristic vector of a linear transformation, T, is a non-zero vector that changes by a escalar factor, λ, when transformed by T. That is, v is an eigenvector of the linear transformation T if

There is a direct correspondence between n×n matrices and linear transformation in the n-dimenstional vector space into itself. That is, every linear transformation T can be represented as a matrix A_T (the matrix depends on the chosen base). Therefore, we can say that A_T has an eigenvector v if

The scale factors of the eigenvectors are called eigenvalues.

We can find the eigenvalues by solving a polynomial function on λ called the characteristic polynomial of A_T:

Now, this equation has non-zero solution if, and only if,

Therefore, we can compute and find all values of λ that makes it equal to 0.

Once we have the eigenvalues, we can use them to find the corresponding eigenvectors.

Example 2.4. Compute the eigenvalues and eigenvectors of A = .

This has as solutions

Therefore, we have λ₁ = 1,λ₂ = 3.

To find the eigenvectors, we solve

For λ₁ = 1, it is

so the eigenvector associated to λ₁ = 1 is

For λ₂ = 3, it is

so the eigenvector associated to λ₂ = 3 is

We call the algebraic multiplicity, t_i, of the eigenvalue λ_i to its multiplicity as root of the characteristic polynomial:

Note that A can have at most n distinct eigenvalues, although some of them may be complex.

The eigenspace of an eigenvalue, λ, is the spave generated by the eigenvectors associated to λ.

The dimension of the eigenspace of λ is the geometric multiplicity of λ. The geometric multiplicity of an eigenvalue is, at most, its algebraic multiplicity.

Example 2.5. Let’s get some eigenspaces:

A = , so

=	= + 4
=	=
=
=	2.

This has roots λ₁ = 1, with algebraic multiplicity 2, and λ₂ = 2, with algebraic multiplicity 1.

Now, we get the eigenvectors associated to them:

For λ₁ this is

so v_λ1 = , with dimension 1 (it could be 2).

For λ₂ this is

so v_λ2 = , with dimension 1 (it could not be differently).

B = , so

=	= + 18
=	=
=	= 2.

This has roots λ₁ = 1, with algebraic multiplicity 2, and λ₂ = -2, with algebraic multiplicity 1.

Now, we get the eigenvectors associated to them:

For λ₁ = 1, we have

Therefore, the eigenspace associated to λ₁ is

For λ₂ = 2, we have

Thus, the eigenspace associated to λ₂is

C = ,

=	= 2 - 2
=
=
=
=	λ.

λ₁ = 0:

so

λ₂ = 1:

so

λ₃ = 3:

so

D = ,

=
=	+ 12 + 2 - 8 + 1 - λ + 3
=	- 4 + 4λ
=	- 2 - 2λ + 3λ + 3λ2 - λ2 - λ3 - 4 + 4λ
=	- λ3 + 2λ2 + 5λ - 6

To obtain the roots, we can use Ruffini:

	-1	2	5	-6
1		-1	1	6
	-1	1	6	0

So λ₁ = 1 is a root and we have now -λ² + λ + 6 = 0, obtaining

and we get λ₂ = -2 and λ₃ = 3.

λ₁ = 1:

Then, E = .

λ₂ = -2:

Then, E = .

λ₃ = 3:

Then, E = .

E = ,

=
=	2 + 4 + 4 - 4 - - 4
=	+ 2 - 8 + λ
=	54 - 36λ + 6λ2 - 9λ + 6λ2 - λ3 - 22 + 8λ + λ
=	- λ3 + 12λ2 - 36λ + 32.

Again, we can use the Ruffini rule:

	-1	12	-36	32
2		-2	20	-32
	-1	10	-16	0

So λ₁ = 2 is a root, and we now have -λ² + 10λ - 16 = 0, which gives us

Therefore, λ₁ is a double root and the other root is λ₂ = 8.

λ₁ = 2:

If x = 0: y = z.

If x = t≠0: -y + z = -2t, working for y = t and z = -t.

So

λ₂ = 8:

Therefore,

F = ,

=
=	- λ2+ 2 - λ
=
=
=	2.

One root is λ₁ = 1 with algebraic dimension 2, and λ₂ = 2 with algebraic dimension 1.

λ₁ = 1:

If x = 0: y = -z.

If x = t≠0: y + z = -t. This works for y = t,z = -2t.

Therefore,

λ₂ = 2:

So

Another way to represent eigenvalues and eigenvectors is

where V = is the matrix formed by putting each eigenvector as a column, and

is the diagonal matrix formed by all eigenvalues.

A matrix A is diagonalizable if there exist n linearly independent eigenvectors. That is, if the matrix V is invertible:

This leads naturally to the eigen-decomposition of the matrix,

A real matrix, U, is orthogonal if U^TU = UU^T = I.

A matrix A is said to be positive semi-definite when it can be obtained as the product of a matrix by its transpose:

Positive semi-definite matrices are always symmetric, because

A symmetric matrix A is positive semi-definite if all its eigenvalues are non-negative.

In this case, since eigenvectors are orthogonal, it is possible to store all the eigenvectors in an orthogonal matrix.

Therefore, the eigen-decomposition of a positive semi-definite matrix, A, could be

with U an orthogonal matrix.

As a consequence, the eigen-decomposition of a positive semi-definite matrix is often referred to as its diagonalization.

An alternative definition for positive semi-definite matrix is:

A is positive semi-definite if x^TAx ≥ 0,∀x.

If it is x^TAx > 0,∀x, then it is positive definite.

If it is x^TAx ≤ 0,∀x, then it is negative semi-definite.

If it is x^TAx < 0,∀x, then it is negative definite.

The rank of a matrix is the dimension of the vector space generated by its columns (or rows). This corresponds to the maximum number of linearly independent columns of A. A matrix whose rank is equal to its size is called a full rank matrix. Only full rank matrices have an inverse.

We can now define the Laplacian matrix for undirected graphs, as

or, equivalently,

where A is the degree is the matrix of G, and A its adjacency matrix.

2.2.1 Exercises

1. What could you say about these matrices?

   1. A = , det = -, A is invertible. Its eigenvalues are λ₁ = -1+ and λ₂ = -1-, with v_λ1 = and v_λ2 = .

   2. B = . The second row is equal to the first row multiplied by -. Therefore, it is not invertible.

   3. I: its determinant is 1. It is symmetric, orthogonal, its own inverse. Triple eigenvalue 1, with eigenspace the whole space.

2. Show that Aⁿ = XΛX^-1.

   First, this is only true if A is diagonalizable. If that is the case, then we can proceed by induction on n:

   n = 1: Obvious.

   n = 2:

   

   Suppose it is true for n - 1:

   

   Then, for n, we have:

   

3. Find the eigenvalues and unit eigenvectors of A^TA and AA^T with A = the Fibonnaci matrix.

   First of all, notice that A is symmetric, so A^TA = AA^T = A² = .

   = - 1 = 2 - 3λ + λ² - 1 = λ² - 3λ + 1. The roots of this polynomial are

   

   Now,

   

   Therefore

   

   with unit eigenvector v₁ = .

   And

   

   with unit eigenvector v₂ = .

4. Without multiplying

   

   find the determinant, the eigenvalues and eigenvectors. Why S is positive definite?

   We have S = UΛU^T with U orthogonal. Therefore, the eigenvalues of S are 2 and 5. Its determinant is 10. The eigenvectors are the eigenvectors of Λ rotated as well, that is:

   

   S is positive definite because

   

   now note that

   

   so

   

   because is positive semi-definite (symmetric with positive eigenvalues).

5. For what numbers c and d are the following matrices positive definite?

   1. A = : all principal minors must be positive. That is:

      • c > 0.

      • = c² - 1 > 0. Combined with the previous one, this is c > 1.

      • = c³+2-3c. Roots: 1,

        	1	0	-3	2
        1		1	1	-2
        	1	1	-2	0

        , and we have c² + c- 2, with roots c = . We are only interested in the interval , in which c³ - 3c + 2 > 0.

      Therefore, it is c > 1.

   2. B = :

      • 1 > 0.

      • = d - 4 > 0 ⇐⇒ d > 4.

      • = 5d + 24 + 24 - 9d - 16 - 20 = -4d + 12 > 0 ⇐⇒ - 4d > -12 ⇐⇒ d < 3.

      Therefore, there is no value for d for which B is positive.

6. Show that if λ₁,λ₂,...,λ_n are the eigenvalues of a matrix A, then A^m has as eigenvalues λ₁^m,λ₂^m,...,λ_n^m.

   Induction on m.

   m = 1: Obvious.

   m = 2: Let v_i be the eigenvector associated to λ_i, then

   

   so λ_i² is an eigenvalue of A², with associated eigenvector v_i.

   Suppose it is true for m - 1, then, for m:

   

   and we have the result.

7. What is the determinant of any orthogonal matrix?

   If U is orthogonal, then UU^T = I. Then,

   

   Therefore, = ±1.

8. For an undirected graph, both the adjacency matrix and the Laplacian matrix are symmetric. Show that the Laplacian matrix is positive semi-definite.

3 Random Walks on Graphs

3.1 First Perron-Frobenius Theorem

The Perron-Frobenius theorem for non-negative matrices leads to the characterization of non-negative primary eigenvectors. This is useful in stationary distributions, such as those of Markov chains and the famous Google’s page rank algorithm.

Note now that a graph, G = , with adjacency matrix A, then: G is connected ⇐⇒∀1 ≤ i,j ≤,∃k ∈ ℕ^* such that A_i,j^k > 0. This means that the adjacency matrix of connected graphs is irreducible.

Now, if a graph is k-connected, i.e., there is a k-path between all nodes, then its adjacency matrix is primitive. One sufficient condition for a graph to be k-connected is being connected and having A_ii > 0 for some i.

3.2 Random Walks on Graphs

A random walk on a graph, G = , is a random process that starts from some vertex v_i, and repeatedly moves to a neighbour v_j chosen at random (for example with uniform distribution). The random walk, ξ_t, is therefore a random variable describing the position of a random walk after t steps. The probability of going from node i to node j is the transition probability,

The sequence of nodes can be regarded as a Markov chain, i.e. a discrete time stochastic process, where the position ξ₀ is the initial state, according to the init distribution, P⁰, and from this point the next state only depends on the current state. The t-step transition probability is

Some examples are the path traced by a molecule in a liquid or a gas (Brownian motion), the price of a fluctuating stock, the financial status of a gambler, etc. The term random walk was first introduced by Karl Pearson in 1905.

The following is a basic visual example of a random walk on a graph:

Note that we can express the transition probability P_ij in a matrix P. This matrix is the transition probabilities matrix, and it is row-stochastic or row-Markov, meaning,

This implies that

This means that is an eigenvector and 1 is an eigenvalue. 1 is the largest eigenvalue because

so, for an eigenvalue λ,

so ≤ 1.

From the Perron-Frobenius theorem for non-negative matrices, we know that:

• v^* = is a right Perron eigenvector for P.

• ≤ λ^* = 1 is a Perron eigenvalue.

• There exists a left Perron eigenvector πP = π.

• If P is irreducible, the vector π is unique.

• If P is primitive, the eigenvalue 1 is unique (there are no complex eigenvalues with norm 1).

3.2.1 The Stationary Distribution

Let π^t be the row vector giving the probability distribution of ξ_t, that is, π_i^t is the probability that the random walk is at node i at time t. Therefore, we can write

which, applied recursively, leads to

Or, we can take limits

If this limit exists, lim_tπ^t = π, then

Convergence is ensured if P is irreducible.

Example 3.1. The following example does not converge:

A common way to perform random walks on graphs is with the uniform probability. That is,

where d_i is the degree of node i. Equivalently,

The random sequence of vertices ξ₀,ξ₁,...,ξ_t,ξ_t+1,... visited on G is a Markov Chain with state space V and matrix transition probabilite P = D^-1A.

Example 3.2. Given the graph:

The transition matrix for the uniform distribution is:

3.2.2 Balance Condition

A probability distribution π satisfies the balance condition if

If π satisfies the balance condition, then it is the stationary distribution for the undirected graph. To see this, notice that the balance condition can be rewritten as

Since the graph is considered without direction, A_ij = A_ji, and then

where c is a constant, for all i,j. Now, we know that ∑ _iπ_i = 1, so

Therefore

Finally, it must be

In this case:

Therefore, we have seen that the stationary probabilities are proportional to the degrees of the vertices.

In particular, if G is d-regular, i.e., all nodes have degree d, then

is the uniform distribution. With this setup, a random walk moves along every edge with the same frequence.

The balance condition implies time-reversibility: the reversed walk is also a Markov chain.

3.2.3 Hitting Time

Definition 3.3. The expected hitting time, H_ij, is the expected number of steps before node j is reached in a random walk starting at node i:

Remark 3.2. H follows the triangle inequality

Definition 3.4. The commute time, C_ij, is the expected number of steps in a random walk starting at node i, reaching node j and coming back to i again:

3.2.4 Lazy Random Walk

The lazy random walk is a variation of the random walk, in which the walk stays at the current node with probability , and continue with the walk with the rest of the probability.

In this case, the transition matrix is

If Q is the transition matrix for the uniform random walk, then

Proof. Let Q be the transition matrix for the uniform random walk, then, the stationary distribution is

For lazy random walk, say the stationary distribution is π′. Then:

Therefore, since Q is irreducible, the uniqueness of π implies π′ = π. __

3.3 PageRank

The web is very heterogeneous bu nature, and certainly huge. We cannot expect the web graph to be connected. Page and Brin proposed a way to overcome this problem, by ensuring the convergence of random walks on the web graph.

The idea is to fix a positive constant, p, between 0 and 1, called the damping factor, and which represents the probability that a user leaves the current page and goes to a random web.

Therefore, the page rank transition matrix is

where B = .

p is usually chosen small, like 0.15, modelling a situation in which a surfer will, most of the time, follow the outgoing links and move on to one of the neighbours. A smaller percentage of time, the surfer will dump the current page and choose arbritrarily a different page from the web.

Proof. We need to proof that, for all i, it holds ∑ _jP_gi,j = 1.

∑ jPgi,j =	∑ jPij + pBij
=	∑ jPij + p∑ jBij
=	⋅ 1 + p∑ j
=	1 - p + p ⋅ n
=	1 - p + p
=	1.

__

4 Centrality Measures

Centrality Measures try to answer the question ’What characterizes an important vertex?’. They define a real-valued function on the vertices of the graph, m : V → ℝ, that serves to rank the vertices. However, there are many different ways to define such function, leading to different definitions of centrality, such as cohesiveness, ability to transfer information across the network, to influence other nodes, to control information flow, etc.

There are many centrality measures that count the number of paths through a given vertex. These differ in how relevant walks are defined and counted. For example, if we only consider paths of length one, we would be computing degree centrality, while if we allow paths of arbitrary length, we would be computing eigenvalue centrality.

4.1 Degree Centrality

The more neighbours a vertex has, the higher its communication ability is, increasing its importance.

Definition 4.1. Given the graph G = , with adjacency matrix A, the degree centrality is computed as

where u = 1 ∈ ℝⁿ.

Example 4.1. Consider the following graph:

The degree centrality is

so the nodes with highest value are nodes .

One drawback of this measure, is that it is very likely that several nodes present the same exact value, difficulting an unique ranking of vertices.

4.2 Neighbourhood centrality

This measure correspond to the average degree of each vertex neighbours. We could understand this measure as measuring how much a vertex is related to influencial vertices.

Definition 4.2. Given the graph G = , with adjacency matrix A, the neighbourhood centrality is computed as

where is the diagonal matrix where _ii = d_i is the degree of vertex i and D is the degree centrality. Each vertex’ measure is

Example 4.2. The neighbourhood centrality of the previous example graph is

so the nodes with highest value are nodes .

4.3 Eigenvector Centrality

A natural extension of degree centrality is to consider all reachable nodes, not just neighbours. Eigenvector centrality measures a node’s importance while considering the importance of its neighbours. A high eigenvector centrality means that a node is connected to many nodes that have high scores themselves.

Definition 4.3. Given the graph G = , with adjacency matrix A, the eigenvector centrality of node v is

where λ is a parameter. Note that this can be written as

or

This means that E is an eigenvector of A, for the eigenvalue λ.

Bonacich suggested that the eigenvector of the largest eigenvalue of A could make a good network centrality measure.

The eigenvector E must be non-negative and according to the Perron-Frobenius theorem, the largest λ enforces this property, making it a suitable value.

Example 4.3. Let’s compute E for the previous example graph. The matrix A has as largest eigenvalue λ = 2.54, and the corresponding eigenvector is

Note that it is usually unfeasible to compute the eigenvalues and eigenvectors. It is more usual to get the vector iteratively as

4.4 PageRank Centrality

Google’s PageRank is a variant of the eigenvector centrality, which uses in-degree to award one centrality point for every link a node receives. As we saw, the algorithm is based on a web surfer who is randomly clicking on links, with a certain probability to go to a different place of the web (the damping factor).

Therefore, we define the matrix

where P_ij = , and B_ij = .

Now, we apply the eigenvector centrality to this modified matrix, as

with λ = 1 because P_g is stochastic.

Or, iteratively as

Note that in this case it is not necessary to normalize the vector at each step, because P_g is stochastic. A good E_g0 is E_g0 = .

4.5 Katz (or alpha) centrality

The main problem with eigenvector centrality is that it only works well when the graph is strongly connected (so Perron-Frobenius is applicable in its stronger form). Real networks do not usually have this property, specially if they are directed. The vertices that are not in strongly connected components will have value 0.

A way to work around this problem was proposed by Leo Katz. The idea is to give each node a minimum, positive amount of centrality, that it can transfer to other nodes, so:

where K_v is the Katz centrality of node v, β is a vector whose elements are all equal to a given positive constant and α ∈ is a parameter. Equivalently, this is

so

and

For this to work, I -αA must be invertible, which happens if and only if ≠0 ⇐⇒≠0, so must not be an eigenvalue of A. This is ensured if we take > λ_max, or 0 < α < .

An iterative way to compute K is

The strength of α decreases at each iteration, acting as attenuation factor.

4.6 Clustering Coefficient Centrality

The clustering coefficient measures the proportion of neighbours of each node, that connected to each other.

Definition 4.4. Given a graph G = , with adjacency matrix A, the clustering coefficient of node v is

where the numerator is the number of triangles involving v and its neighbours, and the denominator is the total number of possible links between v’s neighbours.

The more densely connected the neighbourhood of v is, the higher is its clustering coefficient.

Example 4.4. The clustering coefficient of the graph example that we’ve been working with is

4.7 Closeness Centrality

Closeness centrality is a measure of how close a node is, on average, to the rest of the nodes, in terms of shortest paths. It measures the average distance between a node v and all other nodes in the network. Thus, the more central a node is, the closer it is to all other nodes.

Definition 4.5. Given a graph G = , the closeness centrality of node v is

It can be normalized by the factor

An alternative is the harmonic centrality, obtained as

with dist = 0 if there is no path from v to r.

4.8 Betweenness Centrality

A family of betweenness measures are defined to capture a node’s importance as a conduct of information flow in the network. This has wide applications in network theory, because in a telecommunications network, a node with higher betweenness centrality would have more control over the network, since more information will pass through that node.

The most well-known betweenness metric measures the number of times a node is on a shortest path between two nodes.

Definition 4.6. Given a graph G = , the betweenness centrality of node v is

where σ_s,t is the number of shortest path from source node s to target node t, and σ_s,t is the number of shortest path between these two nodes going through v.

This measure can be normalized by the number of ordered pairs not including v:

• For directed graphs

  

• For undirected graphs

  

5 MapReduce Computation Model

The advent of big data and the increasing analysis needs favorised the design of parallel algorithms, specially in the realm of big data processing pipelines, with a tradeoff between communication costs and degree of parallelism.

MapReduce is a processing paradigm that works on top of distributed environments. More precisely, it was built on top of Google File System (GFS) and Hadoop Distributed File System (HDFS), used to manage large-scale data and to be tolerant to hardware and networks faults. To do this, HDFS splits files into large blocks and distributes thema cross nodes in a cluster, and MapReduce is the programming model used to manage many large-scale parallel computations.

Basically, the idea is that the data is first splitted, then some operation is done to it, and then it’s merged to produce the final results. For this, we will just need to define the Map and Reduce functions, while the system manages the parallel execution on distributed data and the coordination between them, leading with the possibility that one of the tasks may fail.