Theory of Complex Networks
Tutorial 2
8.Clustering coefficient via triangle countssolvedsolution
Show that in any simple non-directed graph with adjacency matrix
, for all nodes with , where is the number of triangles node takes part in.9.Clustering coefficients in the Tutorial 1 graphssolution
Calculate the clustering coefficients of all nodes in the middle and the right graph of exercise 1. Why would we not calculate them for the left graph?
10.Path counts in the Tutorial 1 graphssolution
Use the adjacency matrices from exercise 2 to prove that the left graph of exercise 1 has exactly four paths of length three and no paths of length 4 or larger. Argue why the middle and right graphs contain paths of every length
.11.Clustering coefficient vanishes on treessolvedsolution
Let
be the adjacency matrix of a tree. Show that for all nodes .12.Neumann series for the resolvent of an adjacency matrixsolution
Prove the identity
. Given a matrix norm𝟙 with the usual properties ( , , iff , , ), show there is a sufficiently small nonzero for which the series converges in norm.13.Connectivity as an equivalence relationsolution
Let
be a non-directed graph and write if some path in starts at and ends at (with ). Show that is an equivalence relation on , and define the connected components of through its equivalence classes. Bonus: can you define an equivalence relation on directed graphs? What does it mean in the directed case?
Solutions
8.Clustering coefficient via triangle counts
Closed 3-walks from
through distinct :Each triangle is walked in both directions:
so it is counted twice:
9.Clustering coefficients in the Tutorial 1 graphs
No solution yet.
10.Path counts in the Tutorial 1 graphs
No solution yet.
11.Clustering coefficient vanishes on trees
Since a tree cannot be cyclical and cannot have triangles, we say that the numerator term
is therefore the whole fraction must be .Suppose a triangle through
exists:So
and the numerator vanishes:12.Neumann series for the resolvent of an adjacency matrix
No solution yet.
13.Connectivity as an equivalence relation
No solution yet.