Source-linked AI summary
A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part II
Anton Proskurnikov, Roberto Tempo
TL;DR
The tutorial addresses the gap between Social Network Analysis and control theory by examining recent dynamic models of social processes developed alongside multi-agent systems theory. It synthesizes models involving time-varying graphs, homophily, negative influence, asynchronous interactions, and quantization, while discussing stability, convergence, and future directions.
Problem
Social Network Analysis has benefited little from recent progress in systems and control, despite the importance of coordinating and controlling social systems.
Method
The tutorial examines recent dynamic models of social processes and analyzes their stability and convergence using tools from control theory, networked systems, and multi-agent systems.
Results
The tutorial develops and reports convergence and consensus results across models including gossip-based consensus, Deffuant-Weisbuch dynamics, signed graphs, and time-varying interaction networks.
Takeaways & Limitations
Dynamic social-network models extend classical consensus analysis to clustering, disagreement, signed influence, changing graphs, and other social-process behaviors.
Takeaways & Limitations
The tutorial covers only a special class of dynamic models and omits quantized communication, controllability, and identifiability.
Abstract
from arXiv · showhide
Recent years have witnessed a significant trend towards filling the gap between Social Network Analysis (SNA) and control theory. This trend was enabled by the introduction of new mathematical models describing dynamics of social groups, the development of algorithms and software for data analysis and the tremendous progress in understanding complex networks and multi-agent systems (MAS) dynamics. The aim of this tutorial is to highlight a novel chapter of control theory, dealing with dynamic models of social networks and processes over them, to the attention of the broad research community. In its first part [1], we have considered the most classical models of social dynamics, which have anticipated and to a great extent inspired the recent extensive studies on MAS and complex networks. This paper is the second part of the tutorial, and it is focused on more recent models of social processes that have been developed concurrently with MAS theory. Future perspectives of control in social and techno-social systems are also discussed.
1. Introduction
This introduction positions the tutorial within efforts to connect Social Network Analysis with control theory by developing and analyzing dynamic models of social processes. It presents the paper as the second tutorial part, focused on newer opinion-formation models and related mathematical tools.
- SNA has broad interdisciplinary applications, including politics, medicine, economics, crime prevention, security, and online social networks.Advances in big-data algorithms and software have enabled analysis of online networks with millions of users.
- SNA and network science have focused primarily on network topology, while giving less attention to dynamics over networks.Exceptions include processes such as random walks, branching, queueing, percolation, and contagion dynamics.
- The gap between SNA and control theory reflects a lack of dynamic social-process models and mathematical tools for analyzing them.The paper describes social sciences as having benefited little from recent progress in systems and control.
- Recent progress in multi-agent systems and dynamic networks has enabled efforts to fill the gap between SNA and control theory.The emerging control-theoretic study of social processes is described as a young field without an established name.
- This second tutorial part examines recent models incorporating time-varying graphs, homophily, negative influence, asynchronous interactions, and quantization.The theory of these models and multi-agent control developed concurrently and influenced one another.
- The paper uses more diverse mathematical tools than its first part, but page limits prevent detailed proofs for all discussed results.Some results are presented without proofs or with only brief proof sketches.
2. Preliminaries and notation
The preliminaries introduce opinion-dynamics concepts, agent-based modeling, graph and matrix notation, and classical averaging models. They also frame consensus and opinion clustering as central modeling outcomes and problems.
- Preliminaries and notation: Opinions are scalar or vector quantities associated with social actors and may represent attitudes, belief certainties, or probabilities.The tutorial focuses on models in which opinions can attain a continuous range of values.
- Modeling approaches: Compartmental models represent social behavior through interacting subgroups, tracking population distributions rather than specific actors’ behavior.This approach originated in mathematical biology and is also used in sociodynamics and statistical opinion-formation models.
- Agent-based modeling of opinion evolution: Agent-based models describe how each individual’s opinion evolves under the influence of other individuals, producing collective behavior from individual interactions.These bottom-up models are also called aggregative models.
- Consensus models: The French-DeGroot model uses discrete-time averaging, x(k + 1) = Wx(k), where W is a stochastic matrix.The model evolves the stacked vector of agents’ opinions.
- Consensus models: The continuous-time Abelson model uses Laplacian-flow dynamics based on a non-negative matrix of contact rates.The matrix defines a weighted interaction graph through its Laplacian matrix.
- Consensus and disagreement: Consensus in the classical models requires the corresponding interaction graph to have a directed spanning tree, whereas disconnected graphs can produce community cleavage.Stubborn individuals provide another mechanism preventing consensus because their opinions remain unchanged.
- Consensus and disagreement: The tutorial considers models that can produce either consensus or multiple opinion clusters, extending classical models beyond consensus-only behavior.This addresses Abelson’s problem of explaining disagreement effects in social groups.
3. The models by French-DeGroot and Abelson with time-varying interaction graphs
The section examines time-varying French-DeGroot and Abelson opinion dynamics, relating convergence to persistent interaction structure and connectivity assumptions. It also highlights unresolved convergence issues when reciprocity conditions are absent.
- Time-varying French-DeGroot model: Time-varying French-DeGroot dynamics replace the fixed stochastic matrix with a sequence W(k), yielding x(k + 1) = W(k)x(k).
- Time-varying French-DeGroot model: Under self-confidence and type-symmetry assumptions, opinions converge to an equilibrium, and persistently interacting agents share the same limiting opinion.
- Time-varying French-DeGroot model: Consensus occurs within each connected component of the graph of persistent interactions, while disconnected components may converge to different limits.
- Time-varying French-DeGroot model: The convergence result is equivalent to the equivalence of asymptotic synchronization and convergence of every agent to a common limit.
- Time-varying French-DeGroot model: Exponential consensus follows when the interaction graphs satisfy the stated quasi-strong connectivity conditions.
- Time-varying Abelson model: For the time-varying Abelson model, reciprocal interactions ensure convergence and agreement among persistently interacting agents, whereas convergence without reciprocity remains non-trivial.
- Time-varying Abelson model: With bounded interaction rates and uniformly quasi-strongly connected graphs, Abelson-model opinions exponentially converge to consensus.
- Time-varying Abelson model: The tutorial notes that complete proofs of some continuous-time results are not readily available and that additional assumptions appear in existing proofs.
4. Opinion dynamics with bounded confidence
Bounded-confidence models represent homophily by making agents insensitive to opinions outside their confidence sets. The section introduces the Hegselmann-Krause model and related Deffuant-Weisbuch gossiping dynamics as prominent opinion-formation models.
- Motivation: Homophily means that similar individuals interact more often and intensively than dissimilar people, contributing to social segregation and cleavage.
- Motivation: Opinion models incorporate homophily by strengthening influence between agents whose opinions are closer.
- Bounded-confidence models: Bounded-confidence models make individuals totally insensitive to opinions outside their confidence sets.
- Bounded-confidence models: Krause and Deffuant-Weisbuch independently proposed simple bounded-confidence models; the latter is based on gossiping interactions.
- Bounded-confidence models: The section primarily studies Krause’s model, now known as Hegselmann-Krause, alongside recent extensions.
4.1. The original HK model
The original HK model is a bounded-confidence, state-dependent extension of French-DeGroot averaging in which opinions determine the interaction graph. Its one-dimensional dynamics preserve order, separate into non-merging chains, and converge in finite time, with an O(n^3) termination bound.
- Model definition: Each agent updates to the average opinion of neighbors within distance d, making the influence graph depend on mutual opinion distances.The model is a nonlinear autonomous system and can also be represented as a time-varying French-DeGroot model with state-dependent weights.
- Convergence: The model always reaches a fixed point in finitely many steps, after which every pair either shares an opinion or differs by more than d.The final opinions and termination time depend on the initial opinions and confidence range.
- Basic properties: The HK operator preserves the ordering of agents’ opinions at every iteration.This order-preservation property supports the finite-time convergence analysis.
- Chain dynamics: Different maximal d-chains cannot merge, and connected components of the interaction graph can split but cannot merge.The leftmost opinion in a chain is non-decreasing, the rightmost is non-increasing, and the chain diameter is therefore non-increasing.
- Consensus and clustering: Chains whose diameter is at most d collapse into consensus, whereas chains with at least 5 opinions may split and prevent global consensus despite an initially connected graph.For n < 5, the model always reaches consensus; for n ≥ 5, disagreement can persist through cluster splitting.
- Convergence: 2n^3 −2(n −1)^2 steps is an upper bound on termination time, yielding the asymptotic estimate O(n^3).The bound follows by accounting for chain collapses, splits, and diameter reductions.
4.2. The multidimensional HK model
The multidimensional HK model replaces scalar confidence intervals with norm-dependent balls and retains finite-time termination for any norm. However, higher-dimensional interaction graphs may merge as well as split, and available convergence-time bounds become less sharp.
- Model definition: For opinions in R^m, agents trust those within distance d under a chosen norm, coupling their influence across all opinion dimensions.Strong disagreement on one issue can cause agents to ignore each other’s positions on every other issue.
- Graph evolution: Connected components of the multidimensional interaction graph can merge as well as split.A tetrahedral example in R^3 starts with three components, becomes connected after one step, and reaches consensus in 3 steps.
- Finite-time convergence: For any norm, the multidimensional HK model terminates in a finite number of steps.The proof writes the dynamics as a state-dependent time-varying French-DeGroot system and then establishes finite-time stabilization.
- Convergence-time bounds: In Euclidean dimensions m ≥2, the best cited upper estimate is 2n^4 steps, while the lower bound is Ω(n^2).The lower-bound construction places agents at the vertices of a regular planar n-gon with side d.
- Generalizations: Distance-based extensions with non-increasing interaction functions can converge under conditions including compact support and |ϕ′(r)|^2 ≤ Cϕ(r).Heterophilous interactions, which attract moderately distant opinions more strongly than similar ones, can facilitate consensus.
- Generalizations: Under ϕ(σ) ∈ {0} ∪ [a,b] with ϕ(0) > 0, opinions converge but do not stabilize after finitely many steps.The result extends to heterogeneous pairwise distance functions under analogous positivity and reciprocity conditions.
4.3. Lyapunov methods for the HK model
Lyapunov methods analyze HK dynamics through energy functions tailored to clustering rather than only global consensus. These functions establish monotonicity and provide dimension-independent O(n^4) termination bounds for the standard multidimensional model.
- Lyapunov-function choice: The convex-hull diameter is inadequate when opinions split into multiple clusters, motivating a piecewise-smooth HK-specific Lyapunov function.Unlike the standard consensus setting, the HK convex hull may not collapse to a singleton.
- Energy decrease: The HK energy function is non-increasing along trajectories and strictly decreases until opinion evolution terminates.This energy is a special case of broader Lyapunov functions for nonlinear consensus algorithms.
- Termination bound: During each step, either two opinions merge or the energy decreases by at least d/(2n^2), implying termination in O(n^4) steps independently of opinion dimension.The estimate uses algebraic graph-theoretic techniques.
- Generalized models: For non-increasing interaction functions ϕ, the generalized energy function remains non-increasing.This extends the Lyapunov approach beyond the usual HK indicator interaction rule.
- Proof conditions: The Lyapunov proof strategy relies on concavity and derivative conditions for some interaction functions, while other methods can discard the concavity assumption in the scalar case.The cited convergence results require compact support and |ϕ′(r)|^2 ≤ Cϕ(r) for the concave-function approach.
4.4. Extensions and related models
The tutorial surveys continuous-time, stubborn-agent, truth-seeking, inertial, heterogeneous, and asymmetric extensions of bounded-confidence dynamics. These variants preserve some HK properties but introduce discontinuities, unresolved convergence questions, asymmetric effects, and sensitivity to disturbances.
- Continuous-time models: Continuous-time bounded-confidence models have discontinuous right-hand sides, creating solution-existence issues and allowing generalized solutions with nonunique or pathological behavior.Classical Carathéodory solutions exist for almost all initial conditions, while Krasovskii solutions exist for all initial conditions but need not be unique.
- Truth-seeking models: Truth seekers with λ_i < 1 converge to the truth, while agents with λ_i = 0 either converge to it or stabilize finitely at values at least d away.Convergence to the truth is usually asymptotic rather than finite-time, and the consensus question with non-truth-seeking agents remains open.
- Stubborn agents: Stubborn-agent HK systems with λ_i ∈ {0,1} asymptotically converge, and this result includes the multidimensional Euclidean HK model as a special case.The stubborn agents need not share identical opinions.
- Asymmetric interactions: If asymmetric confidence offsets satisfy η_i ≥ 0 and max_i η_i < d, the asymmetric HK model terminates in finite time.Its termination time is estimated as O(n^3) + O(n^2) ln(1 − ζ), where ζ = η/d < 1.
- Heterogeneous interactions: For heterogeneous confidence bounds, general convergence remains unresolved despite simulations suggesting it is generic.The homogeneous case with stubborn agents is settled, but the general heterogeneous model’s behavior is described as remaining a mystery.
- Robustness: Small additive noises destroy HK clusters and produce quasi-consensus, while floating-point inaccuracies can make the dynamics highly sensitive.These observations motivate attention to robustness against disturbances.
5. Randomized Gossip-based Models
Randomized gossip models replace unrealistic synchronous updates with pairwise asynchronous interactions, often selected randomly to mimic spontaneous social encounters. The tutorial develops consensus criteria and shows that stochastic gossip dynamics can correspond to deterministic models while also producing persistent fluctuations in settings with stubborn agents or nonlinear confidence effects.
- Asynchronous gossiping: At each asynchronous step, two agents interact and one or both opinions may change, contrasting with simultaneous synchronous updates.Randomized pair selection is used to mimic the spontaneity of real social interactions.
- Randomized French-DeGroot models: Randomized French-DeGroot dynamics with i.i.d. stochastic matrices reduce consensus analysis to the deterministic model formed by the expected matrix.Consensus, almost-sure synchronization, convergence in probability, and p-th-moment synchronization are equivalent under the stated result.
- Consensus criteria: A directed spanning tree in the interaction graph is sufficient for the randomized protocol to achieve consensus with probability 1.For the related symmetric condition, consensus occurs exactly when the undirected graph associated with P + P^⊤ is connected.
- Gossiping with stubborn agents: With stubborn agents, gossip opinions may fail to converge almost surely and instead fluctuate ergodically, although their distribution can converge to a probability measure.For the asynchronous gossip-based FJ model, the process can be almost-sure and Lp-ergodic and converge in distribution to a random vector with mean equal to the deterministic final opinion.
- Asynchronous gossip-based FJ model: The asynchronous gossip-based FJ model preserves the deterministic model’s final-opinion correspondence while replacing fixed convergence with fluctuating trajectories and convergent Cesàro averages.For a four-agent example, the deterministic final opinion is approximately (60, 60, 75, 75)ᵀ, while the randomized opinions fluctuate except for stubborn agent 3.
- Opinion-dependent interactions: Nonlinear gossip models with opinion-dependent interactions can converge almost surely, while extremists with narrow confidence intervals can produce ergodic opinion fluctuations.The convergence result also imposes a separation-or-equality condition on limiting opinions: each pair is either at least d apart or equal.
6. Disagreement via Negative Influence
Negative influence extends opinion-dynamics models beyond cooperative averaging, using signed-graph structural balance to characterize polarization, zero consensus, and clustered outcomes. The tutorial also identifies important boundaries for static and time-varying signed networks.
- 6. Disagreement via Negative Influence: Negative ties motivate signed-graph models in which positive arcs represent friendship or trust and negative arcs represent enmity or suspicion.The models extend cooperative-control ideas to antagonistic interactions and can produce non-trivial opinion behavior.
- 6.1. Balance theory: A structurally balanced complete sign-symmetric graph has balanced triads satisfying aijajkaki > 0, corresponding to friendship or two allied friends opposing an enemy.Balance theory associates imbalanced triads with social tensions that actors tend to resolve.
- 6.1. Balance theory: Structural balance requires positive cycles, while strong connectivity makes this condition sufficient; without strong connectivity, even a three-node acyclic graph can be imbalanced.For sign-symmetric graphs, positivity of all semicycles is also presented as sufficient for structural balance.
- 6.1. Balance theory: For strongly connected signed graphs, λ = 0 is an eigenvalue of the signed Laplacian exactly when the graph is structurally balanced.This connects a graph-theoretic balance property to the stability analysis of the Altafini model.
- 6.2.1. The case of a time-invariant signed graph: With a directed spanning tree and structural balance, the Altafini model yields bipartite consensus, whereas strong structural imbalance yields exponential convergence of opinions to zero.In the balanced case, hostile camps converge to opposite values; in the imbalanced strongly connected case, the signed Laplacian dynamics are exponentially stable.
- 6.2.2. The dynamic graph case: In general signed graphs, opinions converge and may split into several clusters whose number and structure depend on the graph, while time-varying signed-graph convergence remains incompletely studied.For dynamic graphs, structural balance with a time-invariant faction decomposition reduces the model to the Abelson model through a gauge transformation.
7. Conclusions and Future Works
The tutorial acknowledges that social-process models remain only partially covered and that existing models capture limited facets of social life. It calls for broader data-informed work to assess realism and guide model choice.
- Scope boundaries: The tutorial covers only a special class of dynamic models, leaving quantized communication, controllability, identifiability, reflected appraisals, and open multi-agent models outside its scope.Open models allow agents to join and leave, offering a perspective for modeling interactions in online social media.
- Purpose: The tutorial aims to introduce the field at the boundary of systems theory and social science to researchers beginning work in social dynamics modeling.The authors note that comprehensively surveying cutting-edge models in a journal paper is difficult and anticipate future textbooks and monographs.
- Open questions: Existing opinion-formation models describe only some facets of social life and often focus on one effect or property of social interaction.The text lists stubbornness, homophily, and xenophobia as examples of specialized effects.
- Open questions: The tutorial raises whether simplified models, holistic models, or different models for different situations are closest to social reality.These questions concern how model complexity and context should relate to real social influence.
- Future work: Realistic models require empirical data, potentially gathered through social experiments or obtained from online social media.The paper notes successful examples of interdisciplinary collaborations in experimental validation, while characterizing broader collaboration as insufficient.