Entrograms and coarse graining of dynamics on complex networks
Using an information theoretic point of view, we investigate how a dynamics acting on a network can be coarse grained through the use of graph partitions. Specifically, we are interested in how aggregating the state space of a Markov process according to a partition impacts on the thus obtained lowe...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Oxford University Press
2017
|
| _version_ | 1797091867411611648 |
|---|---|
| author | Faccin, M Schaub, M Delvenne, J |
| author_facet | Faccin, M Schaub, M Delvenne, J |
| author_sort | Faccin, M |
| collection | OXFORD |
| description | Using an information theoretic point of view, we investigate how a dynamics acting on a network can be coarse grained through the use of graph partitions. Specifically, we are interested in how aggregating the state space of a Markov process according to a partition impacts on the thus obtained lower-dimensional dynamics. We highlight that for a dynamics on a particular graph there may be multiple coarse grained descriptions that capture different, incomparable features of the original process. For instance, a coarse graining induced by one partition may be commensurate with a time-scale separation in the dynamics, while another coarse graining may correspond to a different lower-dimensional dynamics that preserves the Markov property of the original process. Taking inspiration from the literature of Computational Mechanics, we find that a convenient tool to summarize and visualize such dynamical properties of a coarse grained model (partition) is the entrogram. The entrogram gathers certain information-theoretic measures, which quantify how information flows across time steps. These information theoretic quantities include the entropy rate, as well as a measure for the memory contained in the process, i.e., how well the dynamics can be approximated by a first order Markov process. We use the entrogram to investigate how specific macro-scale connection patterns in the state–space transition graph of the original dynamics result in desirable properties of coarse grained descriptions. We thereby provide a fresh perspective on the interplay between structure and dynamics in networks, and the process of partitioning a network from an information theoretic perspective. To illustrate our points, we focus on networks that may be approximated by both a core-periphery or a clustered organization, and highlight that each of these coarse grained descriptions can capture different aspects of a Markov process acting on the network. |
| first_indexed | 2024-03-07T03:38:29Z |
| format | Journal article |
| id | oxford-uuid:bd18540f-1749-41dd-babb-eb8642da9ad0 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:38:29Z |
| publishDate | 2017 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:bd18540f-1749-41dd-babb-eb8642da9ad02022-03-27T05:29:10ZEntrograms and coarse graining of dynamics on complex networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:bd18540f-1749-41dd-babb-eb8642da9ad0Symplectic Elements at OxfordOxford University Press2017Faccin, MSchaub, MDelvenne, JUsing an information theoretic point of view, we investigate how a dynamics acting on a network can be coarse grained through the use of graph partitions. Specifically, we are interested in how aggregating the state space of a Markov process according to a partition impacts on the thus obtained lower-dimensional dynamics. We highlight that for a dynamics on a particular graph there may be multiple coarse grained descriptions that capture different, incomparable features of the original process. For instance, a coarse graining induced by one partition may be commensurate with a time-scale separation in the dynamics, while another coarse graining may correspond to a different lower-dimensional dynamics that preserves the Markov property of the original process. Taking inspiration from the literature of Computational Mechanics, we find that a convenient tool to summarize and visualize such dynamical properties of a coarse grained model (partition) is the entrogram. The entrogram gathers certain information-theoretic measures, which quantify how information flows across time steps. These information theoretic quantities include the entropy rate, as well as a measure for the memory contained in the process, i.e., how well the dynamics can be approximated by a first order Markov process. We use the entrogram to investigate how specific macro-scale connection patterns in the state–space transition graph of the original dynamics result in desirable properties of coarse grained descriptions. We thereby provide a fresh perspective on the interplay between structure and dynamics in networks, and the process of partitioning a network from an information theoretic perspective. To illustrate our points, we focus on networks that may be approximated by both a core-periphery or a clustered organization, and highlight that each of these coarse grained descriptions can capture different aspects of a Markov process acting on the network. |
| spellingShingle | Faccin, M Schaub, M Delvenne, J Entrograms and coarse graining of dynamics on complex networks |
| title | Entrograms and coarse graining of dynamics on complex networks |
| title_full | Entrograms and coarse graining of dynamics on complex networks |
| title_fullStr | Entrograms and coarse graining of dynamics on complex networks |
| title_full_unstemmed | Entrograms and coarse graining of dynamics on complex networks |
| title_short | Entrograms and coarse graining of dynamics on complex networks |
| title_sort | entrograms and coarse graining of dynamics on complex networks |
| work_keys_str_mv | AT faccinm entrogramsandcoarsegrainingofdynamicsoncomplexnetworks AT schaubm entrogramsandcoarsegrainingofdynamicsoncomplexnetworks AT delvennej entrogramsandcoarsegrainingofdynamicsoncomplexnetworks |