If you've spent any time thinking about complex systems, you probably understand the importance of networks. Networks rule our world. From the chemical reactions within the cell, to the network of ecosystem relationships, trade and political networks that shape the course of history.

Or consider this article you are reading. You probably found it in social network, downloaded from computer network and are currently deciphering the meaning with your neural network.

But no matter how much I thought about networks over the years, until recently I did not understand the importance of a simple diffusion.

This is our topic for today: how, how chaotic everything moves and spreads. Some examples to whet your appetite:

• Infectious diseases that pass from carrier to carrier within a population.
• Memes spreading across the graph of followers in social networks.
• Forest fire.
• Ideas and practices permeating culture.
• Neutron cascade in enriched uranium.

A quick note about form.

Unlike all my previous work, this essay is interactive [in original article interactive examples are given with sliders and buttons that control objects on the screen - approx. lane].

So let's get started. The first task is to develop a visual vocabulary for distribution across networks.

Simple model

I am sure that all of you know the basis of networks, that is, nodes + edges. To investigate diffusion, we only need to mark some nodes as active. Or, as epidemiologists like to say, infected:

This activation or infection spreads across the network from node to node according to the rules we will develop below.

Real networks tend to be much larger than this simple network of seven nodes. They are also much more confusing. But for simplicity, we will build a toy model here to study the lattice, that is, the lattice network (lattice network).

(What the grid lacks in realism, it makes up for in being easy to draw 😉

Except where otherwise noted, network nodes have four neighbors, for example:

And you need to imagine that these lattices extend endlessly in all directions. In other words, we are not interested in behavior that occurs only at the edges of the network or in small populations.

Given that the gratings are so ordered, we can simplify them down to pixels. For example, these two images represent the same network:

In one of the behaviors, the active node always transmits the infection to its (uninfected) neighbors. But it's boring. Much more interesting things happen when the transmission probabilistic.

SIR and SIS

В SIR models (Susceptible-Infected-Removed) node can be in three states:

• Susceptible
• Infected (Infected)
• Removed

Here is how the interactive simulation works [in original article you can select the transmission rate of infection from 0 to 1, see the process step by step or in its entirety - approx. per.]:

• Nodes start as susceptible, except for a few nodes that start as infected.
• At each time step, infected nodes get a chance to transmit the infection to each of their susceptible neighbors with a probability equal to the transmission rate.
• Infected nodes then go into the "deleted" state, meaning they are no longer able to infect others or infect themselves.

In the context of disease, removal may mean that the person has died or that they have developed immunity to the pathogen. We say they are "removed" from the simulation because nothing else happens to them.

Depending on what we are trying to model, a different model than SIR may be needed.

If we are simulating the spread of measles or a wildfire outbreak, SIR is perfect. But suppose we are simulating the spread of a new cultural practice, such as meditation. At first the node (person) is receptive because it has never done it before. Then, if he starts meditating (perhaps after hearing about it from a friend), we will model him as infected. But if he stops practicing, he will not die and fall out of the simulation, because in the future he can easily pick up this habit again. So he goes back to the receptive state.

It is a SIS model (Susceptible-Infected-Susceptible). There are two parameters in the classical model: transfer rate and recovery rate. However, in the simulations for this article, I decided to simplify by omitting the recovery rate parameter. Instead, the infected node automatically reverts to a susceptible state at the next time step, unless it is infected by one of its neighbors. In addition, we allow the node infected at step n to infect itself at step n+1 with a probability equal to the transmission rate.

Discussion

As you can see, this is very different from the SIR model.

Since the nodes are never removed, even a very small and limited lattice can sustain a SIS infection for a long time. The infection simply jumps from node to node and back again.

Despite the differences, SIR and SIS turn out to be surprisingly interchangeable for our purposes. Therefore, for the rest of the article, we will focus on SIS - mainly because it is more tenacious and, therefore, more interesting to work with.

Critical Level

After playing around with the SIR and SIS models, you might notice something about the longevity of the infection. At very low transmission rates, such as 10%, the infection tends to die out. While at higher values, such as 50%, the infection remains alive and takes over most of the network. If the network were infinite, we could imagine that it continues and spreads forever.

Such boundless diffusion has many names: "viral", "nuclear" or (in the title of this article) critical.

It turns out there is specific breaking point that separates subcritical networks (doomed to extinction) supercritical networks (capable of infinite growth). This turning point is called critical threshold, and this is a fairly common feature of diffusion processes in conventional networks.

The exact value of the critical threshold differs between networks. What is common is availability such a value.

[In an interactive demo from original article you can try to manually find the critical threshold of the network by changing the value of the transfer rate. It is somewhere between 22% and 23% - approx. per.]

At 22% (and below), the infection eventually dies out. At 23% (and above), the initial infection sometimes dies out, but in most cases it manages to survive and spread long enough to ensure its existence forever.

(By the way, there is a whole scientific area dedicated to finding these critical thresholds for different network topologies. For a quick acquaintance, I recommend quickly scrolling through the Wikipedia article about threshold).

In general, this is how it works: below a critical threshold, any terminal infection in the network is guaranteed (with probability 1) to eventually die out. But above a critical threshold, there is a probability (p > 0) that the infection will continue forever, and in doing so will spread arbitrarily far from the original site.

However, note that the supercritical network is not guaranteesthat the infection will go on forever. In fact, it often fades out, especially in the very early stages of the simulation. Let's see how it goes.

Suppose we started with one infected node and four neighbors. In the first simulation step, the infection has 5 independent chances of spreading (including the chance to "spread" to itself in the next step):

Now suppose the transfer rate is 50%. In this case, in the first step, we toss a coin five times. And if five heads fall, the infection will be destroyed. This happens about 3% of the time - and that's just the first step. An infection that survives the first step has some (usually smaller) chance of dying out in the second step, some (even smaller) chance of dying out in the third step, and so on.

Thus, even when the network is supercritical - if the transfer rate is 99% - there is a chance that the infection will disappear.

But the important thing is that she always will fade away. If we add the probability of all steps fading to infinity, the result is less than 1. In other words, with a non-zero probability, the infection will continue forever. That's what it means for a network to be supercritical.

SISa: spontaneous activation

Up to this point, all of our simulations started with a small piece of pre-infected nodes in the center.

But what if you start from scratch? Next, we model spontaneous activation, a process by which a susceptible node becomes infected by chance (not from one of its neighbors).

It is a called SISa model. The letter “a” means “automatic”.

A new parameter appears in the SISa simulation, the rate of spontaneous activation, which changes the rate of spontaneous infection (the transmission rate parameter we saw earlier is also present).

What is needed for the infection to spread throughout the network?

Discussion

You may have noticed in the simulation that increasing the rate of spontaneous activation does not change whether the infection takes over the entire network or not. Only transmission speed determines whether the network is subcritical or supercritical. And when the network is subcritical (baud rate less than or equal to 22%), no infection can spread to the entire grid, no matter how often it starts.

It's like lighting a fire in a wet field. You can set a few dry leaves on fire, but the flames will quickly go out because the rest of the terrain isn't flammable enough (subcritical). While in a very dry field (supercritical) one spark is enough to start a fire.

Similar things are observed in the realm of ideas and inventions. Often the world is not ready for an idea, in which case it can be invented again and again, but it does not catch the masses. On the other hand, the world can be completely ready for an invention (great latent demand), and as soon as it is born, it is accepted by everyone. In the middle are ideas that are invented in several places and distributed locally, but not enough for any single version to cover the entire network at once. In this last category we find, for example, agriculture and writing, which were independently invented by different human civilizations about ten and three times, respectively.

Immunity

Suppose we make some nodes completely invulnerable, that is, immune to activation. It is as if they are initially in a remote state, and the SIS (a) model is launched on the remaining nodes.

The "immunity" slider controls the percentage of removed nodes. Try changing its value (while the model is running!) and see how it affects the state of the network, whether it is supercritical or not.

Discussion

Changing the number of non-receptive nodes completely changes the picture, whether the network will be sub- or super-critical. And it's not hard to see why. With a large number of immune hosts, the infection has less opportunity to spread to new hosts.

It turns out that this entails a number of very important practical consequences.

One of them is to prevent the spread of forest fires. At the local level, each person must take their own precautions (for example, never leave open flames unattended). But on a large scale, isolated outbreaks are inevitable. Thus, another method of protection is to provide enough "breaks" (in the network of flammable materials) so that the outbreak does not cover the entire network. This function is performed by clearings:

Another outbreak that is important to stop is an infectious disease. Here comes the concept population immunity. This is the idea that some people cannot be vaccinated (for example, they have a compromised immune system), but if enough people are immune to an infection, the disease cannot spread indefinitely. In other words, you should vaccinate sufficient part of the population to bring the population from supercritical to subcritical. When this happens, one patient can still become infected (for example, after traveling to another region), but without a supercritical network to grow in, the disease will only infect a small handful of people.

Finally, the concept of immune nodes explains what happens in a nuclear reactor. In a chain reaction, a decaying uranium-235 atom releases about three neutrons, which cause (on average) more than one U-235 atom to fission. The new neutrons then cause further splitting of the atoms, and so on exponentially:

When building a bomb, the whole point is to ensure that exponential growth continues unhindered. But in a power plant, the goal is to produce power without killing everyone around. For this, they are used control rodsmade of a material capable of absorbing neutrons (for example, silver or boron). Since they absorb rather than release neutrons, they act as immune nodes in our simulation, thereby preventing the radioactive nucleus from going supercritical.

So the trick to a nuclear reactor is to keep the reaction near a critical threshold by moving the control rods back and forth and ensure that whenever something goes wrong, the rods go down into the core and stop it.

Power

Power node is the number of its neighbors. Up to this point, we have considered networks of the 4th degree. But what happens if you change this setting?

For example, you can connect each node not only to four immediate neighbors, but also to four more diagonally. In such a network, the degree will be 8.

Lattices with degrees 4 and 8 are well symmetrical. But with a degree of 5 (for example), a problem arises: which five neighbors to choose? In this case, we choose four nearest neighbors (N, E, S, W) and then randomly choose one neighbor from the set {NE, SE, SW, NW}. The choice is made independently for each node at each time step.

Discussion

Again, it's not hard to see what's going on here. When each node has more neighbors, then the chances of infection spreading increase - and thus the network is more likely to become critical.

However, the consequences can be unexpected, as we will see below.

Cities and Network Density

So far, our networks have been completely homogeneous. Each node looks like any other. But what if we change the conditions and allow different node states throughout the network?

For example, let's try to model cities. To do this, we will increase the density in some parts of the network (a higher degree of nodes). We do this based on the data that the citizens have. wider social circle and more social interactionsthan people outside the cities.

In our model, susceptible nodes are colored based on their grade. Nodes in "countryside" have degree 4 (and are colored light grey), while nodes in "urban" have higher degrees (and are colored darker), starting at degree 5 in the outskirts and ending at 8 in the city center .

Try to choose such a propagation speed so that the activation covers the cities, and then does not go beyond their borders.

I find this simulation both obvious and surprising. Of course, cities are better at maintaining a cultural level than rural areas - everyone knows this. What surprises me is that some of this cultural diversity emerges simply from the topology of the social network.

This is an interesting point, I'll try to explain in more detail.

Here we are dealing with forms of culture that are transmitted simply and directly from person to person. For example, manners, parlor games, fashion trends, linguistic trends, small group rituals and products that spread by word of mouth, plus whole packets of information that we call ideas.

(Note: the dissemination of information between people is extremely complicated by the mass media. It is easier to imagine some technologically primitive environment, for example, Ancient Greece, where almost every spark of culture was transmitted by interaction in physical space).

From the simulation above, I learned that there are ideas and cultural practices that can take root and spread in the city, but they simply cannot spread to the countryside (mathematically they cannot). These are the same ideas and the same people. It's not that the villagers are some kind of "near-minded": when interacting with the same idea, they exactly the same chances of catching itlike the townspeople. It's just that the idea itself can't go viral in the countryside because there aren't many connections for it to spread.

This is perhaps easiest to see in the field of fashion—clothes, hair, etc. In the fashion web, we can capture the edge of the lattice when two people notice each other's outfits. In the city center, each person can see more than 1000 other people every day - on the street, in the subway, in a crowded restaurant, etc. In the countryside, by contrast, each person can see only a couple of dozen others. Based only on this difference, the city is able to support more fashion trends. And only the most compelling trends — those with the highest transmission rates — will be able to gain a foothold outside the city.

We tend to think that if the idea is good, it will eventually reach everyone, and if the idea is bad, it will disappear. Of course, this is true in extreme cases, but in between there are a bunch of ideas and practices that can only go viral on certain networks. It's really amazing.

Not only cities

We are looking at the impact here. network density. It is defined for a given set of nodes as the number actual edgesdivided by the number potential edges. That is, the percentage of possible connections that actually exist.

So we have seen that network density is higher in urban centers than in rural areas. But cities are not the only place where we find dense networks.

High schools are an interesting example. For example, for a particular district, let's compare the network that exists among schoolchildren with the network that exists among their parents. Same geographic area, same population, but one network is many times denser than the other. Therefore, it is not surprising that fashion and linguistic trends spread much faster among teenagers.

Likewise, elite networks tend to be much denser than non-elite networks - a fact that is underestimated in my opinion (people who are popular or influential spend more time networking and therefore have more "neighbors" than regular ones). of people). Based on the simulations above, we expect elite networks to support some cultural forms that the mainstream cannot support, simply based on mathematical laws, based on the average degree of the network. I leave you to think about what these cultural forms might be.

Finally, we can apply this idea to the Internet by modeling it as a huge and very tight city. Not surprisingly, many new kinds of culture are thriving on the internet that simply cannot be sustained in purely spatial networks: niche hobbies, better design standards, greater awareness of injustice, etc. And it's not just nice things. Just as early cities were breeding grounds for diseases that could not spread at low population densities, so the internet is a breeding ground for malignant cultural forms such as clickbait, fake news, and artificial outrage.

Знания

“Engaging the right expert at the right time is often the most valuable resource for creative problem solving.” — Michael Nielsen, "Inventing Discoveries"

We often think of discovery or invention as a process that takes place in the mind of a single genius. He is struck by a flash of inspiration and - Eureka! — all of a sudden we get a new way to measure volume. Or the equation of gravity. Or a light bulb.

But if we take the point of view of a lone inventor at the moment of discovery, then we are looking at the phenomenon in terms of node. While it would be more correct to interpret the invention as network phenomenon.

The network is important in at least two respects. First, already existing ideas must penetrate into consciousness inventor. These are quotations from a new article, a bibliographic section of a new book - the giants on whose shoulders Newton stood. Second, the network is critical to bring back a new idea. back in to the world; an invention that has not spread is hardly worth calling an "invention" at all. Thus, for both of these reasons, it makes sense to model invention—or, more broadly, the growth of knowledge—as a process of diffusion.

In a moment, I'll present a rough simulation of how knowledge can spread and grow within a network. But first I must explain.

At the beginning of the simulation, there are four experts in each quadrant of the grid, arranged as follows:

Expert 1 has the first version of the idea — let's call it Idea 1.0. Expert 2 is the person who knows how to turn Idea 1.0 into Idea 2.0. Expert 3 knows how to transform Idea 2.0 into Idea 3.0. And finally, the fourth expert knows how to put the finishing touches to Idea 4.0.

It's like a technique like origami where techniques are developed and combined with other techniques to create more interesting designs. Or it may be a field of knowledge like physics in which more recent work builds on the fundamental work of predecessors.

The point of this simulation is that we need all four experts to contribute to the final version of the idea. And at each stage, the idea needs to be brought to the appropriate expert.

A few caveats. There are many unrealistic assumptions encoded in the simulation. Here are just a few of them:

1. It is assumed that ideas cannot be preserved and transmitted except from person to person (i.e. there are no books and media).
2. It is assumed that there are permanent experts in the population who are able to generate ideas, although in reality many random factors influence the emergence of a discovery or invention.
3. All four versions of the idea use the same set of SIS parameters (baud rate, immunity percentage, etc.), although it is probably more realistic to use different parameters for each version (1.0, 2.0, etc.)
4. It is assumed that the idea of ​​N+1 always completely replaces the idea of ​​N, although in practice often both the old and the new versions circulate at the same time, without a clear winner.

… and many others.

Discussion

This is a ridiculously simplified model of how knowledge actually grows. A lot of important details remained outside the model (see above). However, it captures an important essence of the process. And so we can, with reservations, talk about the growth of knowledge using our knowledge of diffusion.

In particular, the diffusion model gives insight into how speed up the process: Need to facilitate the exchange of ideas between expert nodes. This may mean clearing the network of dead nodes that interfere with diffusion. Or it could mean locating all the experts in a dense city or cluster where ideas spread quickly. Or just collect them in one room:

So... that's all I can say about diffusion.

But I have one last thought, and it is very important. It's about growthand stagnation) knowledge in scientific communities. This idea is different in tone and content from everything above, but I hope you will forgive me.

About Science Networks

The illustration shows one of the most important positive feedback loops in the world (and has been for quite some time):

The upstroke of the cycle (K ⟶ T) is quite simple: we use new knowledge to develop new tools. For example, understanding the physics of semiconductors allows us to build computers.

However, the downward move requires some explanation. How does the development of technology lead to the growth of knowledge?

One way—perhaps the most direct—is when new technologies give us new ways of perceiving the world. For example, the best microscopes allow you to look deeper inside the cell, throwing up ideas for molecular biology. GPS trackers show how animals move. Sonar allows you to explore the oceans. And so on.

Undoubtedly, this is a vital mechanism, but there are at least two other paths from technology to knowledge. Maybe they are not so simple, but I think they are just as important:

First. Technology leads to economic abundance (that is, wealth), and this allows more people to engage in knowledge production.

If 90% of the population of your country is engaged in agriculture, and the remaining 10% are engaged in some form of trade (or war), then people have very little free time to think about the laws of nature. Perhaps that is why in the old days science was mainly promoted by children from wealthy families.

The US graduates more than 50 PhDs each year. Instead of a person going to work in a factory at the age of 000 (or earlier), a graduate student has to be funded until the age of 18, or perhaps until 30 - and even then it is not clear whether his work will bring any real economic effect. But it is necessary for a person to reach the cutting edge of his discipline, especially in such difficult areas as physics or biology.

The fact is that specialists are expensive from the point of view of systems. And the ultimate source of social wealth that funds these professionals is new technology: the plow subsidizes the pen.

Second. New technologies, especially in the field of travel and communications, are changing the structure of social networks in which knowledge grows. In particular, it allows experts and specialists to interact more closely with each other.

Notable inventions here include the printing press, steamboats and railroads (facilitating travel and/or sending mail over long distances), telephones, airplanes, and the Internet. All of these technologies contribute to increased network density, especially within specialized communities (where almost all knowledge growth occurs). For example, the networks of correspondence that arose among European scientists at the end of the Middle Ages, or how modern physicists use arXiv.

Ultimately, both of these paths are similar. Both increase the density of the network of specialists, which in turn leads to an increase in knowledge:

For many years I have been rather dismissive of higher education. A short stay in graduate school left a bad taste in my mouth. But now that I'm looking back and thinking (there is to abstract from all personal problems), I must conclude that higher education is still extremely important.

Academic social networks (for example, research communities) are one of the most advanced and valuable structures created by our civilization. Nowhere have we accumulated a greater concentration of specialists focused on knowledge production. Nowhere have people developed a greater ability to understand and criticize each other's ideas. This is the beating heart of progress. It is in these networks that the fire of enlightenment burns most strongly.

But we cannot take progress for granted. If crisis with irreproducibility of experiments and taught us something, is that science can have systemic problems. This is a kind of degradation of the network.

Suppose we distinguish between two ways of doing science: real science и careerism. Real science is practices that reliably produce knowledge. It is motivated by curiosity and characterized by honesty (Feynman: "You see, I just need to understand the world"). Careerism, in contrast, is motivated by professional ambition and is characterized by playing politics and scientific labels. It may look and act like science, but not produces reliable knowledge.

(Yes, that's an exaggerated dichotomy. Just a thought experiment. Don't judge me too hard.)

The fact is that when careerists take a place in the real research community, they spoil the work. They seek to promote themselves while the rest of the community tries to acquire and share new knowledge. Instead of striving for clarity, careerists complicate and confuse things in order to sound more impressive. They are engaged in (as Harry Frankfurt would say) scientific nonsense. And, therefore, we could model them as dead nodes, immune to the good faith exchange of information necessary for knowledge growth:

Perhaps the best model is one in which Career Nodes are not only immune to knowledge, but actively disseminate fake knowledge. Fake knowledge can include non-meaningful results that are artificially inflated in importance, or truly false results that result from manipulation or fabricated data.

Regardless of how we model them, careerists can certainly stifle our scientific communities.

It's like a nuclear chain reaction that we badly need - we need an explosion of knowledge - only our enriched U-235 has too much admixture of the non-reactive isotope U-238, which suppresses the chain reaction.

Of course, there is no clear distinction between careerists and real scientists. There is a bit of careerism in each of us. The question is how long the network will last before the spread of knowledge dies out.

Oh, you've read to the end. Thank you for reading.

License

CC0 all rights are not reserved. You can use this work as you see fit :).

Acknowledgements

• Kevin Kwok и Niki Case for thoughtful comments and suggestions on various versions of the draft.
• Nick Barr — for moral support throughout the process and for the most helpful feedback on my work.
• Keith A. for pointing out to me the phenomenon of percolation and the percolation threshold.
• To Jeff Lonsdale for a link to this essay, which (despite its many shortcomings) was the main impetus for this post.

Interactive Essay Samples

• All works by Nicky Case, especially "The Parable of the Polygons" (with Vee Hart) and "Developing a Better Ballot for Voting". This is a high bar for what an interactive essay can be.
• distill.pub: exceptionally high-quality interactive descriptions of machine learning.
• Classic work by Bret Victor "Up and Down the Ladder of Abstraction". I wasn't very good at moving up the stairs, but there's always one more try left.

Source: habr.com