Categories
Uncategorized

COVID-19 and the “Minimum Dominating Set”

Unsurprisingly, the spread of epidemics and network analysis go hand in hand but this article in particular caught my attention due to its bold and perhaps even controversial application of graph theory to a morbid question:

How many Americans need to die before every American knows one of the dead? 

Adam Rogers – Death Cuts the Degree of Separation Between You and Covid-19

I thought at first that it was a bit of a silly question, one that we really shouldn’t have to ask. But I decided to I give the article a chance: it was the best lead I had relevant to current events.

At first they took a relatively simple approach to the analysis: Take the number of people a person is likely to know on average.  Find the percentage of one death out of that total and multiply that by the entire population.  This depended very heavily on the definition of “number of people a person knows on average” and estimates ranged from 546, 000 all the way to 1.6 million people.

Obviously, that isn’t entirely accurate, but it’s the caveats they introduce afterwards that present interesting subtleties about networks that apply to all sorts of analyses about them.  For instance, the way disease spreads isn’t uniform or random.  In class we’ve already learned that the structure of the graph in it of itself isn’t even close to the inherently random processes that generate a graph like Gnp, so it’s not hard to consider that the processes that spread information or illness would depend on the outside context that nodes live in.  Certain cohorts or clusters are far more susceptible to COVID-19 just based on the foci they are involved in or who they are (i.e. older adults or the elderly).  Furthermore, the mutual interaction of clustering and homophily lead to a phenomenon termed in the article as overdispersion, which is a statistical term for greater variance than expected for a particular variable.  This causes the number of people that need to die to go up, because even as the deaths spike, certain communities may remain isolated from the direct effects of the pandemic.

Besides the context, the structure of networks plays a role as well, causing the number of people that need to die to be lower than we expect given the simple analysis above.   Particularly it is the uneven distribution of degree, analogous to the funneling described in Milgram’s experiment related to the fact that certain people have more connections than others.  In this article, it was termed the friendship paradox the idea that your friends probably have more friends than you.  The unfortunate conclusion is however, that people who have a certain “centrality” in the network also have a greater risk of getting sick – and because they know more people, and such a death would mean that the less people overall would need to die before everyone knew someone personally.

Finally however, they bring up that even without all the caveats and extra reasoning about the context of these graphs the theoretical problem we are fundamentally trying to solve is NP-complete.  The problem can be called the Minimum Dominating Set and can be framed as:

“For a given graph, what is the minimum set of nodes such that every node in the graph has at least one neighbor in that set?” 

It is distinct from the “Vertex Cover” problem (which was covered in the CSCC63 Computational Complexity course) where we ask:

“For a given graph, what is the minimum set of nodes such that every edge in the graph has at least one endpoint in that set?” 

Regardless, both are NP complete, as prove by Richard Karp in 1972 (if you’re interested, you can try to prove this using a linear reduction from the set-cover problem, see the the section on computational complexity).  This is to say, of course, that even the simplest version of the problem we proposed cannot be solved in polynomial time, only approximated.

Which perhaps brings me back to my initial thought about this topic.  While its analysis may be intellectually stimulating, and provide an opportunity to ponder tricky problems, it really isn’t the reason why such a question is asked in the first place.  Because in reality, even if we were able to answer such a question efficiently and present the answer to people, it wouldn’t change the very psychological problem that lead to all of this thinking in the first place – that people choose not to listen to the facts and choose not care when it doesn’t affect them personally.  Perhaps, it is not the sheer number of connections, but the weight those connections hold that requires a collective understanding.

A leap of faith, as the author put it.

Or put in other terms, a change of heart.

Source: https://www.wired.com/story/death-cuts-the-degree-of-separation-between-you-and-covid-19/

Leave a Reply