Consensus formation on adaptive networks

Analogies for modeling belief dynamics

Belief dynamics has an important role in shaping our responses to natural and societal phenomena, ranging from climate change and pandemics to immigration and conflicts. Researchers often base their models of belief dynamics on analogies to other systems and processes, such as epidemics or ferromagnetism. Similar to other analogies, analogies for belief dynamics can help scientists notice and study properties of belief systems that they would not have noticed otherwise (conceptual mileage). However, forgetting the origins of an analogy may lead to some less appropriate inferences about belief dynamics (conceptual baggage). Here, we review various analogies for modeling belief dynamics, discuss their mileage and baggage, and offer recommendations for using analogies in model development.

Co-evolving networks for opinion and social dynamics in agent-based models

The rise of digital social media has strengthened the coevolution of public opinions and social interactions that shape social structures and collective outcomes in increasingly complex ways. The existing literature often explores this interplay as a one-directional influence, focusing on how opinions determine social ties within adaptive networks. However, this perspective overlooks the intrinsic dynamics driving social interactions, which can significantly influence how opinions form and evolve. In this work, we address this gap, by introducing the co-evolving opinion and social dynamics using stochastic agent-based models. Agents' mobility in a social space is governed by both their social and opinion similarity with others. Similarly, the dynamics of opinion formation is driven by the opinions of agents in their social vicinity. We analyze the underlying social and opinion interaction networks and explore the mechanisms influencing the appearance of emerging phenomena, such as echo chambers and opinion consensus. To illustrate the model's potential for real-world analysis, we apply it to General Social Survey data on political identity and public opinion regarding governmental issues. Our findings highlight the model's strength in capturing the coevolution of social connections and individual opinions over time.

Perspectives on adaptive dynamical systems

Adaptivity is a dynamical feature that is omnipresent in nature, socio-economics, and technology. For example, adaptive couplings appear in various real-world systems, such as the power grid, social, and neural networks, and they form the backbone of closed-loop control strategies and machine learning algorithms. In this article, we provide an interdisciplinary perspective on adaptive systems. We reflect on the notion and terminology of adaptivity in different disciplines and discuss which role adaptivity plays for various fields. We highlight common open challenges and give perspectives on future research directions, looking to inspire interdisciplinary approaches.

Coevolutionary Dynamics with Global Fields

We investigate the effects of external and autonomous global interaction fields on an adaptive network of social agents with an opinion formation dynamics based on a simple imitation rule. We study the competition between global fields and adaptive rewiring on the space of parameters of the system. The model represents an adaptive society subject to global mass media such as a directed opinion influence or feedback of endogenous cultural trends. We show that, in both situations, global mass media contribute to consensus and to prevent the fragmentation of the social network induced by the coevolutionary dynamics. We present a discussion of these results in the context of dynamical systems and opinion formation dynamics.

Seeking Tracking Consensus for General Linear Multiagent Systems With Fixed and Switching Signed Networks

The existing studies for tracking consensus of multiagent systems (MASs) are all restricted to networks with only cooperative relationships among agents. Tracking consensus, however, requires beyond these traditional models due to the ubiquitous competition in many real-world MASs, such as biological systems and social systems. Taking into account this fact, this article aims to extend the dynamics of tracking consensus to signed networks containing both cooperative and competitive relationships among agents. A group of agents with general linear dynamics is considered. The cases of the fixed network as well as switching networks are analyzed, respectively. In the end, some algebraic conditions related to the network structure and the positive/negative edge weight are established to ensure the implementation of tracking consensus. Moreover, the single decoupling system is allowed to be strictly unstable in theory, and the upper bound of the eigenvalue modulus of the system matrix related to the system instability is given.

Quantifying the impact of network structure on speed and accuracy in collective decision-making

Found in varied contexts from neurons to ants to fish, binary decision-making is one of the simplest forms of collective computation. In this process, information collected by individuals about an uncertain environment is accumulated to guide behavior at the aggregate scale. We study binary decision-making dynamics in networks responding to inputs with small signal-to-noise ratios, looking for quantitative measures of collectivity that control performance in this task. We find that decision accuracy is directly correlated with the speed of collective dynamics, which is in turn controlled by three factors: the leading eigenvalue of the network adjacency matrix, the corresponding eigenvector's participation ratio, and distance from the corresponding symmetry-breaking bifurcation. A novel approximation of the maximal attainable timescale near such a bifurcation allows us to predict how decision-making performance scales in large networks based solely on their spectral properties. Specifically, we explore the effects of localization caused by the hierarchical assortative structure of a "rich club" topology. This gives insight into the trade-offs involved in the higher-order structure found in living networks performing collective computations.

Spontaneous symmetry breaking of active phase in coevolving nonlinear voter model

We study an adaptive network model driven by a nonlinear voter dynamics. Each node in the network represents a voter and can be in one of two states that correspond to different opinions shared by the voters. A voter disagreeing with its neighbor's opinion may either adopt it or rewire its link to another randomly chosen voter with any opinion. The system is studied by means of the pair approximation in which a distinction between the average degrees of nodes in different states is made. This approach allows us to identify two dynamically active phases: a symmetric and an asymmetric one. The asymmetric active phase, in contrast to the symmetric one, is characterized by different numbers of nodes in the opposite states that coexist in the network. The pair approximation predicts the possibility of spontaneous symmetry breaking, which leads to a continuous phase transition between the symmetric and the asymmetric active phases. In this case, the absorbing transition occurs between the asymmetric active and the absorbing phases after the spontaneous symmetry breaking. Discontinuous phase transitions and hysteresis loops between both active phases are also possible. Interestingly, the asymmetric active phase is not displayed by the model where the rewiring occurs only to voters sharing the same opinion, studied by other authors. Our results are backed up by Monte Carlo simulations.

Bias in social interactions and emergence of extremism in complex social networks

Emergence of extremism in social networks is among the most appealing topics of opinion dynamics in computational sociophysics in recent decades. Most of the existing studies presume that the initial existence of certain groups of opinion extremities and the intrinsic stubbornness in individuals' characteristics are the key factors allowing the tenacity or even prevalence of such extreme opinions. We propose a modification to the consensus making in bounded-confidence models where two interacting individuals holding not so different opinions tend to reach a consensus by adopting an intermediate opinion of their previous ones. We show that if individuals make biased compromises, extremism may still arise without a need of an explicit classification of extremists and their associated characteristics. With such biased consensus making, several clusters of diversified opinions are gradually formed up in a general trend of shifting toward the extreme opinions close to the two ends of the opinion range, which may allow extremism communities to emerge and moderate views to be dwindled. Furthermore, we assume stronger compromise bias near opinion extremes. It is found that such a case allows moderate opinions a greater chance to survive compared to that of the case where the bias extent is universal across the opinion space. As to the extreme opinion holders' lower tolerances toward different opinions, which arguably may exist in many real-life social systems, they significantly decrease the size of extreme opinion communities rather than helping them to prevail. Brief discussions are presented on the significance and implications of these observations in real-life social systems.

Fitting in and breaking up: A nonlinear version of coevolving voter models

We investigate a nonlinear version of coevolving voter models, in which node states and network structure update as a coupled stochastic process. Most prior work on coevolving voter models has focused on linear update rules with fixed and homogeneous rewiring and adopting probabilities. By contrast, in our nonlinear version, the probability that a node rewires or adopts is a function of how well it "fits in" with the nodes in its neighborhood. To explore this idea, we incorporate a local-survey parameter σ_{i} that encodes the fraction of neighbors of an updating node i that share its opinion state. In an update, with probability σ_{i}^{q} (for some nonlinearity parameter q), the updating node rewires; with complementary probability 1-σ_{i}^{q}, the updating node adopts a new opinion state. We study this mechanism using three rewiring schemes: after an updating node deletes one of its discordant edges, it then either (1) "rewires-to-random" by choosing a new neighbor in a random process; (2) "rewires-to-same" by choosing a new neighbor in a random process from nodes that share its state; or (3) "rewires-to-none" by not rewiring at all (akin to "unfriending" on social media). We compare our nonlinear coevolving voter model to several existing linear coevolving voter models on various network architectures. Relative to those models, we find in our model that initial network topology plays a larger role in the dynamics and that the choice of rewiring mechanism plays a smaller role. A particularly interesting feature of our model is that, under certain conditions, the opinion state that is held initially by a minority of the nodes can effectively spread to almost every node in a network if the minority nodes view themselves as the majority. In light of this observation, we relate our results to recent work on the majority illusion in social networks.

Adaptive voter model on simplicial complexes

Collective decision making processes lie at the heart of many social, political, and economic challenges. The classical voter model is a well-established conceptual model to study such processes. In this work, we define a form of adaptive (or coevolutionary) voter model posed on a simplicial complex, i.e., on a certain class of hypernetworks or hypergraphs. We use the persuasion rule along edges of the classical voter model and the recently studied rewiring rule of edges towards like-minded nodes, and introduce a peer-pressure rule applied to three nodes connected via a 2-simplex. This simplicial adaptive voter model is studied via numerical simulation. We show that adding the effect of peer pressure to an adaptive voter model leaves its fragmentation transition, i.e., the transition upon varying the rewiring rate from a single majority state into a fragmented state of two different opinion subgraphs, intact. Yet, above and below the fragmentation transition, we observe that the peer pressure has substantial quantitative effects. It accelerates the transition to a single-opinion state below the transition and also speeds up the system dynamics towards fragmentation above the transition. Furthermore, we quantify that there is a multiscale hierarchy in the model leading to the depletion of 2-simplices, before the depletion of active edges. This leads to the conjecture that many other dynamic network models on simplicial complexes may show a similar behavior with respect to the sequential evolution of simplices of different dimensions.

Algorithmic bias amplifies opinion fragmentation and polarization: A bounded confidence model

The flow of information reaching us via the online media platforms is optimized not by the information content or relevance but by popularity and proximity to the target. This is typically performed in order to maximise platform usage. As a side effect, this introduces an algorithmic bias that is believed to enhance fragmentation and polarization of the societal debate. To study this phenomenon, we modify the well-known continuous opinion dynamics model of bounded confidence in order to account for the algorithmic bias and investigate its consequences. In the simplest version of the original model the pairs of discussion participants are chosen at random and their opinions get closer to each other if they are within a fixed tolerance level. We modify the selection rule of the discussion partners: there is an enhanced probability to choose individuals whose opinions are already close to each other, thus mimicking the behavior of online media which suggest interaction with similar peers. As a result we observe: a) an increased tendency towards opinion fragmentation, which emerges also in conditions where the original model would predict consensus, b) increased polarisation of opinions and c) a dramatic slowing down of the speed at which the convergence at the asymptotic state is reached, which makes the system highly unstable. Fragmentation and polarization are augmented by a fragmented initial population.

Consensus of Leader-Following Multiagent Systems: A Distributed Event-Triggered Impulsive Control Strategy

This paper investigates the leader-following consensus problem of multiagent systems using a distributed event-triggered impulsive control method. For each agent, the controller is updated only when some state-dependent errors exceed a tolerable bound. The control inputs will be carried out by actor only at event triggering impulsive instants. According to the Lyapunov stability theory and impulsive method, several sufficient criteria for leader-following consensus are derived. Also, it is shown that continuous communication of neighboring agents can be avoided, and Zeno-behavior can be excluded in our schema. The results are illustrated through several numerical simulation examples.

Emergence of linguistic conventions in multi-agent reinforcement learning

Recently, emergence of signaling conventions, among which language is a prime example, draws a considerable interdisciplinary interest ranging from game theory, to robotics to evolutionary linguistics. Such a wide spectrum of research is based on much different assumptions and methodologies, but complexity of the problem precludes formulation of a unifying and commonly accepted explanation. We examine formation of signaling conventions in a framework of a multi-agent reinforcement learning model. When the network of interactions between agents is a complete graph or a sufficiently dense random graph, a global consensus is typically reached with the emerging language being a nearly unique object-word mapping or containing some synonyms and homonyms. On finite-dimensional lattices, the model gets trapped in disordered configurations with a local consensus only. Such a trapping can be avoided by introducing a population renewal, which in the presence of superlinear reinforcement restores an ordinary surface-tension driven coarsening and considerably enhances formation of efficient signaling.

Group-based rewiring rules of binary opinion competition dynamics

The dynamics of competing opinions on networks has attracted multi-disciplinary research. Most modelling approaches assume uniform or heterogeneous behaviour among all individuals, while the role of distinctive group behaviour is rarely addressed. Here, we consider competition occurring between two opinion groups with bound rewiring rules, i.e., opinion-preferred rewiring, degree-preferred rewiring and random rewiring. When two opinions share a balanced initial proportion, opinion-preferred rewiring is superior to the other rules under low rewiring rates, and coexistence occurs under high rewiring rates. For unbalanced proportions, the best response rule for the minority/majority is unfixed, and this depends on the initial proportion and rewiring frequency. Furthermore, we find evolution processes for all competing cases belong to two categories. Evolution Category I shows an obvious correlation between opinion proportions and the density of discordant edges (connecting nodes with different opinions), and these trends can be effectively described by numerical approximations. However, for Evolution Category II, no such correlation exists for individuals or linking pairs, and an analysis of local structures reveals the emergence of large numbers of open triads with the same opinions, denoting group prevalence. This work broadens the understanding of opinion competition and inspires exploring group strategies employed in social dynamic systems.

Opinion formation and distribution in a bounded-confidence model on various networks

In the social, behavioral, and economic sciences, it is important to predict which individual opinions eventually dominate in a large population, whether there will be a consensus, and how long it takes for a consensus to form. Such ideas have been studied heavily both in physics and in other disciplines, and the answers depend strongly both on how one models opinions and on the network structure on which opinions evolve. One model that was created to study consensus formation quantitatively is the Deffuant model, in which the opinion distribution of a population evolves via sequential random pairwise encounters. To consider heterogeneity of interactions in a population along with social influence, we study the Deffuant model on various network structures (deterministic synthetic networks, random synthetic networks, and social networks constructed from Facebook data). We numerically simulate the Deffuant model and conduct regression analyses to investigate the dependence of the time to reach steady states on various model parameters, including a confidence bound for opinion updates, the number of participating entities, and their willingness to compromise. We find that network structure and parameter values both have important effects on the convergence time and the number of steady-state opinion groups. For some network architectures, we observe that the relationship between the convergence time and model parameters undergoes a transition at a critical value of the confidence bound. For some networks, the steady-state opinion distribution also changes from consensus to multiple opinion groups at this critical value.

Opinion diversity and community formation in adaptive networks

It is interesting and of significant importance to investigate how network structures co-evolve with opinions. In this article, we show that, a simple model integrating consensus formation, link rewiring, and opinion change allows complex system dynamics to emerge, driving the system into a dynamic equilibrium with the co-existence of diversified opinions. Specifically, similar opinion holders may form into communities yet with no strict community consensus; and rather than being separated into disconnected communities, different communities are connected by a non-trivial proportion of inter-community links. More importantly, we show that the complex dynamics may lead to different numbers of communities at the steady state with a given tolerance between different opinion holders. We construct a framework for theoretically analyzing the co-evolution process. Theoretical analysis and extensive simulation results reveal some useful insights into the complex co-evolution process, including the formation of dynamic equilibrium, the transition between different steady states with different numbers of communities, and the dynamics between opinion distribution and network modularity.

Deffuant model on a ring with repelling mechanism and circular opinions

We investigate a Deffuant model on a ring by introducing two modifications: the repelling mechanism and the circular opinions. The repelling mechanism drives the opinions of two individuals away from each other and the circular opinions are defined on a circle. We find that the repelling mechanism tends to polarize the opinions of adjacent individuals and the circular opinions bring up a spatiotemporal pattern in which all individuals take different opinions but the opinion difference between two neighboring individuals tends to zero in the limit of the population size. In the Deffuant model with both repelling mechanism and the circular opinions, opinion dynamics depends on both the bounded confidence and the convergence rate. The interplay between the repelling mechanism and the circular opinion may give rise to time-dependent opinion dynamics.

Opinion formation with time-varying bounded confidence

When individuals in social groups communicate with one another and are under the influence of neighbors' opinions, they typically revise their own opinions to adapt to such peer opinions. The individual threshold of bounded confidence will thus be affected by both a change in individual confidence and by neighbor influence. Individuals thus update their own opinions with new bounded confidence, while their updated opinions also influence their neighbors' opinions. Based on this reasoned factual assumption, we propose an opinion dynamics model with time-varying bounded confidence. A directed network is formed by the rule of the individual bounded confidence threshold. The threshold of individual bounded confidence involves both confidence variation and the in/out degree of the individual node. When the confidence variation is greater, an individual's confidence in persisting in his own opinion in interactions is weaker, and the individual is more likely to adopt neighbors' opinions. In networks, the in/out degree is determined by individual neighbors. Our main research involves the process of opinion evolution and the basic laws of opinion cluster formation. Group opinions converge exponentially to consensus with stable neighbors. An individual opinion evolution is determined by the average neighbor opinion effect strength. We also explore the conditions involved in forming a stable neighbor relationship and the influence of the confidence variation in the convergence of the threshold of bounded confidence. The results show that the influence on opinion evolution is greater with increased confidence variation.

Bounded Confidence under Preferential Flip: A Coupled Dynamics of Structural Balance and Opinions

In this work we study the coupled dynamics of social balance and opinion formation. We propose a model where agents form opinions under bounded confidence, but only considering the opinions of their friends. The signs of social ties -friendships and enmities- evolve seeking for social balance, taking into account how similar agents' opinions are. We consider both the case where opinions have one and two dimensions. We find that our dynamics produces the segregation of agents into two cliques, with the opinions of agents in one clique differing from those in the other. Depending on the level of bounded confidence, the dynamics can produce either consensus of opinions within each clique or the coexistence of several opinion clusters in a clique. For the uni-dimensional case, the opinions in one clique are all below the opinions in the other clique, hence defining a "left clique" and a "right clique". In the two-dimensional case, our numerical results suggest that the two cliques are separated by a hyperplane in the opinion space. We also show that the phenomenon of unidimensional opinions identified by DeMarzo, Vayanos and Zwiebel (Q J Econ 2003) extends partially to our dynamics. Finally, in the context of politics, we comment about the possible relation of our results to the fragmentation of an ideology and the emergence of new political parties.

Lumping evolutionary game dynamics on networks

We study evolutionary game dynamics on networks (EGN), where players reside in the vertices of a graph, and games are played between neighboring vertices. The model is described by a system of ordinary differential equations which depends on players payoff functions, as well as on the adjacency matrix of the underlying graph. Since the number of differential equations increases with the number of vertices in the graph, the analysis of EGN becomes hard for large graphs. Building on the notion of lumpability for Markov chains, we identify conditions on the network structure allowing to reduce the original graph. In particular, we identify a partition of the vertex set of the graph and show that players in the same block of a lumpable partition have equivalent dynamical behaviors, whenever their payoff functions and initial conditions are equivalent. Therefore, vertices belonging to the same partition block can be merged into a single vertex, giving rise to a reduced graph and consequently to a simplified system of equations. We also introduce a tighter condition, called strong lumpability, which can be used to identify dynamical symmetries in EGN which are related to the interchangeability of players in the system.

An Opinion Interactive Model Based on Individual Persuasiveness

In order to study the formation process of group opinion in real life, we put forward a new opinion interactive model based on Deffuant model and its improved models in this paper because current models of opinion dynamics lack considering individual persuasiveness. Our model has following advantages: firstly persuasiveness is added to individual's attributes reflecting the importance of persuasiveness, which means that all the individuals are different from others; secondly probability is introduced in the course of interaction which simulates the uncertainty of interaction. In Monte Carlo simulation experiments, sensitivity analysis including the influence of randomness, initial persuasiveness distribution, and number of individuals is studied at first; what comes next is that the range of common opinion based on the initial persuasiveness distribution can be predicted. Simulation experiment results show that when the initial values of agents are fixed, no matter how many times independently replicated experiments, the common opinion will converge at a certain point; however the number of iterations will not always be the same; the range of common opinion can be predicted when initial distribution of opinion and persuasiveness are given. As a result, this model can reflect and interpret some phenomena of opinion interaction in realistic society.

Self-organization of complex networks as a dynamical system

To understand the dynamics of real-world networks, we investigate a mathematical model of the interplay between the dynamics of random walkers on a weighted network and the link weights driven by a resource carried by the walkers. Our numerical studies reveal that, under suitable conditions, the co-evolving dynamics lead to the emergence of stationary power-law distributions of the resource and link weights, while the resource quantity at each node ceaselessly changes with time. We analyze the network organization as a deterministic dynamical system and find that the system exhibits multistability, with numerous fixed points, limit cycles, and chaotic states. The chaotic behavior of the system leads to the continual changes in the microscopic network dynamics in the absence of any external random noises. We conclude that the intrinsic interplay between the states of the nodes and network reformation constitutes a major factor in the vicissitudes of real-world networks.

The structure and dynamics of multilayer networks

In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.

Older partner selection promotes the prevalence of cooperation in evolutionary games

Evolutionary games typically come with the interplays between evolution of individual strategy and adaptation to network structure. How these dynamics in the co-evolution promote (or obstruct) the cooperation is regarded as an important topic in social, economic, and biological fields. Combining spatial selection with partner choice, the focus of this paper is to identify which neighbour should be selected as a role to imitate during the process of co-evolution. Age, an internal attribute and kind of local piece of information regarding the survivability of the agent, is a significant consideration for the selection strategy. The analysis and simulations presented, demonstrate that older partner selection for strategy imitation could foster the evolution of cooperation. The younger partner selection, however, may decrease the level of cooperation. Our model highlights the importance of agent׳s age on the promotion of cooperation in evolutionary games, both efficiently and effectively.

Hierarchy and polysynchrony in an adaptive network

We describe a simple adaptive network of coupled chaotic maps. The network reaches a stationary state (frozen topology) for all values of the coupling parameter, although the dynamics of the maps at the nodes of the network can be nontrivial. The structure of the network shows interesting hierarchical properties and in certain parameter regions the dynamics is polysynchronous: Nodes can be divided in differently synchronized classes but, contrary to cluster synchronization, nodes in the same class need not be connected to each other. These complicated synchrony patterns have been conjectured to play roles in systems biology and circuits. The adaptive system we study describes ways whereby this behavior can evolve from undifferentiated nodes.

Opinion formation on social media: an empirical approach

Opinion exchange models aim to describe the process of public opinion formation, seeking to uncover the intrinsic mechanism in social systems; however, the model results are seldom empirically justified using large-scale actual data. Online social media provide an abundance of data on opinion interaction, but the question of whether opinion models are suitable for characterizing opinion formation on social media still requires exploration. We collect a large amount of user interaction information from an actual social network, i.e., Twitter, and analyze the dynamic sentiments of users about different topics to investigate realistic opinion evolution. We find two nontrivial results from these data. First, public opinion often evolves to an ordered state in which one opinion predominates, but not to complete consensus. Second, agents are reluctant to change their opinions, and the distribution of the number of individual opinion changes follows a power law. Then, we suggest a model in which agents take external actions to express their internal opinions according to their activity. Conversely, individual actions can influence the activity and opinions of neighbors. The probability that an agent changes its opinion depends nonlinearly on the fraction of opponents who have taken an action. Simulation results show user action patterns and the evolution of public opinion in the model coincide with the empirical data. For different nonlinear parameters, the system may approach different regimes. A large decay in individual activity slows down the dynamics, but causes more ordering in the system.

Freezing period strongly impacts the emergence of a global consensus in the voter model

It is well known that human beings do not always change opinions or attitudes, since the duration of interaction with others usually has a significant impact on one's decision-making. Based on this observation, we introduce a freezing period into the voter model, in which the frozen individuals have a weakened opinion switching ability. We unfold the presence of an optimal freezing period, which leads to the fastest consensus, using computation simulations as well as theoretical analysis. We demonstrate that the essence of an accelerated consensus is attributed to the biased random walk of the interface between adjacent opinion clusters. The emergence of an optimal freezing period is robust against the size of the system and the number of distinct opinions. This study is instructive for understanding human collective behavior in other relevant fields.

Extracting tag hierarchies

Tagging items with descriptive annotations or keywords is a very natural way to compress and highlight information about the properties of the given entity. Over the years several methods have been proposed for extracting a hierarchy between the tags for systems with a "flat", egalitarian organization of the tags, which is very common when the tags correspond to free words given by numerous independent people. Here we present a complete framework for automated tag hierarchy extraction based on tag occurrence statistics. Along with proposing new algorithms, we are also introducing different quality measures enabling the detailed comparison of competing approaches from different aspects. Furthermore, we set up a synthetic, computer generated benchmark providing a versatile tool for testing, with a couple of tunable parameters capable of generating a wide range of test beds. Beside the computer generated input we also use real data in our studies, including a biological example with a pre-defined hierarchy between the tags. The encouraging similarity between the pre-defined and reconstructed hierarchy, as well as the seemingly meaningful hierarchies obtained for other real systems indicate that tag hierarchy extraction is a very promising direction for further research with a great potential for practical applications. Tags have become very prevalent nowadays in various online platforms ranging from blogs through scientific publications to protein databases. Furthermore, tagging systems dedicated for voluntary tagging of photos, films, books, etc. with free words are also becoming popular. The emerging large collections of tags associated with different objects are often referred to as folksonomies, highlighting their collaborative origin and the “flat” organization of the tags opposed to traditional hierarchical categorization. Adding a tag hierarchy corresponding to a given folksonomy can very effectively help narrowing or broadening the scope of search. Moreover, recommendation systems could also benefit from a tag hierarchy.

Multiopinion coevolving voter model with infinitely many phase transitions

We consider an idealized model in which individuals' changing opinions and their social network coevolve, with disagreements between neighbors in the network resolved either through one imitating the opinion of the other or by reassignment of the discordant edge. Specifically, an interaction between x and one of its neighbors y leads to x imitating y with probability (1-α) and otherwise (i.e., with probability α) x cutting its tie to y in order to instead connect to a randomly chosen individual. Building on previous work about the two-opinion case, we study the multiple-opinion situation, finding that the model has infinitely many phase transitions (in the large graph limit with infinitely many initial opinions). Moreover, the formulas describing the end states of these processes are remarkably simple when expressed as a function of β=α/(1-α).

Spontaneous scale-free structure in adaptive networks with synchronously dynamical linking

Inspired by the anti-Hebbian learning rule in neural systems, we study how the feedback from dynamical synchronization shapes network structure by adding new links. Through extensive numerical simulations, we find that an adaptive network spontaneously forms scale-free structure, as confirmed in many real systems. Moreover, the adaptive process produces two nontrivial power-law behaviors of deviation strength from mean activity of the network and negative degree correlation, which exists widely in technological and biological networks. Importantly, these scalings are robust to variation of the adaptive network parameters, which may have meaningful implications in the scale-free formation and manipulation of dynamical networks. Our study thus suggests an alternative adaptive mechanism for the formation of scale-free structure with negative degree correlation, which means that nodes of high degree tend to connect, on average, with others of low degree and vice versa. The relevance of the results to structure formation and dynamical property in neural networks is briefly discussed as well.

Collective opinion formation model under Bayesian updating and confirmation bias

We propose a collective opinion formation model with a so-called confirmation bias. The confirmation bias is a psychological effect with which, in the context of opinion formation, an individual in favor of an opinion is prone to misperceive new incoming information as supporting the current belief of the individual. Our model modifies a Bayesian decision-making model for single individuals [M. Rabin and J. L. Schrag, Q. J. Econ. 114, 37 (1999)] for the case of a well-mixed population of interacting individuals in the absence of the external input. We numerically simulate the model to show that all the agents eventually agree on one of the two opinions only when the confirmation bias is weak. Otherwise, the stochastic population dynamics ends up creating a disagreement configuration (also called polarization), particularly for large system sizes. A strong confirmation bias allows various final disagreement configurations with different fractions of the individuals in favor of the opposite opinions.

Role of conviction in nonequilibrium models of opinion formation

We analyze the critical behavior of a class of discrete opinion models in the presence of disorder. Within this class, each agent opinion takes a discrete value (± 1 or 0) and its time evolution is ruled by two terms, one representing agent-agent interactions and the other the degree of conviction or persuasion (a self-interaction). The mean-field limit, where each agent can interact evenly with any other, is considered. Disorder is introduced in the strength of both interactions, with either quenched or annealed random variables. With probability p (1-p), a pairwise interaction reflects a negative (positive) coupling, while the degree of conviction also follows a binary probability distribution (two different discrete probability distributions are considered). Numerical simulations show that a nonequilibrium continuous phase transition, from a disordered state to a state with a prevailing opinion, occurs at a critical point p(c) that depends on the distribution of the convictions, with the transition being spoiled in some cases. We also show how the critical line, for each model, is affected by the update scheme (either parallel or sequential) as well as by the kind of disorder (either quenched or annealed).

Bond-site duality and nature of the explosive-percolation phase transition on a two-dimensional lattice

To establish the bond-site duality of explosive percolations in two dimensions, the site and bond explosive-percolation models are carefully defined on a square lattice. By studying the cluster distribution function and the behavior of the second largest cluster, it is shown that the duality in which the transition is discontinuous exists for the pairs of the site model and the corresponding bond model which relatively enhances the intrabond occupation. In contrast the intrabond-suppressed models which have no corresponding site models undergo a continuous transition and satisfy the normal scaling ansatz as ordinary percolation.

Naming game on adaptive weighted networks

We examine a naming game on an adaptive weighted network. A weight of connection for a given pair of agents depends on their communication success rate and determines the probability with which the agents communicate. In some cases, depending on the parameters of the model, the preference toward successfully communicating agents is essentially negligible and the model behaves similarly to the naming game on a complete graph. In particular, it quickly reaches a single-language state, albeit some details of the dynamics are different from the complete-graph version. In some other cases, the preference toward successfully communicating agents becomes much more important and the model gets trapped in a multi-language regime. In this case gradual coarsening and extinction of languages lead to the emergence of a dominant language, albeit with some other languages still present. A comparison of distribution of languages in our model and in the human population is discussed.

Fragmentation transitions in multistate voter models

Adaptive models of opinion formation among humans can display a fragmentation transition, where a social network breaks into disconnected components. Here we investigate this transition in a class of models with arbitrary number of opinions. In contrast to previous work we do not assume that opinions are equidistant or arranged on a one-dimensional conceptual axis. Our investigation reveals detailed analytical results on fragmentations in a three-opinion model, which are confirmed by agent-based simulations. Furthermore, we show that in certain models the number of opinions can be reduced without affecting the fragmentation points.

Opinion group formation and dynamics: structures that last from nonlasting entities

We extend simple opinion models to obtain stable but continuously evolving communities. Our scope is to meet a challenge raised by sociologists of generating "structures that last from nonlasting entities." We achieve this by introducing two kinds of noise on a standard opinion model. First, agents may interact with other agents even if their opinion difference is large. Second, agents randomly change their opinion at a constant rate. We show that for a large range of control parameters, our model yields stable and fluctuating polarized states, where the composition and mean opinion of the emerging groups is fluctuating over time.

Early fragmentation in the adaptive voter model on directed networks

We consider voter dynamics on a directed adaptive network with fixed out-degree distribution. A transition between an active phase and a fragmented phase is observed. This transition is similar to the undirected case if the networks are sufficiently dense and have a narrow out-degree distribution. However, if a significant number of nodes with low out degree is present, then fragmentation can occur even far below the estimated critical point due to the formation of self-stabilizing structures that nucleate fragmentation. This process may be relevant for fragmentation in current political opinion formation processes.

Graph fission in an evolving voter model

We consider a simplified model of a social network in which individuals have one of two opinions (called 0 and 1) and their opinions and the network connections coevolve. Edges are picked at random. If the two connected individuals hold different opinions then, with probability 1 - α, one imitates the opinion of the other; otherwise (i.e., with probability α), the link between them is broken and one of them makes a new connection to an individual chosen at random (i) from those with the same opinion or (ii) from the network as a whole. The evolution of the system stops when there are no longer any discordant edges connecting individuals with different opinions. Letting ρ be the fraction of voters holding the minority opinion after the evolution stops, we are interested in how ρ depends on α and the initial fraction u of voters with opinion 1. In case (i), there is a critical value α(c) which does not depend on u, with ρ ≈ u for α > α(c) and ρ ≈ 0 for α < α(c). In case (ii), the transition point α(c)(u) depends on the initial density u. For α > α(c)(u), ρ ≈ u, but for α < α(c)(u), we have ρ(α,u) = ρ(α,1/2). Using simulations and approximate calculations, we explain why these two nearly identical models have such dramatically different phase transitions.

Reconciling long-term cultural diversity and short-term collective social behavior

An outstanding open problem is whether collective social phenomena occurring over short timescales can systematically reduce cultural heterogeneity in the long run, and whether offline and online human interactions contribute differently to the process. Theoretical models suggest that short-term collective behavior and long-term cultural diversity are mutually excluding, since they require very different levels of social influence. The latter jointly depends on two factors: the topology of the underlying social network and the overlap between individuals in multidimensional cultural space. However, while the empirical properties of social networks are intensively studied, little is known about the large-scale organization of real societies in cultural space, so that random input specifications are necessarily used in models. Here we use a large dataset to perform a high-dimensional analysis of the scientific beliefs of thousands of Europeans. We find that interopinion correlations determine a nontrivial ultrametric hierarchy of individuals in cultural space. When empirical data are used as inputs in models, ultrametricity has strong and counterintuitive effects. On short timescales, it facilitates a symmetry-breaking phase transition triggering coordinated social behavior. On long timescales, it suppresses cultural convergence by restricting it within disjoint groups. Moreover, ultrametricity implies that these results are surprisingly robust to modifications of the dynamical rules considered. Thus the empirical distribution of individuals in cultural space appears to systematically optimize the coexistence of short-term collective behavior and long-term cultural diversity, which can be realized simultaneously for the same moderate level of mutual influence in a diverse range of online and offline settings.

Reinforced communication and social navigation: remember your friends and remember yourself

In social systems, people communicate with each other and form groups based on their interests. The pattern of interactions, the network, and the ideas that flow on the network naturally evolve together. Researchers use simple models to capture the feedback between changing network patterns and ideas on the network, but little is understood about the role of past events in the feedback process. Here, we introduce a simple agent-based model to study the coupling between peoples' ideas and social networks, and better understand the role of history in dynamic social networks. We measure how information about ideas can be recovered from information about network structure and, the other way around, how information about network structure can be recovered from information about ideas. We find that it is, in general, easier to recover ideas from the network structure than vice versa.

Interplay between structure and dynamics in adaptive complex networks: emergence and amplification of modularity by adaptive dynamics

Many real networks display modular organization, which can influence dynamical clustering on the networks. Therefore, there have been proposals put forth recently to detect network communities by using dynamical clustering. In this paper, we study how the feedback from dynamical clusters can shape the network connection weights with a weight-adaptation scheme motivated from Hebbian learning in neural systems. We show that such a scheme generically leads to the formation of community structure in globally coupled chaotic oscillators. The number of communities in the adaptive network depends on coupling strength c and adaptation strength r. In a modular network, the adaptation scheme will enhance the intramodule connection weights and weaken the intermodule connection strengths, generating effectively separated dynamical clusters that coincide with the communities of the network. In this sense, the modularity of the network is amplified by the adaptation. Thus, for a network with a strong community structure, the adaptation scheme can evidently reflect its community structure by the resulting amplified weighted network. For a network with a weak community structure, the statistical properties of synchronization clusters from different realizations can be used to amplify the modularity of the communities so that they can be detected reliably by the other traditional algorithms.

Social network dynamics of face-to-face interactions

The recent availability of data describing social networks is changing our understanding of the "microscopic structure" of a social tie. A social tie indeed is an aggregated outcome of many social interactions such as face-to-face conversations or phone calls. Analysis of data on face-to-face interactions shows that such events, as many other human activities, are bursty, with very heterogeneous durations. In this paper we present a model for social interactions at short time scales, aimed at describing contexts such as conference venues in which individuals interact in small groups. We present a detailed analytical and numerical study of the model's dynamical properties, and show that it reproduces important features of empirical data. The model allows for many generalizations toward an increasingly realistic description of social interactions. In particular, in this paper we investigate the case where the agents have intrinsic heterogeneities in their social behavior, or where dynamic variations of the local number of individuals are included. Finally we propose this model as a very flexible framework to investigate how dynamical processes unfold in social networks.

Methods for generating complex networks with selected structural properties for simulations: a review and tutorial for neuroscientists

Many simulations of networks in computational neuroscience assume completely homogenous random networks of the Erdös–Rényi type, or regular networks, despite it being recognized for some time that anatomical brain networks are more complex in their connectivity and can, for example, exhibit the “scale-free” and “small-world” properties. We review the most well known algorithms for constructing networks with given non-homogeneous statistical properties and provide simple pseudo-code for reproducing such networks in software simulations. We also review some useful mathematical results and approximations associated with the statistics that describe these network models, including degree distribution, average path length, and clustering coefficient. We demonstrate how such results can be used as partial verification and validation of implementations. Finally, we discuss a sometimes overlooked modeling choice that can be crucially important for the properties of simulated networks: that of network directedness. The most well known network algorithms produce undirected networks, and we emphasize this point by highlighting how simple adaptations can instead produce directed networks.

Analytical calculation of fragmentation transitions in adaptive networks

In adaptive networks, fragmentation transitions have been observed in which the network breaks into disconnected components. We present an analytical approach for calculating the transition point in general adaptive network models. Using the example of an adaptive voter model, we demonstrate that the proposed approach yields good agreement with numerical results.

Stability in flux: community structure in dynamic networks

The structure of many biological, social and technological systems can usefully be described in terms of complex networks. Although often portrayed as fixed in time, such networks are inherently dynamic, as the edges that join nodes are cut and rewired, and nodes themselves update their states. Understanding the structure of these networks requires us to understand the dynamic processes that create, maintain and modify them. Here, we build upon existing models of coevolving networks to characterize how dynamic behaviour at the level of individual nodes generates stable aggregate behaviours. We focus particularly on the dynamics of groups of nodes formed endogenously by nodes that share similar properties (represented as node state) and demonstrate that, under certain conditions, network modularity based on state compares well with network modularity based on topology. We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically. Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change. These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.

Adaptive networks: Coevolution of disease and topology

Adaptive networks have been recently introduced in the context of disease propagation on complex networks. They account for the mutual interaction between the network topology and the states of the nodes. Until now, existing models have been analyzed using low complexity analytical formalisms, revealing nevertheless some novel dynamical features. However, current methods have failed to reproduce with accuracy the simultaneous time evolution of the disease and the underlying network topology. In the framework of the adaptive susceptible-infectious-susceptible (SIS) model of Gross [Phys. Rev. Lett. 96, 208701 (2006)]10.1103/PhysRevLett.96.208701, we introduce an improved compartmental formalism able to handle this coevolutionary task successfully. With this approach, we analyze the interplay and outcomes of both dynamical elements, process and structure, on adaptive networks featuring different degree distributions at the initial stage.