Implement K-Spanning Tree, Implement Prim's algorithm for KSpanning Tree in Python or R. For the cases: a) The edge weights indicate distance b) Edge weights indicate similarity. Also, check if you can utilize library methods and apply on large graphs. You can use the dataset: http://www-personal.umich.edu/~mejn/netdata/
Implement Highly Connected Subgraph Clustering algorithm also Karger's MinCut Algorithm., Implement Prim's algorithm for KSpanning Tree in Python or R. You can use the dataset: http://www-personal.umich.edu/~mejn/netdata/
Apply on small Graphs/datasets before you try on Large Graphs/Datasets.