HW #2 Solution

$30.00

Description

Instructions: Implementation should be done using Python and NetworkX library. Please submit you code in .py files (file per question) or .ipynb file (Jupyter Notebooks). The theoretical part of the question should be submitted in PDF file.

Do not forget to write IDs of all member in the team (pair). Submit only once per team! Please ZIP all files together, name the file HW2_<student_id>.zip and upload it to Moodle.

Question #1:

  1. Implement Newman-Girvan algorithm for non-overlapping communities. The algorithm should receive a network and parameter k (number of communities) are return the communities.

  2. Run this algorithm on the following dataset: https://bit.ly/2KLHN60 Each line of the file represent and edge between two nodes.

  1. (Manually) Find how to split the following network into 2 non-overlapping communities using the above algorithm:

Build dendrogram of each split.

Question #2:

  1. Implement k-clique communities detection algorithm. The algorithm should receive a network and parameter k (size of clique) are return the communities.

  2. Run this algorithm on the following dataset: https://bit.ly/2KLHN60

  1. (Manually) Find how to split the following network into overlapping communities using the above algorithm and k=3:

Question #3:

  1. Given the following graph, including edge weights, assume we have randomly generated the following thresholds:

A – 0.6; B – 0.1; C – 0.5; D – 0.3; E – 0.4; F – 0.7; Find the most influential node using the Linear Threshold model.

Question #4:

  1. 4 friends want to decide if they meet and watch Champions League final or work on a homework*. Following graph depicts the influence of the friends on each other. Assuming that (a) and (d) want to watch the game (opinion = 1) and (b) and (c) do not (opinion = 0). Compute, using DeGroot model, if they are going to agree on a consensus. If they agree, what is the severity they will actually watch the game?

  1. Using the code shown in class – construct this example and check if you got same result

Question #5:

A group of n people are connected each to other, and using 2 ways of communications – phone and mail. Prove that they can decide to use only one of these two ways and still all of them will be reachable to each other (not necessarily directly connected)

* Reminder: max group of students allowed to work together on a homework is 3.