Given the following graph in Figure A1. < (1) (2 points) Find out the bridges and...

     

Transcribed Image Text:

Given the following graph in Figure A1. < (1) (2 points) Find out the bridges and local bridges. < (2) (2 point) Find all the shortest paths between nodes B and F. < (3) (2 point) What is the diameter of the graph? (4) (2 points) Calculate the neighbourhood (edge) overlap values for edges (E, G). < ( 2 E D A F G C Figure. A1 B H Suppose we have the initial set S including six nodes in Figure A2. < (1) (2 points) we say that a node X is a local gatekeeper if there are two neighbors of X, say Y and Z, that are not connected by an edge. List all local gatekeepers in S. < (2) (4 points) If we add two nodes G and H to the network by BA algorithm with m=2, what's the probability that there is an edge between nodes G and H? H F A E B D C Figure. A24 new nodes G H 2 Given the following graph in Figure A3. < (1) (2 points) Calculate cluster coefficient values for nodes F. < (2) (2 points) Given a graph G, the dual construction can create a new graph G' based on the following rules: < (a) If (X, Y) is an edge of G, then XY is a node of G' (note that XY and YX are the same node in G'). < (b) If two edges in G share the same point, their corresponding nodes in G' are linked. More specifically, if edges (X, Y) and (X, Z) exist in G, nodes XY and XZ in G' are connected because they have a common point X in G. < Given the graph in Fig. A3, draw a new graph by applying the above dual construction. < (3) (2 points) Given a star with n edges (i.e., a central node and n leaf node linked with the central node, and n 2), what is the graph derived from the above dual construction? (notice that you do not need to draw your answer, just describe your answer) < C D F B Figure. A3+ E A (1) In a small-world network, how does the presence of a few highly connected nodes (hubs) influence the average path length, thus maintaining the small-world property? (2) . Are the graphs in Figure A4(2) isomorphic? If yes, show one possible one-to-one mapping between their nodes. < A B Loo D E 2 C 1 Figure. A4(2) < 4 2 5 6 3 Given the following graph in Figure B1. (1) (2 points) What are the nodes with the highest degree centrality? Explain your answer. < (2) (4 points) What are the nodes with the highest betweenness centrality? Explain your answer. < A D TI F B E Figure B1 H G Given the following graph in Figure A1. < (1) (2 points) Find out the bridges and local bridges. < (2) (2 point) Find all the shortest paths between nodes B and F. < (3) (2 point) What is the diameter of the graph? (4) (2 points) Calculate the neighbourhood (edge) overlap values for edges (E, G). < ( 2 E D A F G C Figure. A1 B H Suppose we have the initial set S including six nodes in Figure A2. < (1) (2 points) we say that a node X is a local gatekeeper if there are two neighbors of X, say Y and Z, that are not connected by an edge. List all local gatekeepers in S. < (2) (4 points) If we add two nodes G and H to the network by BA algorithm with m=2, what's the probability that there is an edge between nodes G and H? H F A E B D C Figure. A24 new nodes G H 2 Given the following graph in Figure A3. < (1) (2 points) Calculate cluster coefficient values for nodes F. < (2) (2 points) Given a graph G, the dual construction can create a new graph G' based on the following rules: < (a) If (X, Y) is an edge of G, then XY is a node of G' (note that XY and YX are the same node in G'). < (b) If two edges in G share the same point, their corresponding nodes in G' are linked. More specifically, if edges (X, Y) and (X, Z) exist in G, nodes XY and XZ in G' are connected because they have a common point X in G. < Given the graph in Fig. A3, draw a new graph by applying the above dual construction. < (3) (2 points) Given a star with n edges (i.e., a central node and n leaf node linked with the central node, and n 2), what is the graph derived from the above dual construction? (notice that you do not need to draw your answer, just describe your answer) < C D F B Figure. A3+ E A (1) In a small-world network, how does the presence of a few highly connected nodes (hubs) influence the average path length, thus maintaining the small-world property? (2) . Are the graphs in Figure A4(2) isomorphic? If yes, show one possible one-to-one mapping between their nodes. < A B Loo D E 2 C 1 Figure. A4(2) < 4 2 5 6 3 Given the following graph in Figure B1. (1) (2 points) What are the nodes with the highest degree centrality? Explain your answer. < (2) (4 points) What are the nodes with the highest betweenness centrality? Explain your answer. < A D TI F B E Figure B1 H G

Answer rating: 100% (QA)

Solution Bridges If there is an edge in the graph joining two nodes XY is a bridge if deleting the e... View the full answer