Skip to content

Graph Theory Exercises

Through these exercises, you will practice computing similarity metrics, centrality measures, network properties, and graph algorithms 🧙

Exercise 1 : Similarity Metrics

This exercise focuses on measuring similarity between entities in networks, which is fundamental for recommendation systems and collaborative filtering.

You're analyzing a social network where people are connected based on shared interests.

Question 1.1

Given two users with the following interests:

  • User A: \(\{Music, Sports, Reading, Gaming\}\)
  • User B: \(\{Music, Reading, Cooking, Travel\}\)

Calculate step by step:

  1. Jaccard Similarity between A and B
  2. Overlap Coefficient between A and B

Question 1.2

In a recommendation system, you have 5 users and their movie preferences:

  • User 1: \(\{Action, Comedy, Drama\}\)
  • User 2: \(\{Action, Horror, Sci\text{-}Fi\}\)
  • User 3: \(\{Comedy, Drama, Romance\}\)
  • User 4: \(\{Action, Comedy, Horror\}\)
  • User 5: \(\{Drama, Romance, Thriller\}\)

Calculate step by step:

  1. Create a similarity matrix using Jaccard Similarity for all user pairs
  2. Which pair of users is most similar?
  3. Which user would you recommend User 1 to connect with based on highest similarity?

Question 1.3

You're analyzing a bipartite graph of customers and products with ratings:

  • Customer A: \(\{(Phone, 5), (Laptop, 4), (Headphones, 3), (Case, 4)\}\)

  • Customer B: \(\{(Phone, 4), (Tablet, 5), (Headphones, 4), (Charger, 3), (Case, 3)\}\)

  • Customer C: \(\{(Laptop, 5), (Monitor, 4), (Keyboard, 4), (Mouse, 3)\}\)

Calculate step by step:

  1. Weighted Jaccard similarity using rating-adjusted intersection
  2. Predict Customer A's rating for Monitor using collaborative filtering
  3. Calculate recommendation precision if similarity threshold is \(\theta = 0.3\)

Exercise 2 : Centrality Measures

Let's explores various centrality measures used to identify important nodes in a network, such as key employees in an organization or influential users in social media.

You are analyzing an organizational network with 5 employees.

Question 2.1

Given adjacency matrix for directed network:

\[A = \left(\begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{array}\right)\]

Calculate step by step:

  1. In-degree centrality: \(C_{in}(v) = \sum_{u} A_{u,v}\)
  2. Out-degree centrality: \(C_{out}(v) = \sum_{u} A_{v,u}\)
  3. Which node has highest total degree centrality?

Question 2.2

Calculate betweenness centrality for node B using:

\[C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}\]

Calculate step by step:

  1. Find all shortest paths between every pair of nodes
  2. Count paths passing through B: \(\sigma_{st}(B)\)
  3. Apply the betweenness formula

Question 2.3

Calculate PageRank centrality with damping factor \(d = 0.85\): \(\(PR(v) = \frac{1-d}{N} + d \sum_{u \in M(v)} \frac{PR(u)}{L(u)}\)\)

Calculate step by step:

  1. Initialize: \(PR_0(v) = \frac{1}{N} = 0.2\) for all nodes
  2. Perform 3 iterations
  3. Show convergence pattern

Exercise 3 : Complex Networks & Degree Distribution

This exercise examines the structural properties of different network models, comparing random networks with scale-free networks that exhibit power-law degree distributions.

Question 3.1

Degree sequence: \([1, 2, 2, 3, 3, 3, 4, 5, 6]\)

Calculate step by step:

  1. Total edges using handshaking lemma: \(|E| = \frac{1}{2}\sum_{v} deg(v)\)
  2. Average degree: \(\langle k \rangle = \frac{1}{n}\sum_{v} deg(v)\)
  3. Validate sequence

Question 3.2

Compare network models:

  • Random: \(n=100\), edge probability \(p=0.05\)
  • Scale-free: Power law \(P(k) \propto k^{-\gamma}\) with \(\gamma = 2.5\)

Calculate step by step:

  1. Expected degree in random network: \(\langle k \rangle = (n-1)p\)
  2. Probability of exactly 3 connections: \(P(k=3) = \binom{n-1}{k}p^k(1-p)^{n-1-k}\)
  3. Scale-free node count ratio

Question 3.3

Network resilience analysis with clustering coefficient calculation.

Calculate step by step:

  1. Random network clustering: \(C_{random} = p\)
  2. Scale-free clustering with hub concentration
  3. Compare failure resilience: \(R = 1 - \frac{S_{after}}{S_{before}}\)

Exercise 4: Bipartite Graphs & Projections

This exercise demonstrates how to work with bipartite graphs and how to create meaningful projections for analysis.

Let's dive into a simple movie recommendation system analysis.

Question 4.1

Bipartite graph \(G = (U \cup M, E)\) where \(U = \{U_1, U_2, U_3\}\), \(M = \{M_1, M_2, M_3, M_4\}\):

  • \(U_1\) watched: \(\{M_1, M_2\}\)
  • \(U_2\) watched: \(\{M_2, M_3\}\)
  • \(U_3\) watched: \(\{M_1, M_3, M_4\}\)

Calculate step by step:

  1. Create user projection with weights \(w(u_i, u_j) = |N(u_i) \cap N(u_j)|\)
  2. Calculate edge weights
  3. Identify most similar users

Question 4.2

Extended bipartite network:

  • \(U_1: \{M_1, M_2, M_3\}\), \(U_2: \{M_2, M_4, M_5\}\), \(U_3: \{M_1, M_3, M_6\}\), \(U_4: \{M_4, M_5, M_6\}\)

Calculate step by step:

  1. Movie-movie projection with Jaccard weights
  2. Calculate \(J(M_1, M_3)\) and \(J(M_2, M_4)\)
  3. Recommendation algorithm: Should \(M_6\) be recommended to \(U_1\)?

Question 4.3

Collaborative filtering with matrix factorization approach.

Calculate step by step:

Implement user-based CF:

\[\hat{r}_{ui} = \bar{r}_u + \frac{\sum_{v \in S^k(u,i)} sim(u,v)(r_{vi} - \bar{r}_v)}{\sum_{v \in S^k(u,i)} |sim(u,v)|}\]

Calculate prediction accuracy using RMSE:

\[RMSE = \sqrt{\frac{1}{|T|}\sum_{(u,i) \in T}(\hat{r}_{ui} - r_{ui})^2}\]

Optimize similarity threshold \(\theta\) for maximum precision

Exercise 5: Network Properties & Complex Analysis

In this exercise we will covers advanced network properties including reciprocity, transitivity, clustering coefficients, and multi-layer network analysis.

Let's take a look at a basic communication network with edges: \(E = \{(A,B), (B,A), (B,C), (C,D), (D,A)\}\)

Question 5.1

Calculate step by step:

  1. Reciprocity: \(\rho = \frac{L^{\leftrightarrow}}{L}\) where \(L^{\leftrightarrow}\) is bidirectional edges
  2. Transitivity: Check triangles \(\triangle = \{(i,j), (j,k), (k,i)\}\)
  3. Local clustering for node B: \(C_i = \frac{2e_i}{k_i(k_i-1)}\)

Question 5.2

Self-referencing network with loops: \(E = \{(A,B), (B,C), (C,A), (A,A), (B,B), (C,D), (D,B)\}\)

Calculate step by step:

  1. Global clustering coefficient: \(\langle C \rangle = \frac{1}{n}\sum_i C_i\)
  2. Transitivity with self-loops: \(T = \frac{3 \times \text{triangles}}{\text{connected triplets}}\)
  3. Impact analysis: How do self-loops affect centrality rankings?

Question 5.3

Multi-layer network analysis comparing formal hierarchy vs. informal connections.

Calculate step by step:

  1. Structural holes using Burt's constraint: \(C_i = \sum_j \left(p_{ij} + \sum_{q} p_{iq}p_{qj}\right)^2\)
  2. Bridge detection between layers
  3. Network efficiency: \(E = \frac{1}{n(n-1)}\sum_{i \neq j} d_{ij}^{-1}\)

Exercise 6: Advanced Applications 🚀[BONUS]

This bonus exercise challenges you to combine multiple graph theory concepts and optimization techniques to design an advanced recommendation algorithms 🥷

Question 6.1

Design a recommendation algorithm combining multiple similarity measures:

\[S_{hybrid}(u,v) = \alpha \cdot J(u,v) + \beta \cdot \cos(u,v) + \gamma \cdot corr(u,v)\]

Where \(\alpha + \beta + \gamma = 1\) and:

  • \(J(u,v)\) is Jaccard similarity
  • \(\cos(u,v) = \frac{u \cdot v}{||u|| \cdot ||v||}\) is cosine similarity
  • \(corr(u,v)\) is Pearson correlation

Calculate optimal weights \((\alpha, \beta, \gamma)\) to maximize recommendation precision.

Question 6.2 (Implementation)

Code the following algorithms to solve your problem :

  1. Greedy optimisation basic
  2. Gradient descent
  3. Modularity optimization: \(Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)\)