Review of Linked: The New Science of Networks

As I’ve noted previously, I’ve been exploring the science of complexity these last few months, trying to get a feel for the different subfields and how it can be applied to various real world issues. One of the areas in the field of Complexity is that of Network Science.

Linked:  The New Science of Networks by Albert-Laszlo Barabasi is a useful overview of the field.  It’s an easy read that covers a broad amount of the field and is a good layman’s introduction to network theory.  He shows that the world around us can be described in terms of Networks, and comments on how they are formed, what forms they take, and how they grow.  Note:  This is one of my longer reviews, and I left a lot out!

Barabasi starts off with one of the most famous network problems of history: the bridges of Konigsberg.  He shows how the problem can be solved using nodes and links, which was discovered by Leonhard Euler.  This segues into a discussion of graph theory and its history. Graph theory describes a network as a collection of links and nodes.  How to connect these nodes and the relations between them, as well as how the network grows in the first place, is the focus of the book.  Hr runs through a history, starting with random networks which although helpful in formulating basic laws, do not really describe real world networks.  He describes Stanley Milgram’s famous six degrees experiment and how Barabasi and his team researched it and found similarities in other networks of small worlds, where any node can reach any other node in a small number of jumps no matter how large the network.  He also talks about the strength of weak ties.

Clustering – each of us has a small number of close friends – is a key structure in networks and Barabasi talks about these and how a few links between them reduces the length between distant nodes.  Still, the nodes are all egalitarian and this is not how it works in real life.  Barabasi refers back to Malcolm Gladwell’s book The Tipping Point, talking about connectors and hubs – which means they have more than the average number of links which the egalitarian model doesn’t allow.  Hubs are apparent in the Kevin Bacon Game and in airline networks, among others.  The distribution follows a Power Law rather than a bell curve.  These networks are “scale-free” since there is no average node.

A discussion Of Pareto’s 80 / 20 law and a discussion of “phase transitions” follows, and how understanding them helps us to see how hubs appear in networks.  He notes that networks grow and are not static, and that counterintuitively just because a hub is old doesn’t mean it will get the most links – although that does play a role.  There is “preferential attachment” – nodes prefer to link to nodes that already have a lot of links.  Google today is a perfect example.  In other words, the rich get richer…

A basic prediction of scale-free networks is that the first mover will have an advantage in forming the most links.  In real life networks, however, this isn’t the case.  This is because contrary to the assumption that all links are the same, they instead are all different with different intrinsic properties.  This is defined as fitness.  More fit nodes will end up with more links.  This is complementary to preferential attachment which only examines the number of links.  It also shows that the number of links is therefore independent of when the node joins the network.

In an intriguing chapter,  Barabasi then turns to the weaknesses of a highly-interconnected network.  Most networks in nature are highly interconnected and are also highly robust in that the failure of one component won’t take down the whole network.  Barabasi and his team investigated this phenomenon.  They found that for these networks, removing a large number of nodes typically had little or no effect on the functioning of the network.  This is due to the hubs model – removing nodes randomly eliminates a large number of tiny nodes and not very many hubs, which preserves the integrity of the network since the tiny nodes aren’t very interconnected.  However, if the Hubs are specifically AND simultaneously targeted, the network will quickly break apart.  This, then is the primary weakness of these networks.  they are not vulnerable to accident, but are highly vulnerable to attack.  This applies to both man-made and natural networks from the internet to food webs.  Cascading failures can happen when the load from a failed node is shifted to other nodes that are unable to handle the load, whereupon they fail and pass it on to yet more nodes that cannot handle the load, and so on.  This is what happens during blackouts and rolling power failures and in denial of service attacks on routers.  These happen in dynamic networks and still need researched.


Using these findings of network theory, Barabasi discusses the spread of ideas, fads, and viruses, using as examples AIDS, computer viruses, jokes, and hybrid corn.   Malcolm Gladwell covers some of this in The Tipping Point.  One of the more surprising findings was that the rate of spread does not depend on virulence.  The solution is to target the cures to the hubs.  In AIDS, this would involve targeting the people who are most likely spreading the virus (those with many partners) as opposed to those who don’t (people with only one or two partners).  There are, obviously, ethical questions associated with this course of action.  Barabasi also examines the resilience of today’s internet (the physical infrastructure as opposed to the World Wide Web).  Instead of being a mesh as it was originally designed inj the 1950s, the Internet is more of a hub and spoke model that has grown organically.   This is why the Internet, too, is vulnerable to an attack on Hubs, rather than being perfectly resilient.  It also enables “parasitic computing,” where your computer can be “hijacked” and used to perform functions for a computer thousands of miles away – this is done with spam, for example.  It can also be used voluntarily, as in SET@Home or research into protein-folding.  Another question asked is that as the Internet continues to grow across the planet as it is connected to computers and sensors and cell-phones, will it eventually become self-aware?

One surprising thing about the World Wide Web is how difficult it can be to find information, even though theoretically the amount of information is limitless.  Google, surprisingly, indexes less than 25% of all the pages out there!  Worse yet, despite the fact that most webpages are separated by an average of nineteen links, due to the architecture of the Web, only 24% of pages can be reached by surfing from one to the other.  This is due to the structure of the Web: it is a Directed Network.  Barabasi describes this in detail.  Also, due to these properties, sections of the web can be partitioned off – providing a tool for control of access.  However, the topology of the Web as described here is much more effective than a government at keeping a website hidden!  Barabasi notes that the Web is little understood and a great deal more time and attention should be paid to understanding it.


Networks are common, and especially so in biology.  Barabasi also discusses how network theory can be applied to business and the economy.  He posits that to compete organizations need to go from a tree hierarchy to a web or network instead.  They will also participate in ever interconnected webs with suppliers and customers.  He shows how members of boards of corporations are ever more interconnected with hubs – 20% of them serve on more than one board.  The degree of separation of boards of directors is only three!


In conclusion, Barabasi summarizes:  “…though real networks are not as random…as envisioned, chance and randomness do play an important role in their construction.  Real networks are not static, as all graph theoretical models were until recently.  Instead, growth plays a role in shaping their topology.  They are not as centralized as a star network is.  Rather, there is a hierarchy of hubs that keep these networks together, a heavily connected node followed by several less connected ones, trailed by dozens of even smaller nodes. ”  There is no center, or controller, in the middle of the network that could be removed to destroy the web.  They are instead self-organized with emergent behavior.  Al-Qaeda is an example of a web organization, which is why the United States military – a hierarchical tree organization – has had trouble battling it.  Barabasi suggests that “We must eliminate the need and desire of the nodes to form links to terrorist organizations by offering them a chance to belong to more constructive and meaningful webs.”  We can do this by attacking “…the underlying social, economic, and political roots that fuel the network’s growth.”  Barabasi sees the future of network theory as understanding complexity and “move beyond structure and topology and start focusing on the dynamics that take place along the links.”


Advertisements

What is Complexity: Part 1

A while ago, I noted that one of the subjects I’ve been exploring this year is that of Complexity.  I’ve read a number of books on the subject, and the first thing I’ve learned is that there is no commonly agreed definition of Complexity itself!  It’s a very wide ranging, interdisciplinary field.  Wikipedia has an excellent article on it, and I encourage you to check out the accompanying chart because it will give you a good overview of all the different areas included under the heading of Complexity!

So, as I’ve said, I’ve read several books now, and Deep Simplicity: Bringing Order to Chaos and Complexity by John Gribbin is one of the better overviews of the field.  I first encountered Gribbin’s books twenty years ago with his “In Search Of” titles, and I knew he was a skilled writer that can take a complex subject and make it so non-experts can understand without “dumbing down” the material, and he again accomplishes this in Deep Simplicity.

Gribbin begins with a short history that takes the reader from the early days of science and the Greeks to the beginning of the Twentieth Century, covering the development of Physics, Calculus, and Chemistry and how these lead to laws that could describe the world, as well as the phenomenon of Entropy – some processes don’t run in reverse spontaneously, unless you add energy to the system.  Unfortunately, adding energy to a closed system increases the entropy outside the closed system (i.e., the Universe!) and so entropy always increases.

He then moves on to a discussion of Chaos Theory.  Basically, the idea of chaos is this:  Given a system, very small changes in the starting conditions can lead to very large changes in the outcome.  For example, if you take two planets and calculate their orbits around each other, you will end up with a reasonably accurate systems if you run it forward a few hundred years.  If you add a third planet, however, there is no way to tell where the system will end up.  A more well known version is the so-called “Butterfly Effect” of the weather.  Forecasters can be reasonably accurate a few days ahead, but anything past a week is simply too complex to forecast accurately.  (Note that Anthropogenic Global Warming advocates insist that climate can be predicted 50 years in advance…)

Gribbin then talks about one of the most well-known equations in chaos theory:  the Logistic Equation, which discusses how population changes over time.  Gribbin uses this to demonstrate some common properties of Chaos.  In addition to the “sensitive dependence on initial conditions” noted above, Chaos curves split – a process called bifurcation – and then countinue to double until they hit a point where their behavior becomes (what else) “chaotic.”  I am very much oversimplifying here, but this is a deep subject and it’s hard to cover in a blog post what Gribbins uses an entire book to try to do!  Gribbin also covers cellular automata and fractals as examples of complex behavior arising from simple conditions.

One key item to note is that a completely chaotic system is not complex, and neither is a simple system.  Complexity lies somewhere in the middle.

Having laid this foundation, Gribbins now describes Complexity Theory.  He shows how complex behavior can arise in a system with two plates with a thin layer of liquid between them – add heat, and convection cells arise (rotating strips of water).  Add more heat, and eventually you get chaotic behavior, but in between equilibrium and chaos is the complex region with the convection cells.  You can also see this with your faucet – when it’s off, you have equilibrium.  Turn it on a little, you get a smooth stream of water.  A little more, and the water starts getting complex with twists.  On all the way, and it’s chaotic.

Gribbins also covers the concept of self-similarity – take a coastline, for example.  When you see it from space, it has a jagged appearance.  From the air, a mile up, still jagged, but on a smaller scale.  Walking along it, still jagged.  And so on.  Whatever scale you view it at, it’s still jagged and looks the same.  You can never really find the exact length of coastline because you can always reduce the scale and make it longer.  (Those of you with a Calculus background: It does approach a limit, of course, but I’ll save that for another day!)  In addition Gribbin talks about power laws – where the distribution on a graph follows a curve.  An example is the population of U.S. cities – New York City is obviously the largest, but the next largest comes in at about one-half of New York’s size.  And the third largest is about one-half of the second…and so on.  Power laws, surprisingly, can be found in many places in nature – complexity theory is exploring why.  Gribbins than describes network theory and how the dynamics of a system can be described by it.

Now, Gribbins gets to his objective, which is to show how complexity can be used to discover the properties of living systems.  It shows how a species can change through time based on outside influences, as well as how the operations inside a cell can be described by complexity and network theory.  In his final chapter, Gribbins talks about how this all relates to Gaia theory (Note:  Gribbins sees this as describing a COMPLEX SYSTEM, not as the earth being a living goddess or even one living creature).

Overall, the book was decent introduction to complexity, chaos, and networks and how they can apply to many areas.  This book was a little too focused on the biological end, though, and I think that Melanie Mitchell’s book Complexity: A Guided Tour is a better overview for that reason.  But Gribbins is very good at taking a “complex” subject and making it easy for the layperson to understand.

Note:  If you’re a Christian like me, the book is still worth a read.  Even if you don’t subscribe to macroevolutionary theory or the Theory of Evolution by Natural Selection, you can still get quite a bit out of this book, and I think it has a lot to say about microevolution!

Continue reading “What is Complexity: Part 1”

Coming attractions

Been working much overtime at the moment, but here’s what I’ll be posting on as the year goes by…

I’ve always had an eclectic range of interests. I’m trained and have worked as a mechanical engineer, but also have an MBA and read widely in many fields. Lately, I’ve been consulting with the Matthew Ridgway Center for International Security Studies on tracking nuclear weapons smuggling.

So, some things I’ve been into in the past year:

1.) Mathematics. I’ve gone deeper into algebra, geometry and calculus. I’ve touched on abstract algebra and topology. I’ve even done some reading in chaos theory.

2.) Complexity theory – this applies across a wide range of disciplines such as social networks and physics. It may be applicable to terrorist networks.

3.) The future of work – outsourcing, of course, but also globalization, economics, and telecommuting.

4.) the future, period. Bob Kaplan’s gated communities, Richard Florida’s creative class and Great Reset.

5.) Economics and the stock market – are we really in a recovery or just still sliding into Great Depression 2?

6.) Terrorists and nuclear smuggling – as part of my gig at Pitt.

7.) How do many of the above subjects tie into the future of Pittsburgh (which is where I live)? How does the concept of city states apply, and is it a viable model for the future for the region?

These are all subjects I hope to keep exploring, and I hope to write more about them here on my blog.