Programming Assignment # 4 Recommending friends on social networks Solution

Description

• Introduction

One of the main functionalities o ered by online social platforms such as Facebook and Twitter is the recommendation of new friends. This is achieved by utilizing various information about the users, but the main factor used for recommending a new friend to a user is how well these two users are connected. A social network such as Facebook can be represented as undirected graph such as the one shown in Figure 1. We can use the information contained in the graph to select the top candidate friends for a given user. There are many ways to do this, but we will focus on two methods:

1. Popular users: In this method, we recommend the most popular users in the graph, that is nodes with the highest degrees (number of neighbors).

Example 1. If we want to recommend 4 new friends for user 3 using the popular users method, we recommend:

1. 1. User 8, which has degree 7.

1. 2. User 12, which has degree 5.

1. 3. User 4, which has degree 3.

1. 4. User 6, which has degree 3 (we break ties according to user ID).

2. Common neighbors: In this method, we recommend users who have the most common friends with the user.

Example 2. If we want to recommend 4 new friends for user 3 using the common neigh-bors method, we recommend:

1. 1. User 4, which has 2 common neighbors with 3, nodes 1 and 5.

1. 2. User 6, which has 2 common neighbors with 3, nodes 2 and 5.

1. 3. User 12, which has 1 common neighbor with 3, node 1.

1. 4. User 8, which has 0 common neighbors with 3 (we break ties according to user ID).

2

3

2.2 Implementing a map	3

p u b l i c i n t e r f a c e Map < K extends Comparable <K > , T > {

// Return the size of the map .

i n t size () ;

• Return true if the map is full . boolean full () ;

• Remove all elements from the map . void clear () ;

• Update the data of the key k if it exists and return true . If k does

not exist , the method returns false .

boolean update ( K k , T e ) ;

// Search for element with key k and returns a pair c o n t a i n i n g true and its data if it exists . If k does not exist , the method returns

false and null .

Pair < Boolean , T > retrieve ( K k ) ;

• Insert a new element if does not exist and return true . If k already exists , return false .

boolean insert ( K k , T e ) ;

// Remove the element with key k if it exists and return true . If the element does not exist return false .

boolean remove ( K k ) ;

• Return the list of keys in i n c r e a s i n g order . List <K > getKeys () ;

}

Notice that this interface does not have a current element. Write the class BSTMap that imple-ments the interface Map:

p u b l i c c l a s s BSTMap < K	extends	Comparable <K > ,	T > implements Map <K , T > {
p u b l i c BSTNode <K , T >	root ;	// Do not change	this
…
p u b l i c BSTMap () {
…
}
}

The interface List is de ned as follows:

p u b l i c	i n t e r f a c e List <T > {
boolean		empty () ;
boolean		full () ;
void	fi nd Fi rs t () ;
void	findNext () ;
boolean		last () ;
T retrieve () ;
void	update ( T e ) ;
void	insert ( T e ) ;

4

void remove () ;

// Return the number of elements in the list .

i n t size () ;

• Searches for e in the list . Current must not change . boolean exists ( T e ) ;

}

• Representing the social network

To represent the friendship graph, we use the following interface:

p u b l i c i n t e r f a c e Graph < K extends Comparable <K > > {

• Add a node to the graph if it does not exist and return true . If the node already exists , return false .

boolean addNode ( K i ) ;

• Check if i is a node boolean isNode ( K i ) ;

// Add an edge to the graph if it does not exist and return true . If i

or j do not exist or the edge (i , j ) already exists , return false .

boolean addEdge ( K i , K j ) ;

• Check if (i , j ) is an edge . boolean isEdge ( K i , K j ) ;

• Return the set of ne ig hb or s of node i . If i does not exist , the method returns null .

List <K > neighb ( K i ) ;

// Return the degree ( the number of ne ig hb or s ) of node i . If i does not exist , the method returns -1.

i n t deg ( K i ) ;

• Return a list c o n t a i n i n g the nodes in i n c r e a s i n g order . List <K > getNodes () ;

}

We will use adjacency list representation, but instead of an array of lists, we use a map of lists. Each list in the map represents the neighbors of a node. Write the class MGraph that implements the interface Graph using this representation:

p u b l i c c l a s s MGraph < K extends	Comparable <K > > implements Graph <K > {
p u b l i c Map <K , List <K > > adj ;	// Do not change this
p u b l i c MGraph () {
…
}
…
}

5

• The friends recommender

Write the class Recommender that implements the two friends recommendation methods discussed above:

import java . io . File ;

import java . util . Scanner ;

p u b l i c c l a s s R e c o m m e n d e r {

// Return the top k r e c o m m e n d e d friends for user i using the popular nodes method . If i does not exist , return null . In case of a tie ,

users with the lowest id are selected .

p u b l i c s t a t i c <K extends Comparable <K > > PQK < Double , K > r e c o m m e n d P o p (

Graph <K > g , K i , i n t k ) {

return n u l l ;

}

// Return the top k r e c o m m e n d e d friends for user i using common

ne ig hb or s method . If i does not exist , return null . In case of a tie

, users with the lowest id are selected .

p u b l i c s t a t i c <K extends Comparable <K > > PQK < Double , K > r e c o m m e n d C N (

Graph <K > g , K i , i n t k ) {

return n u l l ;

}

}

• Deliverable and rules

You must deliver:

1. Source code submission to Web-CAT. You have to upload the following classes (and any other classes you need)in a zipped le:

PQKImp.java BSTMap.java MGraph.java

Recommender.java

Notice that you should not upload the interfaces and classes given to you.

The submission deadline is:

You have to read and follow the following rules:

1. The speci cation given in the assignment (class and interface names, and method signatures) must not be modi ed. Any change to the speci cation results in compilation errors and consequently the mark zero.

2. All data structures used in this assignment must be implemented by the student. The use of Java collections or any other data structures library is strictly forbidden.

3. This assignment is an individual assignment. Sharing code with other students will result in harsh penalties.

6

4. Posting the code of the assignment or a link to it on public servers, social platforms or any communication media including but not limited to Facebook, Twitter or WhatsApp will result in disciplinary measures against any involved parties.

4. The submitted software will be evaluated automatically using Web-Cat.

4. All submitted code will be automatically checked for similarity, and if plagiarism is con-rmed penalties will apply.

4. You may be selected for discussing your code with an examiner at the discretion of the teaching team. If the examiner concludes plagiarism has taken place, penalties will apply.

CSC 212 PA # 4