opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp


Planet Lisp



Talking Points Memo

This Modern World

Working for Change

Other home


Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006


Linked: the New Science of Networks (chapters 1 - 10)
Saturday, May 22, 2004

Linked is one of those nice "popular science" books -- easy to read but missing most of the details. I had heard that Barabasi's book was full of self-congratulatory praise but I haven't found that to be true so far. To be sure, there is a good deal of personal anecdote and his groups research is featured more than others. This, however, is par for the course for these kind of books.

Overall, Linked is fun to read and informative. I've got the sense that I'm learning about the important directions in graph / network theory. The tone is a bit preachy at times but that doesn't detract too much for the science. In any case, here is my summary of the first 10-chapters:

Chapter 1: Networks are everywhere

Chapter 2: Euler starts graph theory; Erdos & Renyi invent the theory of random graphs.

Chapter 3: Most networks are not random. They are instead "Small world" networks: you can get there from here and you can do it quickly.

Chapter 4: Watts & Strogatz's clustering theory provides one explanation for small-world networks: space matters. If a network has an initial overlay of links, then adding (relatively) few random links will make it small-world.

Chapter 5: Real networks have "hubs": some nodes have many (many, many) more links than others. We call these networks "scale-free".

Chapter 6: (Many) networks have power laws relating a variety of their properties (e.g., the number of links for each node). This can't be explained by either random graphs or by Watts-Strogatz graphs.

Chapter 7: Real networks also exist in time: they grow (and decay) and the addition of links is not random. If you add growth and "rich get richer" properties to a network, you get power laws. There has been a lot of research examining different models and their properties (e.g., death, internal links, re-linking, non-linear effects and so on).

Chapter 8: Not all nodes are the same; add fitness to the network and it gets even more interesting. Some networks can behave like a Bose-Einstein condensate -- the winner takes all. Microsoft is a (potential) example of this in the business world.

Chapter 9: Scale free networks are robust against topological failures but vulnerable to targeted attacks. You can remove nodes or links randomly without worrying, but if you take out a hub, things go bad fast.

Chapter 10: The spread of ideas, disease, etc. all follow similar models but the accuracy of these models depend on the underlying network by means of which the thing spreads. Scale-free networks do not behave like other networks. In particular, even things with a very low spreading rate may have no critical threshold (the level at which the traditional models predict that the thing won't spread).


Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006