[Solved] INF553 Assignment 4-Girvan- Newman algorithm

In this assignment, you will s implement your own Girvan- Newman algorithm using the Spark Framework to detect communities in graphs. You will use the ub_sample_data.csv dataset to find users who have a similar business taste. The goal of this assignment is to help you understand how to use the Girvan-Newman algorithm to detect communities in an efficient way within a distributed environment.

2. Requirements

2.1 Programming Requirements

1. You must use Python to implement all tasks. There will be 10% bonus for each task if you also submit a Scala implementation and both your Python and Scala implementations are correct.

1. You can ONLY use Spark RDD and standard Python or Scala libraries.
   • Programming Environment

Python 3.6, Scala 2.11 and Spark 2.3.3

We will use these library versions to compile and test your code. There will be a 20% penalty if we cannot run your code due to the library version inconsistency.

• Write your own code

Do not share code with other students!!

For this assignment to be an effective learning experience, you must write your own code! We emphasize this point because you will be able to find Python implementations of some of the required functions on the web. Please do not look for or at any such code!

TAs will combine all the code we can find from the web (e.g., Github) as well as other students code from this and other (previous) sections for plagiarism detection. We will report all detected plagiarism.

• What you need to turn in

Your submission must be a zip file with the name convention: firstname_lastname_hw4.zip (all lowercase,

e.g., junyu_liu_hw4.zip). You should pack the following required (and optional) files in the zip file (see Figure 1):

1. [REQUIRED] one Python scripts, named: (all lowercase) firstname_lastname_task1.py b1. [OPTIONAL] one Scala scripts, named: (all lowercase) firstname_lastname_task1.scala b2. [OPTIONAL] one jar package, named: (all lowercase) firstname_lastname_hw4.jar

1. [OPTIONAL] You can include other scripts to support your programs and also name it with the prefix:

firstname_lastname_ (e.g. junyu_liu_Graph.py)

1. You dont need to include your results. We will grade on your code with our testing data (data will be in the same format).

Figure 1: Submission Structure

3. Datasets

You will continue to use Yelp dataset. We have generated a sub-dataset, sample_data.csv, from the Yelp review dataset containing user_id and business_id. You can download it from Blackboard.

4. Tasks

4.1Graph Construction

To construct the social network graph, each node represents a user and there will be an edge between two nodes if the number of times that two users review the same business is greater than or equivalent to the filter threshold. For example, suppose user1 reviewed [business1, business2, business3] and user2 reviewed [business2, business3, business4, business5]. If the threshold is 2, there will be an edge between user1 and user2.

If the user node has no edge, we will not include that node in the graph.

NOTICE: In this assignment, the filter threshold is 7.

4.2Task1: Community Detection Based on Girvan-Newman algorithm (12.5 pts)

In, you will implement your own Girvan-Newman algorithm to detect the communities in the network graph. You can refer to the Chapter 10 from the Mining of Massive Datasets book for the algorithm details.

For this homework, you can ONLY use Spark RDD and standard Python or Scala libraries.

4.2.1Betweenness Calculation (6 pts)

In this part, you will calculate the betweenness of each edge in the original graph.

Then you need to save your result in a txt file. The format of each line is

(user_id1, user_id2), betweenness value

Your result should be firstly sorted by the betweenness values in the descending order and then the first

user_id in the tuple in lexicographical order (the user_id is type of string). The two user_ids in each tuple should also in lexicographical order. You do not need to round your result.

Figure 3: betweenness output file format

4.2.2Community Detection (6.5 pts)

You are required to divide the graph into suitable communities, which reaches the global highest modularity. The formula of modularity is shown below:

According to the Girvan-Newman algorithm, after removing one edge, you should re-compute the betweenness.

The m in the formula represents the edge number of the original graph. The A in the formula is the adjacent matrix of the original graph. (Hint: In each remove step, m and A should not be changed).

If the community only has one user node, we still regard it as a valid community.

You need to save your result in a txt file. The format is the same with the output file from task1.

4.2.3Output Result

In this task, you need to save your result of communities in a txt file. Each line represents one community and the format is:

user_id1, user_id2, user_id3, user_id4,

Your result should be firstly sorted by the size of communities in the ascending order and then the first user_id in the community in lexicographical order (the user_id is type of string). The user_ids in each community should also be in the lexicographical order.

If there is only one node in the community, we still regard it as a valid community.

Figure 2: community output file format

4.3 Execution Format Execution example:

Python:

spark-submit class firstname_lastname_task1.py <filter threshold>

<input_file_path> <betweenness_output_file_path> <community_output_file_path>

Scala:

spark-submit class firstname_lastname_task1 firstname_lastname_hw4.jar <filter threshold> <input_file_path> <betweenness_output_file_path> <community_output_file_path> Input parameters:

1. <filter threshold>: the filter threshold to generate edges between user nodes.
2. <input file path>: the path to the input file including path, file name and extension.
3. <betweenness output file path>: the path to the betweenness output file including path, file name and extension.
4. <community output file path>: the path to the community output file including path, file name and extension.

Execution time:

The overall runtime of your task (from reading the input file to finishing writing the community output file) should be less than 180 seconds.

If your runtime is between 180 seconds and 240 seconds, there will be 20% penalty. If your runtime exceeds 300 seconds, there will be 50% penalty for this task.