MProblem
homework | 代写Network | network代写 | Algorithm代写 – 该题目是一个常规的图算法的练习题目代写, 是有一定代表意义的图算法/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).