# homework | 算法作业 | Algorithm – Graph practice

### Graph practice

homework | Network作业 | 代写network | Algorithm – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 是有一定代表意义的Network/network/Algorithm等代写方向, 这是值得参考的homework代写的题目

### Problem 1

Two graphs,G(V, E) andG(V, E), areisomorphicif there is abijectionf: VVsuch that (u, v)Eiff (f(u), f(v))E. Do isomorphic graphs share the same eigenvectors? And the eigenvalues? Propose an isomorphism checking Algorithm based on the spectrum of the Laplacian matrix. Is this algorithm always correct?

### Problem 2

Consider the problem of selecting training vertices for a label propagation algo- rithm (similar to the problem in homework 1). You can consider any of the label propagation approaches described in the class. Propose an algorithm for select- ing training vertices. You should justify your algorithm with either a (strong) theoretical argument or with experiments. You are free to make adjustments to the probleme.g. assuming you have access to all vertex labels and want to select a subset or that only the graph structure is available. If you opt for a the- oretical argument, you can make reasonable assumptions about the relationship between attributes and the graph structure. If you opt for an empirical argu- ment, find a (labeled) dataset and compare your approach against an alternative that picks training vertices at random.

### Problem 3

The Cora dataset^1 is a citation network where vertices represent papers, edges represent citations, and vertex attributes are binary vectors indicating the ab- sence/presence of words in the papers. Your goal is to apply spectral clustering to group the papers based on attributes (words) and the citation network (links). Show results comparing the clusters found using a clustering evaluation met- ric (e.g. normalized rand-score). Which type of information is more useful? How would you combine them? Because the graph is disconnected, you can use its largest connected component. Hints: (1) sklearn has an implementation of spectral clustering that works for attributes and a graph (adjacency matrix)

(^1) https://linqs.org/datasets/

##### 1

and (2) vary the number of clusters predicted and usenearest-neighborsfor the clustering based on attributes (it is faster).