Description
ECE 232E Summer 2025 Project 1 Random Graphs and Random Walks
1. Generating Random Networks
1. Create random networks using Erd¨os-R´enyi (ER) model
(a) Create undirected random networks with n = 900 nodes, and the probability p for
drawing an edge between two arbitrary vertices 0.002, 0.006, 0.012, 0.045, and 0.1.
Plot the degree distributions. What distribution (linear/exponential/gaussian/binomial
or something else) is observed? Explain why. Also, report the mean and variance of
the degree distributions and compare them to the theoretical values.
Hint Useful function(s): samplegnp (erdos.renyi.game) , degree ,
degreedistribution , plot
(b) For each p and n = 900, answer the following questions:
Are all random realizations of the ER network connected? Numerically estimate the
probability that a generated network is connected. For one instance of the networks
with that p, find the giant connected component (GCC) if not connected. What is
the diameter of the GCC?
Hint Useful function(s): isconnected , clusters , diameter
(c) It turns out that the normalized GCC size (i.e., the size of the GCC as a fraction of
the total network size) is a highly nonlinear function of p, with interesting properties
occurring for values where p = O(
1
n
) and p = O(
ln n
n
).
For n = 900, sweep over values of p from 0 to a pmax that makes the network almost
surely connected and create 100 random networks for each p. pmax should be roughly
determined by yourself. Then scatter plot the normalized GCC sizes vs p. Plot a line
of the average normalized GCC sizes for each p along with the scatter plot.
i. Empirically estimate the value of p where a giant connected component starts to
emerge (define your criterion of “emergence”)? Do they match with theoretical
values mentioned or derived in lectures?
ii. Empirically estimate the value of p where the giant connected component takes
up over 99% of the nodes in almost every experiment.
(d) i. Define the average degree of nodes c = n × p = 0.5. Sweep over the number of
nodes, n, ranging from 100 to 10000. Plot the expected size of the GCC of ER
networks with n nodes and edge-formation probabilities p = c/n, as a function
of n. What trend is observed?
ii. Repeat the same for c = 1.
iii. Repeat the same for values of c = 1.15, 1.25, 1.35, and show the results for these
three values in a single plot.
iv. What is the relation between the expected GCC size and n in each case?
2. Create networks using preferential attachment model
(a) Create an undirected network with n = 1050 nodes, with preferential attachment
model, where each new node attaches to m = 1 old nodes. Is such a network always
connected?
Hint Useful function(s): samplepa (barabasi.game)
(b) Use fast greedy method to find the community structure. Measure modularity. Define
Assortativity. Compute Assortativity.
Hint Useful function(s): clusterfastgreedy , modularity
(c) Try to generate a larger network with 10500 nodes using the same model. Compute
modularity and assortativity. How is it compared to the smaller network’s modularity?
2
(d) Plot the degree distribution in a log-log scale for both n = 1050, 10500, then estimate
the slope of the plot using linear regression.
(e) In the two networks generated in 2(a) and 2(c), perform the following:
Randomly pick a node i, and then randomly pick a neighbor j of that node. Plot the
degree distribution of nodes j that are picked with this process, in the log-log scale.
Is the distribution linear in the log-log scale? If so, what is the slope? How does this
differ from the node degree distribution?
Hint Useful function(s): sample
(f) Estimate the expected degree of a node that is added at time step i for 1 ≤ i ≤ 1050.
Show the relationship between the age of nodes and their expected degree through
an appropriate plot. Note that the newest added node is the youngest.
(g) Repeat the previous parts (a-f) for m = 2, and m = 6. Compare the results of each
part for different values of m.
(h) Again, generate a preferential attachment network with n = 1050, m = 1. Take its
degree sequence and create a new network with the same degree sequence, through
stub-matching procedure. Plot both networks, mark communities on their plots,
and measure their modularity. Compare the two procedures for creating random
power-law networks.
Hint In case that fastgreedy community detection fails because of self-loops, you
may use “walktrap” community detection.
Useful function(s): sampledegseq
3. Create a modified preferential attachment model that penalizes the age of a node
(a) Each time a new vertex is added, it creates m links to old vertices and the probability
that an old vertex is cited depends on its degree (preferential attachment) and age.
In particular, the probability that a newly added vertex connects to an old vertex is
proportional to:
P[i] ∼ (ckα
i + a)(dlβ
i + b),
where ki
is the degree of vertex i in the current time step, and li
is the age of vertex
i. Produce such an undirected network with 1050 nodes and parameters m = 1,
α = 1, β = −1, and a = c = d = 1, b = 0. Plot the degree distribution. What is the
power law exponent?
Hint Useful function(s): samplepaage
(b) Use fast greedy method to find the community structure. What is the modularity?
3
2. Random Walk on Networks
1. Random walk on Erd¨os-R´enyi networks
(a) Create an undirected random network with 900 nodes, and the probability p for
drawing an edge between any pair of nodes equal to 0.015.
(b) Let a random walker start from a randomly selected node (no teleportation). We
use t to denote the number of steps that the walker has taken. Measure the average
distance (defined as the shortest path length) ⟨s(t)⟩ of the walker from his starting
point at step t. Also, measure the variance σ
2
(t) = ⟨(s(t) − ⟨s(t)⟩)
2
⟩ of this distance.
Plot ⟨s(t)⟩ v.s. t and σ
2
(t) v.s. t. Here, the average ⟨·⟩ is over random choices of the
starting nodes.
(c) Measure the degree distribution of the nodes reached at the end of the random walk.
How does it compare to the degree distribution of graph?
(d) Repeat 1(b) for undirected random networks with 9000 nodes. Compare the results
and explain qualitatively. Does the diameter of the network play a role?
2. Random walk on networks with fat-tailed degree distribution
(a) Generate an undirected preferential attachment network with 900 nodes, where each
new node attaches to m = 1 old nodes.
(b) Let a random walker start from a randomly selected node. Measure and plot ⟨s(t)⟩
v.s. t and σ
2
(t) v.s. t.
(c) Measure the degree distribution of the nodes reached at the end of the random walk
on this network. How does it compare with the degree distribution of the graph?
(d) Repeat 2(b) for preferential attachment networks with 90 and 9000 nodes, and m = 1.
Compare the results and explain qualitatively. Does the diameter of the network play
a role?
3. PageRank
The PageRank algorithm, as used by the Google search engine, exploits the linkage structure of the web to compute global “importance” scores that can be used to influence the
ranking of search results. Here, we use random walk to simulate PageRank.
(a) We are going to create a directed random network with 900 nodes, using the preferential attachment model. Note that in a directed preferential attachment network, the
out-degree of every node is m, while the in-degrees follow a power law distribution.
One problem of performing random walk in such a network is that, the very first
node will have no outbounding edges, and be a “black hole” which a random walker
can never “escape” from. To address that, let’s generate another 900-node random
network with preferential attachment model, and merge the two networks by adding
the edges of the second graph to the first graph with a shuffling of the indices of the
nodes. For example,
1 → 2
2 → 3
3 → 4
Initial edge list of
the second network
4 → 3
3 → 1
1 → 2
Edge list after
node idx shuffling
(the edges that should be
added to the first network)
shuffled to
1,2,3,4 4,3,1,2
4
Create such a network using m = 4. Measure the probability that the walker visits
each node. Is this probability related to the degree of the nodes?
Hint Useful function(s): asedgelist , sample , permute , addedges
(b) In all previous questions, we didn’t have any teleportation. Now, we use a teleportation probability of α = 0.2 (teleport out of a node with prob=0.2 instead of going to
its neighbor). By performing random walks on the network created in 3(a), measure
the probability that the walker visits each node. How is this probability related to
the degree of the node and α ?
4. Personalized PageRank
While the use of PageRank has proven very effective, the web’s rapid growth in size and
diversity drives an increasing demand for greater flexibility in ranking. Ideally, each user
should be able to define their own notion of importance for each individual query.
(a) Suppose you have your own notion of importance. Your interest in a node is proportional to the node’s PageRank, because you totally rely upon Google to decide which
website to visit (assume that these nodes represent websites). Again, use random
walk on network generated in question 3 to simulate this personalized PageRank.
Here the teleportation probability to each node is proportional to its PageRank (as
opposed to the regular PageRank, where at teleportation, the chance of visiting all
nodes are the same and equal to 1
N
). Again, let the teleportation probability be
equal to α = 0.2. Compare the results with 3(a).
(b) Find two nodes in the network with median PageRanks. Repeat part 4(a) if teleportations land only on those two nodes (with probabilities 1/2, 1/2). How are the
PageRank values affected?
(c) More or less, 4(b) is what happens in the real world, in that a user browsing the web
only teleports to a set of trusted web pages. However, this is against the assumption
of normal PageRank, where we assume that people’s interest in all nodes are the
same. Can you take into account the effect of this self-reinforcement and adjust the
PageRank equation?
5
Final Remarks
The following functions from igraph library are useful for this project:
• degree, degree.distribution, diameter, clusters, vcount, ecount
• random.graph.game, barabasi.game, aging.prefatt.game, degree.sequence.game
• page rank
For part 2 of the project, you can start off with the Jupyter notebook provided to you.
ECE 232E Summer 2025 Project 2 Social Network Mining
In this project, we will study the various properties of social networks. In the first part of
the project, we will study an undirected social network (Facebook). In the second part of the
project, we will study a directed social network (Google +). You can complete the Project
using R or Python.
1. Facebook network
In this project, we will be using the dataset given below:
http://snap.stanford.edu/data/egonets-Facebook.html
The Facebook network can be created from the edgelist file (facebook combined.txt)
1. Structural properties of the Facebook network
Having created the Facebook network, we will study some of the structural properties of the
network. To be specific, we will study
• Connectivity
• Degree distribution
QUESTION 1: A first look at the network:
QUESTION 1.1: Report the number of nodes and number of edges of the Facebook network.
QUESTION 1.2: Is the Facebook network connected? If not, find the giant connected component
(GCC) of the network and report the size of the GCC.
QUESTION 2: Find the diameter of the network. If the network is not connected, then find the
diameter of the GCC.
QUESTION 3: Plot the degree distribution of the facebook network and report the average
degree.
QUESTION 4: Plot the degree distribution of Question 3 in a log-log scale. Try to fit a line to
the plot and estimate the slope of the line.
1
2. Personalized network
A personalized network of an user vi
is defined as the subgraph induced by vi and it’s neighbors.
In this part, we will study some of the structural properties of the personalized network of the
user whose graph node ID is 1 (node ID in edgelist is 0). From this point onwards, whenever
we are refering to a node ID we mean the graph node ID which is 1 + node ID in edgelist.
QUESTION 5: Create a personalized network of the user whose ID is 1. How many nodes and
edges does this personalized network have?
Hint Useful function(s): makeegograph
QUESTION 6: What is the diameter of the personalized network? Please state a trivial upper
and lower bound for the diameter of the personalized network.
QUESTION 7: In the context of the personalized network, what is the meaning of the diameter
of the personalized network to be equal to the upper bound you derived in Question 6. What is the
meaning of the diameter of the personalized network to be equal to the lower bound you derived in
Question 6 (assuming there are more than 3 nodes in the personalized network)?
3. Core node’s personalized network
A core node is defined as the nodes that have more than 200 neighbors. For visualization
purpose, we have displayed the personalized network of a core node below.
An example of a personal network. The core node is shown in black.
In this part, we will study various properties of the personalized network of the core nodes.
QUESTION 8: How many core nodes are there in the Facebook network. What is the average
degree of the core nodes?
3.1. Community structure of core node’s personalized network
In this part, we study the community structure of the core node’s personalized network. To
be specific, we will study the community structure of the personalized network of the following
core nodes:
2
• Node ID 1
• Node ID 108
• Node ID 349
• Node ID 484
• Node ID 1087
QUESTION 9: For each of the above core node’s personalized network, find the community structure using Fast-Greedy, Edge-Betweenness, and Infomap community detection algorithms. Compare
the modularity scores of the algorithms. For visualization purpose, display the community structure
of the core node’s personalized networks using colors. Nodes belonging to the same community
should have the same color and nodes belonging to different communities should have different
color. In this question, you should have 15 plots in total.
Hint Useful function(s): clusterfastgreedy , clusteredgebetweenness , clusterinfomap
3.2. Community structure with the core node removed
In this part, we will explore the effect on the community structure of a core node’s personalized
network when the core node itself is removed from the personalized network.
QUESTION 10: For each of the core node’s personalized network (use same core nodes as
Question 9), remove the core node from the personalized network and find the community structure
of the modified personalized network. Use the same community detection algorithm as Question 9.
Compare the modularity score of the community structure of the modified personalized network with
the modularity score of the community structure of the personalized network of Question 9. For
visualization purpose, display the community structure of the modified personalized network using
colors. In this question, you should have 15 plots in total.
3.3. Characteristic of nodes in the personalized network
In this part, we will explore characteristics of nodes in the personalized network using two
measures. These two measures are stated and defined below:
• Embeddedness of a node is defined as the number of mutual friends a node shares with
the core node.
• Dispersion of a node is defined as the sum of distances between every pair of the mutual
friends the node shares with the core node. The distances should be calculated in a
modified graph where the node (whose dispersion is being computed) and the core node
are removed.
For further details on the above characteristics, you can read the paper below:
http://arxiv.org/abs/1310.6753
QUESTION 11: Write an expression relating the Embeddedness between the core node and
a non-core node to the degree of the non-core node in the personalized network of the core node.
3
QUESTION 12: For each of the core node’s personalized network (use the same core nodes as
Question 9), plot the distribution histogram of embeddedness and dispersion. In this question, you
will have 10 plots.
Hint Useful function(s): neighbors , intersection , distances
QUESTION 13: For each of the core node’s personalized network, plot the community structure
of the personalized network using colors and highlight the node with maximum dispersion. Also,
highlight the edges incident to this node. To detect the community structure, use Fast-Greedy
algorithm. In this question, you will have 5 plots.
QUESTION 14: Repeat Question 13, but now highlight the node with maximum embeddedness
and the node with maximum dispersion
embeddedness (excluding the nodes having zero embeddedness if there
are any). Also, highlight the edges incident to these nodes. Report the id of those nodes.
QUESTION 15: Use the plots from Question 13 and 14 to explain the characteristics of a node
revealed by each of this measure.
4. Friend recommendation in personalized networks
In many social networks, it is desirable to predict future links between pairs of nodes in the
network. In the context of this Facebook network it is equivalent to recommending friends to
users. In this part of the project, we will explore some neighborhood-based measures for friend
recommendation. The network that we will be using for this part is the personalized network
of node with ID 415.
4.1. Neighborhood based measure
In this project, we will be exploring three different neighborhood-based measures. Before we
define these measures, let’s introduce some notation:
• Si
is the neighbor set of node i in the network
• Sj
is the neighbor set of node j in the network
Then, with the above notation we define the three measures below:
• Common neighbor measure between node i and node j is defined as
Common Neighbors(i, j) = |Si ∩ Sj
|
• Jaccard measure between node i and node j is defined as
Jaccard(i, j) = |Si ∩ Sj
|
|Si ∪ Sj
|
• Adamic-Adar measure between node i and node j is defined as
Adamic Adar(i, j) = X
k∈Si∩Sj
1
log(|Sk|)
4
4.2. Friend recommendation using neighborhood based measures
We can use the neighborhood based measures defined in the previous section to recommend
new friends to users in the network. Suppose we want to recommend t new friends to some
user i in the network using Jaccard measure. We follow the steps listed below:
1. For each node in the network that is not a neighbor of i, compute the jaccard measure
between the node i and the node not in the neighborhood of i
Compute Jaccard(i, j) ∀j ∈ S
C
i
2. Then pick t nodes that have the highest Jaccard measure with node i and recommend
these nodes as friends to node i
4.3. Creating the list of users
Having defined the friend recommendation procedure, we can now apply it to the personalized
network of node ID 415. Before we apply the algorithm, we need to create the list of users who
we want to recommend new friends to. We create this list by picking all nodes with degree 24.
We will denote this list as Nr.
QUESTION 16: What is |Nr|, i.e. the length of the list Nr?
4.4. Average accuracy of friend recommendation algorithm
In this part, we will apply the 3 different types of friend recommendation algorithms to recommend friends to the users in the list Nr. We will define an average accuracy measure to
compare the performances of the friend recommendation algorithms.
Suppose we want to compute the average accuracy of the friend recommendation algorithm.
This task is completed in two steps:
1. Compute the average accuracy for each user in the list Nr
2. Compute the average accuracy of the algorithm by averaging across the accuracies of the
users in the list Nr
Let’s describe the procedure for accomplishing the step 1 of the task. Suppose we want to
compute the average accuracy for user i in the list Nr. We can compute it by iterating over
the following steps 10 times and then taking the average:
1. Remove each edge of node i at random with probability 0.25. In this context, it is
equivalent to deleting some friends of node i. Let’s denote the list of friends deleted as Ri
2. Use one of the three neighborhood based measures to recommend |Ri
| new friends to the
user i. Let’s denote the list of friends recommended as Pi
3. The accuracy for the user i for this iteration is given by |Pi∩Ri|
|Ri|
By iterating over the above steps for 10 times and then taking the average gives us the average
accuracy of user i. In this manner, we compute the average accuracy for each user in the list
5
Nr. Once we have computed them, then we can take the mean of the average accuracies of the
users in the list Nr. The mean value will be the average accuracy of the friend recommendation
algorithm.
QUESTION 17: Compute the average accuracy of the friend recommendation algorithm that
uses:
• Common Neighbors measure
• Jaccard measure
• Adamic Adar measure
Based on the average accuracy values, which friend recommendation algorithm is the best?
Hint Useful function(s): similarity
2. Google+ network
In this part, we will explore the structure of the Google+ network. The dataset for creating
the network can be found in the link below:
http://snap.stanford.edu/data/egonets-Gplus.html
Create directed personal networks for users who have more than 2 circles. The data required
to create such personal networks can be found in the file named gplus.tar.gz.
QUESTION 18: How many personal networks are there?
QUESTION 19: For the 3 personal networks (node ID given below), plot the in-degree and outdegree distribution of these personal networks. Do the personal networks have a similar in and out
degree distribution? In this question, you should have 6 plots.
• 109327480479767108490
• 115625564993990145546
• 101373961279443806744
1. Community structure of personal networks
In this part of the project, we will explore the community structure of the personal networks
that we created and explore the connections between communities and user circles.
QUESTION 20: For the 3 personal networks picked in Question 19, extract the community
structure of each personal network using Walktrap community detection algorithm. Report the
modularity scores and plot the communities using colors. Are the modularity scores similar? In this
question, you should have 3 plots.
Having found the communities, now we will explore the relationship between circles and communities. In order to explore the relationship, we define two measures:
6
• Homogeneity
• Completeness
Before, we state the expression for homogeneity and completeness, let’s introduce some notation:
• C is the set of circles, C = {C1, C2, C3, · · · }
• K is the set of communities, K = {K1, K2, K3, · · · }
• ai
is the number of people in circle Ci
• bi
is the number of people in community Ki with circle information
• N is the total number of people with circle information
• Aji is the number of people belonging to community j and circle i
Then, with the above notation, we have the following expressions for the entropy
H(C) = −
X
|C|
i=1
ai
N
log( ai
N
) (1)
H(K) = −
X
|K|
i=1
bi
N
log( bi
N
) (2)
and conditional entropy
H(C|K) = −
X
|K|
j=1
X
|C|
i=1
Aji
N
log(Aji
bj
) (3)
H(K|C) = −
X
|C|
i=1
X
|K|
j=1
Aji
N
log(Aji
ai
) (4)
Now we can state the expression for homogeneity, h as
h = 1 −
H(C|K)
H(C)
(5)
and the expression for completeness, c as
c = 1 −
H(K|C)
H(K)
(6)
QUESTION 21: Based on the expression for h and c, explain the meaning of homogeneity and
completeness in words.
QUESTION 22: Compute the h and c values for the community structures of the 3 personal
network (same nodes as Question 19). Interpret the values and provide a detailed explanation. Are
there negative values? Why?
7
3. Cora dataset
One of the well-known categories of machine learning problems is “supervised learning”. In supervised learning, we are given some information called “input” features about certain objects.
For each object, we are also given an “output” or target variable that we are trying to predict
about. Our goal is to learn the mapping between the features and the target variable. Typically, there is a portion of data where both input features and target variables are available.
This portion of the dataset is called the training set. There is also typically another portion
of the dataset where the target variable is missing and we want to predict it. This portion is
called the “test set”. When the target variable can take on a finite number of discrete values,
we call the problem at hand a “classification” problem.
In this project, we are trying to solve a classification problem in settings where some additional information is provided in the form of “graph structure”. In this project we work
with “Cora” dataset. Cora consists of a set of 2708 documents that are Machine Learning
related papers. Each documents is labeled with one of the following seven classes: Case Based,
Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning,
Rule Learning, Theory. For each class, only 20 documents are labeled (a total of 140 for the
seven classes). We refer to them as “seed” documents. Each document comes with a set of
features about its text content. These features are occurrences of a selection of 1433 words in
the vocabulary. We are also given an undirected graph where each node is a document and each
edge represents a citation. There are a total of 5429 edges. Our goal is to use the hints from
text features as well as from graph connections to classify (assign labels to) these documents.
To solve this problem for Cora dataset, we pursue three parallel ideas. Implement each idea
and compare.
QUESTION 23: Idea 1
Use Graph Convolutional Networks [1]. What hyperparameters do you choose to get the optimal
performance? How many layers did you choose?
QUESTION 24: Idea 2
Extract structure-based node features using Node2Vec [2]. Briefly describe how Node2Vec finds
node features. Choose your desired classifier (one of SVM, Neural Network, or Random Forest)
and classify the documents using only Node2Vec (graph structure) features. Now classify the
documents using only the 1433-dimensional text features. Which one outperforms? Why do
you think this is the case? Combine the Node2Vec and text features and train your classifier
on the combined features. What is the best classification accuracy you get (in terms of the
percentage of test documents correctly classified)?
QUESTION 25: Idea 3
We can find the personalized PageRank of each document in seven different runs, one per class.
In each run, select one of the classes and take the 20 seed documents of that class. Then,
perform a random walk with the following customized properties: (a) teleportation takes the
random walker to one of the seed documents of that class (with a uniform probability of 1/20
per seed document). Vary the teleportation probability in {0, 0.1, 0.2}. (b) the probability of
transitioning to neighbors is not uniform among the neighbors. Rather, it is proportional to the
cosine similarity between the text features of the current node and the next neighboring node.
Particularly, assume we are currently visiting a document x0 which has neighbors x1, x2, x3.
8
Then the probability of transitioning to each neighbor is:
pi =
exp(x0 · xi)
exp(x0 · x1) + exp(x0 · x2) + exp(x0 · x3)
; for i = 1, 2, 3. (7)
Repeat part b for every teleportation probability in part a.
Run the PageRank only on the GCC. for each seed node, do 1000 random walks. Maintain
a class-wise visited frequency count for every unlabeled node. The predicted class for that
unlabeled node is the class which lead to maximum visits to that node. Report accuracy and
f1 scores.
For example if node ’n’ was visited by 7 random walks from class A, 6 random walks from class
B… 1 random walk from class G, then the predicted label of node of ’n’ is class A.
Submission
Please submit the report to Gradescope. Meanwhile, please submit a zip file containing your codes and report to BruinLearn. The zip file should be named as
“Project2 UID1 … UIDn.zip” where UIDx are student ID numbers of team members. If you have any questions please feel free to ask them over email or piazza.
References
[1] Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” arXiv preprint arXiv:1609.02907 (2016).
ECE 232E Summer 2025 Project 3 Reinforcement learning and Inverse Reinforcement learning
1 Introduction
Reinforcement Learning (RL) is the task of learning from interaction to achieve a goal.
The learner and the decision maker is called the agent. The thing it interacts with,
comprising everything outside the agent, is called the environment. These interact continually, the agent selecting actions and the environment responding to those actions by
presenting rewards and new states.
In the first part of the project, we will learn the optimal policy of an agent navigating in a 2-D environment. We will implement the Value iteration algorithm to learn the
optimal policy.
Inverse Reinforcement Learning (IRL) is the task of extracting an expert’s reward function by observing the optimal policy of the expert. In the second part of the project, we
will explore the application of IRL in the context of apprenticeship learning.
2 Reinforcement learning (RL)
The two main objects in Reinforcement learning are:
• Agent
• Environment
In this project, we will learn the optimal policy of a single agent navigating in a 2-D
environment.
2.1 Environment
In this project, we assume that the environment of the agent is modeled by a Markov
Decision Process (MDP). In a MDP, agents occupy a state of the environment and
perform actions to change the state they are in. After taking an action, they are given
some representation of the new state and some reward value associated with the new state.
An MDP formally is a tuple (S, A,P
a
ss′, Ra
ss′, γ) where:
1
• S is a set of states
• A is a set of actions
• P
a
ss′ is a set of transition probabilities, where P
a
ss′ is the probability of transitioning from state s ∈ S to state s
′ ∈ S after taking action a ∈ A
– P
a
ss′ = P(st+1 = s
′
|st = s, at = a)
• Given any current state and action, s and a, together with any next state, s
′
, the
expected value of the next reward is Ra
ss′
– Ra
ss′ = E(rt+1|st = s, at = a, st+1 = s
′
)
• γ ∈ [0, 1) is the discount factor, and it is used to compute the present value of future
reward
– If γ is close to 1 then the future rewards are discounted less
– If γ is close to 0 then the future rewards are discounted more
In the next few subsections, we will discuss the parameters that will be used to generate
the environment for the project.
2.1.1 State space
In this project, we consider the state space to be a 2-D square grid with 100 states. The
2-D square grid along with the numbering of the states is shown in figure 1
Figure 1: 2-D square grid with state numbering
2.1.2 Action set
In this project, we consider the action set(A) to contain the 4 following actions:
• Move Right
2
• Move Left
• Move Up
• Move Down
The 4 types of actions are displayed in figure 2
Figure 2: 4 types of action
From the above figure, we can see that the agent can take 4 actions from the state
marked with a dot.
2.1.3 Transition probabilities
In this project, we define the transition probabilities in the following manner:
1. If state s
′ and s are not neighboring states in the 2-D grid, then
P(st+1 = s
′
|st = s, at = a) = 0
s
′ and s are neighbors in the 2-D grid if you can move to s
′
from s by taking an
action a from the action set A. We will consider a state s to be a neighbor of itself.
For example, from figure 1 we can observe that states 1 and 11 are neighbors (we
can transition from 1 to 11 by moving right) but states 1 and 12 are not neighbors.
2. Each action corresponds to a movement in the intended direction with probability
1 − w, but has a probability of w of moving in a random direction instead due to
wind. To illustrate this, let’s consider the states shown in figure 3
3
Figure 3: Inner grid states (Non-boundary states)
The transition probabilities for the non-boundary states shown in figure 3 are given
below:
P(st+1 = 43|st = 44, at =↑) = 1 − w +
w
4
P(st+1 = 34|st = 44, at =↑) = w
4
P(st+1 = 54|st = 44, at =↑) = w
4
P(st+1 = 45|st = 44, at =↑) = w
4
From the above calculation it can be observed that if the agent is at a non-boundary
state then it has 4 neighbors excluding itself and the probability w is uniformly
distributed over the 4 neighbors. Also, if the agent is at a non-boundary state then
it transitions to a new state after taking an action (P(st+1 = 44|st = 44, at =↑) = 0)
3. If the agent is at one of the four corner states (0,9,90,99), the agent stays at the
current state if it takes an action to move off the grid or is blown off the grid by
wind. The actions can be divided into two categories:
• Action to move off the grid
• Action to stay in the grid
To illustrate this, let’s consider the states shown in figure 4
4
Figure 4: Corner states
The transition probabilities for taking an action to move off the grid are given below:
P(st+1 = 10|st = 0, at =↑) = w
4
P(st+1 = 1|st = 0, at =↑) = w
4
P(st+1 = 0|st = 0, at =↑) = 1 − w +
w
4
+
w
4
The transition probabilities for taking an action to stay in the grid are given below:
P(st+1 = 10|st = 0, at =→) = 1 − w +
w
4
P(st+1 = 1|st = 0, at =→) = w
4
P(st+1 = 0|st = 0, at =→) = w
4
+
w
4
At a corner state, you can be blown off the grid in two directions. As a result, we
have P(st+1 = 0|st = 0, at =→) = w
4 +
w
4
since we can be blown off the grid in two
directions and in both the cases we stay at the current state.
4. If the agent is at one of the edge states, the agent stays at the current state if it
takes an action to move off the grid or is blown off the grid by wind. The actions
can be divided into two categories:
• Action to move off the grid
• Action to stay in the grid
To illustrate this, let’s consider the states shown in figure 5
5
Figure 5: Edge states
The transition probabilities for taking an action to move off the grid are given below:
P(st+1 = 0|st = 1, at =←) = w
4
P(st+1 = 11|st = 1, at =←) = w
4
P(st+1 = 2|st = 1, at =←) = w
4
P(st+1 = 1|st = 1, at =←) = 1 − w +
w
4
The transition probabilities for taking an action to stay in the grid are given below:
P(st+1 = 0|st = 1, at =↑) = 1 − w +
w
4
P(st+1 = 11|st = 1, at =↑) = w
4
P(st+1 = 2|st = 1, at =↑) = w
4
P(st+1 = 1|st = 1, at =↑) = w
4
At an edge state, you can be blown off the grid in one direction. As a result, we have
P(st+1 = 1|st = 1, at =↑) = w
4
since we can be blown off the grid in one direction
and in that case we stay at the current state.
The main difference between a corner state and an edge state is that a corner state has
2 neighbors and an edge state has 3 neighbors.
2.1.4 Reward function
To simplify the project, we will assume that the reward function is independent of the current state (s) and the action that you take at the current state (a). To be specific, reward
6
function only depends on the state that you transition to (s
′
). With this simplification,
we have
Ra
ss′ = R(s
′
)
In this project, we will learn the optimal policy of an agent for two different reward
functions:
• Reward function 1
• Reward function 2
The two different reward functions are displayed in figures 6 and 7 respectively
Figure 6: Reward function 1
7
Figure 7: Reward function 2
Question 1: (10 points) For visualization purpose, generate heat maps of Reward function 1 and Reward function 2. For the heat maps, make sure you display the coloring
scale. You will have 2 plots for this question
For solving question 1, you might find the following function useful:
https://matplotlib.org/api/_as_gen/matplotlib.pyplot.pcolor.html
3 Optimal policy learning using RL algorithms
In this part of the project, we will use reinforcement learning (RL) algorithm to find the
optimal policy. The main steps in RL algorithm are:
• Find optimal state-value or action-value
• Use the optimal state-value or action-value to determine the deterministic optimal
policy
There are a couple of RL algorithms, but we will use the Value iteration algorithm since
it was discussed in detail in the lecture. We will skip the derivation of the algorithm here
because it was covered in the lecture (for the derivation details please refer to the lecture
slides on Reinforcement learning). We will just reproduce the algorithm below for the
ease of implementation:
8
1: procedure Value Iteration(P
a
ss′ , Ra
ss′ , S, A, γ):
2: for all s ∈ S do ▷ Initialization
3: V (s) ← 0
4: end for
5: ∆ ← ∞
6: while ∆ > ϵ do ▷ Estimation
7: ∆ ← 0
8: for all s ∈ S do
9: v ← V (s);
10: V (s) ← max
a∈A
X
s
′∈S
P
a
ss′ [Ra
ss′ + γV (s
′
)];
11: ∆ ← max(∆, |v − V (s)|);
12: end for
13: end while
14: for all s ∈ S do ▷ Computation
15: π(s) ← arg max
a∈A
X
s
′∈S
P
a
ss′ [Ra
ss′ + γV (s
′
)];
16: end for
17: end procedure return π
Question 2: (40 points) Create the environment of the agent using the information
provided in section 2. To be specific, create the MDP by setting up the state-space,
action set, transition probabilities, discount factor, and reward function. For creating the
environment, use the following set of parameters:
• Number of states = 100 (state space is a 10 by 10 square grid as displayed in figure
1)
• Number of actions = 4 (set of possible actions is displayed in figure 2)
• w = 0.1
• Discount factor = 0.8
• Reward function 1
After you have created the environment, then write an optimal state-value function that
takes as input the environment of the agent and outputs the optimal value of each state
in the grid. For the optimal state-value function, you have to implement the Initialization
(lines 2-4) and Estimation (lines 5-13) steps of the Value Iteration algorithm. For the
estimation step, use ϵ = 0.01. For visualization purpose, you should generate a figure
similar to that of figure 1 but with the number of state replaced by the optimal value of
that state. In this part of question, you should have 1 plot.
Let’s assume that your value iteration algorithm converges in N steps. Plot snapshots
of state values in 5 different steps linearly distributed from 1 to N. Report N and your
step numbers. What observations do you have from the plots?
Question 3: (5 points) Generate a heat map of the optimal state values across the 2-
D grid. For generating the heat map, you can use the same function provided in the hint
earlier (see the hint after question 1).
Question 4: (15 points) Explain the distribution of the optimal state values across the
2-D grid. (Hint: Use the figure generated in question 3 to explain)
Question 5: (20 points) Implement the computation step of the value iteration algorithm
9
(lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space.
For visualization purpose, you should generate a figure similar to that of figure 1 but
with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your
intuition? Please provide a brief explanation. Is it possible for the agent to compute the
optimal action to take at each state by observing the optimal values of it’s neighboring
states? In this question, you should have 1 plot.
Question 6: (10 points) Modify the environment of the agent by replacing Reward function 1 with Reward function 2. Use the optimal state-value function implemented in
question 2 to compute the optimal value of each state in the grid. For visualization
purpose, you should generate a figure similar to that of figure 1 but with the number of
state replaced by the optimal value of that state. In this question, you should have 1 plot.
Question 7: (20 points) Generate a heat map of the optimal state values (found in
question 6) across the 2-D grid. For generating the heat map, you can use the same
function provided in the hint earlier.
Explain the distribution of the optimal state values across the 2-D grid. (Hint: Use the
figure generated in this question to explain)
Question 8: (20 points) Implement the computation step of the value iteration algorithm
(lines 14-17) to compute the optimal policy of the agent navigating the 2-D state-space.
For visualization purpose, you should generate a figure similar to that of figure 1 but
with the number of state replaced by the optimal action at that state. The optimal actions should be displayed using arrows. Does the optimal policy of the agent match your
intuition? Please provide a brief explanation. In this question, you should have 1 plot.
Question 9:(20 points) Change the hyper parameter w to 0.6 and find the optimal policy
map similar to previous question for reward functions. Explain the differences you observe. What do you think about value of new w compared to previous value? Choose the
w that you think give rise to better optimal policy and use that w for the next stages of
the project.
4 Inverse Reinforcement learning (IRL)
Inverse Reinforcement learning (IRL) is the task of learning an expert’s reward function
by observing the optimal behavior of the expert. The motivation for IRL comes from
apprenticeship learning. In apprenticeship learning, the goal of the agent is to learn a
policy by observing the behavior of an expert. This task can be accomplished in two
ways:
1. Learn the policy directly from expert behavior
2. Learn the expert’s reward function and use it to generate the optimal policy
The second way is preferred because the reward function provides a much more parsimonious description of behavior. Reward function, rather than the policy, is the most
succinct, robust, and transferable definition of the task. Therefore, extracting the reward
function of an expert would help design more robust agents.
In this part of the project, we will use IRL algorithm to extract the reward function.
10
We will use the optimal policy computed in the previous section as the expert behavior
and use the algorithm to extract the reward function of the expert. Then, we will use the
extracted reward function to compute the optimal policy of the agent. We will compare
the optimal policy of the agent to the optimal policy of the expert and use some similarity
metric between the two to measure the performance of the IRL algorithm.
4.1 IRL algorithm
For finite state spaces, there are a couple of IRL algorithms for extracting the reward
function:
• Linear Programming (LP) formulation
• Maximum Entropy formulation
Since we covered the LP formulation of inverse reinforcement learning in lecture—and it
is simpler than the original quadratic-program approach—we adopt that version here [?].
A step-by-step derivation can be found in our course slides [?]. The LP formulation of
the IRL is given by equation 1
maximize
R,ti,ui
P|S|
i=1(ti − λui)
subject to [(Pa1
(i) − Pa(i))(I − γPa1
)
−1R] ≥ ti
, ∀a ∈ A \ a1, ∀i
(Pa1 − Pa)(I − γPa1
)
−1R ⪰ 0, ∀a ∈ A \ a1
−u ⪯ R ⪯ u
|Ri
| ≤ Rmax, i = 1, 2, · · · , |S|
(1)
In the LP given by equation 1, R is the reward vector (R(i) = R(si)), Pa is the
transition probability matrix corresponding to the action a, λ is the adjustable penalty
coefficient, and ti
’s and ui
’s are the extra optimization variables (please note that u(i) =
ui). Throughout IRL section we fix the discount factor to γ = 0.9. Use the
maximum absolute value of the ground-truth reward as Rmax.
For the ease of implementation, we can recast the LP in equation 1 into an equivalent
form given by equation 2 using block matrices.
maximize
x
c
T x
subject to Dx ⪯ b, ∀a ∈ A \ a1
(2)
Question 10: (10 points) Express c, x, D, b in terms of R, Pa, Pa1
, ti
, u, λ and Rmax
4.2 Performance measure
In this project, we use a very simple measure to evaluate the performance of the IRL
algorithm. Before we state the performance measure, let’s introduce some notation:
• OA(s): Optimal action of the agent at state s
• OE(s): Optimal action of the expert at state s
•
m(s) = (
1, OA(s) = OE(s)
0, else
11
Then with the above notation, accuracy is given by equation 3
Accuracy =
P
s∈S m(s)
|S| (3)
Since we are using the optimal policy found in the previous section as the expert behavior,
so we will use the optimal policy found in the previous section to fill the OE(s) values.
Please note that these values will be different depending on whether we used Reward
Function 1 or Reward Function 2 to create the environment.
To compute OA(s), we will solve the linear program given by equation 2 to extract
the reward function of the expert. For solving the linear program you can use the LP
solver in python (from cvxopt import solvers and then use solvers.lp). Then, we will use
the extracted reward function to compute the optimal policy of the agent using the value
iteration algorithm you implemented in the previous section. The optimal policy of the
agent found in this manner will be used to fill the OA(s) values. Please note that these
values will depend on the adjustable penalty coefficient λ. We will tune λ to maximize
the accuracy.
Implementation Guide
Constants γ = 0.8 Rmax = maxi
|Rtrue(si)|
CVXOPT options
from cvxopt import s o l v e r s
s o l v e r s . o p ti o n s . update ({ ’ a b s t o l ’ : 1 e−7,
’ r e l t o l ’ : 1 e −6,
’ f e a s t o l ’ : 1 e −7,
’ s ho w p rog r e s s ’ : Fal s e })
Question 11: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ.
For each value of λ compute OA(s) by following the process described above. For this
problem, use the optimal policy of the agent found in question 5 to fill in the OE(s)
values. Then use equation 3 to compute the accuracy of the IRL algorithm for this
value of λ. You need to repeat the above process for all 500 values of λ to get 500 data
points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot.
Question 12: (5 points) Use the plot in question 11 to compute the value of λ for which
accuracy is maximum. For future reference we will denote this value as λ
(1)
max. Please
report λ
(1)
max
Question 13: (15 points) For λ
(1)
max, generate heat maps of the ground truth reward and
the extracted reward. Please note that the ground truth reward is the Reward function
1 and the extracted reward is computed by solving the linear program given by equation
2 with the λ parameter set to λ
(1)
max. In this question, you should have 2 plots.
Question 14: (10 points) Use the extracted reward function computed in question 13,
to compute the optimal values of the states in the 2-D grid. For computing the optimal
values you need to use the optimal state-value function that you wrote in question 2. For
visualization purpose, generate a heat map of the optimal state values across the 2-D grid
(similar to the figure generated in question 3). In this question, you should have 1 plot.
12
Question 15: (10 points) Compare the heat maps of Question 3 and Question 14 and
provide a brief explanation on their similarities and differences.
Question 16: (10 points) Use the extracted reward function found in question 13 to
compute the optimal policy of the agent. For computing the optimal policy of the agent
you need to use the function that you wrote in question 5. For visualization purpose, you
should generate a figure similar to that of figure 1 but with the number of state replaced
by the optimal action at that state. The actions should be displayed using arrows. In
this question, you should have 1 plot.
Question 17: (10 points) Compare the figures of Question 5 and Question 16 and provide
a brief explanation on their similarities and differences.
Question 18: (30 points) Sweep λ from 0 to 5 to get 500 evenly spaced values for λ.
For each value of λ compute OA(s) by following the process described above. For this
problem, use the optimal policy of the agent found in question 8 to fill in the OE(s)
values. Then use equation 3 to compute the accuracy of the IRL algorithm for this
value of λ. You need to repeat the above process for all 500 values of λ to get 500 data
points. Plot λ (x-axis) against Accuracy (y-axis). In this question, you should have 1 plot.
Question 19: (5 points) Use the plot in question 18 to compute the value of λ for which
accuracy is maximum. For future reference we will denote this value as λ
(2)
max. Please
report λ
(2)
max
Question 20: (15 points) For λ
(2)
max, generate heat maps of the ground truth reward and
the extracted reward. Please note that the ground truth reward is the Reward function
2 and the extracted reward is computed by solving the linear program given by equation
2 with the λ parameter set to λ
(2)
max. In this question, you should have 2 plots.
Question 21: (10 points) Use the extracted reward function computed in question 20,
to compute the optimal values of the states in the 2-D grid. For computing the optimal
values you need to use the optimal state-value function that you wrote in question 2. For
visualization purpose, generate a heat map of the optimal state values across the 2-D grid
(similar to the figure generated in question 7). In this question, you should have 1 plot.
Question 22: (10 points) Compare the heat maps of Question 7 and Question 21 and
provide a brief explanation on their similarities and differences.
Question 23: (10 points) Use the extracted reward function found in question 20 to
compute the optimal policy of the agent. For computing the optimal policy of the agent
you need to use the function that you wrote in question 9. For visualization purpose, you
should generate a figure similar to that of figure 1 but with the number of state replaced
by the optimal action at that state. The actions should be displayed using arrows. In
this question, you should have 1 plot.
Question 24: (10 points) Compare the figures of Question 9 and Question 23 and provide
a brief explanation on their similarities and differences.
13
Question 25: (50 points) From the figure in question 23, you should observe that the
optimal policy of the agent has two major discrepancies. Please identify and provide the
causes for these two discrepancies. One of the discrepancy can be fixed easily by a slight
modification to the value iteration algorithm. Perform this modification and re-run the
modified value iteration algorithm to compute the optimal policy of the agent. Also,
recompute the maximum accuracy after this modification. Is there a change in maximum
accuracy? The second discrepancy is harder to fix and is a limitation of the simple IRL
algorithm.
5 Submission
Please submit your report to Gradescope. Also submit a zip file containing your codes and report to bruinlearn. The zip file should be named as
“Project3 UID1 … UIDn.zip” where UIDx are student ID numbers of team
members.
References
ECE 232E Summer 2025 Project 4 Graph Algorithms
Introduction
In this project we will explore graph theory theorems and algorithms, by applying them on
real data. In the first part of the project, we consider a particular graph modeling correlations
between stock price time series. In the second part, we analyse traffic data on a dataset provided
by Uber.
1. Stock Market
In this part of the project, we study data from stock market. The data is available on this
Dropbox Link. The goal of this part is to study correlation structures among fluctuation
patterns of stock prices using tools from graph theory. The intuition is that investors will
have similar strategies of investment for stocks that are effected by the same economic factors.
For example, the stocks belonging to the transportation sector may have different absolute
prices, but if for example fuel prices change or are expected to change significantly in the near
future, then you would expect the investors to buy or sell all stocks similarly and maximize
their returns. Towards that goal, we construct different graphs based on similarities among the
time series of returns on different stocks at different time scales (day vs a week). Then, we
study properties of such graphs. The data is obtained from Yahoo Finance website for 3 years.
You’re provided with a number of csv tables, each containing several fields: Date, Open, High,
Low, Close, Volume, and Adj Close price. The files are named according to Ticker Symbol
of each stock. You may find the market sector for each company in Name sector.csv. We
recommend doing this part of the project (Q1 – Q8) in R.
1. Return correlation
In this part of the project, we will compute the correlation among log-normalized stock-return
time series data. Before giving the expression for correlation, we introduce the following notation:
• pi(t) is the closing price of stock i at the t
th day
• qi(t) is the return of stock i over a period of [t − 1, t]
qi(t) = pi(t) − pi(t − 1)
pi(t − 1)
1
• ri(t) is the log-normalized return stock i over a period of [t − 1, t]
ri(t) = log(1 + qi(t))
Then with the above notation, we define the correlation between the log-normalized stock-return
time series data of stocks i and j as
ρij =
⟨ri(t)rj (t)⟩ − ⟨ri(t)⟩⟨rj (t)⟩
p
(⟨ri(t)
2⟩ − ⟨ri(t)⟩
2
)(⟨rj (t)
2⟩ − ⟨rj (t)⟩
2
)
where ⟨·⟩ is a temporal average on the investigated time regime (for our data set it is over 3
years).
QUESTION 1: What are upper and lower bounds on ρij? Provide a justification for using lognormalized return (ri(t)) instead of regular return (qi(t)).
2. Constructing correlation graphs
In this part,we construct a correlation graph using the correlation coefficient computed in the
previous section. The correlation graph has the stocks as the nodes and the edge weights are
given by the following expression
wij =
q
2(1 − ρij )
Compute the edge weights using the above expression and construct the correlation graph.
QUESTION 2: Plot a histogram showing the un-normalized distribution of edge weights.
3. Minimum spanning tree (MST)
In this part of the project, we will extract the MST of the correlation graph and interpret it.
QUESTION 3: Extract the MST of the correlation graph. Each stock can be categorized into
a sector, which can be found in Name sector.csv file. Plot the MST and color-code the nodes
based on sectors. Do you see any pattern in the MST? The structures that you find in MST are
called Vine clusters. Provide a detailed explanation about the pattern you observe.
QUESTION 4: Run a community detection algorithm (for example walktrap) on the MST obtained above. Plot the communities formed. Compute the homogeneity and completeness of the
clustering. (you can use the ’clevr’ library in r to compute homogeneity and completeness).
4. Sector clustering in MST’s
In this part, we want to predict the market sector of an unknown stock. We will explore two
methods for performing the task. In order to evaluate the performance of the methods we
define the following metric
α =
1
|V |
X
vi∈V
P(vi ∈ Si)
2
where Si
is the sector of node i. Define
P(vi ∈ Si) = |Qi
|
|Ni
|
where Qi
is the set of neighbors of node i that belong to the same sector as node i and Ni
is
the set of neighbors of node i. Compare α with the case where
P(vi ∈ Si) = |Si
|
|V |
QUESTION 5: Report the value of α for the above two cases and provide an interpretation for
the difference.
5. Correlation graphs for weekly data
In the previous parts, we constructed the correlation graph based on daily data. In this part
of the project, we will construct a correlation graph based on WEEKLY data. To create the
graph, sample the stock data weekly on Mondays and then calculate ρij using the sampled
data. If there is a holiday on a Monday, we ignore that week. Create the correlation graph
based on weekly data.
QUESTION 6: Repeat questions 2,3,4,5 on the WEEKLY data.
6. Correlation graphs for MONTHLY data
In this part of the project, we will construct a correlation graph based on MONTHLY data.
To create the graph, sample the stock data Monthly on 15th and then calculate ρij using the
sampled data. If there is a holiday on the 15th, we ignore that month. Create the correlation
graph based on MONTHLY data.
QUESTION 7: Repeat questions 2,3,4,5 on the MONTHLY data.
QUESTION 8: Compare and analyze all the results of daily data vs weekly data vs monthly data.
What trends do you find? What changes? What remains similar? Give reason for your observations.
Which granularity gives the best results when predicting the sector of an unknown stock and why?
2. Let’s Help Santa!
Companies like Google and Uber have a vast amount of statistics about transportation dynamics. Santa has decided to use network theory to facilitate his gift delivery for the next
Christmas. When we learned about his decision, we designed this part of the project to help
him. We will send him your results for this part!
1. Download the Data
Normally we use the last winter data but this year the latest available data is Winter 2019. Go
to “Uber Movement” website and download data of Travel Times by Month (All Days),
3
2019 Quarter 4, for Los Angeles area1
. The dataset contains pairwise traveling time statistics
between most pairs of points in the Los Angeles area. Points on the map are represented by
unique IDs. To understand the correspondence between map IDs and areas, download Geo
Boundaries file from the same website2
. This file contains latitudes and longitudes of the
corners of the polygons circumscribing each area. To be specific, if an area is represented by a
polygon with 5 corners, then you have a 5 × 2 matrix of the latitudes and longitudes, each row
of which represents latitude and longitude of one corner. We recommend doing this part
of the project (Q9 – Q18) in Python.
2. Build Your Graph
Read the dataset at hand, and build a graph in which nodes correspond to locations, and
undirected weighted edges correspond to the mean traveling times between each pair of locations
(only December). Add the centroid coordinates of each polygon region (a 2-D vector) as an
attribute to the corresponding vertex.
The graph will contain some isolated nodes (extra nodes existing in the Geo Boundaries JSON
file) and a few small connected components. Remove such nodes and just keep the largest
connected component of the graph. In addition, merge duplicate edges by averaging their
weights 3
. We will refer to this cleaned graph as G afterwards.
QUESTION 9: Report the number of nodes and edges in G.
3. Traveling Salesman Problem
QUESTION 10: Build a minimum spanning tree (MST) of graph G. Report the street addresses
near the two endpoints (the centroid locations) of a few edges. Are the results intuitive?
QUESTION 11: Determine what percentage of triangles in the graph (sets of 3 points on the
map) satisfy the triangle inequality. You do not need to inspect all triangles, you can just estimate
by random sampling of 1000 triangles.
Now, we want to find an approximation solution for the traveling salesman problem (TSP) on
G. Apply the 1-approximate algorithm described in the class4
. Inspect the sequence of street
addresses visited on the map and see if the results are intuitive.
QUESTION 12: Find an upper bound on the empirical performance of the approximate algorithm:
ρ =
Approximate TSP Cost
Optimal TSP Cost
QUESTION 13: Plot the trajectory that Santa has to travel!
1
If you download the dataset correctly, it should be named as
los angeles-censustracts-2019-4-All-MonthlyAggregate.csv
2The file should be named los angeles censustracts.json
3Duplicate edges may exist when the dataset provides you with the statistic of a road in both directions. We remove
duplicate edges for the sake of simplicity.
4You can find the algorithm in: Papadimitriou and Steiglitz, “Combinatorial optimization: algorithms and complexity”, Chapter 17, page 414
4
4. Analysing Traffic Flow
Next December, there is going to be a large group of visitors travelling between a location near
Malibu to a location near Long Beach. We would like to analyse the maximum traffic that can
flow between the two locations.
5. Estimate the Roads
We want to estimate the map of roads without using actual road datasets. Educate yourself
about Delaunay triangulation algorithm and then apply it to the nodes coordinates5
.
QUESTION 14: Plot the road mesh that you obtain and explain the result. Create a graph G∆
whose nodes are different locations and its edges are produced by triangulation.
6. Calculate Road Traffic Flows
QUESTION 15: Using simple math, calculate the traffic flow for each road in terms of cars/hour.
Report your derivation.
Hint: Consider the following assumptions:
• Each degree of latitude and longitude ≈ 69 miles
• Car length ≈ 5 m = 0.003 mile
• Cars maintain a safety distance of 2 seconds to the next car
• Each road has 2 lanes in each direction
Assuming no traffic jam, consider the calculated traffic flow as the max capacity of each road.
7. Calculate Max Flow
Consider the following locations in terms of latitude and longitude:
• Source coordinates (in Malibu): [34.04, -118.56]
• Destination coordinates (in Long Beach): [33.77, -118.18]
QUESTION 16: Calculate the maximum number of cars that can commute per hour from Malibu
to Long Beach. Also calculate the number of edge-disjoint paths between the two spots. Does the
number of edge-disjoint paths match what you see on your road map?
5You can use scipy.spatial.Delaunay in Python, or RTriangle package in R.
5
8. Prune Your Graph
In G∆, there are a number of unreal roads that could be removed. For instance, you might
notice some unreal links along the concavities of the beach, as well as in the hills of Topanga.
Apply a threshold on the travel time of the roads in G∆ to remove the fake edges. Call the
resulting graph G˜∆.
QUESTION 17: Plot G˜∆ on actual coordinates. Do you think the thresholding method worked?
QUESTION 18: Now, repeat question 13 for G˜∆ and report the results. Do you see any changes?
Why?
Submission
Please submit your report to Gradescope. In addition, please submit a zip file
containing your codes and report to BruinLearn. The zip file should be named
as “Project4 UID1 … UIDn.zip” where UIDx are student ID numbers of team
members. If you have any questions you can post on piazza.
