Going Critical
meltingasphalt.com
meltingasphalt.com
One eye opener is the extent that the "Degree" parameter reduces the critical threshold.
> The degree of a node is the number of neighbors it has. Up to this point, we’ve been looking at networks of degree 4. But what happens when we vary this parameter?
And here's the power of this interactive essay, you can try it yourself. It's a toy model but makes a visceral argument. It adds up to the kind of media we dreamed of for the world wide web.
The degree parameter has exploded via social networks, greatly lowering the critical threshold of idea transmission. Our cultural DNA is being revised at a supercritical pace. This piece helps make a little sense of it in a way that static words couldn't.
I have also published some research among these lines: https://arxiv.org/pdf/1403.5815.pdf
Could you explain what you mean a little bit more?
I built a rather sophisticated simplex based trade analyser for one of my contracts for a broker trader. From what I've heard it's given them an edge since no one even knows about it. It's been three years so my NDA and non-compete are finished. I might get around to writing it up if I don't get hired to do another one.
Do you mean that real social networks are to networks as tensors are to vectors? More dimensions?
If so, what do those dimensions represent?
Or am I missing your point (which is ... not very clearly made).
What's pretty interesting is that the largest eigenvalue of the adjacency matrix of an undirected graph lies between the average degree and the maximum degree so the gut feeling you get when playing with the degree of a graph is legitimate.
I will jump on the opportunity do shamelessly self-plug our most recent work [3] on how to modify the topology of a network to have the epidemic go subcritical and quickly disappear.
The basic idea in our paper is to keep the maximum number of edges from the original graph under the constraint that the adjacency spectrum is bounded. Since that's a NP-hard problem we go for an approximation algorithm.
In any case, Melting Asphalt's essays are really an example to follow! A gold standard for expository material!
[1] Ganesh et al. https://ieeexplore.ieee.org/abstract/document/1498374
[2] Prakash et al. https://link.springer.com/article/10.1007/s10115-012-0520-y
[3] Bazgan et al. https://link.springer.com/chapter/10.1007/978-3-030-04651-4_...
Cannot recommend this enough.
And on a slightly related note a recent Talking Politics podcast had Sir David King who was UKs chief Scientific Officer to Blair. Early on there was a terrible Foot and Mouth outbreak and Blair was at a loss how to prevent the outbreak spreading from farm to farm. But King understood SIR / SIS networks (and experts in this who wrote the books) and said "give me carte blanche and we will fix this - by day X we will see a tipping point" And the Army shut down every farm, and on day X the infections stopped and he had sufficient political capital to push hard on things like Paris climate treaty (which UK has a lot of impact on)
In other words understanding this article lead to a global first on CO2 reduction.
Science Works Bitches
The most interesting part was transmitting 'dead' information. In the linked article things are alive or not. Now expand this article so that you have a series of things that are being transmitted (maybe blue, red, and green dots to represent each). And then you want to 'kill green' so that green is no longer considered a valid state. Networks need to retain the notion of a tombstone (in epidemiology a residual antibody) to quash flare ups of previously killed information (which can happen when a node that has been down for a while rejoins the network).
It makes for some great coding exercises!
In the blunt form: language limits what we can say; Sapir-Whorf runs contrary to every-day experience. Sure, if ones native language contains le mos juste, it is easy to speak ones mind. But if not, the burden is not great. One must speak at greater length, using more words, and forming the intersections and unions of their meanings, to obtain the exact nuance that you intend. This is the routine craftsmanship of every wordsmith.
Early in the essay Kevin Simler posses a challenge "Here's an SIS network to play around with. Can you find its critical threshold?" What is most interesting is not the numerical value, lets just call it x. What is most interesting is that it is fairly sharply defined. If two idea are both fairly hard to transmit, and hence both close to x, we could easily have a situation in which the burden imposed by a missing mos juste makes all the difference. One idea has a transmissibility just above x and becomes an established staple of the culture. The other idea has a transmissibility just below x so it crops up from time to time but always dies out.
One looks around, admiring the cultural landscape. One idea is present, one absent. Why? Language! While it is wrong to claim that "a person's native language determines how he or she thinks", we have to take account of network criticality.
The much weakened Whorf-style claim that "a person's native language burdens their communications with trivial inconveniences" is plausible and unimportant at the individual level. But we may never-the-less find that "a social network's native language determines which thoughts die out and which ones take over most of the network."
Compare and contrast with Beware Trivial Inconveniences https://www.lesswrong.com/posts/reitXJgJXFzKpdKyd/beware-tri..., which claims that trivial inconviences have real world potency without needing the leverage provided by network effects.
> But if not, the burden is not great. One must speak at greater length, using more words, and forming the intersections and unions of their meanings, to obtain the exact nuance that you intend. This is the routine craftsmanship of every wordsmith.
This is a nice way of putting it, but I question how "easy" and "routine" it is. People can do this, which is why strong form of Sapir-Whorf sounds too strong, but it's not free - and like "Trivial Inconveniences" article shows, that's enough for it to not be done, especially if alternatives like "picking up a similar but not-quite-right word" or "not thinking the thought at all" exists.
I feel this could be especially impactful on imagination (the problem-solving kind), which can be viewed as a randomized reverse-lookup[0]. The brain suggests you things connected to what you're thinking about, and - at least in my experience - they usually come up as words or phrases. If you don't have a word for a concept, you may not think of that concept, and concepts related to it. Not that you couldn't think of it, just you usually and initially won't.
One could think of language as a cache of those "intersections and unions of meanings" that have proven themselves to be useful. Viewed like this it's an optimization trick, but we observe that everything we do and think is time and energy-constrained, so such optimizations can be the difference (especially on a population level) between how precisely you think a thought before you accept it as "good enough".
--
[0] - Meta: the way I figured out this idea actually involved the brain suggesting me the word "reverse-lookup", and me going out from there. My native Polish language doesn't have a word for "lookup", and especially "reverse lookup", so I wonder what would I came up with if I didn't know English?
As mentioned in the article, putting specialists together in the same room is one way to accomplish this, but I can imagine the same happening in the mind of a single polymath, who, though perhaps being mediocre in several subjects, connects enough dots to beat the competition to combining them in a novel way. It might also make sense to recruit a few such polymaths/generalists to be put in your room of distinct experts, since they might serve well as a sort of 'interconnect bus' between them.
That's what Think Tanks and Research Divisions used to be, You'd put a bunch of smart people from different disciplines together, give them some money and a vague direction and stand back.
Building 20 at MIT is another example I can think off, or the Collosus project during WWII (Tommy Flowers and Alan Turing where from radically different backgrounds - Turing was pure theoretical genius, Flowers was an apprentice mechanical engineer who put himself through night school to learn electrical engineer and then worked for the post office - together they (and others) built the Collosus Mk1).
I was sad that the author missed a number of chances to get into more detail about the classic reaction-diffusion problem [1]. I was reminded of a small project I did which produced similar animations, though with periodic boundary conditions, for learning about the Gray-Scott model. These websites are pretty helpful [2][3].
I haven't ever taken a class on systems so I don't know, but after reading this I wonder if the propagation of "scientific bullshit" and "truth" through a network can instead be modeled chemically as in a reaction-diffusion model. The last figure shows real knowledge fizzling out because it turns fake. It also lacks a slider so I can't play with the parameters but there should be some point where they oscillate back and forth, i.e. a Hopf bifurcation or a Turing bifurcation. Adding a bit more complexity might add some more depth to this post. I hope there will be a sequel!
[1] https://en.wikipedia.org/wiki/Reaction%E2%80%93diffusion_sys... [2] https://groups.csail.mit.edu/mac/projects/amorphous/GrayScot... [3] https://www.karlsims.com/rd.html
If I understand correctly the probabilistic infection rate is "history-less"; in other words, the probability of infecting an adjacent neighbor in the current state is not determined by the state transitions of any previous iterations.
It looks like you could model this naively with a discrete time Markov chain using a 3x3 stochastic matrix and three states: healthy, infected and deceased. I would guess you could do the same thing for the SIS model using states susceptible and infected with a 2x2 stochastic matrix instead.
In either case, modeling the epidemic as a Markov process would let you estimate the probabilities of criticality using the limit of the stochastic matrix. In fact, I think the critical threshold (probability of the epidemic going critical) will be given by left multiplying the initial probability vector by the limit of the stochastic Markov matrix.
Diffusion is a Markov process, yes. But you'd need three states per cell (not sure if that's what you meant by three states).
What bothers me, though, is the effort to link the mathematics to 'real-world' applications. I agree that forest fires, disease outbreaks, and the spread of ideas might be good candidates for this sort of modelling. But I think you'd need an awful lot of solid evidence to back that up.
Many years ago I went through teacher training, and one of the biggest things you learn is to always make material relevant to students by linking abstract concepts to real-world applications they actually care about.
It is true that in writing an article like this, you need to be very careful with your wording to distinguish between things that "appear like", "are similar to", "suggest", or even "is a first-order approximation of", versus stating that this is the model of epidemiology, forest fires, etc. (which needs citations, etc.). But in this particular article, the examples seem fairly straightforward as first-order approximations -- curious what sentences you're specifically objecting to?
Lines like this: If we're simulating the spread of measles or an outbreak of wildfire, SIR is perfect. The author could have said "this kinda-sorta looks like it might be useful in simulating wildfire but I haven't checked", but of course that would be less convincing and less exciting.
Which is fine as far as it goes. The problem is what happens when someone takes one of these models seriously without actually checking the details, or without being qualified to check them.
Not this particular article, no. But there's a whole genre of excited mathematical modelling literature where the author demonstrates a gee-whizz concept that looks like it could be really useful. The trouble is that once you start digging down into the specific details, they turn out to be really hard to get right, and at best you end up with a model that's brittle, for want of a better word.
An example that I have in mind is the literature on power law distributions. A little bit of theory showed how power law distrbutions could arise via a process known as preferential attachment, and everyone got excited and suddenly people were spotting them everywhere. The literature on this topic is massive.
The thing is, it turns out that it's quite hard to check that a given dataset follows a power law. This paper [0] showed that many of the claims were sloppy, and the researchers hadn't been careful with their statistics.
The crux of what I'm saying is that establishing that a model fits well is hard, whether it's a diffusion model, a power law distribution, or anything else. If someone wants to claim that some mathematical widget can be used to model X, they'd better be able to back that claim up with a real demonstration and carefully laid-out details. Otherwise they're just waving their hands in the air.
[0] http://www.cse.cuhk.edu.hk/~cslui/CMSC5734/Clauset_Shalizi_N...
As someone who spent a fair number of hours teaching mathematics to engineering students, exciting is what you want. What use is it to state the complex hypotheses of a theorem if the student cannot feel the result coming?
That's a problem with absolutely any kind of statement you can put on-line. There's only so much an author can do to prevent stupid from misreading them; the responsibility is not all on author here.
> The author could have said "this kinda-sorta looks like it might be useful in simulating wildfire but I haven't checked"
Why? Maybe they actually checked. I did, and keeping in mind that I'm not a medical scientist, it does seem that SIR model with modifications is widely used to study disease spread, and it also does look like a good first-order approximation for measles. It also does look like a good first-order approximation of wildfires.
I actually did a thesis on using cellular automata for simulating indoor fires and used some of the same ideas presented here. SIR is essentially what I'd get if I ignored the details of heat convection, conduction and radiation - which at the scale of forest fire is something you can do (unlike my work, where modelling these details was kind of the entire point).
How do you know? To validate this sort of model surely you need to know an awful lot about statistical modelling and about forest fires.
The main sort of insight this model would give you is that setting up clear spaces like roads through a forest would hinder the spread of fire. If you took the model literally, you might end up ignoring the fact that sparks can be carried by the wind to areas that are far away from the trees that are currently burning.
> it does seem that SIR model with modifications is widely used to study disease spread
Fair - there's a whole wikipedia page [0] about this sort of model. But like I'm saying, that page is big on theory and light on evidence. Those models are full of parameters like transmission rate that are not typically known until after the fact.
The world is full of theorists writing down academic models that are, frankly, a little useless. What I would find more convincing is a writeup of how a big practitioner health organisation like the CDC or the WHO used one of these models to gain a new insight that they couldn't have found any other way.
[0] https://en.wikipedia.org/wiki/Compartmental_models_in_epidem...
First-order approximation and all. You validate according to your needs, but yes, you'd also need to know a lot about statistical modelling and the domain. I'm guessing the author just read that SIR can be used for some diseases and forest fires, and that what they read was written by people who do know that. FWIW, our CA models were validated by our supervisor (who had access to firefighters) to roughly the level of "reproduces what happens on recordings of real fire" - which was good enough to show that the model has a potential to give real-time insights, but not something I'd like an actual firefighter to use on the scene.
> If you took the model literally, you might end up ignoring the fact that sparks can be carried by the wind to areas that are far away from the trees that are currently burning.
That's a very good point. However, like with all models, you need to be aware of the limitations. Maybe the author should have guarded the text for this, but I doubt the government epidemiologists and firefighters were the target audience here. I expect these professionals to understand the models in greater depth before using them (though maybe I'm hoping for too much - given how our industry is full of "professionals" mindlessly copy-pasting code from SO).
> that page is big on theory and light on evidence
Fair. I was actually going to link to a Wikipedia page in my previous comment, but I noticed a surprising lack of citations for the claims made. So instead I went and looked around Google Scholar before saying that "it does seem that SIR model with modifications is widely used to study disease spread".
> Those models are full of parameters like transmission rate that are not typically known until after the fact.
Sure. Again, I hope that no epidemiologist uses the article to develop disease spread models. But it works as giving general overview and intuition about network models, with focus on the phenomenon of criticality.
> What I would find more convincing is a writeup of how a big practitioner health organisation like the CDC or the WHO used one of these models to gain a new insight that they couldn't have found any other way.
I would absolutely love to see that.
BTW. I hope we're not just arguing about whether the word "perfect" was used in the article correctly.
I guess I'm trying to make a point about theory vs. practice. I think theorists tend to be pretty cavalier about writing down models and waving away the fine details, whereas practitioners tend to appreciate how hard it is to get the details right.
As an example, the literature on finance is full of this stuff. There's a whole body of literature on how to create an optimal stock portfolio under various constraints assuming you know the joint distribution of individual stock returns. It turns out that fitting that distribution in a sensible way is extremely difficult to do. The theorists came up with a `clever' model that's mostly useless in practice, but everyone still insists that it has `applications' in finance.
Personally I find theory really interesting, and beautiful in its own right. It just annoys me when the usefulness of that theory gets overstated.
This article is a great example of that for diffusion I think.
The real-world examples of epidemiology and city technology expertise are perfect IMHO. Kudos to the author!
As a small translation aid, when physicists talk about criticality, they tend to talk about "dimensions" instead of "degree".
In a one-dimensional system, a line, you can have at most two nearest neighbors, in a two-dimensional system 4, 3D has 6 neighbors, and so on.
Physicists have no trouble talking about fractional dimensions either, which can be realized in surfaces, fractal-like substances and so on.
Dimensions higher than 3 are achieved when interactions between non-nearest neighbors are relevant.
It was one of the more eye-opening math books I ever read.
I do not believe the spread of knowledge works this way, however. For one thing, knowledge is productive. Consider a population of agents each having a body of knowledge some kind of prolog-like set of facts and implications. Clearly the receipt of the same new fact p by different agents will have different logical closures. If for some agents but not others there is the fact p |= q, then the spread of q might appear to work quite differently than the epidemiological model.
This article takes a complex set of ideas and presents them by using appropriate symbols, building a base of knowledge, and then adding to it incrementally. I thoroughly enjoyed it, and I hope many of you take the time to enjoy it as well.
(One final thought - one of my early JavaScript projects a couple decades ago was to write a simulation like this using Conway's Game of Life and some GIF files I created in MS Paint of red/blue dots, two types of trees, or the front/back of pigs. So there's some nostalgia boosting my enjoyment here!)
I'm working on a map generator, and the previous version generated land by placing tiles at random. I implemented the SIR algorithm, and now the map looks much more like an actual map.
which presents the first method which accurately quantifies the spreading power of all nodes in a network.
It's based on applying statistical physics to diffusion over a network, which is why it outperforms all prior approaches such as degree/k-shell/page rank/ etc etc.