首页 >
> 详细

CS 506 Spring 2020 - HW3

Social Networks and Recommendation Systems

Due date: April 27, 2020

1 Background

In this homework, you will try to recommend new collaborations to researchers

of the Machine Learning community. Our approach will follow the guidelines of

collaborative filtering: “If your past behavior/preferences were similar to some

other user’s, your future behavior may be as well”. As an example, imagine you

like Rolling Stones, Beatles and Jimmy Hendrix. It turns out that most people

that like the aforementioned artists, are also fans of Eric Clapton. Then, it is

very likely that if you listen to Eric Clapton’s music, you will like it as well.

In this assignment you will implement a collaborative filtering recommendation

system for suggesting new collaborations to Machine Learning researchers.

A network as a graph: A graph or network represents relationships among

different entities (users of a social network, researchers, products, etc.). Those

entities are represented as nodes and the relationships between them (friends

on Facebook, co-authors of a research paper, products purchased together) as

edges. When there is an edge between two nodes, x and y, we say that y is a

neighbor (or friend) of x (and also - as the graphs we consider are undirected -

x is also a neighbor of y).

Representing a graph in Python: A widely used library in Python, for

representing graphs is NetworkX. You can read the documentation for more

information on how to use this library.

2 Recommend new collaborations - The ML Community

case

In order to provide new collaborations and test the efficiency of the methods

used, you are given two files (you can find them on piazza):

1

• ”old edges.txt”: In this file, every line contains the names of two researchers

that have co-authored a paper in one of the top Machine Learning

conferences (NeurIPS, ICLR, ICML) between 2010 and 2016.

• ”new edges.txt”: In this file, every line contains the names of two researchers

(from those existing in the above file) that formed a new (nonexisting

before) collaboration, in either 2017 and 2018.

With the first file in hand, you will answer the following question:

”For author X, list some non-collaborators in order, starting with the best collaborator

recommendation and ending with the worst”. A non-friend is a user

who is not X and is not a collaborator of X. Depending on the recommendation

algorithm you are going to choose, the list may include all non-collaborators or

some of them.

Then, using the second file, with actual new collaborations formed in the

next 3 years, you will test the efficiency of these algorithms.

3 Tasks

a) [3 pts.] Write a function that reads the file “old edges.txt” and create a

graph using NetworkX.

b) [3 pts.] Write a function that reads the file “new edges.txt” and for each

author, keeps track of the new collaborations this user formed during

2017-2018.

In 2017 and 2018, there were 1,757 new edges formed between existing authors.

For the next tasks, pick (and recommend new collaborations for) those

authors that formed at least 10 new connections between 2017-2018. In the

remaining, when we talk about author X, we refer to one of those authors.

c) [5 pts.] Recommend by number of common friends

if non-friend Y is your friend’s friend, then maybe Y should be your friend

too. If person Y is the friend of many of your friends, then Y is an even

better recommendation.

Write a function common friends number(G, X) that given G and an author

X, returns a list of recommendations for X. The authors in this list are sorted

by the number of common neighbors they have with X (and are not of course

already friends with X). If there are ties, you can break them arbitrarily.

2

d) [5 pts.] Make recommendations using Jaccard’s Index

If Γ(X) is the set of neighbors of X, then the metric we used in part (c),

assigns to a non-friend y, the following recommendation score (with respect

to X): score(y) = |Γ(X)∩Γ(y)|. Jaccard’s Index scales this score by

taking into account the union of X and Y ’s neighbors. Intuitively, X and

Y are more similar, if what they have in common is as close as possible to

what they have together.

Write a function jaccard index(G, X) that given G and an author X, returns a

list of recommendations for X. The authors in this list are sorted by the number

of their Jaccard Index with respect to X (and are not of course already friends

with X). If there are ties, you can break them arbitrarily.

Jaccard Index = |Γ(X)∩Γ(y)|

|Γ(X)∪Γ(y)|

e) [5 pts.] Make recommendations using Adamic/Adar Index

For part (c), we made recommendations using common neighbors. However,

when assigning a score to Y , instead of just taking a count of the

number of common neighbors, we take a weighted sum of them, where the

weight of each common neighbor of X and Y , call her Z, is the inverse of

the logarithm of the number of Z’s neighbors. In that way, we value more

common neighbors that are more selective.

Write a function adamic adar index(G, X) that given G and an author X,

returns a list of recommendations for X. The authors in this list are sorted

by the number of their Adamic/Adar Index with respect to X (and are not of

course already friends with X). If there are ties, you can break them arbitrarily.

Adamic/Adar Index (y)= P

Z∈Γ(X)∩Γ(y)

log|Γ(Z)|

f) [4 pts.] How good are the recommendations we make?

Previously, you implemented 3 functions, that given a user X provide

recommendations for this user. In this task, you will check how good

these recommendations are using the actual new connections formed during

2017-2018.

You will use two different ways, to calculate the efficiency of every approach:

– For each user X, take the 10 first recommendations for this user,

and calculate the number of them that were actually formed during

2017-2018. You should report the average among users X.

– For each newly formed collaboration of user X, calculate the rank

of this collaboration (the index where this new node Y appears in

the recommendations list for X). Report the average among newly

formed edges.

e) [Bonus Question] [2 pts.]

Doing some literature search, suggest your own algorithm for recommend-

ing new links to a user X. Argue about the choice you make, why it makes

sense to suggest users that way? How is the efficiency of this algorithm,

compared to the ones you implemented in parts (c), (d) and (e)?

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 代写cmpt 214编程、代做programming语言、代写c/C++程序 2020-11-08
- 代写csci 2122课程、代做program编程实验、C++程序语言代写代 2020-11-08
- Fit5032语言编程代做、代写web程序实验、Web、Html程序语言代做 2020-11-08
- Com3503程序编程代做、Java，C++，Python留学生编程代写代写 2020-11-08
- 代写program程序课程、代写c++编程实验、C/C++编程语言代做 代做 2020-11-08
- Data留学生编程代做、代写python程序、Java，C++程序语言代写 2020-11-08
- 代写secj 1023实验编程、Programming程序代做、代写c++语 2020-11-08
- 代写cmpsc 465编程、代做java程序语言、Python，C++编程设 2020-11-07
- 代做mf 703语言编程、代写programming程序、Sql编程语言调试 2020-11-07
- 954246编程设计调试、代做programming程序、C++编程语言代写 2020-11-07
- Pstat 115程序实验代写、R编程语言调试、Data留学生程序代做 代写 2020-11-07
- Com1005课程编程代做、代写python程序、Java，C++程序语言调 2020-11-07
- Tcp留学生程序代写、Java程序设计调试、Java编程语言代写 帮做r语言 2020-11-07
- 代写program语言编程、代做data留学生程序、Python，Java编 2020-11-07
- 代做cosc2666编程、代写programming程序、C/C++程序语言 2020-11-07
- Digital编程设计代写、代做r程序实验、代写r留学生程序 调试matla 2020-11-07
- 代写programming程序实验、R程序语言调试、Data课程编程代做 代 2020-11-07
- Comp104-17B程序代写、代做c++编程实验、C++程序语言调试 帮做 2020-11-07
- Csc8501课程程序代做、C++编程语言调试、代写program编程课程 2020-11-07
- 代写css3留学生程序、代做html、Css编程语言、Data课程程序代做 2020-11-07