Abstract
We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ condition inherent in DPO rewriting. Our main result is that the linear span of marked graph occurrence-counting functions – or motif functions – form an algebra which is closed under the infinitesimal generator of (the Markov chain associated with) any such rewriting system. This gives a general procedure to derive the moment semantics of any such rewriting system, as a countable (and recursively enumerable) system of differential equations indexed by motif functions. The differential system describes the time evolution of moments (of any order) of these motif functions under the rewriting system. We illustrate the semantics using the example of preferential attachment networks; a well-studied complex system, which meshes well with our notion of marked graph rewriting. We show how in this case our procedure obtains a finite description of all moments of degree counts for a fixed degree.
This work was sponsored by the European Research Council (ERC) under the grants DOPPLER (587327) and RULE (320823).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
The Preferential Attachment ODE Generator (2015). https://github.com/sstucki/pa-ode-gen/
Bapodra, M., Heckel, R.: From graph transformations to differential equations. ECEASST 30 (2010)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Barabási, A.L., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Physica A: Statistical Mechanics and its Applications 272(1), 173–187 (1999)
Chaput, P., Danos, V., Panangaden, P., Plotkin, G.D.: Approximating Markov processes by averaging. Journal of the ACM 61(1), 5 (2014)
Corradini, A., Heindel, T., Hermann, F., König, B.: Sesqui-pushout rewriting. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT 2006. LNCS, vol. 4178, pp. 30–45. Springer, Heidelberg (2006)
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation. Part I: basic concepts and double pushout approach. In: Handbook of Graph Grammars and Computing by Graph Transformation, pp. 163–245 (1997)
Danos, V., Heindel, T., Honorato-Zimmer, R., Stucki, S.: Approximations for stochastic graph rewriting. In: Merz, S., Pang, J. (eds.) ICFEM 2014. LNCS, vol. 8829, pp. 1–10. Springer, Heidelberg (2014)
Danos, V., Honorato-Zimmer, R., Jaramillo-Riveri, S., Stucki, S.: Deriving rate equations for site graph rewriting systems. In: SASB (2013)
Danos, V., Honorato-Zimmer, R., Jaramillo-Riveri, S., Stucki, S.: Coarse-graining the dynamics of ideal branched polymers. In: Electronic Notes in Theoretical Computer Science, Workshop on Static Analysis and Systems Biology, SASB 2012, Deauville, pp. 47–64, April 2015
Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of networks with aging of sites. Phys. Rev. E 62, 1842–1845 (2000)
Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Phys. Rev. Lett. 85, 4633–4636 (2000)
Durrett, R., Gleeson, J.P., Lloyd, A.L., Mucha, P.J., Shi, F., Sivakoff, D., Socolar, J.E., Varghese, C.: Graph fission in an evolving voter model. Proceedings of the National Academy of Sciences 109(10), 3682–3687 (2012)
Ehrig, H., Ehrig, K., Habel, A., Pennemann, K.H.: Theory of constraints and application conditions: From graphs to high-level structures. Fundamenta Informaticae 74(1), 135–166 (2006)
Ehrig, H., Heckel, R., Korff, M., Löwe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic approaches to graph transformation. Part II: Single pushout approach and comparison with double pushout approach. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, pp. 247–312. World Scientific, River Edge (1997)
Ehrig, H., Pfender, M., Schneider, H.J.: Graph-grammars: an algebraic approach. In: 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 167–180 (1973)
Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley (1986)
Evans, M.R., Ferrari, P.A., Mallick, K.: Matrix representation of the stationary measure for the multispecies TASEP. Journal of Statistical Physics 135(2), 217–239 (2009)
Fages, F., Soliman, S.: Formal cell biology in Biocham. In: Bernardo, M., Degano, P., Zavattaro, G. (eds.) SFM 2008. LNCS, vol. 5016, pp. 54–80. Springer, Heidelberg (2008)
Feret, J., Danos, V., Harmer, R., Krivine, J., Fontana, W.: Internal coarse-graining of molecular systems. PNAS 106(16), 6453–6458 (2009)
Gleeson, J.P.: High-accuracy approximation of binary-state dynamics on networks. Physical Review Letters 107(6), 068701 (2011)
Harmer, R., Danos, V., Feret, J., Krivine, J., Fontana, W.: Intrinsic information carriers in combinatorial dynamical systems. Chaos 20(3) (2010)
Hayman, J., Heindel, T.: Pattern graphs and rule-based models: the semantics of Kappa. In: Pfenning, F. (ed.) FOSSACS 2013 (ETAPS 2013). LNCS, vol. 7794, pp. 1–16. Springer, Heidelberg (2013)
Heckel, R.: DPO transformation with open maps. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2012. LNCS, vol. 7562, pp. 203–217. Springer, Heidelberg (2012)
Heckel, R., Lajios, G., Menge, S.: Stochastic graph transformation systems. Fundam. Inform. 74(1), 63–84 (2006)
Heckel, R., Wagner, A.: Ensuring consistency of conditional graph grammars - a constructive approach. Electronic Notes in Theoretical Computer Science 2(0), 118–126 (1995)
van Kampen, N.: Stochastic processes in physics and chemistry, 3rd edition, North-Holland (2007)
Lack, S., Sobociński, P.: Adhesive categories. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 273–288. Springer, Heidelberg (2004)
Lack, S., Sobocinski, P.: Adhesive and quasiadhesive categories. Theoretical Informatics and Applications 39(2), 522–546 (2005)
Lopez, C.F., Muhlich, J.L., Bachman, J.A., Sorger, P.K.: Programming biological models in Python using PySB. Molecular Systems Biology 9(1) (2013)
Löwe, M.: Algebraic Approach to Single-Pushout Graph Transformation. Theoretical Computer Science 109(1&2), 181–224 (1993)
Lynch, J.F.: A logical characterization of individual-based models. In: 23rd Annual IEEE Symposium on Logic in Computer Science, LICS 2008, pp. 379–390. IEEE (2008)
Norris, J.R.: Markov chains. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press (1998)
Shkarin, S.A.: Some results on solvability of ordinary linear differential equations in locally convex spaces. Mathematics of the USSR-Sbornik 71(1), 29 (1992)
Stukalin, E.B., Phillips III, H., Kolomeisky, A.B.: Coupling of two motor proteins: a new motor can move faster. Physical Review Letters 94(23), 238101 (2005)
Thomas, P., Matuschek, H., Grima, R.: Intrinsic noise analyzer: a software package for the exploration of stochastic biochemical kinetics using the system size expansion. PloS ONE 7(6), e38518 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Danos, V., Heindel, T., Honorato-Zimmer, R., Stucki, S. (2015). Moment Semantics for Reversible Rule-Based Systems. In: Krivine, J., Stefani, JB. (eds) Reversible Computation. RC 2015. Lecture Notes in Computer Science(), vol 9138. Springer, Cham. https://doi.org/10.1007/978-3-319-20860-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-20860-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-20859-6
Online ISBN: 978-3-319-20860-2
eBook Packages: Computer ScienceComputer Science (R0)