2. Suppose we have a social network like Twitter represented by a directed graph. A directed edge (u, v) is present in the graph if person v follows person u on Twitter (think of the edge as representing the flow of information. If y follows u then when u tweets, v receives it). What we're trying to do is determine the most famous follower of everyone in the graph. For instance, your most famous follower would be calculated by determining the most famous person who follows you, or follows one of your followers, or follows one of your follower's followers, etc. You may also assume that a node follows itself by default as a base case. That way even nodes with no followers have a MFF. In simple terms, your most famous follower is the most famous person who would see your tweet if all your followers retweeted your tweet and all your followers followers retweeted it, etc. More formally, suppose every node, u V, has a unique integer fame rank, R(u), in the range 1, 2, ...,V. Think of this rank as representing each user's popularity in terms of how many followers they have. According to Wikipedia, Barack Obama is 1 with 129 million followers, Justin Bieber is 2 with 113 million, Katy Perry is 3 with 109 million. You do not have to calculate the fame rank, just assume each node has a field that contains its unique rank. For each vertex u V, let Follow(u) = {v Vu v} (the notation u ~ v means that there is a path from u to v). This set is composed of u itself, the people who directly follow u, the people who follow the followers of u and so on. Let the most famous follower of a node u be represented by MFF(u) which is equal to the vertex in Follow(u) whose rank is minimum. In other words MFF(u) is the vertex v such that R(u) = min{R(w) | W Follow(u)}. Give a lincar time algorithm to compute MFF(u) for all vertices u E V. Justify the correctness and running time of your solution. Note that I'm defining Follow(u) above in order to explain MFF(u) but the Follow set for each node is not given to you and you cannot compute it in linear time. You must compute MFF(u) for each node directly from the given graph. 2. Suppose we have a social network like Twitter represented by a directed graph. A directed edge (u, v) is present in the graph if person v follows person u on Twitter (think of the edge as representing the flow of information. If y follows u then when u tweets, v receives it). What we're trying to do is determine the most famous follower of everyone in the graph. For instance, your most famous follower would be calculated by determining the most famous person who follows you, or follows one of your followers, or follows one of your follower's followers, etc. You may also assume that a node follows itself by default as a base case. That way even nodes with no followers have a MFF. In simple terms, your most famous follower is the most famous person who would see your tweet if all your followers retweeted your tweet and all your followers followers retweeted it, etc. More formally, suppose every node, u V, has a unique integer fame rank, R(u), in the range 1, 2, ...,V. Think of this rank as representing each user's popularity in terms of how many followers they have. According to Wikipedia, Barack Obama is 1 with 129 million followers, Justin Bieber is 2 with 113 million, Katy Perry is 3 with 109 million. You do not have to calculate the fame rank, just assume each node has a field that contains its unique rank. For each vertex u V, let Follow(u) = {v Vu v} (the notation u ~ v means that there is a path from u to v). This set is composed of u itself, the people who directly follow u, the people who follow the followers of u and so on. Let the most famous follower of a node u be represented by MFF(u) which is equal to the vertex in Follow(u) whose rank is minimum. In other words MFF(u) is the vertex v such that R(u) = min{R(w) | W Follow(u)}. Give a lincar time algorithm to compute MFF(u) for all vertices u E V. Justify the correctness and running time of your solution. Note that I'm defining Follow(u) above in order to explain MFF(u) but the Follow set for each node is not given to you and you cannot compute it in linear time. You must compute MFF(u) for each node directly from the given graph