Friday, February 21, 2014

Complex systems, Scale-free networks and Affiliation networks



This post is a follow-up of the previous one about complex systems. I will further focus on the fifth point which said that efficiency in a complex system is strongly related to the capability to support information exchange flows, and will expand on the importance of Scale-free networks . The importance and the size of information flows are directly related to the complexity of such systems, which is the amount of interaction between the components.
What makes a good information flow network for a complex system? Here are five characteristics that spring to mind:
  • Latency : to minimize the time it takes from some information to travel from one subsystem to the other.
  • Throughput : to simultaneously transmit large amounts of information between all subsystems.
  • Resilience: to continue functioning when some subsystems or some links become unavailable.  These three characteristics are universal for all complex systems, for instance information systems or enterprise communication channels.
  • Searchability: to ease the task of finding related subsystem through the exploration of the communication network. This property is related to dynamic growth and self-organization. In an autonomic system, automatic discovery of new features and new component is at the heart of the system’s dynamic organization.
  • Cost: to minimize the total weight of the communication network, whether we talk about energy, mass or dollars. Related to cost is the scalability of the communication network structure. Scalability means that the structure may easily evolve as the complex system grows.

To reduce latency, one must reduce the diameter of the network, which is (roughly) the average path length. The easier way is to add additional links. Similarly, to increase throughput and resilience, one must rely on path redundancy (the fact that many paths exist for routing one flow). However, there is a double trade-off: increasing the average degree and the number of edges both increases the cost and reduces searchability.

Nature seems to have found the perfect solution for this trade-off with the scale-free network structure. A scale-free network is a graph whose degree distribution follows a power law. Compared to a random graph, this means that there is a higher frequency of highly connected nodes, with large degrees. Scale-free have many wonderful properties, as explained by Duncan Watts or Albert-Laszlo Barabasi. Their diameter is logarithmic in their size, and they are very resilient, that is their level of connectivity is weakly changed when some nodes become unavailable. The name “scale-free” comes from the self-similarity that the degree distribution implies. Somehow, a scale-free network may be seen as a “fractal structure”, which makes it an interesting candidate for self-growth and self-organization.

What has been found in the past 20 years is that scale-free networks are everywhere, both in the nature-made complex systems (such as the network of chemical reactions within the brain), and in the human-grown systems that incorporate feedback and learning, such as the Web (network of pages) or the Internet (network of computers). Let me quote the introduction of « Scale-Free Networks : A Decade and Beyond » from Albert-Laszlo Barabasi : For decades, we tacitly assumed that the components of such complex systems as the cell, the society, or the Internet are randomly wired together. In the past decade, an avalanche of research has shown that many real networks, independent of their age, function, and scope, converge to similar architectures, a universality that allowed researchers from different disciplines to embrace network theory as a common paradigm.” As with any general big idea, this is an approximation of the real world, and there are some debates whether real networks have an exact power law for their degree distribution. Still, it is both a useful and powerful concept, when trying to design communication networks.



I will now write a brief summary of « Linked », a great book by Albert-Laszlo Barabasi. I have read this book many years ago, and promised to give a review in my other blog, but never found the time to do it. Still it is very relevant to what I just wrote (together with many other books which I have selected in this post ) since it contains a lot of details and examples about the importance of scale-free networks. The following is a short list of relevant key ideas that are well illustrated in this book, with no claim of completeness:
  • The book starts with the concepts of diameter and average path length. Throughout the book, many examples are given of really large networks with small diameters. For instance, the Web  (URL network) diameter is 19. Another interesting example is the molecule interaction network in a living cell, through chemical reactions. The “diameter” is only 3 (three degrees of separation). Lately we have learned that the diameter of Facebook social graph is 4.7.
  • By looking more closely at these networks, we see that the short diameter is not due to the number of edges but the presence of “connectors” (hubs), as defined by Malcom Gladwell in “The Tipping PointJ This is true for cell reactions, where a few molecules interact with many others. Small-world networks, as defined by Watts and Strogatz, also exhibit a higher clustering coefficient than random graphs. These small-world structures may be thought of as small tightly connected groups, linked by connectors – hubs with high degrees.
  • This leads to the concept of scale-free networks, by looking at the node degree distribution law. The presence of connectors is the result of power laws, which are also called “fat tailed” because the number of nodes with very high degree is much higher than a typical “exponential decay” law. Another interesting example of scale-free networks is the graph of word co-occurrence in natural language.
  • A good part of the book deals with how scale-free network may be grown, that is how they emerge in real life. This leads to the powerful “rich get richer” paradigm (also called the Matthew Effect), where the probability of creating a new edge is proportional to the existing degree. Growth is a signature of Scale-free networks. I quote from the book : “The power laws emerge – nature’s unmistakable sign that chaos is departing in favor of order. The theory of phase transitions told us loud and clear that the road from disorder to order is maintained by the powerful forces of self-organization and is paved by power laws”.
  • A very interesting part of the book deals with resilience, with examples drawn from biology such as the protein network in our metabolism. There is an interesting comparison with hierarchical networks (such as organizational charts in a traditional company or electricity distribution network) which are less fault-tolerant than scale-free networks (even with added redundancy for the high value links). Another quote: “The coexistence of robustness and vulnerability plays a key role in understanding the behavior of most complex systems. Simulations have shown that the protein network refuses to break apart under randomly generated mutations.”
  • Scale-free networks are graphs, with edges between two nodes that only describe binary interactions. Most of real world complex systems use more complex “n-ary” interactions, which could be described with hypergraphs, two-mode networks or affiliation networks. For instance, the meetings between coworkers in a company or the chemical reaction networks are hypergraphs. A meeting is an hyper-edge since it binds many participants; a chemical reaction is also an hyper-edge in the molecule graph. It is easy to model an affiliation network with a regular bi-partite graph (just add a few nodes for the hyper-edges), so this is not a big technical difference, but more and more interest is given to affiliation networks since they are very common in the real world of complex systems.

Five years ago I decided to see if Duncan Watts’s results would also apply to Affiliation Networks. I wrote a paper entitled “Efficiency of Meetings as a Communication Channel : A Social Network Analysis” which I presented at the “Management and Social Networks” conference in Geneva (2012). The main findings may be described as follows:
  • I have shown that the most efficient meeting network structure relies on small meetings that have a high frequency. There is no surprise here, since this is a tenet of agile companies which are organized around daily short team meetings. Still, it is interesting to see that this is a deep structural property of the underlying network.
  • I have proposed a “latency performance indicator” that predicts the speed of information propagation as  “ #of-monthly-meetings * log(#people-that-one-wants-to-communicate with) / log(#people-that-one-actually-meets-in-a-month)”. For those mathematically inclined, one may retrieve the best practices (fewer meeting, frequent meetings, a few large meetings) within the formula.
  • The most interesting piece is the emergence of a small-world structure as the most efficient meeting network, which is a hybrid combination of small team meetings and a few larger meetings.  This reproduces, in the case of an affiliation network, the results found ten years ago by Duncan Watts. It tells that companies should reproduce the diversity found in nature, implement path redundancy and combine many really small and frequent meetings such as SCRUM stand-up meetings together with a few overlapping “town-hall” meetings (large audiences).

Scale-free networks are similar to what sociology calls “ambidextrous organizations”.  Ambidextrous organizations leverage the power of cliques and the strength of weak ties. The “power of cliques” is precisely the strength of team work, small group of people that are all connected to one another (hence the clique name), establishing “strong ties” (which means frequent in the world of social network science). The “strength of weak ties” is the law established by Mark Granovetter that says that we need to use our “weak ties”/extended network to get out from difficult or exceptional situations. “Weak ties” refer to people that we see rarely (as opposed to strong ties) ; the “weak ties” make the edge of our social network, they provide the diversity of viewpoint and culture which is often absent from the core of our social network (since “strong ties” tend to be very similar to ourselves).


The idea that complex systems sciences in general and social network structures in particular, are relevant to enterprise organization is becoming more and more popular (this is precisely the topic of my other blog).  I will conclude with three examples which are closely related to this post, since those three theories attempt to improve management efficiency through a better-designed information network:

  • Sociocracy  uses circles as a team structure, and doublelinks (each intersection between circles is represented by two individuals) to implement redundant information propagation paths. The illustration is taken from Wikipedia.
  • BetaCodex is a management theory and practice whose claim is to “organize for complexity”. It is based on a cellular network structure, which draws its organizing principles from biology. The tree structure is replaced by a denser network of circles (with a clear reference to sociocracy), providing shorter and more resilient information propagation paths.
  • Holacracy is another recent management theory that draws on complex system theory. Here again we find a system of self-organizing circles (with a similar influence from sociocracy). The most defining feature of holacracy is “to organize around purpose” (cf. the fourth principle of our previous list).



 
Technorati Profile