Problem Name: Facebook Recommendations Problem Description: You can visualize Facebook as a graph where the nodes represent a set of users and the edges between the nodes (as a “friend” connection between you and everyone who you have befriended). Your job is to write a program that automatically computes and suggests a new friend recommendation for a user, given knowledge of the entire network. In other words, for each user, suggest the most probable user to befriend based upon the intersection of your common friends. For example, if Person A is a user on the network, Person A will get a recommendation to add Person B as their friend if Person B has the most friends in common with Person A, but B is currently not friends with Person A. The high-level idea is that for any user, you should A) go through all the other users and calculate the number of friends they have in common. B) Find the user in the social network who they are currently not friends with but have the most friends in common. Intuitively, it makes sense why they might want to be connected as friends. Input Format The first line of the file is an integer representing the number of users in the given network. The following lines are of the form: user_u user_v where user_u and user_v are the IDs of two users who are friends. For example, here is a very small file that has 5 users in the social network: 5 0 1 1 2 1 4 2 3 The above is a representation of a social network that contains 5 users. User ID=0 is friends with User IDs = 1 User ID=1 is friends with User IDs = 0, 2, 4 User ID=2 is friends with User IDs = 1, 3 User ID=3 is friends with User IDs = 2 User ID=4 is friends with User IDs = 1 Approach There are multiple ways to approach this. I would recommend the following After reading in the input file, construct the network using NxN a adjacency matrix F where N is the number of users and ??,?is 1 if user i is friends with user j and 0 otherwise. Keep in mind, friend connections are symmetrical , which means if ??,? is 1 ??,? will also be 1. Next construct a NxN similarity matrix S where N is the number of users and ??,?is the number of common friends between user i and user j. For example, for the small network shown in the input format section, ?1,3 = 1 , since user 1 and user 3 have exactly one friend in common (user id 2) Finally use the 2 matrixes generated above to recommend the user with the most common friends to a particular user. There are some special cases you will need to take care of, when using the above method. Sample Runs You are provided with 2 sample files. The first is a small network with 10 users. The second is an actual dataset obtained from Facebooks Enter file name: small_network_data.txt Finished reading File. Network shown below 0 : [1, 2, 3] 1 : [0, 4, 6, 7, 9] 2 : [0, 3, 6, 8, 9] 3 : [0, 2, 8, 9] 4 : [1, 6, 7, 8] 5 : [9] 6 : [1, 2, 4, 8] 7 : [1, 4, 8] 8 : [2, 3, 4, 6, 7] 9 : [1, 2, 3, 5] Enter user id in the range 0 to 9 (-1 to quit) : 0 The suggested friend for 0 is 9 Enter user id in the range 0 to 9 (-1 to quit) : 3 The suggested friend for 3 is 1 Enter user id in the range 0 to 9 (-1 to quit) : 8 The suggested friend for 8 is 1 Enter user id in the range 0 to 9 (-1 to quit) : abc Error: Invalid Input Enter user id in the range 0 to 9 (-1 to quit) : 15 Error: input must be an int between 0 and 9 Enter user id in the range 0 to 9 (-1 to quit) :-1 Goodbye! Enter file name: facebook_data.txt **Network representation too large to show** Enter user id in the range 0 to 999 (-1 to quit) : 88 The suggested friend for 88 is 213 Enter user id in the range 0 to 999 (-1 to quit) : 20 The suggested friend for 20 is 116 Enter user id in the range 0 to 999 (-1 to quit) : 5 The suggested friend for 5 is 67 Enter user id in the range 0 to 999 (-1 to quit): 5000 Error: input must be an int between 0 and 999 Enter user id in the range 0 to 999 (-1 to quit) :-1 Goodbye! Submission 1. Facebook.py 2. A screenshot of sample output when running on the larger dataset. Guidelines and Constraints You should attempt to use Pythonic ways of writing your solution, when possible, if you have a simple loop, that’s doing just one thing, consider using a list comprehension. For common operations like max, min, count try to use the built-in array methods without implementing your own. Your only constraint is you cannot use anything that has not been explicitly covered in class. This problem should be solved by only using lists, no other data structure or external library should be used.

Problem Name: Facebook Recommendations Problem Description: You can visualize Facebook as a graph where the nodes represent a set of users and the edges between the nodes (as a “friend” connection between you and everyone who you have befriended). Your job is to write a program that automatically computes and suggests a new friend recommendation for a user, given knowledge of the entire network. In other words, for each user, suggest the most probable user to befriend based upon the intersection of your common friends. For example, if Person A is a user on the network, Person A will get a recommendation to add Person B as their friend if Person B has the most friends in common with Person A, but B is currently not friends with Person A. The high-level idea is that for any user, you should A) go through all the other users and calculate the number of friends they have in common. B) Find the user in the social network who they are currently not friends with but have the most friends in common. Intuitively, it makes sense why they might want to be connected as friends. Input Format The first line of the file is an integer representing the number of users in the given network. The following lines are of the form: user_u user_v where user_u and user_v are the IDs of two users who are friends. For example, here is a very small file that has 5 users in the social network: 5 0 1 1 2 1 4 2 3 The above is a representation of a social network that contains 5 users. User ID=0 is friends with User IDs = 1 User ID=1 is friends with User IDs = 0, 2, 4 User ID=2 is friends with User IDs = 1, 3 User ID=3 is friends with User IDs = 2 User ID=4 is friends with User IDs = 1 Approach There are multiple ways to approach this. I would recommend the following After reading in the input file, construct the network using NxN a adjacency matrix F where N is the number of users and ??,?is 1 if user i is friends with user j and 0 otherwise. Keep in mind, friend connections are symmetrical , which means if ??,? is 1 ??,? will also be 1. Next construct a NxN similarity matrix S where N is the number of users and ??,?is the number of common friends between user i and user j. For example, for the small network shown in the input format section, ?1,3 = 1 , since user 1 and user 3 have exactly one friend in common (user id 2) Finally use the 2 matrixes generated above to recommend the user with the most common friends to a particular user. There are some special cases you will need to take care of, when using the above method. Sample Runs You are provided with 2 sample files. The first is a small network with 10 users. The second is an actual dataset obtained from Facebooks Enter file name: small_network_data.txt Finished reading File. Network shown below 0 : [1, 2, 3] 1 : [0, 4, 6, 7, 9] 2 : [0, 3, 6, 8, 9] 3 : [0, 2, 8, 9] 4 : [1, 6, 7, 8] 5 : [9] 6 : [1, 2, 4, 8] 7 : [1, 4, 8] 8 : [2, 3, 4, 6, 7] 9 : [1, 2, 3, 5] Enter user id in the range 0 to 9 (-1 to quit) : 0 The suggested friend for 0 is 9 Enter user id in the range 0 to 9 (-1 to quit) : 3 The suggested friend for 3 is 1 Enter user id in the range 0 to 9 (-1 to quit) : 8 The suggested friend for 8 is 1 Enter user id in the range 0 to 9 (-1 to quit) : abc Error: Invalid Input Enter user id in the range 0 to 9 (-1 to quit) : 15 Error: input must be an int between 0 and 9 Enter user id in the range 0 to 9 (-1 to quit) :-1 Goodbye! Enter file name: facebook_data.txt Network representation too large to show Enter user id in the range 0 to 999 (-1 to quit) : 88 The suggested friend for 88 is 213 Enter user id in the range 0 to 999 (-1 to quit) : 20 The suggested friend for 20 is 116 Enter user id in the range 0 to 999 (-1 to quit) : 5 The suggested friend for 5 is 67 Enter user id in the range 0 to 999 (-1 to quit): 5000 Error: input must be an int between 0 and 999 Enter user id in the range 0 to 999 (-1 to quit) :-1 Goodbye! Submission 1. Facebook.py 2. A screenshot of sample output when running on the larger dataset. Guidelines and Constraints You should attempt to use Pythonic ways of writing your solution, when possible, if you have a simple loop, that’s doing just one thing, consider using a list comprehension. For common operations like max, min, count try to use the built-in array methods without implementing your own. Your only constraint is you cannot use anything that has not been explicitly covered in class. This problem should be solved by only using lists, no other data structure or external library should be used.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Approach
There are multiple ways to approach this. I would recommend the following
After reading in the input file, construct the network using NxN a adjacency matrix F where N is the
number of users and ??,?is 1 if user i is friends with user j and 0 otherwise. Keep in mind, friend
connections are symmetrical , which means if ??,? is 1 ??,? will also be 1.
Next construct a NxN similarity matrix S where N is the number of users and ??,?is the number of
common friends between user i and user j. For example, for the small network shown in the input
format section, ?1,3 = 1 , since user 1 and user 3 have exactly one friend in common (user id 2)
Finally use the 2 matrixes generated above to recommend the user with the most common friends to a
particular user. There are some special cases you will need to take care of, when using the above
method.
Sample Runs
You are provided with 2 sample files. The first is a small network with 10 users. The second is an actual
dataset obtained from Facebooks
Enter file name: small_network_data.txt
Finished reading File.
Network shown below
0 : [1, 2, 3]
1 : [0, 4, 6, 7, 9]
2 : [0, 3, 6, 8, 9]
3 : [0, 2, 8, 9]
4 : [1, 6, 7, 8]
5 : [9]
6 : [1, 2, 4, 8]
7 : [1, 4, 8]
8 : [2, 3, 4, 6, 7]
9 : [1, 2, 3, 5]
Enter user id in the range 0 to 9 (-1 to quit) : 0
The suggested friend for 0 is 9
Enter user id in the range 0 to 9 (-1 to quit) : 3
The suggested friend for 3 is 1
Enter user id in the range 0 to 9 (-1 to quit) : 8
The suggested friend for 8 is 1
Enter user id in the range 0 to 9 (-1 to quit) : abc

Error: Invalid Input
Enter user id in the range 0 to 9 (-1 to quit) : 15
Error: input must be an int between 0 and 9
Enter user id in the range 0 to 9 (-1 to quit) :-1
Goodbye!
Enter file name: facebook_data.txt
**Network representation too large to show**
Enter user id in the range 0 to 999 (-1 to quit) : 88
The suggested friend for 88 is 213
Enter user id in the range 0 to 999 (-1 to quit) : 20
The suggested friend for 20 is 116
Enter user id in the range 0 to 999 (-1 to quit) : 5
The suggested friend for 5 is 67
Enter user id in the range 0 to 999 (-1 to quit): 5000
Error: input must be an int between 0 and 999
Enter user id in the range 0 to 999 (-1 to quit) :-1
Goodbye!
Submission
1. Facebook.py
2. A screenshot of sample output when running on the larger dataset.
Guidelines and Constraints
You should attempt to use Pythonic ways of writing your solution, when possible, if you
have a simple loop, that’s doing just one thing, consider using a list comprehension. For
common operations like max, min, count try to use the built-in array methods without
implementing your own. Your only constraint is you cannot use anything that has not
been explicitly covered in class. This problem should be solved by only using lists,
no other data structure or external library should be used.

Expert Solution

Step 1: Algorithm

Read Network Data:
- Read the input filename from the user.
- Read the network data from the file and construct the network using an adjacency list.
Calculate Similarity Matrix:
- Calculate the similarity matrix that stores the number of common friends between users.
Recommend Friend:
- For each user, calculate the potential friend with the most common friends that the user is not already friends with.
Main Procedure (main):
- Display the network data and user interface.
- Prompt the user for a user ID to recommend a friend for.
- Recommend a friend based on common friends.
- Handle invalid inputs and quitting the program.
Entry Point (__name__ == "__main__"):
- Read the network data.
- Calculate the similarity matrix.
- Display the network data.
- Execute the main procedure to interact with the user and recommend friends.

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.