The Dynamics of Large Sparse Graphs

Peter Boothe

This research has been done under the watchful, but not necessarily approving, eye of Andrzej Proskurowski with occasional assistance from Art Farley, Jun Li, and many others

Large Sparse Graphs

• Occur everywhere: internet, the interstate highway system, P2P overlays, web graph, social networks, dependency graphs, etc.
• We want to analyze these graphs for abstract concepts: robustness, reliability, efficiency, fairness
• large graphs (≥ 10000 nodes)
• sparse graphs (# of edges is o(n^1+ε) ∀ ε ≥ 0)

Dynamics

• These graphs are changing over time (some faster than others)
• How are their associated properties changing?
• Should we track the property? d(property)/dt? d²(property)/dt²?

Naturally Occurring Graphs

• These graphs are often small world graphs or power law graphs, which means we can leverage things developed for those arenas
• Small world
  • Average shortest path is low (6 degrees of separation, etc)
  • Omnipresent occurrence of these graphs is detailed in Small Worlds by Duncan Watts
• Power law
  • The degree distribution is power law
  • A non-trivial number of vertices have very high degree
  • most have a low degree

Sample Degree Distributions

Properties - Easy

• Not too hard to compute, but easy to construct cases where they are misleading:
  • Number of Nodes
  • Number of Edges
  • Mean/Median/Mode Degree
  • Degree distribution
  • Size of the graph after trees are trimmed
  • Clustering coefficient
  • Diameter
  • Eccentricity

Properties - Hard

• Computationally painful, but often very informative:
  • Average shortest path length
  • Average number of shortest paths that pass through a given vertex
  • Average number of shortest paths that pass through a given edge
  • Average path length
  • Average number of paths that pass through a given vertex
  • Average number of paths that pass through a given edge
  • Size of the largest 2-connected component
  • Size of the largest k-connected component
  • Clusters/cliques
  (Note how many good measurements are too hard?)

Properties - Weird

• Std. deviation of the number of edges crossing a random 75%/25% partition of nodes
• Std. deviation in the % of nodes that need to fail before a particular node can't connect to 25% of the graph
• Expected time for a random walk to get from node a to node b in the graph

(these are conceptually kind of weird, but it's not clear whether they are easy or difficult to compute)

Weird Metrics Justified

A Case Study: The Internet

• A large, sparse, dynamic graph
• 8 years of data available from Routeviews
• In the past 8 years the internet has changed a lot
• Its design documents articulate specific goals - survivability, robustness, ease of connection
• Social significance if we find that something strongly negatively affected it
• A good test will be if our metrics indicate more than "it got bigger"

Let's watch some metrics...

• Size
• Relative size of the graph after removing all trees
• Clustering Coefficient
• Proportion of the graph that is leaves
• Characteristic Path length (average shortest path length)

How big is it?

How much of it is not a tree?

What is its Clustering Coefficient?

CC of the non-tree part

Proportion of leaves

Characteristic Path Length

Lessons learned

• Real life data is noisy, and this is especially noisy
• Around mid 2001, something happened that affected the shape of our graphs
• It would be nice to have some error bars
• Even O(n³) is prohibitively computationally expensive unless you are really sure of yourself
  (it took a 64+ CPU cluster much more than 72 hours to produce the path length graph - thanks Prof. Malony!)
• We need metrics that are computationally tractable

Future directions

i.e. What am I doing now...

• Conducting a survey of FCC rule changes and major economic events in 2001
• Figuring out how to put error bars on the graphs
• Trying to develop a sampling approach to measuring these properties
• Trying to find more and more of the weird properties to measure, as they seem most amenable to a sampling approach
• Developing another test case with the Gnutella network, thanks to Dan

Summary

• Large sparse dynamic graphs are everywhere
• Characterizing their dynamism is tricky
• Easy things seem too uninformative
• Informative things seem too hard
• Perhaps statistics can help us
• The internet went a little weird in mid 2001, but seems okay again

Discussion

• Any good ideas for relevant metrics?
• Any worries about these analysis techniques?
• Any questions at all?

-- Peter Boothe
peter@cs.uoregon.edu
Slides by S⁵