## Instructions
1. This note book contains instructions for **COMP9318-lab5**.
* You are required to complete your implementation in a file `submission.py` provided along with this notebook.
* You are not allowed to print out unnecessary stuff. We will not consider any output printed out on the screen. All results should be returned in appropriate data structures via corresponding functions.
* You can submit your implementation for **lab5** via following link: http://kg.cse.unsw.edu.au:8318/lab5/ .
* For each question, we have provided you with detailed instructions along with question headings. In case of any problem, you can post your query **@ Piazza.**
* You are allowed to add other functions and/or import modules (you may have to in this lab), but you are not allowed to define global variables. **Only functions are allowed** in `submission.py`.
* You should not import unnecessary modules/libraries, failing to import such modules at test time will lead to errors.
* We will provide immediate feedback on your submission. You can access your scores using the online submission portal on the same day.
* For **Final Evaluation** we will be using a different dataset, so your final scores may vary.
* You are allowed to submit as many times as you want before the deadline, but **ONLY the latest version will be kept and marked**.
* Submission deadline for this assignment is **23:59:59 on 10th June, 2018**. We will **not** accept any late submissions.
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
# Reading edges in a Graph...
data_file='./asset/a'
with open(data_file) as infile:
edges = [tuple(map(int,(line.strip().split(' ')))) for line in infile]
# Creating a new Graph...
G = nx.Graph(name="Ex1")
for edge in edges:
G.add_edge(*edge)
# You can visualize the Graph for your own understanding...
nx.draw_networkx(G, with_labels=True, node_color='y')
plt.show()
You need to **implement** spectral clustering algorithm (i.e., `spectral_clustering()` in the file: `submission.py`). The input arguments of `spectral_clustering()` are:
**Input:**
* `G`: A graph as defined above
**Output:**
1. `eigenvectors`, i.e., a numpy matrix containing two eigenvectors starting with the second smallest eigenvector. Its dimensions should be (N,2), where N stands for number of nodes in the graph.
* `clusters`, i.e., lists of sub-lists containing the NODE-IDs corresponding to two clusters.
For example, a sample output is shown in the cell given below:
# Submission
You need to complete the function `spectral_clustering()` in the file: `submission.py`. You can test your submission against sample test cases via online submission system (i.e., http://kg.cse.unsw.edu.au:8318/lab5/).
# Test Environment
For testing, we have pre-installed the requisite modules and/or libraries in the testing environment. You are only allowed to use following libraries:
* python: 3.5.2
* numpy: 1.14.0
* networkx: 2.1
* nltk: 3.2.5
**Note:**
1. You need to implement the methodology by yourself. You are not allowed to import **sklearn** and/or any other library in Lab5.
2. For cluster labels you should use the priorly provided commands (given in last cell) to generate the clusters.
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
def spectral_clustering(G): # do not change the heading of the function
pass # **replace** this line with your code