Skip to main content
GISc — a “Leitwissenschaft” (a leading or guiding science) Indiana University

GISc — a “Leitwissenschaft” (a leading or guiding science)


at the Kelley School of Business

Explosive Quarantine: A novel approach to spatial quarantine

Posted on by rudy

Explosive percolation (https://science.sciencemag.org/content/323/5920/1453) is a recent concept where random networks R0 (basic reproductive number) is reached abruptly. When R0 crosses 1.0 there is complete connectivity (a network of nodes and links are completely connected; #nodes = #links makes R0 =1 because R0 = #nodes/#links). This 1912 paper https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3320609/ shows the first evidence of mathematical modeling of infections. Later Erdos & Reyni developed the math for random networks and further scholarship showed the link between R and networks.

Explosive percolation is an extension of random networks.

But first, let’s start with random networks. Your regular street network is a random network. That might seem strange at first but the definition of a random network: In a street network: each node (or intersection) has an average of 4 links (or streets, defined as a continuous uninterrupted segment that starts and ends in an intersection). Some nodes may have 3 links originating from it (a T- intersection), 4 links (regular 4-way stop), 5, 6, 7 or sometimes, rarely, more (sometimes called circle centers). However, it’s mean is 4 and varies between 1 through 8, but mostly it is 3, 4, or 5. This follows a statistical distribution called a bell curve (Gaussian) with mean 4 and spread approximately 1 (see left graph below from Barabasi (barabasi.com/f/226.pdf).

http://barabasi.com/f/226.pdf Barabasi showed that road networks are random whereas airline networks are scale-free.

Now one way to create a random network is to first have a fixed number of nodes, say n, then join any two randomly selected nodes with a link. When you join enough nodes something magical happens: there is complete connectivity in the system when the #links reaches #nodes. Suddenly no node is isolated! This a continuous process and the phase change (or total connectivity: R0 = 1) occurs smoothly.

In 2015, a paper by Dimitris Achlioptas, Raissa M. D’Souza & Joel Spencer:

Explosive Percolation in Random Networks
https://science.sciencemag.org/content/323/5920/1453
showed that instead of randomly assigning 2 nodes with one link, if we attach pairs of links (3 nodes with 2 attached links), we get a sudden build up of connectivity (R reaching 1) but abruptly. This abrupt change is called a phase change in physics and in this case it is not continuous.That is: there is complete connectivity but it happens like water freezing to ice at a particular temperature of 32F. Raise one degree and all will melt. In the case of explosive percolation (proven to happen only with finite n), the links suddenly reach complete connectivity unlike with random random networks where you can see slowly the network is reaching complete connectivity.
[One note on paired random links is that it relates to a first order markovian process and can be thought of as random walks].
Here is the abstract for the paper:
“Explosive Percolation in Random Networks. Abstract: Networks in which the formation of connections is governed by a random process often undergo a percolation transition, wherein around a critical point, the addition of a small number of connections causes a sizable fraction of the network to suddenly become linked together. Typically such transitions are continuous, so that the percentage of the network linked together tends to zero right above the transition point. Whether percolation transitions could be discontinuous has been an open question. Here, we show that incorporating a limited amount of choice in the classic Erdös-Rényi network formation model causes its percolation transition to become discontinuous.”

I did some simulations to show that road networks can suddenly isolate using random networks when they need to access a central point in the network like connecting a house (a random node) to a hospital (a central node). Sometimes just a 20 percent drop in links cause a 100 percent drop in accessibility to central nodes (see below).

It is scale free (see above). It does not matter what spatial filter (e.g. zip code areas, blocks, voronoi service areas etc.). Some areas will lose all connectivity even with as low as 5 percent dropped links but some areas will be connected even with 90 percent loss of links. The above experiment can be further studied to show that dropping pairs of random links will create this scale free condition even faster and with abrupt phase change!

What about paired random links? Explosive percolation

 

The above graph shows explosive percolation (orange line) vs gaussian percolation (blue line). When you drop, say 20 percent of links we get gaussian percolation (blue line showing lack of access to e.g. central places like hospitals) where as explosive percolation (orange line showing access is “baaad”).

With gaussian percolation (dropping randomly say 20 percent of street segments) we see whole segments of the map becoming ‘marooned’ (‘marooned’ meaning 100 percent lack of access to, say, any hospital).  With explosive percolation (dropping 20 percent but paired street segments randomly — i.e. dropping 10 percent + their neighboring segments jointly). Do we see explosive ‘marooning’? I am running experiments and seeing that no percolation is occuring. Maybe 90 percent drop will do? Please wait for an update soon.

Explosive marooning may have implications to contain, say explosive pandemics likes Covid19 (coronavirus).  For example: by installing road barriers/medical screening at strategic points within optimally derived hospital coverage areas we can optimally isolated and treat marooned zones. For areas with resilient connectivity, isolation will not be possible so other strategies may be more appropriate.

“Metastatic” growth

The marooning in certain areas create what can be termed as “metastatic” growth (all at once) https://www.pnas.org/content/111/46/E4911 .

Social Networks and Transportation networks: diffusion of disease implications 

The paper ‘Modelling disease outbreaks in realistic urban social networks (Eubanks et al 2004)’ http://www.uvm.edu/pdodds/research/papers/others/2004/eubank2004a.pdf provides an excellent exposition of social and transportation networks that models the intricate contact process by which diseases spread. They use bipartite graphs as a novel and enhanced way to match origin destination trips. Using a GIS, I model origin-destination trips the traditional way. I guess, using bipartite matching may improve the model.

Explosive Percolation, Backward Bifurcation and Hysteresis: Is there a link?

   

Above are two diagrams (Paul Gruenewald, PRC Berkeley) that show when population is mixed, R1 can be reached without reaching 1 (hysteresis)! But, the nature of population mixing is not explored much. With Achlioptas et. al. we may be able to identify this nature …

[White Paper] Hospital Architecture and Infection Modeling: A Network Approach

Posted on by rudy

 

 

 

I am working on a proposal that may be of interest to NSF RAPID. My background in architecture, medical geography, location optimization and network science may help identify key scientific insights and spatial inefficiencies in hospital infections.

“

Hospital Infection Model — A Network Approach

 

If infections are due to exposure and exposure is a function of distance then infections can be reduced by optimizing travel behavior of infection agents (e.g. doctors, nurses, patients, germs) inside a hospital. We use the Sidney & Lois Eskenazi Hospital at Indiana University Purdue University Indianapolis to demonstrate an ~180 percent increase in ‘time to washing’ efficiency by using best optimal locations for hand washing. We simulated all probable pathways within the hospital architecture (all rooms, hallways, restrooms etc.) using Simulation Science (Polyak averaging), Computer Aided Design (CAD) and Geographic Information Science (GISc) to determine a globally optimal set of locations of disinfection stations (wash place, restrooms, detox stations etc.). We minimize distance to disinfection stations using Network Science, human behavior, Operations Research (p-medians), CAD & GISc. Preliminary results show large variations in distance to infection when sub-optimal locations for disinfection are used. Combining Network Science with Operations Research optimization approach we find best locations for disinfection. Presently, we apply completely chaotic movement behavior (completely deterministic billion plus routes) and robust stochastic optimization techniques to establish empirical proof and theoretical insights. Finally, we would like to show the ’emergent’ or tipping point behavior of COVID19 infections. This would entail obtaining a compendium of hospital floor plans (across all USA) to support the collection of critical ephemeral data and conduct research on an accelerated basis to fight COVID19. Researching confined geometrical and topological spaces will help us understand infection mechanics and would contribute directly to geographic and spatial theory, spatial science, location science and infection epidemiology. In addition, we will investigate the ’emergent’ properties (related to the Reproductive Number R0) in this confined spatial context. We would like to investigate the especially important ‘backward bifurcation and hysteresis’ principle of spatial models as it pertains to p-median optimization that contributes to infection control.

 

 

Sidney & Lois Eskenazi Hospital Floor Plan Architecture

Simulation details of all possible trips inside a section of Hospital floor

 

OPTIMALLY LOCATED STATIONS

  1. There is a 182 percent increase in efficiency (against legacy/random/unoptimized detox stations)
  2. i.e. a significant reduction between wash times
  3. If applied, there can be a significant reduction in Hospital Acquired infections related deaths

 

Subsequently, we would like to answer questions from real hospital data that we will collect, as follows:

(Based on hospital floor architecture, we have agents flowing through the network with some latent risk (asymptomatic) and some known risk (nodes w/ patients) and then you have nodes that reduce risk of agents flowing through (washing station). So then the network science questions are …)

  1. How do you rewire the network (architectural design) to reduce the spread of Covid19?
  2. How do you optimally place reduction nodes (washing stations) to reduce spread of Covid19?
  3. Where do you place known risk in the network (patients with Covid19) to minimize risk?
  4. How do you change behavior or the agents to reduce risk?

 

In addition, this optimization approach can be adopted to any floor plans like fire stations, office buildings, public places etc. with appropriate parameterization of infection propensities in the network nodes and weighted link nodes. We can join the micro-spatial CAD environment with the meso- & macro- spatial GISc environments to create seamless integration for a comprehensive infection control system for health inside and outside the hospital.”

 

[White Paper] Hospital Architecture and Preventing Infections: A Network Approach

[The NSF rapid can be a good fit for my NetSci 2018 Paris conference poster Hospital Architecture and Infection Modeling: A Network Approach see https://iu.box.com/s/4c38d79abqhyg9eeucxrc66gdrzhowrh]

  • Abstract: If infections are due to exposure and exposure is a function of distance then infections can be reduced (preventative therapy) by optimizing travel behavior of infection agents (e.g. doctors, nurses, patients) inside the hospital. We simulate all probable pathways within the hospital architecture to determine a globally optimal set of locations of disinfection stations (wash place, restrooms, detox stations etc.) that minimizes infections using network/graph theory and GISc. Results show large variations in distance to infection when sub-optimal locations for disinfection are located. Using a graph theoretic integer programming optimization method we find optimal sets locations for disinfection. Presently, we apply completely chaotic movement behavior (completely deterministic) and use robust stochastic optimization techniques to establish further empirical proof.
  • Keywords: network science, infection, agent based simulation, operations research, GISc, applied graph theory, hospital architecture.

Covid19 is a specific ‘leaf’ from the SARS-coV-2 ‘branch’ of the Coronavirus ‘tree’.

Nosocomial infections, like MRSA and possibly Covid19 (we don’t know the re-infection rates), are a result of treatment in a hospital, but secondary to the patient’s original condition.

  • Before the Covid19 pandemic, the US CDC estimates that the total direct costs of such infections are above $17bn.
  • Restating Kho (2008): virus innovate and cooperate and evolve and adapt to resist drugs and can transfer genetic traits between strains …
  • For the first time, we apply network science, operations research, stochastic simulations of human behavior and Geographic Information Science to clearly demonstrate flawed hospital processes, including inappropriate sanitizer placements and poor hand washing by providers.
  • Collecting bedside vital signs using the latest streamlined and automated processes is potentially increasing interpatient spread of infections.
  • It is more important now than ever to provide access to sanitizers/restrooms/detox-units across hospital architecture in an optimal fashion.
  • Using networks science, optimal sanitation units can potentially reduce MRSA infections. However, optimal locations can only be empirically derived using very large simulations and optimization algorithms as shown below.

Background

Methicillin-resistant Staphylococcus aureus (MRSA) is a bacterium responsible for difficult-to-treat infections in humans. It may also be referred to as multidrug-resistant Staphylococcus aureus or oxacillin-resistant Staphylococcus aureus (ORSA). MRSA is by definition a strain of Staphylococcus aureus that is resistant to a large group of antibiotics called the beta-lactams, which include the penicillins and the cephalosporins. MRSA/Methicillin Resistant Staphylococcus aureus was discovered in 1961 in the United Kingdom. It made its first major appearance in the United States in 1981 among intravenous drug users. MRSA is often referred to in the press as a “superbug“.

  • Nosocomial infections are infections which are a result of treatment in a hospital or a healthcare service unit, but secondary to the patient’s original condition. Infections are considered nosocomial if they first appear 48 hours or more after hospital admission or within 30 days after discharge.Nosocomial comes from the Greek word nosokomeion (νοσοκομείον) meaning hospital (nosos = disease, komeo = to take care of). This type of infection is also known as a hospital-acquired infection (or more generically healthcare-associated infection).
  • The Centers for Disease Control and Prevention (CDC) estimates that each year in the United States there are about 1.7 million nosocomial infections in hospitals and 99,000 associated deaths. The estimated incidence is 4.5 nosocomial infections per 100 admissions, with direct costs (at 2004 prices) ranging from $10,500 (£5300, €8000 at 2006 rates) per case (for bloodstream, urinary tract, or respiratory infections in immunocompetent patients) to $111,000 (£57,000, €85,000) per case for antibiotic resistant infections in the bloodstream in patients with transplants. With these numbers, conservative estimates of the total direct costs of nosocomial infections are above $17bn. The reduction of such infections forms an important component of efforts to improve healthcare safety (BMJ 2007).
  • IEEE ENGINEERING IN MEDICINE AND BIOLOGY MAGAZINE 0739-5175/08/ ©2008IEEE NOVEMBER/DECEMBER 2008
  • Not only that, Kho (2008) states: “Bacteria innovate and cooperate. They evolve and adapt to resist antibiotics and can transfer genetic traits between strains.”

Similarly, Covid19 is highly infectious and require similar sanitation.

 

Hospital Floor Plan Architecture

Simulation details of all possible trips inside a section of Hospital floor

 

OPTIMALLY LOCATED STATIONS

  1. There is a 182 percent increase in efficiency (against legacy/random/unoptimized detox stations)
  2. i.e. a significant reduction between wash times
  3. If applied, there can be a significant reduction in Hospital Acquired infections related deaths

APPENDIX

First, [A] we clarify with an Example. Second, [B] we Formalize and Compute the optimal solution.

 

[A] Example: Suppose there were five detox stations (hand-sanitizing stations, bathrooms etc.) in a hospital floor. Are they optimally location to reduce infections since distance to cleaning facility increases infections proportionately. We want to ‘optimally’ locate these facilities by minimizing the cost of walking to those stations for all travelers on all trips. Costs can be represented in terms of distance or travel times, representing trip impedance, and we can define five optimal “p-median” locations which simultaneously minimizes trip impedance for all locations assuming that every person on the hospital floor wishes to go to their nearest location – the “median” location – minimizing, in principle, the total cost of walking for all points of the floor.  Now suppose that there are ‘n’ people walking from some location to these five outlets. The total distance traveled by each person to their nearest station can be measured using shortest paths to the nearest of the five median-based locations.

Not all trips are close to these stations. Trips away from these stations will face more distance and hence they are less accessible.

 

[B] Formalize and Compute optimal solution: Strategically placing five outlets in order to minimize the total distance traveled by all ‘n’ individuals is a challenging task. Randomly selected the five stations will not be optimal. However, methodically choosing all sets of five locations out of a typical floor with 100s of thousands of potential sites (of stations) provides a combinatorial problem that requires more than polynomial computation time O(Nk).  This location problem is common in determining geographic locations of outlets and other businesses or services that wish to optimize locations relative travel patterns in urban settings and can be solved using a group of mathematical models called the p-median problem and is typically formulated as an Integer Program (IP) (ReVelle and Eiselt 2005)[1].

The least cost trip can be identified as that route which minimizes distances to the 5-locations.  But we can also define a second least cost route, a third least cost route, and so on (i.e., called k-routes, where k=1 means the least cost one; e.g when we use Google routes they provide k=3 or 3 best routes ranked).  Therefore, for any ‘p’-median location of outlets, ‘n’ people can take k-routes. In the mathematical optimization context, this translates into a parsimonious representation by using graph theory where: p-median (nodes), n people (nodes) and ‘k’ routes (links) form a network that can mathematically be investigated for optimal location of p-medians when k=1 (the shortest route chosen).  Direct estimation of all possible k-routes would be an ideal way to simulate human behavior since people may not take or know the optimal route. In addition, solving this problem would take exponentially more computational time as number of people (n) increase (an NP-hard problem, (Reese, n.d.); (Schrijver 1986)).  We can, however, simulate a sample of k-routes using computational methods and convert a well-defined deterministic but computationally hard problem into a probabilistic but computationally easy problem.

 

 

 

REFERENCES

 

Albert, Réka, Hawoong Jeong, and Albert-László Barabási. 2000. “Error and Attack Tolerance of Complex Networks.” Nature 406 (6794): 378–82. https://doi.org/10.1038/35019019.

Hakimi, S. L. 1965. “Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems.” Operations Research 13 (3): 462–75.

ReVelle, C. S., and H. A. Eiselt. 2005. “Location Analysis: A Synthesis and Survey.” European Journal of Operational Research 165 (1): 1–19. https://doi.org/10.1016/j.ejor.2003.11.032.

Schrijver, Alexander. 1986. Theory of Linear and Integer Programming. USA: John Wiley & Sons, Inc.

Winston, Wayne, and Jeffrey Goldberg. 2004. Operations Research: Applications and Algorithms.

 

[1]

-The End-

2 Trillion DOS (Drones Operating System)

Posted on by rudy

Hi,

A few years back (in 2019), I gave a talk named ‘1 Trillion DOS‘ in Bloomington, Indiana at their first IOT (Internet of Things conference). Over the last 3 years, I have devoted my time into making last mile drone delivery a more concrete endeavor. SkyDOS is a drone operating system company that I have started with serial entrepreneur David Woll, who is currently the CEO of SkyDOS.

We qualified for a top ten spot at the IU startup competition, Oct 13, 2022 in Bloomington. Lots of fun. And, although we did not win a prize there, we had many useful and fun conversations.

We presented an updated version of SkyDOS. Things are starting to roll and we are planning on submitting our first NSF SBIR grant.

Here’s a pdf version of the 5 min presentation:

SkyDOS 5 min final.pdf

Regards, Rudy B.

Predictive Speech!

Posted on by rudy

Once again we are at the crossroads of technology and its limits. In the future, you will talk to someone from a Moon base, but wait! … There will be a 3 second delay. The speed of light (or internet, telephony, messaging, video) is a huge barrier in space communications. Mars is 3 light minutes when closest and 16+ mins. when earth and mars are at the opposite ends of the sun.

So how do we carry a conversation?

Big pregnant pauses or … predictive speech?

Just like emails are now supported by automatic phrase extensions, we will upload our ‘type’ into the AI and they will carry on the conversation with us sending keywords intermittently. Speech will become this new habit we are unfamiliar with now. More on this later …

‘Scientific Paradoxes’ in the SARS-COV2 Pandemic

Posted on by rudy

A 1994 paper by the geographer-physicist duo, Gould & Wallace (https://www.tandfonline.com/doi/abs/10.1080/04353684.1994.11879669 ) showed the mistakes of traditional epidemiologists in understanding the spread of AIDS due to their focus on the continuous time series differential equations and not on the spatial heterodoxy of quantized spatial jumps in AIDS diffusion. A quarter century later, with enormous progress in network epidemiology, spatial epidemiology, spatial statistics and the new field of network science we are still held back by temporal epidemiology, or at the most macro and meso scale spatial models (global and country/regional based units). Micro-level spatial models are absent. Moreover, we need a hierarchical spatial (macro-meso- micro) and temporal interaction model to understand this pandemic. Gould & Wallace, through a series of discoveries, showed the complex ‘backcloth’ of transportation vectors (streets, highways, air routes etc) that pushed the AIDS pandemic. The difference between AIDS and COVID2 is that latter is way faster. Here, time is squished, reducing further the value of the temporal differential equations that depend of stability (2nd order differentials require equilibrium). So the only way out is controlling micro-scale spatial diffusion.

What is spatial diffusion?

What are the tools to stop spatial diffusion?

 

[use per capita gas use to show transportation footprint of rich nations and hence their contact network larger than poor countries; Greece having less problems than richer neighbors; Vietnam than China (adjusted for quarantine quality)

SPDEs & Point processes

Posted on by rudy

 

It would be useful to provide an update on the latest in spatial point pattern analysis. For national grants etc. the ball has moved for spatial point analysis from geary-g stats etc to SPDEs (Stochastic Partial Differential Equations) implemented through INLAs (Integrated Nested Laplace Transformations). It all sounds very math-y but it’s quite easily implemented through R software (it’s more of a problem with R install than running the codes!). It’s useful with big data.

SPDE : according to Blangiardo & Cameletti “…spatial process is second-order stationary if the mean function is constant in space …but [sic] …The disadvantage of the modeling approach involving the spatial covariance function is known as “big n problem” (Banerjee et al., 2004; Jona Lasinio et al., 2013) and concerns the computational costs required for algebra operations with dense covariance … In particular dense matrix operations scale cubically with the matrix size, given by the number [emphasis me because of big data] of locations where the process is observed. A computationally effective alternative is given by the stochastic partial differential equation (SPDE) approach (Lindgren et al., 2011) and consists in performing the computations using a GMRF [Gaussian Markov Random Field] representation of the GF [gaussian field], thus allowing us to adopt the INLA approach. …”
An open source version (code included can be found here http://www.statistica.it/marta/stbook/Chapter6.R) : https://sites.google.com/a/r-inla.org/stbook/ chapter 6  “…point level—presenting Bayesian kriging through the stochastic partial differential equations (SPDE) approach and showing how to model observed data and also to predict for new spatial locations…”

 

A Trillion DOS

Posted on by rudy

 

Tell us about your idea:

 

“1 Trillion Drone Trips!” I presented this idea at the ‘Internet of Things Symposium’ held at Indiana University in April 2019. Imagine: your friend 3 miles away made an amazing cocktail and sends you a sample for your opinion?

Or, in 2050, a grandma wants an elephant shaped refrigerator and her granddaughter taps on her haptic “screen” ordering “one-tap” from Walmart a modular refrigerator to be 3D printed at their massive printer shop 2 miles away, shipped 2 pounds at a time by a fleet of 150 electric ultralight drones! And, assembled by the $5000 home robot, relieving grandma of all the trouble of purchasing, assembling and siting early 21st century 3D objects in her private environment. Or, “Electrification of aircraft, in general, is expected to fundamentally change the aerospace industry in the near future,” Furbush said. https://techxplore.com/news/2019-04-jetsons-future-role-cars-sustainable.html.

Americans took ~ 411 billion daily vehicle trips last year or about 1,500 trips per person. With the above grandma example, capitalist societies will hyper charge delivery, far beyond the half-trillion trips, similar to what we saw with the communications explosion triggered by the internet (phone calls to video chat sharing).

I am proposing a novel’-ish’ idea to make drones follow a 3D ‘operating system’ that replicates our already existing terrestrial roadway system … to be replicated in the sky.

What will it take to achieve this idea, and why now? 

There are ~50 million road segments in the US and it has all the trapping of complex traffic rules. Automated vehicles are predicted to use our existing roads. However, due to automation they need no traffic lights or other traffic furniture (everything is computerized with predicted routing using a centralized computer system).

I developed, using the latest traffic simulation geographic information software, a traffic-signal-less operating system for terrestrial vehicles and projected them into space 300 feet above ground. 200 to 400 feet is the FAA restriction for drone space so a ‘pipeline like’ aerial highway will be used and sold to companies (similar to how the Federal Communications Commission ‘sells’ airwaves). This will eliminate the chaos of insect-like swarms of drones affecting quality of life by restricting airspace based on a regulatory framework. In addition, centrally planned trips would eliminate ‘unqualified’ and rogue drones to ever violate this delicate and extraordinary innovation we may call what’s essentially a 3D electric transport architecture.

It takes around 2 hours, using terrestrial transportation GIS simulation software Transmodeler™ (the most advanced in the market), to simulate say, downtown San Francisco. See my example of “A blueprint for a Drone skyway” video here: https://youtu.be/u0VdKrsOtSM .

 

Instead of everyone using drones by themselves, an FCC type 3D electric ‘spectrum’ will be auctioned off to companies and the money will be used to monitor and control drone space like the FAA.

 

Skip to toolbar