Abstract: Networks capture relationships between interactive agents in a population. Dynamical processes, such as epidemics, over networks is frequently used as a model to understand how information/virus/rumors/ opinions/failures spread amongst agents in a heterogenous population.

The inclusion of heterogenous network structure introduces combinatorial complexity to the problem for which few exact solutions exist. We developed the scaled SIS (susceptible-infected-susceptible) process, a binary-state, epidemics process over arbitrary, finite-size network, which accounts for both spontaneous and neighbor-to-neighbor infection as well as healing.

The scaled SIS process has an exact, closed-form equilibrium distribution of the Gibbs form and depends on the underlying network structure through the adjacency matrix.

Further, the most-probable configuration (i.e., ground state) of the equilibrium distribution can be found in polynomial-time for a range of infection/healing rates using submodular optimization.

Through the most-probable configuration, we can relate the severity of the epidemics to the existence of ‘denser-than’ subgraphs in the network and identify exactly the set of agents that would be more susceptible to infection.