Scale-Free Networks
At the beginning of this century, scale-free networks (or graphs) raised a lot of noise in the circles that none of us belong to. These networks have many amazing properties; I’ll be looking at the most important of these.
Those networks and graphs are everywhere. With a microscope, one find them in protein interactions; without one — in a heap of broccoli at a market stall. These graphs are in our phone books, in social networks; they are deeply embedded in the network of transport and in the architecture of modern computers. Scale-free graphs describe well how the Internet works and how everything built on top of it works.
What do I mean by ‘scale-free network’? It all started with D.S. Price who studied the citation graph in scientific papers: ‘who’ mentions ‘whom’ in a never-ending chain of white papers about chains of white supremacy. Mr. Price established that the number of mentions is distributed according to the Pareto law (or ‘power law’). That explains perfectly why the citation network is liberated of scales (it is so obvious and self-evident, that even I didn’t get it. So, I won’t go in details here).
It wasn’t Price, though, who came up with the idea with the name. This is common among inventors: one person discovers a thing, and it gets named by another. (Who came up with the Bezier curves first? Hint: not Bezier).
There was a Hungarian-American (yet Romanian by birth) mathematician by the name of Albert-László Barabashi. He had an idea, novel at the time, to replicate Price’s work in the context of the World Wide Web: take blog posts instead of whitepapers and fashion bloggers instead of academics.
The Barabashi’s ‘apple’ might have given birth to the Google ‘apple tree’ and then to a billion-dollar advertising business, but the mathematician was interested in something else. They all are, aren’t they?
He was interested in the properties of these ‘scale-free networks’ and in the reasons for these properties to emerge.
While Barabashi was busy with the puzzle of the ‘scale-free networks’ and their properties, the business world was having a bash over a wide class of the systems that fell into the definition of ‘scale-free’.
There were a plenty of those: biological, sociological, technological. If there is a word ending in ‘-ical’, there are scale-free graphs in it.
Everyone around was talking about scale-free networks, and quite soon some went from talking right into doing: they started to design such networks, measure their properties and optimise.
One of the greatest discoveries about these networks is that they have very fast signal propagation. In such a network, the distance between two nodes is small.
Highly convenient property for a travelling salesman. For a transport network designer, it can help people to save on gasoline. Designer of microchips? Save the industry on conductive materials. IT department architect? Save money on routers and cables. Social networks are F-A-B for marketing. Yet, let’s not get ahead of ourselves.
Several years have passed and the critics have appeared. Some scientists have questioned whether scale-free networks are ubiquitous. Some even claimed they can’t be found in real world at all.
A heated discussion flared up. As it usually happens with heated discussions, everyone turned out to be a mathematician.
Barabashi himself took part in the heat. All the provided real world examples, so he said, were full of features for which the generalized model of scale-free networks didn’t account.
Well, almost all the examples. One of the varieties of real-world networks still fit well into the model. These are networks created by humans. Roads, computers, everything digital. And social networks. More precisely, some of those.
The Internet Is a Big Village of Skyscrapers
Everything that happens on the Internet is very well described by the power law and scale-free network models. Conway’s law provides an explanation: organizations design systems that mirror their own communication structure. As one might say, if a carpenter from Liverpool builds a shed, it’ll have a roof with a Scouse ascent.
We created computers based on microchips and integrated boards — all these components have the ‘scale-free properties’ we coveted. Then we connected these computers into a network, also of a ‘scale-free’ kind — to optimise throughput.
Immediately, life sprouted from nothing in this network — just like fleas on an alley cat. The emergent World Wide Web, or just ‘The Web’, was quickly dubbed a ‘global village’. I can still remember these times. But it was only recently that I realized how far from the truth this turned out to be. Almost in Orwellian way.
We live in an environment enriched and powered by Internet-connected devices. In turn, our habitat — this digitally-enhanced Earth we created — creates us. We are no longer a subject of Conway’s law, but an object of it.
It’s no good. Every rotation of the digitalised planet makes us less and less human. Now, it is time to talk about how it all happened.
Brave (Small) World
Let's start at the beginning. Every quest begins in a village, which is a small world where anyone knows everyone. Not six handshakes are needed, not even three, to connect any two of the village drunkards at the only tavern there is.
We study this social network — not ‘Facebook’, but a ‘Tavern 2.0’ where everyone shakes hands with each patron coming in. Then we walk by another hundred or thousand of similar villages with similar taverns. We walk until we see a few patterns emerge.
Such social networks are called ‘small worlds’ and have some similarities to scale-free networks. Yet they have differences, and those differences are all that matter.
What Are the Properties of Small World Networks?
- The distance between the nodes is small (just like with scale-free networks).
- The main supporting structure is ‘hubs’. In ‘small worlds’, there are many small clusters: tightly connected cliques that are then interconnected by a small number of links (scale-free networks don’t work like that!).
- ‘Small worlds’ are highly assortative.
Assortativity is like this: people tend to make connections with their own kind. Birds of the feather make a movie together. Rich men have rich man’s clubs. To this comparison, we will return a tad later. Now, it is time to answer the question we haven’t even asked ourselves yet.
The Two-Phase Evolution
How complexly organized systems are born from the soup of random connections? How does social order emerge from social chaos? With ants, it is achieved simply: just feed them barley. With people it is a bit different.
Once, someone offered me a witty explanation: music festivals. Who that someone was, I can’t recall; I was at a festival.
Each village lives its own life: everyone gets to know each other; people communicate and establish close and long-term ties. They visit the ‘Tavern 2.0’ social network and tweet away their food afterwards.
Once a year, an event happens to which the inhabitants of several villages come together. Not all of them, but some. Usually, the most active and the most attractive. There they listen to music for three days, covered by rain and mushrooms. They make connections alright, but these are much less close than the connections within their own village.
There are two phases in the life of such a society: the strengthening of local ties and the creation of short-lived ties with distanced peers. One can call them ‘local’ and ‘global’ phases which establish permanent and temporary connections respectively. While global phase is a period of enrichment, the local one becomes the time to digest.
These phases alternate and so, according to the researchers, the social structure of ‘small worlds’ emerge. There were a lot of good things going on within this small-world-branded society. Festivals, at the very least.
A People, Liberated
The formerly strong boundary between ‘local’ and ‘global’ worlds is now gone. Anyone can meet a person from the other side of the world and send them an aubergine emoji. The Internet has done a great job of liberating people from their ‘locality’.
The ideologists of this liberation say, ‘now one can choose for oneself what phase they are in’. The phone in the pocket enables a person to switch between ‘local’ and ‘global’ phases every given second.
The Internet is always with us now. The tight circle of 100,500 contacts on Instagram, Facebook, and Tiktok is always vibrating in the pocket.
Social networks have gone from ‘six handshakes’ to hundreds, then thousands and hundreds of thousands of followers and followees. People relationships began to take the form of the environment they have to exist. Social media are turning our society into a scale-free network.
In a scale-free network, the ‘two-phase evolution’ doesn’t have a place to happen. Once the locality restrictions are removed, the phases cease to change, and the network of small worlds coverts into a scale-free one.
Sometimes, scale-free networks are called ‘ultra-small worlds’. Isn’t being ‘ultra-small’ even better than just ‘small’? Let’s find out by comparing ‘scale-free’ with ‘small world’.
Scale-Free Networks vs. Small Worlds
Those pixels on your screens don’t come for free, so I’ll introduce a notation to save us some screen space and electricity:
- C - clustering coefficient (how densely the nodes are interconnected)
- L - average path length (average distance between nodes)
Here's how these coefficients look for different types of networks:
- Ordered network: C+, L+ (strong clustering, long path)
- Random network: C–, L+ (no clusters, long path)
- Small world: C+, L– (many clusters, short path)
- Scale-free network: C–, L–– (super-connectors, very short path)
Here is what the ‘ultra-small’ means: the paths are shorter, and the clustering is sparser. No doubt, short paths are great — as we already observed. But what about clustering?
The scale-free hubs are called ‘super-connectors’. They help the signal to spread quickly amongst the networks. Once it reaches just a couple of such super-connected hubs, the world gets a pocket epidemic.
Super-connectors play the king of the hill: each super-hub has its own super-super-hub to which it is a mere pleb. Small worlds are organised in a different way. Instead of the pyramids of hierarchy, ‘clubs’ are formed. Surely, those clubs are still layered — there are clubs for ‘rich’ and clubs for ‘poor’. But even the poor have friends.
In a scale-free network, the highest probability is that a person only has one connection — the upward connection to their super-hub. In a scale-free networks a random person is — most probably — a loser. While in a small-world network the same loser has a company of five to seven other losers just like them. That is, each of them is a little less of a loser. Shouldn’t it be considered a win?
Bobby, Fabby, and Me, Part I
If you still don’t see why the ‘small worlds’ are a better fit for humanity, then you, my friend, aren’t smart. I’m not smart, either, having you as a friend. Admitting our matching intellectual capabilities, we can move our conversation to a whole new level.
Let me introduce a couple of my close friends from the block: Bobby (left) and Fabby (middle), my boys. I am on the right.
What Happens after Shizit Hits the Fans
While it seems that everyone smart is interested in AI, some are still stuck with animals and their social networks. Not only with Facebook, but also with those which other animals form. The scientists suspected the structure of these networks emerged due to natural selection, evolution, and other so-called ‘Darwinistic nonsense’ which is not nonsense at all. There should be some sort of connection at least.
And there is.
Firstly, ‘small world’ networks have high clustering. It dampens the natural selection process: those who live together limit each other’s appetites.
Bobby, Fabby, and Myself, Part II
When I take the Bobby’s heifer, Bobby will get dead drunk. The block that he rackets (we call it ‘protection’) will be taken by Fabby. Now Fabby has two blocks for his turf. Which won’t do well for me. So, I’d rather leave Bobby’s heifer alone. I mean, let Bobby has her.
Many ‘neutral mutations’ appear, which are equally inefficient from the point of view of natural selection. What it really means, each of us receives an individuality.
Bobby, Fabby, and Me, Part III
Bobby loves French rap, Fabby got crazes over proper British punk, and I love Vivaldi the Italian. But our diverse musical preferences do not affect our little Mexican stand-off over our turfs. The fragile balance of knives and bats keeps all of us alive.
Our diversity is preserved and passed on to our children and grandchildren. Individuality flourishes.
Small world network takes care of individuality. From humanistic perspective, it is an excellent argument in favour. 1:0, small worlds team is in the lead.
Secondly, ‘scale-free’ networks have super-connector hubs. They help the mutations to spread rapidly. These super-connectors do some random sampling of everything that comes to them and post the summary on Tiktok. Millions of potential memes result in one that skyrockets.
This is where the theory of neutral evolution comes to mind. When the natural selection does not occur, then evolution happens by genetic drift over neutral mutations — washing out some of them. In our world, natural selection is not really a huge factor, despite all the quarrels.
Bobby, Fabby, and Me, Part IV
If I pick a sample of all Bobbies and Fabbies of this world, it might turn out that none of them listen to my Vivaldi. As soon as super-connectors will start to promote Franco-British punk-rap, Vivaldi fans will gradually dissolve.
Soon, there will be no Vivaldi and less variety.
Scale-free networks favour less variety.
Bobby, Fabby, and Me, Part V
Here is another, about that Bobby’s heifer.
She goes on dates with Bobby, Fabby, and me. These are three different dates, mind you. We are proper people here. And it is clear who is the best bloke on the block (though, as I already revealed, I’d better keep my hands to myself so I can keep them).
It is always like this on our turf. The chick looks at them all, the tough blokes, the normos, the suckers. Well, of course, she doesn’t even look at the suckers.
But if one sucker pumps himself up, put on some blings and posh clothes, then maybe — maybe — the heifer will open the beaver cage.
In the end, everyone is happy. Except of Bobby, who brought it to himself by neglecting the heifer’s needs. He should be more thoughtful of his coupling. Y’know, gift flowers, refurbished stereos, boosted cars, all that shizit. Then his heifer’s beaver won’t even float.
Small world network requires its members to invest in relationships. While in the world of Tinders and Tiktoks, things swing the other way.
Bobby, Fabby, and Me, Part VI
The chicks keep staring at Kanye and Bieber, not at us simple blokes. Here is the deal. If all what a chick see on TV is celebrities, why in the seven bottles of hell would she even spare one look to us simple skinheads?
As for me, why would I buy flowers or nick a stereo for a heifer when I can order a chick via Tinder to Netflix and chill with a glass of Vodka Red Bull? I swipe left on this.
In a scale-free network, relationships between members deteriorate. From the humanistic perspective, 2:0 for small worlds.
Artificial and Natural
There are people in academia who doubt the supremacy of the scale-free networks; those who don’t, keep the disclaimer — to build an adequate network model, one must know the nature of the source.
Real world always introduces imperfections, limitations, and restrictions. As we perhaps know from the above, it is exactly the limitations and restrictions that allow for ‘two-phase evolution’ to emerge. In the real world as in the nature.
But not in the systems we ourselves design with a purpose in mind. We want to optimise performance: faster signal spreading, less pathways. In those systems, we don’t need the helping hand of evolution. We are quite better off without it. We are gods of order.
For our single-minded purpose, scale-free fits the best. Signal is transmitted rapidly and with low overhead. We make ourselves part of it: with the help of internets, we transmit signals — memes! — quite rapidly.
In such networks, it is the ‘viruses’ who benefit the most: the novel coronavirus, the dubstep cat, the fake news.
Human society is not just a scale-free network. It is a part of an even greater one. The network of everything digital: it starts with semiconductors, then go up to microchips, devices, operating systems, apps. Then there are we. And up above — who is the digital super-connector to us? Google, Facebook, the so-called ‘megacorp’.
The super-connectors in this network need us, humans, to connect the layer of digital hardware with the layer of digital products and services.
The Megamachine
People, software, hardware, corporations — it is one single Mega-machine now. While its consciousness is dormant, it has only one task: to survive. The mega machine of which we are only a part wants to continue in the world.
To survive, the machine needs someone to replace its parts. Someone who changes microchips, charges batteries, pulls wires, makes new people and new digital products.
Thus, the machine itself developed a way to keep people locked inside. This way, people are indoctrinated in young age to become willful slaves who salivate at just a sight of a Kardashian’s ice bucket challenge. The machine (which we are a part of) learned to produce ‘digital content’.
The digital content is optimised to spread rapidly across the indoctrinated population. The quality of such content doesn’t matter, really. The only quality that matters is the volume of saliva it induces. That’s not a bar too high.
Every day, this bar is surpassed by hundreds of thousands ‘digital content items’: posts, videos, instagrams, tiktoks. That lucky that reaches the super-connectors first, gets to spread across the world.
What is happening in the super-connector world? Do they have their ‘rich man’s club’? Or do the play in the king of the hill? How many plausible search engines we have? How many social networks — given Facebook, Whatsapp, and Instagram is one? Winner takes it all.
What Should We Do?
So, the humanity tamed the scale-free network to serve our need for fast computing, fast delivery, fast communication. And we made it. Everything is fast now.
In return, we are now part of it. We built ourselves quite some scale-free slaves, and now they are ascended. They are making slaves out of us.
A Question from Bobby to Fabby
Here is my question, Fabby.
Do we want to be the meat paddy in the scale-free sandwich?
The bottom part of the scale-free network is made of silicon, the top one — of self-organising digital software. We are in the middle, the connecting tissue.
It is not Alphabet Co. at the top, but Google itself: a mega-machine of datacentres, cloud virtual machines, AI training farms, Android phones. It is not Meta Co., but a mega-machine built of Facebook, Whatsapp, Instagram, Cambridge Analytics, Oculus Quest.
Thankfully, not all is lost. Scale-free networks can ‘degrade’ back to small worlds, if limited wisely. Yet more restrictions mean less freedom. Will we return to the world that was too tight to breath? Or will we ascend?
Fabby’s Answer
Honestly, I don’t care.
What I care about is to get our pub at the corner back.
Bibliography
- Wikipedia: Scale-free Network.
https://en.wikipedia.org/wiki/Scale-free_network - Dokholyan NV, DeLisi C, Shakhnovich B, Shakhnovich EI. Expanding protein universe and its origin from the biological Big Bang.
- Borodovsky MY, Gusein-Zade SM. A general rule for ranged series of codon frequencies in different genomes.
- Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationship of the internet topology.
- Ebel H, Mielsch LI, Bornholdt S. Scale-free topology of e-mail networks.
- Wuchty S. Scale-free behavior in protein domain networks.
- De Solla Price, D.J. (1965). Networks of Scientific Papers.
- Albert, Réka; Barabási, Albert-László (2002). Statistical mechanics of complex networks.
- A.-L. Barabási and R. Albert. Emergence of scaling in random networks.
- Anna D. Broido; Aaron Clauset (2019). Scale-free networks are rare.
- Petter Holme (2019). Rare and everywhere: Perspectives on scale-free networks.
- Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, Dmitri Krioukov (2019). Scale-free networks well done.
- Barabási, Albert-László (2018). Love is all you need.
https://www.barabasilab.com/post/love-is-all-you-need - Wikipedia: Small-world Network.
https://en.wikipedia.org/wiki/Small-world_network - Milgram S (1967). The Small World Problem.
- Watts DJ, Strogatz SH (June 1998). Collective dynamics of 'small-world' networks.
- Watts DJ (1999). Small Worlds: The Dynamics of Networks Between Order and Randomness.
- Six Degrees of Kevin Bacon.
https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon - Green, D.G.; Liu, J. & Abbass, H. (2014). Dual Phase Evolution: from Theory to Practice.
- Stocker, R.; Cornforth, D. & Green, D.G. (2003). A simulation of the impact of media on social cohesion.
- Ralf H.J.M. Kurvers, Jens Krause, Darren P. Croft, Alexander D.M. Wilson, and Max Wolf (2014). The evolutionary and ecological consequences of animal social networks: emerging issues.
- Wikipedia: Neutral Theory of Moleculart Evolution.
https://en.wikipedia.org/wiki/Neutral_theory_of_molecular_evolution