Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Distributed Averaging in Opinion Dynamics
Indexado
WoS WOS:001119139100026
Scopus SCOPUS_ID:85164022291
DOI 10.1145/3583668.3594593
Año 2023
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ζu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours v1, v2, ⋯ , vk are selected. Then, u updates its current value ζu(t) to [EQUATION], where α ĝ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, v) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and v as the selected neighbour.For both processes, the values of all nodes converge to the same value F, which is a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of F is the average of the initial values [EQUATION]. For the NodeModel and non-regular graphs, the expectation of F is the degree-weighted average of the initial values.Our results are two-fold. We consider the concentration of F and show tight bounds on the variance of F for regular graphs. We show that when the initial values do not depend on the number of nodes, then the variance is negligible, and hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time Tϵ required to make all node values 'ϵ-close' to each other. Our bounds are asymptotically tight under some assumptions on the distribution of the initial values.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Berenbrink, Petra Mujer Universität Hamburg - Alemania
1 Berenbrink, P. - UNIV HAMBURG - Alemania
2 Cooper, Colin Hombre King's College London - Reino Unido
2 Cooper, C. - Kings Coll London - Reino Unido
3 Gava, Cristina Mujer King's College London - Reino Unido
Kings Coll London - Reino Unido
4 Marzagão, David Kohan Hombre University of Oxford - Reino Unido
4 Mallmann-Trenn, Frederik Hombre King's College London - Reino Unido
Kings Coll London - Reino Unido
5 Radzik, Tomasz Hombre King's College London - Reino Unido
Kings Coll London - Reino Unido
6 Marzagao, D. Kohan - UNIV OXFORD - Reino Unido
7 Rivera, Nicolas Hombre Universidad de Valparaíso - Chile
7 Rivera, N. - Universidad de Valparaíso - Chile
8 ACM Corporación

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
EPSRC
Deutsche Forschungsgemeinschaft (DFG)
ANID
ANID Fondecyt

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
P. Berenbrink was in part supported by the Deutsche Forschungsgemeinschaft (DFG) - Project number 491453517 and number DFGFOR 2975. F. Mallmann-Trenn was in part supported by the EPSRC grant EP/W005573/1. N. Rivera was supported by ANID FONDECYT 3210805 and ANID SIA 85220033.
P. Berenbrink was in part supported by the Deutsche Forschungsgemeinschaft (DFG) - Project number 491453517 and number DFGFOR 2975. F. Mallmann-Trenn was in part supported by the EPSRC grant EP/W005573/1. N. Rivera was supported by ANID FONDECYT 3210805 and ANID SIA 85220033.
P. Berenbrink was in part supported by the Deutsche Forschungsgemeinschaft (DFG) -Project number 491453517 and number DFGFOR 2975. F. Mallmann-Trenn was in part supported by the EPSRC grant EP/W005573/1. N. Rivera was supported by ANID FONDECYT 3210805 and ANID SIA 85220033.

Muestra la fuente de financiamiento declarada en la publicación.