Graph Clustering 4% of Final Grade As described in the course…

Question Answered step-by-step Graph Clustering 4% of Final Grade As described in the course… Graph Clustering 4% of Final Grade As described in the course notes, the Fiedler vector of a Laplacian matrix of a graph can be used to cluster the vertices of a graph into two sets. Set 1 contains the indices of vertices that have a negative Fiedler entry and Set 2 contains the indices of vertices that have a positive Fiedler entry. The problem is: given an edge list, use a for loop to create a Laplacian matrix for the graph and then cluster the vertices of the graph. The input is an array in which each row is a pair of integers that index the list of vertices. The output is a vector that indicates the clustering of the vertices, in which each entry is -1 for Set 1 and +1 for Set 2. For this problem, you will need to modify the instructor’s “starter” code that is in the accompa- nying ZIP file. The starter code will return a constant clustering vector, intended to act as a guide for you in learning how a MAILAB function can return values. For testing, a randomly generated graph has been provided. Diagrams of the test graph are shown in Figure 1. There are two files that you can use to test your code:testedge. txt contains edges of the graph, and testsets. txt contains the correct set vector. You can check your results, replacing xxxxxxxx with your student number, using the MAILAB commands load (‘testedge. txt’) ; al xxxxxxx×(testedge) and this is the starter code: function set12 = a1_00000000(elist) % Function for CISC271, Winter 2022, Assignment #1 % % IN: % elist – Mx2 array of edges, each row is a pair of vertices % OUT: % set12 – Nx1 vertex clsutering, -1 for SET1 and +1 for SET2 % Problem size: number of vertices in the graph n = max(elist(:)); % % % % STUDENT CODE GOES HERE: replace this trivial adjacency matrix % % with your computation; the first line is a hint for how to % % initialize your matrix correctly % % A = zeros(n); A = [ 0 1 0 0 ; 1 0 1 0 ; 0 1 0 1 ; 0 0 1 0]; % % % % STUDENT CODE GOES HERE: replace this constant clustering vector % % with your computation that uses the Fiedler vector; the % % vector SET12 should be plus/minus 1 for automated grading % % set12 = [-1; -1; 1; 1]; % % % % STUDENT CODE GOES HERE: replace this trivial display to console % % with your computation from the vector SET12 % % disp(‘Set 1 vertices are:’); disp([1 2]); disp(‘Set 2 vertices are:’); disp([3 4]); % Plot the graph, Cartesian and clustered plot271a1(A, set12); end function plot271a1(Amat, cvec) % PLOTCLUSTER(AMAT,CVEC) plots the adjacency matrix AMAT twice; % first, as a Cartesian grid, and seconnd, by using binary clusters % in CVEC to plot the graph of AMAT based on two circles % % INPUTS: % Amat – NxN adjacency matrix, symmetric with binary entries % cvec – Nx1 vector of class labels, having 2 distinct values % OUTPUTS: % none % SIDE EFFECTS: % Plots into the current figure % % % % Part 1 of 2: plot the graph as a rectangle % % % Problem size [m n] = size(Amat); % Factor the size into primes and use the largest as the X size nfact = factor(n); nx = nfact(end); ny = round(n/nx); % Create a grid and pull apart into coordinates; offset Y by +2 [gx, gy] = meshgrid((1:nx) – round(nx/2), (1:ny) + 2); % Offset the odd rows to diagram the connections a little better for ix=1:2:ny gx(ix, 🙂 = gx(ix, 🙂 + 0.25*ix; end % The plot function needs simple vectors to create the graph x = gx(:); y = flipud(gy(:)); % Plot the graph of A using the Cartesian grid plot(graph(tril(Amat, -1), ‘lower’), ‘XData’, x, ‘YData’, y); axis(‘equal’); % % % % Part 2 of 2: plot the graph as pair of circles % % % Set up the X and Y coordinates of each graph vertex xy = zeros(2, numel(cvec)); % Number of cluster to process kset = unique(cvec); nk = numel(kset); % Base circle is radius 2, points are centers of clusters bxy = 2*circlen(nk); % Process each cluster for ix = 1:nk jx = cvec==kset(ix); ni = sum(jx); xy(:, jx) = bxy(:, ix) + circlen(ni); end hold on; plot(graph(Amat), ‘XData’, xy(1,:), ‘YData’, xy(2,:)); hold off; title(sprintf(‘Clusters of (%d,%d) nodes’, … sum(cvec==kset(1)), sum(cvec==kset(2)))); end function xy = circlen(n) % XY=CIRCLEN(N) finds N 2D points on a unit circle % % INPUTS: % N – positive integer, number of points % OUTPUTS: % XY – 2xN array, each column is a 2D point xy = [cos(2*pi*(0:(n-1))/n) ; sin(2*pi*(0:(n-1))/n)]; end the testedge file: 01 02 01 06 01 08 01 09 01 13 01 14 01 15 01 19 02 01 02 05 02 06 02 08 02 09 02 12 02 13 02 14 02 15 02 18 02 19 03 04 03 05 03 07 03 10 03 12 03 17 03 20 04 03 04 07 04 10 04 11 04 12 04 16 04 17 04 20 05 02 05 03 05 07 05 10 05 12 05 16 05 20 06 01 06 02 06 08 06 09 06 11 06 14 06 15 06 18 06 19 07 03 07 04 07 05 07 10 07 11 07 12 07 16 07 20 08 01 08 02 08 06 08 09 08 13 08 14 08 15 08 18 08 19 09 01 09 02 09 06 09 08 09 13 09 14 09 15 09 18 09 19 10 03 10 04 10 05 10 07 10 11 10 12 10 14 10 16 10 17 10 18 10 20 11 04 11 06 11 07 11 10 11 12 11 14 11 16 11 17 11 20 12 02 12 03 12 04 12 05 12 07 12 10 12 11 12 13 12 17 12 20 13 01 13 02 13 08 13 09 13 12 13 14 13 15 13 18 13 19 13 20 14 01 14 02 14 06 14 08 14 09 14 10 14 11 14 13 14 15 14 18 14 19 15 01 15 02 15 06 15 08 15 09 15 13 15 14 15 18 15 19 16 04 16 05 16 07 16 10 16 11 16 17 16 20 17 03 17 04 17 10 17 11 17 12 17 16 17 20 18 02 18 06 18 08 18 09 18 10 18 13 18 14 18 15 18 19 19 01 19 02 19 06 19 08 19 09 19 13 19 14 19 15 19 18 20 03 20 04 20 05 20 07 20 10 20 11 20 12 20 13 20 16 20 17 the testsets.txt file: -1 -1 1 1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 1 1 -1 -1 1 Grading Guide: We will test your code on your individual, randomly generated edge list. The edges for ev- eryone are in the file alfiles. zip; your data file is coded as your Queen’s netid as indicated in onQ. A correct clustering of “your” graph will be part of your grade for this assignment. This means that your single figure should be the diagram produced for your individual edge list, and your single table should be the clustering of vertices for your individual edge list. The TA’s have been instructed to use this quide when they mark your assignment. Your grade will be based on the numerical results and on the report. The distribution of points for the assign- ment grade are: 4/16 points: numerical values that are produced by the code and that are presented in the results 4/16 points: quality of the code in the modified “starter” functions, and any other changes in the submission file that was used to generate values and plots for the report 8/16 points: quality of the report, especially including the figures and descriptions; clarity may be assessed, in part, by the written discussion of results. Grading Considerations: • The quality of your report will be considered. You need, at minimum, to conform to the “student version” of the report style in the onQ website; you may wish to consider the “grader version” that we will use for assessing your report. • The quality of your MAILAB code will be considered. Your code should be appropriately indented, sufficiently commented, and otherwise be appropriate software. • The output of your code will be considered. , Your code can use functions provided by MAILAB, but the code that vou submit must be your original work. You may not use any builtin functions that perform optimization or clustering such as k-means, although you may wish to use such functions as you develop and test your software. • Code that causes MAILAB to produce an error or warning will result in a failing grade.Image transcription textSuppose there were 233 thousandcomputer programming jobs in 2010and that the number increa… Show more… Show moreImage transcription text11. For computer programming in anyprogramming language, or for manyproblem solving situations… Show more… Show more  Engineering & Technology Computer Science COMS 3251 Share QuestionEmailCopy link Comments (0)