Efficient Simulation of Sparse Graphs of Point Processes
Article No.: 1, Pages 1 - 27
Abstract
We derive new discrete event simulation algorithms for marked time point processes. The main idea is to couple a special structure, namely the associated local independence graph, as defined by Didelez, with the activity tracking algorithm of Muzy for achieving high-performance asynchronous simulations. With respect to classical algorithms, this allows us to drastically reduce the computational complexity, especially when the graph is sparse.
References
[1]
P. K. Andersen, O. Borgan, R. Gill, and N. Keiding. 1996. Statistical Models Based on Counting Processes. Springer.
[2]
Manuel Barrio, Kevin Burrage, André Leier, and Tianhai Tian. 2006. Oscillatory regulation of Hes1: Discrete stochastic delay modelling and simulation. PLoS Computational Biology 2, 9 2006, e117.
[3]
Rudolf Bayer. 1972. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica 1, 4 (1972), 290–306.
[4]
Alexandre Bouchard-Côté, Sebastian J. Vollmer, and Arnaud Doucet. 2018. The bouncy particle sampler: A nonreversible rejection-free Markov chain Monte Carlo method. Journal of the American Statistical Association 113, 522 (2018), 855–867.
[5]
P. Brémaud. 1981. Point Processes and Queues. Springer, New York, NY. https://books.google.fr/books?id=lo-YZwEACAAJ.
[6]
Pierre Brémaud and Laurent Massoulie. 1996. Stability of nonlinear Hawkes processes. Annals of Probability 24, 3 (1996), 1563–1588. http://www.jstor.org/stable/2244985.
[7]
E. N. Brown, R. Barbieri, V. Ventura, R. E. Kass, and L. M. Frank. 2006. The time-rescaling theorem and its application to neural spike train data analysis. Neural Computation 4, 2 (2006), 325–346.
[8]
E. N. Brown, R. Barbieri, V. Ventura, R. E. Kass, and L. M. Frank. 2002. The time-rescaling theorem and its application to neural spike train data analysis. Neural Computation 14, 2 (2002), 325–346.
[9]
J. H. Cha and M. Finkelstein. 2018. Point Processes for Reliability Analysis. Springer.
[10]
J. Chevallier, M. J. Cáceres, M. Doumic, and P. Reynaud-Bouret. 2015. Microscopic approach of a time elapsed neural model. Mathematical Models and Methods in Applied Sciences 25, 14 (2015), 2669–2719.
[11]
Daryl J. Daley and David Vere-Jones. 2003. An Introduction to the Theory of Point Processes. Vol. I. Probability and Its Applications. Springer.
[12]
A. Dassios and H. Zhao. 2013. Exact simulation of Hawkes process with exponentially decaying intensity. Electronic Communications in Probability 18, 62 (2013), 1–13.
[13]
V. Didelez. 2008. Graphical models of Markes point processes based on local independence. Journal of the Royal Statistical Society: Series B 70, 1 (2008), 245–264.
[14]
J. L. Doob. 1945. Markoff chains—Denumerable case. Transactions of the American Mathematical Society 58, 3 (1945), 455–473.
[15]
W. Gerstner and W. M. Kistler. 2002. Spiking Neuron Models: Single Neurons, Populations, Plasticity. Cambridge University Press.
[16]
D. T. Gillespie. 1977. Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81, 25 (1977), 2340–2361.
[17]
P. Grazieschi, M. Leocata, C. Mascart, J. Chevallier, F. Delarue, and E. Tanré. 2019. Network of interacting neurons with random synaptic weights. ESAIM: Proceedings and Surveys 65 (2019), 445–475.
[18]
D. A. Heger. 2004. A disquisition on the performance behavior of binary search tree data structures. European Journal for the Informatics Professional 5, 5 (2004), 67–75. https://web.archive.org/web/20140327140251http://www.cepis.org/upgrade/files/full-2004-V.pdf.
[19]
S. Herculano-Houzel and R. Lent. 2005. Isotropic fractionator: A simple, rapid method for the quantification of total cell and neuron numbers in the brain. Journal of Neuroscience 25, 10 (2005), 2518–2521. arXiv:https://www.jneurosci.org/content/25/10/2518.full.pdf.
[20]
P. A. W. Lewis and G. S. Shedler. 1978. Simulation of Nonhomogeneous Poisson Processes. Technical Report. Naval Postgraduate School, Monterey, CA.
[21]
Iacopo Mastromatteo, Emmanuel Bacry, and Jean-François Muzy. 2015. Linear processes in high dimensions: Phase space and critical properties. Physical Review E 91, 4 (April2015), 042142.
[22]
Makoto Matsumoto and Takuji Nishimura. 1998. Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8, 1 (Jan. 1998), 3–30.
[23]
M. D. Mesarovic and Y. Takahara. 1975. General Systems Theory: Mathematical Foundations. Vol. 113. Academic Press.
[24]
A. Muzy. 2019. Exploiting activity for the modeling and simulation of dynamics and learning processes in hierarchical (neurocognitive) systems. Computing in Science Engineering 21, 1 (Jan.2019), 84–93.
[25]
Alexandre Muzy and Bernard P. Zeigler. 2014. Specification of dynamic structure discrete event systems using single point encapsulated control functions. International Journal of Modeling, Simulation, and Scientific Computing 5, 3 (2014), 1450012.
[26]
J.-F. Muzy, E. Bacry, S. Delattre, and M. Hoffmann.2013. Modelling microstructure noise with mutually exciting point processes. Quantitative Finance 13, 1 (2013), 65–77.
[27]
Y. Ogata. 1981. On Lewis’ simulation method for point processes. IEEE Transaction on Information Theory 27, 1 (1981), 23–31.
[28]
Y. Ogata. 1985. Statistical models for earthquake occurrences and residual analysis for point processes. Journal of the American Statistical Association 83, 401 (1985), 9–27.
[29]
B. Pakkenberg, D. Pelvig, L. Marner, M. J. Bundgaard, H. J. G. Gundersen, J. R. Nyengaard, and L. Regeur. 2003. Aging and the human neocortex. Experimental Gerontology 38, 1 (2003), 95–99.
[30]
E. A. J. F. Peters and G. de With. 2012. Rejection-free MonteCarlo sampling for general potentials. Physical Review E 85, 026703 (2012), 026703.
[31]
P. Reynaud-Bouret, V. Rivoirard, and C. Tuleau-Malot. 2013. Inference of functional connectivity in neurosciences via Hawkes processes. In Proceedingsof the1st IEEE Global Conference on Signal and Information Processing.
[32]
P. Reynaud-Bouret and S. Schbath. 2010. Adaptive estimation for Hawkes processes; application to genome analysis. Annals of Statististics 38, 5 (2010), 2781–2822.
[33]
K. D. Tocher. 1967. PLUS/GPS III Specification. Technical Report. Department of Operational Research, United Steel Companies Ltd., Sheffield.
[34]
D. Vere-Jones and T. Ozaki. 1982. Some examples of statistical estimation applied to earthquake data. Annals of the Institute of Statistical Mathematics 34, B (1982), 189–207.
[35]
C. S. von Bartheld, J. Bahney, and S. Herculano-Houzel. 2016. The search for true numbers of neurons and glial cells in the human brain: A review of 150 years of cell counting. Journal of Comparative Neurology 524, 18 (2016), 3865–3895.
[36]
B. P. Zeigler. 1976. Theory of Modelling and Simulation. John Wiley. 75038977https://books.google.fr/books?id=M-ZQAAAAMAAJ.
[37]
B. P. Zeigler, A. Muzy, and E. Kofman. 2018. Theory of Modeling and Simulation: Discrete Event & Iterative System Computational Foundations. Academic Press.
Index Terms
- Efficient Simulation of Sparse Graphs of Point Processes
Recommendations
Graphs that are simultaneously efficient open domination and efficient closed domination graphs
A graph is an efficient open (resp.źclosed) domination graph if there exists a subset of vertices whose open (resp.źclosed) neighborhoods partition its vertex set. Graphs that are efficient open as well as efficient closed (shortly EOCD graphs) are ...
A New Characterization of $$P_k$$Pk-Free Graphs
Let $$G$$G be a connected $$P_k$$Pk-free graph, $$k \ge 4$$k 4. We show that $$G$$G admits a connected dominating set that induces either a $$P_{k-2}$$Pk-2-free graph or a graph isomorphic to $$P_{k-2}$$Pk-2. In fact, every minimum connected dominating ...
A new characterization of P6-free graphs
We study P"6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P"6-free if and only if each connected induced subgraph of G on more than one vertex ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2023
159 pages
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 28 February 2023
Online AM: 15 November 2022
Accepted: 16 September 2022
Revised: 05 September 2022
Received: 26 February 2021
Published in TOMACS Volume 33, Issue 1-2
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- French government
- Côte d’Azur Investissements d’Avenir
- National Research Agency
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 152Total Downloads
- Downloads (Last 12 months)35
- Downloads (Last 6 weeks)6
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format