Theory of Complex Networks

Tutorial 2

6 problems · 2 solved

  1. 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.

  2. 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?

  3. 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 .

  4. 11.Clustering coefficient vanishes on treessolvedsolution

    Let be the adjacency matrix of a tree. Show that for all nodes .

  5. 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.

  6. 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

  1. 8.Clustering coefficient via triangle counts

    Closed 3-walks from through distinct :

    Each triangle is walked in both directions:

    so it is counted twice:

  2. 9.Clustering coefficients in the Tutorial 1 graphs

    No solution yet.

  3. 10.Path counts in the Tutorial 1 graphs

    No solution yet.

  4. 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:

  5. 12.Neumann series for the resolvent of an adjacency matrix

    No solution yet.

  6. 13.Connectivity as an equivalence relation

    No solution yet.

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card