2011-03-21: Grasshopper, prepare yourself. It is time to speak of graphs and digital libraries and other things.
Announcing the publication of an Old Dominion Computer Science Department technical report and an homage to Davide Carradine, Keye Luke and the television series Kung Fu.
"Grasshopper."
"Yes, Master Po?"
"Grasshopper, you have passed many tests of strength, agility and stamina. But that is not enough. There are other trials you must pass before you are permitted to attempt to lift the fiery brazier. I will ask you a series of questions.
“Let us begin. What is a graph?"
"Master; a graph is a mathematical construct made of objects that may, or may not be connected to each other."
"Grasshopper, how does a graph relate to digital libraries and the world where we live?"
"Master; a graph is composed of nodes (or vertices) that can be connected in a pairwise manner with edges (or arcs). In the world of Facebook, people take the place of nodes and the connection that is made when one person “friends” another creates an edge. In the World Wide Web, pages can be nodes and navigational links can be edges. In digital libraries, a complex digital object, with all its contents and metadata, can be a node and the URIs of other digital objects are its edges. In our Shaolin temple, you and I can be nodes and your teachings are our edge."
"Grasshopper, explain what you mean by objects that in a graph may or may not be connected to each other."
"Master; one can think of the Internet as a graph made up of routers as nodes and cables as edges. If a cable between two routers is severed then the Internet can still function. Not as fully as before, but it will still function."
"Grasshopper, are you saying that a graph that is not connected can still function, al beit at a lower level?"
"Yes, Master."
"Grasshopper, I have in one hand a graph and in the other a hira shuriken. I will answer three questions and then you must cause as much damage as you can to the graph."
"Master; may I see the graph?"
"No. That is one question. I will tell you the name of one node. It is called 5."
"Master; to whom is 5 connected?"
"5 is connected to 4, 6, 8 and 9. That is two questions."
"Master who is connected to 4, 6, 8 and 9?"
"4 is connected to 2, 3 and 5. 6 is connected to 5, 7 and 11. 8 is connected to 2, 5 and 7. 9 is connected to 5 and 10. That is three questions. Now Grasshopper, you must select one node to remove with the shuriken."
"Master, I choose to attack node 5 because it has a the highest a 1 as its vertex centrality betweenness, while all others are far less than 0.5."
"Grasshopper, you have chosen wisely. Now, when node 5 is removed, how much damage has been done to the graph you have discovered?"
"Master, the damage is 0.29 after the first deletion."
"Grasshopper, here is the total graph. What will be the damage to the
discovered graph and to the total graph after the 5th deletion if I were to tell you the friends of the friends of the friends of 5?"
"Master, the damage to the discovered graph would be 0.89 and 0.68 for the total graph."
"Grasshopper, you have answered well. How and where did you learn these things?"
"Master; I read the technical report: Connectivity Damage to a Graph by the Removal of an Edge or a Vertex.”
“Grasshopper, tell me more about this report.”
"Master; it has an abstract that reads:
“The approach of quantifying the damage inflicted on a graph in Albert, Jeong and Barab´asi’s (AJB) report “Error and Attack Tolerance of Complex Networks” using the size of the largest connected component and the average size of the remaining components does not capture our intuitive idea of the damage to a graph caused by disconnections. We evaluate an alternative metric based on average inverse path lengths (AIPLs) that better fits our intuition that a graph can still be reasonably functional even when it is disconnected. We compare our metric with AJB’s using a test set of graphs and report the differences. AJB’s report should not be confused with a report by Crucitti et al. with the same name.
“Based on our analysis of graphs of different sizes and types, and using various numerical and statistical tools; the ratio of the average inverse path lengths of a connected graph of the same size as the sum of the size of the fragments of the disconnected graph can be used as a metric about the damage of a graph by the removal of an edge or a node. This damage is reported in the range (0,1) where 0 means that the removal had no effect on the graph’s capability to perform its functions. A 1 means that the graph is totally dysfunctional. We exercise our metric on a Collection of sample graphs that have been subjected to various attack profiles that focus on edge, node or degree betweenness values.
“We believe that this metric can be used to quantify the damage done to the graph by an attacker, and that it can be used in evaluating the positive effect of adding additional edges to an existing graph.”
“Grasshopper, where did you find this report?”
"Master; I found it at: http://arxiv.org/abs/1103.3075"
"Grasshopper, go and prepare for your next trial."
"Yes, Master."
Dr. Michael Nelson played the part of the Master Po. The part of Grasshopper is poorly played.
Chuck Cartledge
"Grasshopper."
"Yes, Master Po?"
"Grasshopper, you have passed many tests of strength, agility and stamina. But that is not enough. There are other trials you must pass before you are permitted to attempt to lift the fiery brazier. I will ask you a series of questions.
“Let us begin. What is a graph?"
"Master; a graph is a mathematical construct made of objects that may, or may not be connected to each other."
"Grasshopper, how does a graph relate to digital libraries and the world where we live?"
"Master; a graph is composed of nodes (or vertices) that can be connected in a pairwise manner with edges (or arcs). In the world of Facebook, people take the place of nodes and the connection that is made when one person “friends” another creates an edge. In the World Wide Web, pages can be nodes and navigational links can be edges. In digital libraries, a complex digital object, with all its contents and metadata, can be a node and the URIs of other digital objects are its edges. In our Shaolin temple, you and I can be nodes and your teachings are our edge."
"Grasshopper, explain what you mean by objects that in a graph may or may not be connected to each other."
"Master; one can think of the Internet as a graph made up of routers as nodes and cables as edges. If a cable between two routers is severed then the Internet can still function. Not as fully as before, but it will still function."
"Grasshopper, are you saying that a graph that is not connected can still function, al beit at a lower level?"
"Yes, Master."
"Grasshopper, I have in one hand a graph and in the other a hira shuriken. I will answer three questions and then you must cause as much damage as you can to the graph."
"Master; may I see the graph?"
"No. That is one question. I will tell you the name of one node. It is called 5."
"Master; to whom is 5 connected?"
"5 is connected to 4, 6, 8 and 9. That is two questions."
"Master who is connected to 4, 6, 8 and 9?"
"4 is connected to 2, 3 and 5. 6 is connected to 5, 7 and 11. 8 is connected to 2, 5 and 7. 9 is connected to 5 and 10. That is three questions. Now Grasshopper, you must select one node to remove with the shuriken."
"Master, I choose to attack node 5 because it has a the highest a 1 as its vertex centrality betweenness, while all others are far less than 0.5."
"Grasshopper, you have chosen wisely. Now, when node 5 is removed, how much damage has been done to the graph you have discovered?"
"Master, the damage is 0.29 after the first deletion."
"Grasshopper, here is the total graph. What will be the damage to the
discovered graph and to the total graph after the 5th deletion if I were to tell you the friends of the friends of the friends of 5?"
"Master, the damage to the discovered graph would be 0.89 and 0.68 for the total graph."
"Grasshopper, you have answered well. How and where did you learn these things?"
"Master; I read the technical report: Connectivity Damage to a Graph by the Removal of an Edge or a Vertex.”
“Grasshopper, tell me more about this report.”
"Master; it has an abstract that reads:
“The approach of quantifying the damage inflicted on a graph in Albert, Jeong and Barab´asi’s (AJB) report “Error and Attack Tolerance of Complex Networks” using the size of the largest connected component and the average size of the remaining components does not capture our intuitive idea of the damage to a graph caused by disconnections. We evaluate an alternative metric based on average inverse path lengths (AIPLs) that better fits our intuition that a graph can still be reasonably functional even when it is disconnected. We compare our metric with AJB’s using a test set of graphs and report the differences. AJB’s report should not be confused with a report by Crucitti et al. with the same name.
“Based on our analysis of graphs of different sizes and types, and using various numerical and statistical tools; the ratio of the average inverse path lengths of a connected graph of the same size as the sum of the size of the fragments of the disconnected graph can be used as a metric about the damage of a graph by the removal of an edge or a node. This damage is reported in the range (0,1) where 0 means that the removal had no effect on the graph’s capability to perform its functions. A 1 means that the graph is totally dysfunctional. We exercise our metric on a Collection of sample graphs that have been subjected to various attack profiles that focus on edge, node or degree betweenness values.
“We believe that this metric can be used to quantify the damage done to the graph by an attacker, and that it can be used in evaluating the positive effect of adding additional edges to an existing graph.”
“Grasshopper, where did you find this report?”
"Master; I found it at: http://arxiv.org/abs/1103.3075"
"Grasshopper, go and prepare for your next trial."
"Yes, Master."
Dr. Michael Nelson played the part of the Master Po. The part of Grasshopper is poorly played.
Chuck Cartledge
Comments
Post a Comment