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.