Category Archives: General Graphs

The Structure and Function of Complex Networks. Newman. SIAM Review 2003

Like his other paper I looked at, this is an arxiv version, so not sure how different it is from the journal version.

This paper is a much longer paper than the other one, and seems to be more of a survey, which is good for my purposes at the moment.

  1. Focus on study of networks has changed recently, as networks of interest have exploded in size
  2. Paper is concerned with examining networks from many perspectives – biology, social dynamics, www
  3. Lists recommended books on the subject
  4. Power law in many natural networks
  5. Mentions random graphs of Erdos and Renyi, and that many real-world graphs do not have the properties that arise in the model they proposed
  6. Geodesic distance is shortest path distance
  7. A harmonic mean is the reciprocal (1/x) average value of reciprocal values.  This has the benefit of making infinite values zero.  This is useful because when computing average path length for a graph if there are two points that can’t be connected the entire average becomes infitine
  8. The “small world effect” that most items can get from source to destination quickly is a natural property of graphs, because the number of reachable vertices generally grows with path length from the source
    1. <On the other hand, you can’t do blind search this way because of the exponential blowup, so pruning is critical>
  9. This effect has taken a more exact definition recently, with it commonly being formally described as a network where average path length increases logarithmically (or slower) in the number of nodes, for a network of fixed mean degree
    1. This property has been shown for many types of networks (many citations)
  10. Idea of transitivity (which was the focus of Granovetter’s paper), where if A and B are friends, and A and C are friends, there is an increased likelihood that B and C are friends
  11. There is a measure of the proportion of transitive connections (A+B, B+C, A+C), some graphs have a property that as they grow large this probability asymptotes to some nonzero value, but others (such as completely random networks) don’t have this property and approach 0
  12. Another common descriptive measure of graphs are the distribution over degree for each node. Due to large skew that commonly arise in natural graphs, it is often hard to measure this number from sampling uniformly, because a very small number of nodes will drastically alter the mean
    1. <The median is probably more easy to measure accurately then?>
    2. Propose a binning scheme that has variable width bins so items are expected to fall into each bin at equal rate
    3. Or doing CDFs wrt degree being greater than a value
  13. Power laws and exponential distributions are “particularly easy to spot experimentally.”
  14. Graphs with power-law degree distributions are called “scale-free networks”
    1. <Not sure what is “scale free” about them though, the paper says the degree distributions are scale-free.  Does that just mean that the histogram of degrees doesn’t characteristically change as the graph grows?>
    2. <Wikipedia says these networks are robust to failure – removing a node often has a number of well-connected backup nodes>
  15. Moves on to discussion of maximum degree, and likelihood that a graph has a particular max degree
  16. A good approximation of the expected value of maximum degree is the modal value <of the degree?>
  17. Briefly mentions Markov graphs <which seem different from Markov chains?>
  18. In small world networks, topology corresponds to some feature, and then there are usually a few occasional long distance hops
    1. For example social networks are often clumped around where you grew up, but you might know some far away people from college, work, etc
    2. The most commonly studied topology is the 1-d ring formation, that is then perturbed in some way, so graphs can range between a ring to a pure random graph depending on perturbation
  19. <Stopping here, may come back to this work later.  A nice survey, but part of the focus seems on topics not so relevant at the moment.>