Hierarchies and networks

We, scientists, love the word “hierarchy.” In every professor, it evokes a picture of us chalking up a pyramid on the blackboard and confidently explaining, “at the top, we have the …” Hierarchies are systematic and meaningful orderings. They are the successful ends of research projects, and bringers of peace to our curious minds. They connect us to the giants of the past: from (probably way before) Descartes to Chomsky.

Like many words of the vernacular, “hierarchy” doesn’t have a razor-sharp definition. This is a mixed blessing: On one hand, we always have to double-check what someone means by it; on the other, we still have some leeway to squeeze it into our papers. Here, I will list four ways of thinking about hierarchies and their consequences. If this was something more than just a blog post, there would be some history and background here, including hierarchies of angles and quotations from The Book of Change; but it isn’t, so I’ll go straight to the first item.

Type 1. A hierarchy is a partial ordering of objects. So for every object, there are other objects above, below, and at the same level. This is a generous definition. So generous that it doesn’t mean much to have found a hierarchy. In any random network, the nodes form a hierarchy based on their degree; any group of people could build a hierarchy based on age, weight, or height. With this definition, everything is close to trivially hierarchical. Still, note that many models of complex systems are actually not hierarchical even with this generous definition, as all constituents are identical. (This is not necessarily a methodological problem, just funny.)

Type 2. A hierarchy is a partial ordering of objects with (exponentially?) increasingly many objects per level. I mentioned pyramids. Although sometimes not explicitly stated, in anyone’s mental picture of a hierarchy, there would usually be one item on top, a few below, and more for every tier. By this definition, most socioeconomic systems become hierarchies, with the wealth and power concentrated to an elite. A natural or social system being a hierarchy in this way is equivalent to some essential traits of the constituents having a right-skewed, strictly decreasing distribution. This is often the case, but if this is trivial, or a wondrous mystery, or somewhere in between, is a debate without an end in sight.

Type 3. A hierarchy is a partial ordering of objects with increasingly many objects per level, and no connections between levels other than the one above and below. The title of this post contains the word “networks.” Of course, we don’t want to let go of our favorite network slogan, “everything is connected.” If everything is connected, then how are things connected? If hierarchies make you think of the military (I do), then you have an idea—like the chain of command. One person is connected to his/her superiors and subordinates. Mathematically, it is a (rooted) tree. This is a very restrictive definition of a hierarchy and, as such, trivial. Now basically nothing is a hierarchy (unless it was designed to be—ergo, trivial).

Type 4. A hierarchy is a partial ordering of objects with increasingly many objects per level, and no connections between levels other than the one above and below, and within a level. To slightly relax definition 4 above, we can allow connections to happen within a layer. Now a hierarchy is a graph decorated by layers such that all paths between nodes go: (i) to higher layers, (ii) in the same layer, (iii) to lower layers. This idea is one I first heard about in the context of the definitions of tiers in the BGP routing protocol of the Internet. One point with this definition is that we no longer need to be categorical about if a system is a hierarchy or not. We have a way of measuring how close to hierarchical the network is. That is the idea of this half-forgotten classic by Axelsen et al., where they define “degree hierarchical paths” as those traversing nodes of (i) larger, (ii) equal, then (iii) smaller degrees, and use this as a basis of measuring the degree-hierarchical order. This paper by Katifori and Magnasco (which is the one that prompted me to write this post), has an interesting scheme, based on similar ideas, to reduce a network to a tree and subsequently trace hierarchical patterns. A cool approach would be to try to optimize the assignment of layers, to make as many paths as possible hierarchical, then measure the deviation from a perfect hierarchy. I’m not sure anyone has done that? Anyone up for collaboration?

To sum up, a statement about a system being hierarchical could be anything from trivial to spectacular, depending on the definition of “hierarchy.” It’s a useful concept, but it shouldn’t—scientifically speaking—be anything catchy to throw into your next paper title. (Still, I don’t know if I can resist it if I get the chance . . . )