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

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 members in the team (pair). Submit only once per team!

Please ZIP all files together, name the file HW1_<student_id>.zip and upload it to Moodle.

Question #1:

1. Implement an ErdsRnyi model. Write a function that gets n number of nodes and p probability of an edge and returns a random graph.
2. Implement a function that computes the clustering coefficient of a given graph. Implement a helper function that computes clustering coefficient of each node.

Question #2:

1. Implement 3 centrality measures: Degree centrality, Betweenness centrality and Closeness centrality.
2. Run these measures on a random Gnp network with n=15 and p=0.5 and report top-5 nodes according to each of the measures.
3. Visualize the network using different centrality measures by changing node sizes based on the centrality measure value of each node.
4. Compute (manually) each of the centrality measures for red, green, blue and grey nodes. Rank the nodes by each of the measures and explain the difference between gray and green nodes in terms of different centrality measures.

Question #3:

1. Implement check_balance(G) function that checks balance (according to

Theory of Structural Balance) of a G. Explain your implementation decision.

1. Generate a random network using ErdsRnyi using n=10 and p=0.4. On each edge, assign random sign (+ or -) with different probabilities:
2. p(+) = 0.95, p(-) = 0.05 ii. p(+) = 0.05, p(-) = 0.95
3. Visualize the graph with different colors for positive and negative edges. Run the check_balance(G) on each of the graphs.
4. Think about a real-world example of a signed social network (up to 10 nodes). Present the network, explain the nodes and the edges. Check (manually) if the network follows the Theory of Structural Balance and explain the results.
5. Find a number N>3 (one example is enough) for which a complete graph with N nodes is balanced and has the same number of + edges and – edges.

Question #4:

A group of n people are connected to each 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)