Metrics
Some Possible Metrics that we have decided to look at include:
Static metrics on the graph (these are properties that are inherent to the network):
(1) How many results does the average query return when x% of the nodes have failed (credit Beverly for this)
(2) What is the largest connected component in Gnutella after x% of the nodes have failed
(3) Finding the radius and diameter of the graph using the eccentricity. The eccentricity of a node, v is defined as the distance to the furthest node of that graph. The radius is the minimum of all the eccentricities over all vertices. The diameter is the maximum of all the eccentricities over all vertices.
(4) Find the center of the graph (can use notion of status, cutting center, or some other notion of center).
(5) Look at metrics associated with the adjacency and the distance matrix of the graph (such as the eigenvalue).
(6) Compute the distance degree sequence, dds, of the graph. di(v) is the number of nodes at distance i from v. Hence, the dds of the graph is (d0(v), d1(v), d2(v), …, de(v)(v)).
(7) What proportion p of the most-connected (using whatever notion of most-connected that you want) nodes that you need to look at for all nodes to be covered in some certain number, say n, hops?
Some metrics that could be used in our algorithm to redesign the graph (computing algorithms to keep the graph robust is really up to us; we can use any combination of the static metrics to derive algorithms):
(1) Find the minimum spanning tree of the graph and remove some nodes to create a sort of backbone for the Gnutella protocol.
(2) Try to find all the cliques of the graph and make sure that the cliques have connections.
(3) Using some kind of a max flow / min cut algorithm to redesign our graph.