I am modeling an Independent cascade model in graph diffusion, by simulating a disease. I have an undirected graph, and I need to choose 50 nodes to vaccinate before the disease starts spreading, and my goal is to get to the least amount of infected nodes.
I am trying to figure out a way to choose those 50 nodes wisely in order to achieve the beat outcome.
I thought about choosing the 50 nodes with the highest degree, but I am looking for alternatives and better ways.
If it's a small graph, an evolutionary algorithm or MCMC might be a good approach. Represent your graph as a vector indexed by node, where nodes that get vaccinated are 1 and everything else is 0. Define your loss as number of nodes infected after some fixed time interval, and fit the graph-vector that minimizes that loss.
An alternative that would probably work (both for a small or large graph) would be to encode your graph topology as graph and node embeddings, then fit an RL agent that takes a graph embedding as input and returns a state vector that you compare to your node embeddings (something like cosine similarity would probably work here, or just fit a separate scoring model that takes the agent state and a node as input) to get a ranking of the top 50 candidates to vaccinate.
Heuristically, you could just try different centrality measures. You already identified degree centrality as a candidate heuristic: I'd recommend you consider something like pagerank, eigen centrality, or betweenness centrality as well.
One issue that immediately comes to mind here is that the graph topology and scale will have a lot of impact on the optimality of your intervention. It might be the case that there is no heuristic under which choosing fifty nodes like this will make a difference. The famous Chains of Affection study (Bearman et. al, 2004) comes to mind. The authors wanted to model the topology of student sexual relationships at a high school to recommend interventions to reduce the spread of STDs. Like you, they went into the study with the assumption that there was likely a small cohort of students they could target to have a sizable effect on the broader population. Here's some relevant discussion of their findings:
Discussion
Disease diffusion is widespread among adolescent populations. The standard models that epidemiologists use to describe the dynamics of diffusion carry implicit ideas about the contact structure through which disease travels. These ideas are associated with distinct structural features of sexual networks. The most critical feature in STD epidemiology is the idea of a core, which is associated with cycles in networks. Moody et al. (2003) have demonstrated that very low average degree networks can give rise to densely interconnected cores, characterized by high cyclicity. In our data, we find that this key structural feature is largely absent. We have proposed a reason for its absence, specifically a norm against seconds partnerships. [...]
In theory, spanning trees are among the most efficient structures for diffusion since the absence of redundant lines maximizes reach at lowest density. Yet their efficiency is counteracted by their fragility: spanning trees are highly susceptible to breaks in transmission. [...] It follows that for highly infectious diseases with long periods of infectivity, transmission is also quite efficient under a spanning tree. Yet if the duration of infectivity is short, or if the disease is not particularly infectious, the probability of transmission within any given partnership is low. From the perspective of disease spread, failure to transmit disease within a given partnership is effectively a structural break in the network (Watts 2003). Since the natural infectivity and duration of infectiousness varies across STDs, we believe the most effective strategy for reducing disease diffusion rests on creating structural breaks.
We might then ask a new question: What kinds of policy intervention will be most effective at inducing structural breaks in the sexual networks of adolescents? Here the answer is exceedingly simple. Assume that some proportion of actors who are “reached” through an intervention decide to change their behavior. Under core and inverse core structures, it matters enormously which actors are reached, while under a spanning tree structure the key is not so much which actors are reached, just that some are. This is because given the dynamic tendency for unconnected dyads and triads to attach to the main component, the structure is equally sensitive to a break (failure to transmit disease) at any site in the graph. In this way, relatively low levels of behavior change—even by low-risk actors, who are perhaps the easiest to influence—can easily break a spanning tree network into small disconnected components, thereby fragmenting the epidemic and radically limiting its scope. Obviously, similarly low levels of change in cores will have little impact.
All this is to say that you might be operating under a false premise: targeting a small subset of your population might not be the best allocation of your resources. There may be a more effective intervention that targets the graph more broadly, in which case "Which 50 nodes should I vaccinate?" is the wrong question. If you can attribute a monetary cost to implementing this program, it would be worth trying to model some kind of broader intervention that falls into the same budget. Would the vaccination program be comparable in cost to an awareness marketing program that could reach more of the population? Something to consider.
