This page is intentionally left blank.
Please do not open this question set before you are allowed to do so.

4810-1185 Network Optimizations (Autumn 2018)
Midterm Problem 1
In this problem, we will try to use the tree decomposition technique to speeding up the calculation of
the betweenness centrality.
Question 1.1: Calculate the betweenness centrality of all edges in the following social networks.

Question 1.2: Devise an algorithm that can calculate betweenness centrality of all edges in 𝑂(||𝑉||)
when the input graph is a tree.
Question 1.3: Find a tree decomposition of the following social network. Your tree decomposition
must have small treewidth.

Question 1.4: Calculate a betweenness centrality for all edges in the graph appeared in Question 1.3.
Question 1.5: Consider the following tree of bags in a tree decomposition. Discuss why all the paths
from a node in Bag 1 to a node in Bag 3 must include some node in Bag 2.

Question 1.6: Give an idea for calculating the betweenness centrality on the graph with smalltreewidth. It would be more desirable if your algorithm’s running time is in 𝑂(𝑓(𝑘)||𝑉||) when 𝑘 is
the treewidth and 𝑓 is an arbitrary large function.

4810-1185 Network Optimizations (Autumn 2018)
Midterm Problem 2
In this graph, we will calculate PageRank centrality for a web graph of a web portal service, such asYahoo. In this graph, the users always begin browsing at the homepage. Then, they will go to the web
portal of a particular topic (such as sports or IT), and, from the web portal of a particular topic, go tothe web portal of a sub-topic (such as Football, Sumo, Blockchain, or AI). From all pages we canbrowse back to the homepage.
Our web graphs look like the following graph:

Question 2.1: Calculate PageRank for all webs in the above graph.
Question 2.2: Devise an algorithm to calculate PageRank centrality for such a graph in 𝑂(||𝑉||).
From next question, we will calculate the personalized PageRank of such web graphs. Suppose that𝛽 = 0.5.
Question 2.3: Calculate the matrix 𝑀 for the web graph in Question 2.1.
Question 2.4: Calculate the matrix (𝐼 − (1 − 𝛽)𝑀) for the web graph in Question 2.1.
Question 2.5: Which elimination order is the most suitable for the matrix (𝐼 − (1 − 𝛽)𝑀)?
Question 2.6: Give an algorithm for PageRank based on LU decomposition. Discuss why thedecomposition will finish in 𝑂(||𝑉||).

Hint: The process of LU Decomposition is as follows:4810-1185 Network Optimizations (Autumn 2018)
Midterm Problem 3
Consider the following social network:

Question 3.1: Based on the properties of the 𝑘-way clustering, guess the clustering result when thedesired number of clustering is 2. (You do not need to really calculate 𝑘-way clustering, but you haveto give a reason for your guess.)
Question 3.2: Based on your answer in Question 3.1, assume that the input graph is a tree. Design analgorithm that finishes in 𝑂(||𝑉||) for the 2-group cluster. Discuss why your result would be similar
to that of 𝑘-way clustering.
3

Question 3.3: Based on your answer in Question 3.1, design an algorithm that finishes in 𝑂 (||𝑉|| )for the 3-group cluster. Discuss why your result would be similar to that of 𝑘-way clustering.
ℓ+1

Question 3.4: Based on your answer in Question 3.1, design an algorithm that finishes in 𝑂 (||𝑉||for the ℓ-group cluster. Discuss why your result would be similar to that of 𝑘-way clustering.
Question 3.5: Discuss why your algorithm in Question 3.4 is not a fixed-parameter tractability
algorithm, even when the parameter that we assume small is ℓ.

)