Local Approximation

Code implementing the Local Approximation as part of the Applied Math honors thesis "Stationarity and Ergodicity of Local Dynamics of Interacting Markov Chains on Large Sparse Graphs." We investigate the numerical and theoretical aspects of certain approximations to local behavior of interacting particle systems on graphs.

There are implementations of the local approximation, k-approximation, mean field approximation, and dynamics for several processes:

• Ising Model
• Contact Process
• Voter Model
• Oscillating Cellular Automata
• Potts

Setup/ Requirements

Code is implemented in Python 3 with heavy use of the following packages:

• Numpy
• Pandas
• Networkx
• Matplotlib

The code is black-box optimized with Numba, a Just-In-Time compiler for Python. Install can be found here. Numba is used to speed up simulation of the local approximation / k approximation as well as the dynamics.

Description

Implementation

Code for simulating dynamics, the local approximation, the k approximation, mean field can be found in the SimulateProcesses folder. The code is split up by the interacting particle system.

As setup for the simulation of dynamics and the local approximation, there is code for creating graphs on which the processes are run in Create_Graphs.py, and code for creating dyadic measures (on which the local/ kapproximations are based) in Dyadic_Measures.py. There are miscellaneous functions for working with the processes in Misc.py.

Within each IPS-specific folder, there is code implementing the mean field and dynamics, the latter of which is sped up by JIT. The local approximations and k approximations are implemented in the files JittedLocalApprox.py or just Local Approx.py. To summarize the data generated by the Local Approx, some methods have been written in the Monitor.py classes.

The Implementation of the Local Approx / k Approx amounts to setting up the initial measure, then precomputing conditional expectations, and evolving the measure according to the probability kernel. The code for implementing the kapprox/local approx is modular: all one needs to do is to put in the model-specific function that computes the probability of a node transitioning to $1$ in the functions probability_of_one. Each Local approx file for the different processes are structured similarly, but this could not be abstracted due to limitations with Numba - hence there is a different file for each model. See the LocalApproxTemplate.py for an idea of how the Local approx is generally implemented (for two states. The Potts model code implements the general multistate case).

Higher level functions running each of these approximations and dynamics are found in the folder ComparisonSimulation under the files ..._Simulation, ..._Reimplementation, under the names run_mean_field_approximation, run_local_approximation, run_k_approximation, run_dynamics. Running these functions outputs several summary statistics for each approximation, saves the data to a folder, and has options to read in data.

Comparison Simulation

There are two simulations done here: comparing performance of each approximation for the processes, , plotting both probabilities over time as well as performance as a function of the degree of the tree / depth. Comparisons for large time between the kapproximation, dynamics, and mean field are found in ContactFastSimulations.py, OscillatingCASimulation.py, while the comparisons for small time between the local approximation are found in the files ...SmallT.py.

There are also simulations comparing, for the Ising model, performance of the mean field approx and local approx / kapprox for different values of degree - kappa - of the tree and beta, for both small time and large times - these are the results showing poorer performance near the critical regime of degree (where there is a phase transition for beta). The comparison between the local approx and mean field for small time is found in IsingFastSimulations.py and IsingMeanFieldComparison.py, while the comparison for large times between the mean field and k approx as compared to dynamics is found in IsingMFvsKApprox.py. Furhter investigation into the critical region can be found in KApproxCriticalRegion.py, IsingKApproxComparison.py.

Ergodicity Simulation

The folder ErgodicitySimulation contains code for analyzing ergodic properties for the k-approximation - analyzing nonuniqueness of stationary distributions or phase transition properties.