everything above this is background information and everything below that says #grade is what i need help with
Graphs In graph theory, a graph is a set of nodes ("vertices") that are connected to one another with edges. This first example is a graph with 4 nodes and 5 edges. (calculating turn-by-turn directions involves solving a graph problemt). Adjacency Matrix Aij={10ifnodesiandjshareacommonedgeotherwise Mare ganarally, for a directed graph with n nodes, the adjacancy matrix ARnn is such that: Ai,j={10ifGcontainsanedgefromnodejtonouleiotherwise For example, A0.2 stores whether there is an edge from node 2 to node 0 . Example 1: Check your answers: Write the adjacency matrix that generates the undirected graph illustrated abewe, Store the matrix as a 2d numpy' array of integers and assign it to the variable A. *grade (enter your code in this cel2 - DO NOT DELETE THIS LIME) A= np. A rray ([10,1,1,0],[1,1,1,01,[1,1,0,11,[0,0,1,0]1) You can use the function graph. draw_nat rix to make the graph from a given adjacency matrix: graph. draw mat rix(Ar show weights-False) Note that any nonzero value along the main diagonal results in a seif loog. In this example, the graph is undirected, so its edges do not have directicn. The adjacency matrix A at an undirected graph is always syonmetric; that is, AT=A. Graph Walks A walk of length k is a sequence of k+1 vertices and k edges between two nodes (including the start and end) that may repeat. 1 frem node 1 to itself since A1,1=1. Essentially, the adjacnncy matrix telis you if you can walk fram one node to another in one step. Discuss with your group: Trace the edges and count the number of walks of length k between the following nodes. a) node 2 to node 3:3x walks of length 2 b) node 2 to node 2: walks af length 3 c) node 1 to node 3 : Z walks of length 2 d) node 3 to node 1: w walks of lenegth 3 Check your answers: *grade ionter your code in this ceil - Do NOT DELETE THIS LINEj x=0y=3z=1y=2 Try this! A2=A+k2 Indead, tha antry (A2), represents how many ways wn can mowe from node j to nodn i via a walk af langth 2 (i.n. in twa stapa). Try this! Discuss the foliawing questiars with your group: 1. Use A2 to check if your answers from questions a) and c) abono were curract. 2. What would you need to co to verify youf answers from questions b) and dy? shaw_weightsmrue) The number of walks of length exactly k from node j to node i is by given by (Ak)i,j Example 2: print''The graph below shows the number of malks of length 1 between any two nodes') graphadras_ratrixid, show_weights=Truel The graph below shows the nurber of walks of length 1 between any two nodes [8) : print('The graph below shows the nunber of walks of tength 2 between any two nodes') graph. dram_natrix (BeB, show_we ights-True) print 'The graph beles shous the nuaber of walks af length 3 between any two nedes') graphndram_ndtrix (beBe8, shoN_weights=True) By inspecting the above plots, we tind that from node D to node 1 we have: - cone wakk of iengeht - zero waks of iength 2 waks of length 3 This occurs because when node 1 is resched, it must be lelt in the following step. So if we reach a node sooner than in the desired number of steps, haw can we adjust th We can add self-loops! Take a look at the graph for the identity matrix: 9] - graph, dran_natrix [np-eye\{4, dtype-int]\} Check your answers: Modify the matrix B by adding a self-lcop to each node ceven if there is already a self-loop present, in which case there will be entries 2 2). Store the modilied matrix in I 0] Agrade (enter your code in this cetl - Do wOr DeLete thIs LIME B1=np=array[[[1,1,1,81, [1,1,8,1], [1,8,2,6] [0,1,0,2]1? Note that by adding self-loops, Bi expresses the same pairs of cistinct nodes that may be reached via a walk of length 1 as does B. The difference is only in the numbe 1. graph.draw_natrixind Number of Steps in Walk In the previaus exampies we were picking arbitrary valuns of k far nur walks. What if we want to find the smallest value of k such that each node is connected to every other node? If such a k exists, we say the graph is fully connected. Lat's lack at a few scenarias here. In this first uxampln, all nodes are connected with anch ather. 2] I n=4 c=npones({n,n), dtype=int } graph.draw_nat rux\{C, shod_weights-True } For the example above, we can see that any nede can resch another node with a walk of length 1 , and hence the smallest value of k is k=1. Let's lock at this other axample (we use mumpy-eye to define matrices with is in the upper and lower diagonals) Check your answers: Modify the matrix O abave, such that each note can also more to itself. Store that as the variable Di. * grade (enter your code in this celi - Do NOT DElETE ThIS LIME) Di=np. array [[11,1,0,1,[1,1,1,0],[0,1,1,11,[,0,1,1]1] We can think af the ibentity matrix as counting walks af "length zero", since it takes zera maves to get fram a note to itself. By adding the ident ty nudes. arach.draw natrixidi, showeights-True\} We do not yet have a graph that is fully connected. That is, we cannot reach every node from any ather node via a walk af length 1. What if we want to consider the connections that can be reached with up to waks of length 2 ? Try it! Crate a matrix which reprusants waks of length at most 2 Store it as the variabla 0i2. Hint: Which matrix counts wales of length exactly 1? You'll need to use it to find the walks of Inngth exactly 2. Do you stil get entries that are zero, indicating that not all nodes can be reached from any noce in up to 2 steps? Did you gat a fully cannected graph when considering walks of length at most 2 ? Keep adding Dk until you find the necessary k value. In summary, every node of a connected graph G is connected to every other node via walks of length at most k when k is such that the matr I+k=1kGi dons not ecntain any 0 untries. This matrix captures the number af distinct walks of length at most k batwen each pair of nodes. Without I, the sum af matrices represents Edge-node Incidence Matrix Now, we consider directed graphs and define them according to their adjacency matrices. The edge-node incidence matrox M of the directed Mi,l=110ifedgeileavesnodejifedgeientersnodejotherwise where m is the number of edges and n is the number of nodes. Note that establishes an ordering on the edges. Ccnsider tha adjacency matrix belaw: Think about this: Why does the incidence matrix have 8 rows? A. components. Using this knawledgn, answer the following questian: Suppose that the nulspace of the incidence matrix af a graph is given by the following matrix: 100100100000101 What is the index of the node which is in a cornected component al by itselt? In the following cell, store your answar as lonety_index. 1: agrade (enter your code in this cell - Do not DELETE THIS LINE) I: nu11_42.shape[1] The number of nodes in each cornected component is given by the count of 1 entries in each rulspace coluimn. We can compute the columnwise sum of a nulspace matrix as follows: null_2, u [axis=9] The first cannected component camprisas 2 nudus while the second connectad component comprises 3 nudas. Social Network Analysis model several properties of the network. My Freceacek frienca on Tue 8 ea 2715.11,352011 CEST (htte:/fanw.kakacu-works,comjmytnetwork/weloome.htm) We can visualize the social network in a graph format: graph.draw_matrix(friends, shou_weights=False) Check your answers: the adjacency matrix. *grade (enter your code in this cell - DO NOT DELETE THIS LIME) Check your answers: How many people are in the largest friend group? Store this number as max_group_size *grade (enter your code in this cell - DO NOT DELETE THIS LINE) Meme Spread (Meme stolen from reddit.comirimathmemes) We will use a slightly larger graph of n=100 people, represented as an adjacency matrix. \[ \begin{array}{l} n=100 \\ \text { neme_network = graph.gen_randon_friends }(n, 0.98) \end{array} \] Here is the (quite large!) graph showing friend connectivity: graph.draw_matrix(neme_network, show_weights=False) Check your answers: How many frlend groups exdst in this network? Store that in ngroups. What is the size of each one of these groups? Save your results as a 1d numpy array nfriends_pergroup. How many people will receive the meme? Store that in receive_mene. a matrix A that are equal to 5, you could use np, whe re (A=5), *grade (enter your cade in this cell - DO NOT OELETE THIS LIME) Graphs In graph theory, a graph is a set of nodes ("vertices") that are connected to one another with edges. This first example is a graph with 4 nodes and 5 edges. (calculating turn-by-turn directions involves solving a graph problemt). Adjacency Matrix Aij={10ifnodesiandjshareacommonedgeotherwise Mare ganarally, for a directed graph with n nodes, the adjacancy matrix ARnn is such that: Ai,j={10ifGcontainsanedgefromnodejtonouleiotherwise For example, A0.2 stores whether there is an edge from node 2 to node 0 . Example 1: Check your answers: Write the adjacency matrix that generates the undirected graph illustrated abewe, Store the matrix as a 2d numpy' array of integers and assign it to the variable A. *grade (enter your code in this cel2 - DO NOT DELETE THIS LIME) A= np. A rray ([10,1,1,0],[1,1,1,01,[1,1,0,11,[0,0,1,0]1) You can use the function graph. draw_nat rix to make the graph from a given adjacency matrix: graph. draw mat rix(Ar show weights-False) Note that any nonzero value along the main diagonal results in a seif loog. In this example, the graph is undirected, so its edges do not have directicn. The adjacency matrix A at an undirected graph is always syonmetric; that is, AT=A. Graph Walks A walk of length k is a sequence of k+1 vertices and k edges between two nodes (including the start and end) that may repeat. 1 frem node 1 to itself since A1,1=1. Essentially, the adjacnncy matrix telis you if you can walk fram one node to another in one step. Discuss with your group: Trace the edges and count the number of walks of length k between the following nodes. a) node 2 to node 3:3x walks of length 2 b) node 2 to node 2: walks af length 3 c) node 1 to node 3 : Z walks of length 2 d) node 3 to node 1: w walks of lenegth 3 Check your answers: *grade ionter your code in this ceil - Do NOT DELETE THIS LINEj x=0y=3z=1y=2 Try this! A2=A+k2 Indead, tha antry (A2), represents how many ways wn can mowe from node j to nodn i via a walk af langth 2 (i.n. in twa stapa). Try this! Discuss the foliawing questiars with your group: 1. Use A2 to check if your answers from questions a) and c) abono were curract. 2. What would you need to co to verify youf answers from questions b) and dy? shaw_weightsmrue) The number of walks of length exactly k from node j to node i is by given by (Ak)i,j Example 2: print''The graph below shows the number of malks of length 1 between any two nodes') graphadras_ratrixid, show_weights=Truel The graph below shows the nurber of walks of length 1 between any two nodes [8) : print('The graph below shows the nunber of walks of tength 2 between any two nodes') graph. dram_natrix (BeB, show_we ights-True) print 'The graph beles shous the nuaber of walks af length 3 between any two nedes') graphndram_ndtrix (beBe8, shoN_weights=True) By inspecting the above plots, we tind that from node D to node 1 we have: - cone wakk of iengeht - zero waks of iength 2 waks of length 3 This occurs because when node 1 is resched, it must be lelt in the following step. So if we reach a node sooner than in the desired number of steps, haw can we adjust th We can add self-loops! Take a look at the graph for the identity matrix: 9] - graph, dran_natrix [np-eye\{4, dtype-int]\} Check your answers: Modify the matrix B by adding a self-lcop to each node ceven if there is already a self-loop present, in which case there will be entries 2 2). Store the modilied matrix in I 0] Agrade (enter your code in this cetl - Do wOr DeLete thIs LIME B1=np=array[[[1,1,1,81, [1,1,8,1], [1,8,2,6] [0,1,0,2]1? Note that by adding self-loops, Bi expresses the same pairs of cistinct nodes that may be reached via a walk of length 1 as does B. The difference is only in the numbe 1. graph.draw_natrixind Number of Steps in Walk In the previaus exampies we were picking arbitrary valuns of k far nur walks. What if we want to find the smallest value of k such that each node is connected to every other node? If such a k exists, we say the graph is fully connected. Lat's lack at a few scenarias here. In this first uxampln, all nodes are connected with anch ather. 2] I n=4 c=npones({n,n), dtype=int } graph.draw_nat rux\{C, shod_weights-True } For the example above, we can see that any nede can resch another node with a walk of length 1 , and hence the smallest value of k is k=1. Let's lock at this other axample (we use mumpy-eye to define matrices with is in the upper and lower diagonals) Check your answers: Modify the matrix O abave, such that each note can also more to itself. Store that as the variable Di. * grade (enter your code in this celi - Do NOT DElETE ThIS LIME) Di=np. array [[11,1,0,1,[1,1,1,0],[0,1,1,11,[,0,1,1]1] We can think af the ibentity matrix as counting walks af "length zero", since it takes zera maves to get fram a note to itself. By adding the ident ty nudes. arach.draw natrixidi, showeights-True\} We do not yet have a graph that is fully connected. That is, we cannot reach every node from any ather node via a walk af length 1. What if we want to consider the connections that can be reached with up to waks of length 2 ? Try it! Crate a matrix which reprusants waks of length at most 2 Store it as the variabla 0i2. Hint: Which matrix counts wales of length exactly 1? You'll need to use it to find the walks of Inngth exactly 2. Do you stil get entries that are zero, indicating that not all nodes can be reached from any noce in up to 2 steps? Did you gat a fully cannected graph when considering walks of length at most 2 ? Keep adding Dk until you find the necessary k value. In summary, every node of a connected graph G is connected to every other node via walks of length at most k when k is such that the matr I+k=1kGi dons not ecntain any 0 untries. This matrix captures the number af distinct walks of length at most k batwen each pair of nodes. Without I, the sum af matrices represents Edge-node Incidence Matrix Now, we consider directed graphs and define them according to their adjacency matrices. The edge-node incidence matrox M of the directed Mi,l=110ifedgeileavesnodejifedgeientersnodejotherwise where m is the number of edges and n is the number of nodes. Note that establishes an ordering on the edges. Ccnsider tha adjacency matrix belaw: Think about this: Why does the incidence matrix have 8 rows? A. components. Using this knawledgn, answer the following questian: Suppose that the nulspace of the incidence matrix af a graph is given by the following matrix: 100100100000101 What is the index of the node which is in a cornected component al by itselt? In the following cell, store your answar as lonety_index. 1: agrade (enter your code in this cell - Do not DELETE THIS LINE) I: nu11_42.shape[1] The number of nodes in each cornected component is given by the count of 1 entries in each rulspace coluimn. We can compute the columnwise sum of a nulspace matrix as follows: null_2, u [axis=9] The first cannected component camprisas 2 nudus while the second connectad component comprises 3 nudas. Social Network Analysis model several properties of the network. My Freceacek frienca on Tue 8 ea 2715.11,352011 CEST (htte:/fanw.kakacu-works,comjmytnetwork/weloome.htm) We can visualize the social network in a graph format: graph.draw_matrix(friends, shou_weights=False) Check your answers: the adjacency matrix. *grade (enter your code in this cell - DO NOT DELETE THIS LIME) Check your answers: How many people are in the largest friend group? Store this number as max_group_size *grade (enter your code in this cell - DO NOT DELETE THIS LINE) Meme Spread (Meme stolen from reddit.comirimathmemes) We will use a slightly larger graph of n=100 people, represented as an adjacency matrix. \[ \begin{array}{l} n=100 \\ \text { neme_network = graph.gen_randon_friends }(n, 0.98) \end{array} \] Here is the (quite large!) graph showing friend connectivity: graph.draw_matrix(neme_network, show_weights=False) Check your answers: How many frlend groups exdst in this network? Store that in ngroups. What is the size of each one of these groups? Save your results as a 1d numpy array nfriends_pergroup. How many people will receive the meme? Store that in receive_mene. a matrix A that are equal to 5, you could use np, whe re (A=5), *grade (enter your cade in this cell - DO NOT OELETE THIS LIME)
