Models for information propagation on graphs
We propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave, which emanates from a set of known nodes at an initial time, to all other unknown nodes at later times with an ordering determined by the arrival time of the...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
|
| Series: | European Journal of Applied Mathematics |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S0956792524000895/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832589942741532672 |
|---|---|
| author | Oliver R. A. Dunbar Charles M. Elliott Lisa Maria Kreusser |
| author_facet | Oliver R. A. Dunbar Charles M. Elliott Lisa Maria Kreusser |
| author_sort | Oliver R. A. Dunbar |
| collection | DOAJ |
| description | We propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave, which emanates from a set of known nodes at an initial time, to all other unknown nodes at later times with an ordering determined by the arrival time of the information wave front. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial known set of nodes to a node is defined as the minimum of a generalised travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each unknown node, with boundary conditions at the known nodes. The solution value of the local equation at a node is coupled to those of neighbouring nodes with lower values. We provide precise formulations of the model classes and prove equivalences between them. Finally, we apply the front propagation models on graphs to semi-supervised learning via label propagation and information propagation on trust networks. |
| format | Article |
| id | doaj-art-daf036209efc4d0c8cacef2c72da0dc2 |
| institution | Kabale University |
| issn | 0956-7925 1469-4425 |
| language | English |
| publisher | Cambridge University Press |
| record_format | Article |
| series | European Journal of Applied Mathematics |
| spelling | doaj-art-daf036209efc4d0c8cacef2c72da0dc22025-01-24T05:16:32ZengCambridge University PressEuropean Journal of Applied Mathematics0956-79251469-442512210.1017/S0956792524000895Models for information propagation on graphsOliver R. A. Dunbar0Charles M. Elliott1Lisa Maria Kreusser2https://orcid.org/0000-0002-1131-1125California Institute of Technology, Pasadena, CA, USAMathematics Institute, University of Warwick, Coventry, UKDepartment of Mathematical Sciences, University of Bath, Bath, UKWe propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave, which emanates from a set of known nodes at an initial time, to all other unknown nodes at later times with an ordering determined by the arrival time of the information wave front. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial known set of nodes to a node is defined as the minimum of a generalised travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each unknown node, with boundary conditions at the known nodes. The solution value of the local equation at a node is coupled to those of neighbouring nodes with lower values. We provide precise formulations of the model classes and prove equivalences between them. Finally, we apply the front propagation models on graphs to semi-supervised learning via label propagation and information propagation on trust networks.https://www.cambridge.org/core/product/identifier/S0956792524000895/type/journal_articlewave front sets in context of PDEsHamilton–Jacobi equationsshortest pathsnumerical methods for difference equations35A1835F2152B0568R10 |
| spellingShingle | Oliver R. A. Dunbar Charles M. Elliott Lisa Maria Kreusser Models for information propagation on graphs European Journal of Applied Mathematics wave front sets in context of PDEs Hamilton–Jacobi equations shortest paths numerical methods for difference equations 35A18 35F21 52B05 68R10 |
| title | Models for information propagation on graphs |
| title_full | Models for information propagation on graphs |
| title_fullStr | Models for information propagation on graphs |
| title_full_unstemmed | Models for information propagation on graphs |
| title_short | Models for information propagation on graphs |
| title_sort | models for information propagation on graphs |
| topic | wave front sets in context of PDEs Hamilton–Jacobi equations shortest paths numerical methods for difference equations 35A18 35F21 52B05 68R10 |
| url | https://www.cambridge.org/core/product/identifier/S0956792524000895/type/journal_article |
| work_keys_str_mv | AT oliverradunbar modelsforinformationpropagationongraphs AT charlesmelliott modelsforinformationpropagationongraphs AT lisamariakreusser modelsforinformationpropagationongraphs |