Graph Mining: K-Spanning Trees: Learn by finding answers to the following questions. Can you answer the questions?
What is a Spanning Tree?
What is a Minimum Spanning Tree?
For the undirected Graph below, what is a Spanning Tree? First, draw the Graph, then Try to find the answer, and then check the answer below.
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
What is a minimum spanning tree?
What is the minimum spanning tree for the graph as provided above?
What is Prim's Algorithm for Spanning Trees?
Describe the steps as used in Prim's Algorithm?
Give the Algorithm i.e. Prim's Algorithm?
Write pseudo-code for Prim's Algorithm?
Implement Prim's Algorithm in Python, R, Matlab, or in any other language of your choice?
What is the initialization step in Prim's Algorithm?
Can you choose any node to start with Prim's Algorithm?
True or False, Prim's algorithm does not include all nodes in the output?
How an edge/path is selected in Prim's Algorithm?
True or False, to proceed and when to select an edge, the edge does not need to belong to the already formed Minimum Spanning Tree (MST)?
True or False, to proceed and to select a new edge, the edge will need to have the highest weight outgoing from the MST or from the vertex under consideration)?
True or False, to proceed and to select a new edge, the edge will need to have the minimum weight outgoing from the MST (or from the vertex under consideration)?
True or False? The new edge selection steps are as follows.
Step 1. For the new edge, exactly one of its vertices/edge-points will need to be in the MST already
Step 2. The new edge has the minimum weight that satisfies step 1.
How long will you continue to add new edges to the MST? i.e. terminating condition for your algorithm.
Apply Prim's algorithm to find the MST in Graph given above/below: See the answer after you give it a try
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
What is K-Spanning tree?
What are the steps in K-Spanning Tree?
Give the Algorithm for K-Spanning?
Write pseudo-code for K-Spanning?
Implement the K-Spanning tree algorithm in Python, R, Matlab, or in any other language of your choice?
What is K in the K-Spanning Tree algorithms?
How many edges do you remove to create k Clusters?
What is the first step in the K-Spanning tree?
When you remove edges from an MST - which edges do you remove? Edges represent distance. The ones with the highest weights or the lowest weights?
Some Answers:
What is a Spanning Tree?
Ans: A connected subgraph with all vertices and no cycles
For the undirected Graph below, what is a Spanning Tree?
Edges with weights: {1, 2, 7} {1, 3, 2} {3, 4, 2} {3, 5, 6}
Weight: 17
What is a minimum spanning tree?
Ans: Spanning trees with the minimum sum of edge weights where weights indicate distances.
What is the minimum spanning tree for the graph as provided above?
Ans: the same spanning tree with weight sum = 17
i.e. {1, 2, 7} {1, 3, 2} {3, 4, 2} {3, 5, 6}
What is Prim's Algorithm for Spanning Trees?
Ans: Finds the minimum spanning tree
Apply Prim's algorithm to find the MST in Graph given above/below: See the answer after you give it a try
Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
Draw the graph that will make things easier
Ans: Select node 5
Select (5, 4, 4) from {3, 5, 6} {4, 5, 4}
Add (5, 4) to the MST
select edge {3, 4, 2} from {3, 5, 6} {2, 4, 5} {3, 4, 2} {1, 4, 4}
MST: {5, 4, 4} {3, 4, 2}
Similarly: select (3, 2, 3) {1, 3, 2}
Final Output: {5, 4, 4} {3, 4, 2} (3, 2, 3) {1, 3, 2}
What is the K-Spanning tree?
Ans: Community/Clustering Algorithm
When you remove edges from an MST - which edges do you remove? Edges represent distance. The ones with the highest weights or the lowest weights?
Ans: highest
By
Sayed Ahmed
Linkedin: https://ca.linkedin.com/in/sayedjustetc
Blog: http://Bangla.SaLearningSchool.com, http://SitesTree.com
Online and Offline Training: http://Training.SitesTree.com