CAP XXXXXXXXXXSpring) Homework 1 [12 points, Due: Feb 8, Late Penalty: -1/day] [If two homework submissions are found to be similar to each other, both submissions will receive 0 grade] [Homework...

I'm completely stuck on this. I have to take this class as an elective for my masters and I have ZERO experience in this subject matter. It's way over my head.


CAP 6315 (2020 Spring) Homework 1 [12 points, Due: Feb 8, Late Penalty: -1/day] [If two homework submissions are found to be similar to each other, both submissions will receive 0 grade] [Homework solutions must be submitted through Canvas. No email submission is accepted. If you have multiple files, please include all files as one zip file, and submit zip file online (only zip, pdf, or word files are allowed). You can always update your submissions. I will only grade the latest version.] Question 1 [2 pts: 0.2/each]: Use your own language to briefly explain the following concepts: 1) Graph and Social Network: 2) Undirected graph: 3) Adjacency matrix: 4) Adjacency list: 5) Graph Walk, Trail, Path: 6) Bipartite Graph: 7) Depth First Search: 8) Breath First Search: 9) Random Network: 10) Scale Free Network: Figure 1 Figure 2: Breath First Search (BFS) Question 2 [1 pt] Figure 1 shows a search tree with 21 nodes. Please uses Breath First Search (BFS) algorithm showing in Figure 2 to traverse the tree and report the order of the nodes being visited. Please report Queue structure of each step as show in the table below [0.5 pt]. Compare the Queue structure and explain the memory consumption with respect to branching factor (b) and the search depth (d) [0.5 pt]. BFS Queue Node visited Queue Size Search depth Figure 3 Depth First Search (DFS) Question 3 [1 pt] Figure 1 shows a search tree with 21 nodes. Please uses Depth First Search algorithm showing in Figure 3 to traverse the tree. Report Stack structure of each step as show in the table below [0.5 pt]. Compare the Stack structure and explain the memory consumption of each method, with respect to branching factor (b) and the search depth (d) [0.5 pt]. DFS Stack Node visited Stack Size Search depth Figure 4: Unweighted graph Question 4 [1 pt]: · In Figure 4, starting from node “a”, please show the order of the nodes visited using a Breath First Search (BFS) to traverse the whole graph (nodes at the same tier are visited by following the alphabetic order) [0.5pt] · In Figure 4, starting from node “a”, please show the order of the nodes visited using a Depth First Search (DFS) to traverse the whole graph (nodes at the same tier are visited by following the alphabetic order) [0.5pt] Figure 5: Weighted graph Question 5 [1 pt] · In the weighted graph in Figure 5, please use Dijkstra algorithm to find the shortest path (including path length and the path) from source node “a” to all remaining nodes. Please report the L table as shown in the lecture note [1.0 pt] Question 6 [2 pts]: In the network showing in Figure 4: · Report degree distributions of the network [0.5 pt] · Please use “power of the adjacency matrix” to find diameter of the network (show your solution and the diameter of the network) [0.5 pt]. · Calculate network edge density [0.25], global clustering coefficient [0.25], and clustering coefficient of very nodes in the network [0.5 pt]. Question 7 [1 pt]: Use Python or R to create a network similar to the one showing in Figure 4. The number of vertices and edges, vertex lables, and edge lables should be the same as Figure 4 (you can also use other programming language) [1 pt]. Please report the network and the source code as a Notebook submission. Question 8 [2 pts]: The “karate.gml” in the Dataset folder (in Canvas) is a social network with 34 vertices and 78 edges. Use Python or R to implement the following tasks (you can also use other programming language): Karate network: http://konect.uni-koblenz.de/networks/ucidata-zachary. Please submit the source code and the results as a Notebook File (or integrate in your word/pdf submission) 1) Read the karate.gml and plot the network (showing all vertices and edges). [0.25 pt] 2) Change the color of the vertices, such that all nodes connected to node 1 (the node with ID 1), including node 1, are colored in “red”, all nodes connected to node 34 (the node with ID 34) , including node 34, are colored in “yellow”. Nodes connecting to both 1 and 34 are colored in “orange”. All other nodes are colored in “blue”. [0.5 pt] 3) Resize each vertex, such that the node size is linearly proportional to its degree [0. 25 pt] 4) Change the edge label, such that each edge is labeled using its incident vertices. For example, an edge connecting to node 1 and 3 would be labeled as “1-3” [0.5 pt] 5) Use a layout to plot the network, and explain the meaning of the layout [0.5 pt] Question 8 [1 pt]: The “netscience.gml” in the Dataset folder is a coauthorship network of scientists working on network theory and experiment (http://networkdata.ics.uci.edu/data/netscience/) A brief description of the network is given in the “netscience.txt” (of the above URL). The names of the scientists (which correspond to the nodes of the networks) are given in “netscience.gml”. Please download the dataset and use Python or R to implement the following tasks. Please submit the Python or R code and the results as a Notebook file 1. Please report and draw the degree distributions of the whole network [0.25 pt]. Convert the figure to log-log space and validate whether it complies with the power-law distributions [0.25 pt]. 2. Please report cumulative degree distribution of the network [0.25 pt], and convert it to log-log space and validate whether it complies with the power-law distributions [0.25 pt]. 3. Please report Rank-Degree distribution of the network [0.25 pt], and convert it to log-log space and validate whether it complies with the power-law distributions [0.25 pt].