Instructions: Implementation should be done using Python and NetworkX library. Please submit your code in .py files (file per question) or .ipynb file (Jupyter Notebooks).
The theoretical part of the question should be submitted in a PDF file.
Do not forget to write IDs of all the members in the team (pair). Submit only once per team! Please ZIP all files together, name the file HW3_<student_id>.zip and upload it to Moodle.
- Give a complete graph with 3N nodes representing an organization (where everyone works directly with all other colleagues), After restructuring the organization divided into 3 groups of N workers.
- How many connections were removed?
- What is the overall change in the clustering coefficient (before vs after the restructuring)
- What is the overall change in the average degree centrality (before vs.
after the change)
- Given an undirected graph of 6 nodes. Using the Link Prediction algorithm with Common Neighbors and Preferential Attachment heuristics, find the (non-existing) top-3 edges that have the highest chance to be created in this network.
- Explain the difference in the result.
- Given the following graph, including edge weights, assume we have randomly generated the following thresholds:
A – 0.3; B – 0.1; C – 0.8; D – 0.1; E – 0.1; F – 0.3;
Find the most influential node using the Linear Threshold model.
- 4 friends want to decide if they should go to Eilat. Following graph depicts the influence of the friends on each other. Assuming that (a), (c) and (d) want to go to Eilat (opinion = 1) and (b) does 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 go to Eilat?
- Using the code shown in class – construct this example and check if you got same result
- Given a requirement for a graph with 10 nodes with all node degrees with are odd (1, 3, …). Show example that has:
- Minimum possible clustering coefficient
- Maximum possible clustering coefficient
- No cycles
- Given a network of 9 nodes. Each node’s degree is at least 4. Prove that the graph is connected.
- Given a network of n nodes. Each node’s degree is at least round_up((n-1)/2). Prove that the graph is connected.