  We study the convergence properties of Social Hegselmann-Krause dynamics, a
{variant} of the Hegselmann-Krause (HK) model of opinion dynamics where a
physical connectivity graph that accounts for the extrinsic factors that could
prevent interaction between certain pairs of agents is incorporated. As opposed
to the original HK dynamics (which terminate in finite time), we show that for
any underlying connected and incomplete graph, under a certain mild assumption,
the expected termination time of social HK dynamics is infinity. We then
investigate the rate of convergence to the steady state, and provide bounds on
the maximum $\epsilon$-convergence time in terms of the properties of the
physical connectivity graph. We extend this discussion and observe that for
almost all $n$, there exists an $n$-vertex physical connectivity graph on which
social HK dynamics may not even $\epsilon$-converge to the steady state within
a bounded time frame. We then provide nearly tight necessary and sufficient
conditions for arbitrarily slow merging (a phenomenon that is essential for
arbitrarily slow $\epsilon$-convergence to the steady state). Using the
necessary conditions, we show that complete $r$-partite graphs have bounded
$\epsilon$-convergence times.

Optimization and Control