[Solved] Algorithms and Applications in Social Networks HW #2

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 biggest connected component of the following dataset: https://bit.ly/2KLHN6 0 ( with k=3)

Each line of the file represents an edge between two nodes.

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

Build a 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 biggest connected component of the following dataset: https://bit.ly/2KLHN6 0 ( with k=4)
3. (Manually) Find how to split the following network into overlapping communities using the above algorithm and k=3:

Question #3:

A group of 10 chess players are going to play a one round tournament (every pair will play exactly once).

1. How many games will occur?
2. 14 games already played. Prove that there are at least 3 players that didnt play against each other.

Question #4:

There are 20 people, all of them connected to each other (in a undirected manner). 18 connections are removed. Prove that the graph is still connected.

Question #5:

In a given undirected network each person is connected to 5 other people. The number of edges in this network is 46. How many nodes are in this network?

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.