[SOLVED] Algorithms-Applications in Social Networks Homework 2

Description

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 didn’t 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?