On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics

Rohit Parasnis; Massimo Franceschetti; Behrouz Touri

doi:10.1109/CDC40024.2019.9030053

On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics

Rohit Parasnis
, Massimo Franceschetti
, Behrouz Touri

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We address the problem of identifying physical connectivity graphs that guarantee a finite upper bound on the time required for the associated social Hegselmann-Krause dynamics to ϵ-converge to the steady state. We handle the cases of consensus as well as non-consensus steady states, and for each case, we provide sufficient conditions for a physical connectivity graph to have unbounded ϵ-convergence time. We then show that every complete r-partite graph on n vertices has a finite maximum ϵ-convergence time, regardless of the values of r and n. Finally, we show that enhancing the connectivity of agents may not always speed up convergence to the steady state, even when the steady state is a consensus.

Original language	English (US)
Title of host publication	2019 IEEE 58th Conference on Decision and Control, CDC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	6431-6436
Number of pages	6
ISBN (Electronic)	9781728113982
DOIs	https://doi.org/10.1109/CDC40024.2019.9030053
State	Published - Dec 2019
Externally published	Yes
Event	58th IEEE Conference on Decision and Control, CDC 2019 - Nice, France Duration: Dec 11 2019 → Dec 13 2019

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2019-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	58th IEEE Conference on Decision and Control, CDC 2019
Country/Territory	France
City	Nice
Period	12/11/19 → 12/13/19

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Online availability

10.1109/CDC40024.2019.9030053

Library availability

Discover UIUC Full Text

Cite this

Parasnis, R., Franceschetti, M., & Touri, B. (2019). On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics. In 2019 IEEE 58th Conference on Decision and Control, CDC 2019 (pp. 6431-6436). Article 9030053 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC40024.2019.9030053

On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics. / Parasnis, Rohit; Franceschetti, Massimo; Touri, Behrouz.
2019 IEEE 58th Conference on Decision and Control, CDC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 6431-6436 9030053 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Parasnis, R, Franceschetti, M & Touri, B 2019, On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics. in 2019 IEEE 58th Conference on Decision and Control, CDC 2019., 9030053, Proceedings of the IEEE Conference on Decision and Control, vol. 2019-December, Institute of Electrical and Electronics Engineers Inc., pp. 6431-6436, 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, 12/11/19. https://doi.org/10.1109/CDC40024.2019.9030053

Parasnis R, Franceschetti M, Touri B. On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics. In 2019 IEEE 58th Conference on Decision and Control, CDC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 6431-6436. 9030053. (Proceedings of the IEEE Conference on Decision and Control). doi: 10.1109/CDC40024.2019.9030053

@inproceedings{55d31329d0df4c409be794b2f06218e4,

title = "On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics",

abstract = "We address the problem of identifying physical connectivity graphs that guarantee a finite upper bound on the time required for the associated social Hegselmann-Krause dynamics to ϵ-converge to the steady state. We handle the cases of consensus as well as non-consensus steady states, and for each case, we provide sufficient conditions for a physical connectivity graph to have unbounded ϵ-convergence time. We then show that every complete r-partite graph on n vertices has a finite maximum ϵ-convergence time, regardless of the values of r and n. Finally, we show that enhancing the connectivity of agents may not always speed up convergence to the steady state, even when the steady state is a consensus.",

author = "Rohit Parasnis and Massimo Franceschetti and Behrouz Touri",

note = "This research is supported by National Science Foundation (NSF) grant ECCS-1913131.; 58th IEEE Conference on Decision and Control, CDC 2019 ; Conference date: 11-12-2019 Through 13-12-2019",

year = "2019",

month = dec,

doi = "10.1109/CDC40024.2019.9030053",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "6431--6436",

booktitle = "2019 IEEE 58th Conference on Decision and Control, CDC 2019",

address = "United States",

}

TY - GEN

T1 - On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics

AU - Parasnis, Rohit

AU - Franceschetti, Massimo

AU - Touri, Behrouz

N1 - This research is supported by National Science Foundation (NSF) grant ECCS-1913131.

PY - 2019/12

Y1 - 2019/12

N2 - We address the problem of identifying physical connectivity graphs that guarantee a finite upper bound on the time required for the associated social Hegselmann-Krause dynamics to ϵ-converge to the steady state. We handle the cases of consensus as well as non-consensus steady states, and for each case, we provide sufficient conditions for a physical connectivity graph to have unbounded ϵ-convergence time. We then show that every complete r-partite graph on n vertices has a finite maximum ϵ-convergence time, regardless of the values of r and n. Finally, we show that enhancing the connectivity of agents may not always speed up convergence to the steady state, even when the steady state is a consensus.

AB - We address the problem of identifying physical connectivity graphs that guarantee a finite upper bound on the time required for the associated social Hegselmann-Krause dynamics to ϵ-converge to the steady state. We handle the cases of consensus as well as non-consensus steady states, and for each case, we provide sufficient conditions for a physical connectivity graph to have unbounded ϵ-convergence time. We then show that every complete r-partite graph on n vertices has a finite maximum ϵ-convergence time, regardless of the values of r and n. Finally, we show that enhancing the connectivity of agents may not always speed up convergence to the steady state, even when the steady state is a consensus.

UR - https://www.scopus.com/pages/publications/85082500233

UR - https://www.scopus.com/pages/publications/85082500233#tab=citedBy

U2 - 10.1109/CDC40024.2019.9030053

DO - 10.1109/CDC40024.2019.9030053

M3 - Conference contribution

AN - SCOPUS:85082500233

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 6431

EP - 6436

BT - 2019 IEEE 58th Conference on Decision and Control, CDC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 58th IEEE Conference on Decision and Control, CDC 2019

Y2 - 11 December 2019 through 13 December 2019

ER -

On Graphs with Bounded and Unbounded Convergence Times in Social Hegselmann-Krause Dynamics

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this