Homework 7
(15 points)
Use the enclosed file “simulatedSocialMedia.csv”. This file is a simulation of a graph dataset
and each row presents two nodes that are connected to each other. - Dijkstra to find the shortest path in the graph. Since the graph is large you can create a smaller
file and work on the smaller graph. (1 point)
- Prim and Kruskal to find the MST from two arbitrary nodes one will be source one node will be
target (2 points).
- Page rank and HITS algorithm to order the graph nodes based on their importance. Again, if
the graph is too large for your system you can made a smaller file and use a subgraph. (4
points)
- Louvain and Leiden for community detection (3 points), and visualize the result (5 points). Your result for community detection should be visualized as well. You should research on your
own about visualizing graph communities. We did not describe visualization in the class and this
is the main challenge of this homework. For example, the size of the node circle could be used
to visualize the importance of a node in Page rank and HITS.
Please do not forget to submit the video presentation of your homework as well. If you have
any trouble during your work, please contact the TA or RA before the deadline. We will
schedule an appointment to help you progress in your homework.