Assignment 3: Recommendation systems
Submit only main.cpp via LMS
When you sign into Facebook, it suggests friends. In this assignment, you will write a
program that reads Facebook data and makes friend recommendations.
Background: Recommendation systems
Facebook suggests people you may be (or should be) friends with. Netflix suggests
movies you might like. Amazon suggests products to buy. How do they do that? In this
assignment, you will learn one simple way to make such suggestions, called
“collaborative filtering”. The actual algorithms used by these companies are closely
guarded trade secrets.
A computer system that makes suggestions is called a recommender system. As
background, there are two general approaches: collaborative filtering and content-
based filtering.
• Collaborative filtering says that, if your past behavior/preferences were similar
to some other user’s, then your future behavior may be as well. As a concrete
example, suppose that you like John, Paul, and George, and other people like
John, Paul, George, and Ringo. Then it stands to reason that you will like Ringo
as well, even if you had never previously heard of him. The recommender
system does not have to understand anything about what “John”, “Paul”,
“George”, and “Ringo” are — they could even be brands of toilet paper, and the
algorithm would work identically.
• Content-based filtering considers the characteristics of the things you like, and
it recommends similar sorts of things. For instance, if you like “Billie Jean”,
“Crazy Train”, and “Don’t Stop the Music”, then you might like other songs in the
key of F-sharp minor, such as Rachmaninoff’s “Piano Concerto No. 1”, even if no
one else has ever had that particular set of favorite songs before.
In this assignment, you will implement a collaborative filtering recommendation
system for suggesting friends on Facebook.
Representing a social network as a graph
A graph or network represents relationships among things. The things are represented
as nodes
or vertices, and the relationships are represented as edges.
One common use for a graph is to represent travel possibilities, such as on a road map
or airline map. The nodes of the graph are cities, and the edges show which cities are
directly connected. Then, you can use the graph to plan travel.
Another common use for a graph is to represent friendship among people in a social
network. For example, here is the friendship graph for some of the characters of
“Romeo and Juliet”:
An edge between person A and person B means that A considers B a friend, and also B
considers A a friend.
This graph is unable to represent certain information. For example, Count Paris
