emergent order
What do the Internet, social networks, viruses, human cells, Hollywood, the nervous system and ecosystems have in common?

    



Key concepts

  • Networks, Small Worlds, Emergence/Emergent Order, Hidden Order, Synchrony/Spontaneous Order, Self-organization/decentralized order, Chaos, Complexity, Catastrophe, Criticality, Complex adaptive systems
  • What is COMPLEXITY? Consider a network or web of nodes, where the nodes could be people, events, computers, airports, cities, etc. The network increases in complexity with an increase in some attributes of nodes such as:
    • NUMEROSITY: the number of nodes
    • VARIETY: the types of nodes in the web
    • CONFIGURATIONS: the state a node can assume
    • DEPENDENCY: the extent to which the state or configuration of a node is dependent on the state of other nodes in the web
    • RANDOM EXTERNAL EVENTS
As the numerosity, configurations, variety and dependencies among nodes increase, so does the complexity of the network. E.g. of light bulb array -- numbers, variety (colors), configurations (on and off), dependency (various).
  • Reductionism vs. Complex networks (see Emergence)
  • Network or web: A collection of interconnected nodes.
  • Node: a individual member --person, computer, organism, neuron, air terminus, etc. -- of a network
  • Degree of separation: the number of steps it takes to get from one node to another in a network.
  • Network "diameter"
    • This is the average "distance" or "degree of separation" between any arbitrary pair of nodes in a web.
  • Small world
  • Six degrees of separation: the putative expected number of nodes between any arbitrary pair of individuals in the world
  • Hub
    • Nodes that are connected to relatively large numbers of other nodes are considered "hubs"
    • Hubs are very important. A random attack on a network will cause little harm. A coordinated attack on the key hubs can bring down the network
  • Clustering: In many networks, such as human social networks (e.g., a family), nodes tend to cluster together. Thus in the network of students at BSU, there are many sub-groups of students who have frequent or intense interactions within the members of the group. In an ecosystem, strong bonds also exist among specific predators and prey.
  • Strong and weak links
    • Links within node clusters are considered "strong", representing a high frequency or intensity of interaction.
    • Links between nodes located in two different clusters (or between a member node in a cluster and a node outside of a cluster ) -- e.g., two different nuclear families -- tend to be less intense or frequent and are termed "weak".
    • Large networks are often made up many separate node clusters. These node clusters are connected by weak links.
    • The network is held together by weak links. The network can survive the loss of random strong links but will collapse with the loss of weak links. Hence, weak links are more important than strong links. Consider for example the road network within Bangalore and across India. The local streets of Bangalore are strong links and the highways linking Bangalore to other cities are weak links. The network of roads in India can survive the loss of some local Bangalore streets, but will be seriously affected by the loss of key highways connecting Bangalore to the rest of India.
    • A few, random weak links thrown into large ordered network dramatically reduces its diameter, thereby generating the small-world effect.
  • Types of webs or networks
    • Random
    • Ordered
    • Clustered (some order and some randomness)
  • Random: random links among nodes with no strong links between nodes. In other words, there are no local clusters of links. Here are Paul Erdos' calculations of degrees of separation of Earthlings using graph theory):
    • 6 billion people, each knowing fifty others
    • 1 degree of separation -> 50
    • 2 -> 2,500 (50 squared)
    • 3 -> 125,000 (50 cubed)
    • 4 -> 6,250,000 (etc.)
    • 5 -> 312,500,000
    • 6 -> 15,625, 000,000
  • Ordered
    • An "ordered" network or web is one in which each node is connected to several neighboring nodes in its locality, but not to distant nodes, e.g., a rectangular array or grid of nodes. Consequently, it is possibly to get from any node to any other node in the network through intermediate nodes. However, if the number of nodes is large, then there may be a large degree of separation between many nodes, e.g., the diagonally opposite corner nodes in a large rectangular grid.
    • A "fully connected" web of nodes is one in which each node is directly connected to every other node. Such a web has nC2 (combinatorial) links. Fully connected webs are possible in small groups, such as nuclear families where each member knows and interacts with every other member. Such webs are rare, if they exist at all in networks with a large number of nodes.
  • Clustered
    • Aristocratic: a few nodes strongly connected randomly to other nodes (and therefore, hubs) with weak links to large numbers of other nodes. e.g., Internet (see maps here), river systems, words in a language, corporate board members, scientific authors
    • Egalitarian: Each node is connected to about the same number of other nodes. Clustering of highly connnected nodes, with strong links within each cluster and a few random weak links between clusters): Watts and Strogatz:
      • for 6 billion and fifty near neighbors - 50 million steps to get from one place to farthest
      • add 0.02 percent random links between clusters - 8 degrees of separation
      • add 0.3 percent random links between clusters- 5 degrees of separation
      • e.g., brain, C rhabditis, transportation networks, electrical power grid, are highly clustered small world, facilitates synchronization
    • Structural limitations can cause networks to go from aristocratic to egalitarian, e.g. the network of airports
  • Aristocratic webs
    • Scale-free distributions
    • Power-law curve. inverse relationship between the number of links a node has and the number of such nodes (with a like number of links) in the network. The relationship between link size and number of links is logarithmic: increase the number of links by a certain power (say, square or cube), then the number of such links reduces by a fixed factor (say four or six times). [read, Nature of Networks];
    • Fat tails
    • Rich get richer: highly linked nodes grow faster than poorly linked ones
    • Phase transition (tipping point) -- beyond the point, there is a spontaneous emergence of order and the entire network begins to act like a single entity, with property of network shared across all nodes
    • Power law leads to fractal nature of such webs: each part of the web, magnified, looks a lot like the whole network. The network is far simpler than it looks due to its self-similarity (see the general in the particular).
  • Internet studies
  • Examples of small worlds
    • Brain
  • Synchronization
    • Many organisms and organs demonstrate a capacity for synchronized action without the need for a central controlling function, e.g., schools of fish, swarms of locusts and fireflies.
    • They appear to act in unison apparently spontaneously. Speed of response is a key consequence of synchronization.
    • A regular or ordered network ensures the transmission of information, but synchronization takes a long time. A random network enables quick transmission of information, but synchronization doesn't occur because of the lack of order. The only way achieve rapid synchronization is through an egalitarian small-world internal structure.
  • Rich getting richer growth of a network and the emergence of hubs.
  • Groupthink
  • History and accidents.
  • Riots

Interesting factoid: "It has been calculated that the maximum relationship a person living in the modern age can be to someone else, anywhere in the world, is 30-32 generations removed, which is roughly 1200 years of ancestry. "

Some topics for discussion

  • Getting a team in sync:
    • e.g., a programming/systems development team
    • a few members might form the core or the "hubs"; they hold the team together.
    • compare with, say, a soccer team
  • Self-managing teams: once they are in sync, little should be done by way of "management" except to maintain the team in sync; team takes on a life of its own
  • Problem solving teams: specific members as catalysts; specific ideas as catalysts
  • Creating a system of interacting, interdependent program modules: core modules (hubs); other modules (nodes)
  • Maintaining a network in a state of dynamic equlibrium (and up) in the face of random events
  • Peer-to-peer networking
  • Viruses
  • Nomadic Computing, wireless, and small worlds
  • Designing computer networks as small worlds for growth and survivability
  • Computer security
  • Small worlds and code testing
  • Small worlds and open source (or "bazaar") systems development
  • Designing applications interfaces from a small worlds perspective

Links

  • General Systems Theory
  • JASSS | Amblard reviews of Buchanan's and other books
  • Complex Adaptive Systems
  • Graph structure in the Web
  • Getting a job: A study of contacts and careers by Mark Granovetter. It's not what but who you know that gets you a job.
    • [In the late 60s, Granovetter, a sociologist now at Stanford, studied how people found jobs. Until then, it was generally assumed that society was homogenous. Granovetter discovered that society is made up of groups of people, which is now known as clustering. Granovetter showed that weak contacts were twice as effective (28%) as strong contacts (17%) for finding a job. Casual connections were more likely to lead to a job.
    • This seems counter-intuitive. It would seem close friends would be better job leads. We tend to gather within groups of similiar interests. If a tennis instructor wants new students, there's no point in asking her friends, who are all tennis instructors. She will find more students by asking people in clusters that have nothing to do with tennis, such as church groups, knitting clubs, and so on. Those clusters (church groups and so on) probably lack tennis instructors. So if you are creating networks, for job hunting, sales, and so on, make lots of casual acquaintances in groups that are outside your normal interests. Better yet, make contacts to the leaders of those clusters, because everyone within those clusters will know the leaders.]

Important Thinkers/Contributors

  • Paul Erdos and Alfred Renyi (mathematicians), 1950's-60's -random graphs
  • Stanley Milgram (psychologist), 1960's - small world
  • Paul Baran (communications engineer), 1964, ARPA -> internet, web
  • Mark Granovetter (sociologist), 1973, "The Strength of Weak Ties: A Network Theory Revisited", American Journal of Sociology 78: 1360-1380.
  • John Guare (playwright), 1990, Six Degrees of Separation: A Play
  • Brett Tjaden and Glenn Wasson (computer science students), 1995 - Oracle of Kevin Bacon www.imdb.com
  • Duncan Watts and Steve Strogatz (mathematician), 1998 "Collective Dynamics of Small World Networks", Nature 393: 440-442.
  • Albert-Laszlo Barabasi et al (physicists), to present, origins and sensitivity

Bibliography