Hierarchy Depth in Directed Networks.

In this study, we explore the depth measures for flow hierarchy in directed networks. Two simple measures are defined-rooted depth and relative depth-and their properties are discussed. The method of loop collapse is introduced, allowing investigation of networks containing directed cycles. The behavior of the two depth measures is investigated in Erdös-Rényi random graphs, directed Barabási-Albert networks, and in Gnutella p2p share network. A clear distinction in the behavior between non-hierarchical and hierarchical networks is found, with random graphs featuring unimodal distribution of depths dependent on arc density, while for hierarchical systems the distributions are similar for different network densities. Relative depth shows the same behavior as existing trophic level measure for tree-like networks, but is only statistically correlated for more complex topologies, including acyclic directed graphs.

Is the voter model a model for voters?

The voter model has been studied extensively as a paradigmatic opinion dynamics model. However, its ability to model real opinion dynamics has not been addressed. We introduce a noisy voter model (accounting for social influence) with recurrent mobility of agents (as a proxy for social context), where the spatial and population diversity are taken as inputs to the model. We show that the dynamics can be described as a noisy diffusive process that contains the proper anisotropic coupling topology given by population and mobility heterogeneity. The model captures statistical features of U.S. presidential elections as the stationary vote-share fluctuations across counties and the long-range spatial correlations that decay logarithmically with the distance. Furthermore, it recovers the behavior of these properties when the geographical space is coarse grained at different scales-from the county level through congressional districts, and up to states. Finally, we analyze the role of the mobility range and the randomness in decision making, which are consistent with the empirical observations.

Critical properties of Heider balance on multiplex networks.

Heider's structural balance theory has proven invaluable in comprehending the dynamics of social groups characterized by both friendly and hostile relationships. Since people's relations are rarely single faceted, we investigate Heider balance dynamics on a multiplex network, consisting of several copies of the same agent displaying correlated relations at different layers building the multiplex. Intralayer interactions in our model adhere to Heider dynamics, while interlayer correlations stem from Ising interactions, with the heat-bath dynamics of link signs. Our investigation reveals a multifaceted system with a diverse equilibrium landscape contingent on the coexistence of distinct phases across layers. We observe that, starting from a paradise state with positive links in all layers, an increase in temperature triggers a discontinuous transition to a disordered state akin to single-layer scenarios. The critical temperature surpasses that of the single-layer case, a fact verified through extended mean-field analysis and agent-based simulations. Furthermore, the scenario shifts when one layer exhibits a two-clique configuration instead of a paradise state. This change introduces additional transitions: synchronization of interlayer relations and a transition to the disorder, appearing at a different, lower temperature compared to matching paradise states. This exploration shows the intricate interplay of Heider balance and multiplex interactions.

Topic selectivity and adaptivity promote spreading of short messages.

Why is the Twitter, with its extremely length-limited messages so popular ? Our work shows that short messages focused on a single topic may have an inherent advantage in spreading through social networks, which may explain the popularity of a service featuring only short messages. We introduce a new explanatory model for information propagation through social networks that includes selectivity of message consumption depending on their content, competition for user's attention between messages and message content adaptivity through user-introduced changes. Our agent-based simulations indicate that the model displays inherent power-law distribution of number of shares for different messages and that the popular messages are very short. The adaptivity of messages increases the popularity of already popular messages, provided the users are neither too selective nor too accommodating. The distribution of message variants popularity also follows a power-law found in real information cascades. The observed behavior is robust against model parameter changes and differences of network topology.

Comparison of observer based methods for source localisation in complex networks.

In recent years, research on methods for locating a source of spreading phenomena in complex networks has seen numerous advances. Such methods can be applied not only to searching for the "patient zero" in epidemics, but also finding the true sources of false or malicious messages circulating in the online social networks. Many methods for solving this problem have been established and tested in various circumstances. Yet, we still lack reviews that would include a direct comparison of efficiency of these methods. In this paper, we provide a thorough comparison of several observer-based methods for source localisation on complex networks. All methods use information about the exact time of spread arrival at a pre-selected group of vertices called observers. We investigate how the precision of the studied methods depends on the network topology, density of observers, infection rate, and observers' placement strategy. The direct comparison between methods allows for an informed choice of the methods for applications or further research. We find that the Pearson correlation based method and the method based on the analysis of multiple paths are the most effective in networks with synthetic or real topologies. The former method dominates when the infection rate is low; otherwise, the latter method takes over.

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.

Fast and accurate detection of spread source in large complex networks.

Spread over complex networks is a ubiquitous process with increasingly wide applications. Locating spread sources is often important, e.g. finding the patient one in epidemics, or source of rumor spreading in social network. Pinto, Thiran and Vetterli introduced an algorithm (PTVA) to solve the important case of this problem in which a limited set of nodes act as observers and report times at which the spread reached them. PTVA uses all observers to find a solution. Here we propose a new approach in which observers with low quality information (i.e. with large spread encounter times) are ignored and potential sources are selected based on the likelihood gradient from high quality observers. The original complexity of PTVA is O(N α ), where α ∈ (3,4) depends on the network topology and number of observers (N denotes the number of nodes in the network). Our Gradient Maximum Likelihood Algorithm (GMLA) reduces this complexity to O (N2log (N)). Extensive numerical tests performed on synthetic networks and real Gnutella network with limitation that id's of spreaders are unknown to observers demonstrate that for scale-free networks with such limitation GMLA yields higher quality localization results than PTVA does.

Ising model on two connected Barabasi-Albert networks.

We investigate analytically the behavior of the Ising model on two connected Barabasi-Albert networks. Depending on relative ordering of both networks there are two possible phases corresponding to parallel or antiparallel alignment of spins in both networks. A difference between critical temperatures of both phases disappears in the limit of vanishing inter-network coupling for identical networks. The analytic predictions are confirmed by numerical simulations.

Voter model dynamics in complex networks: Role of dimensionality, disorder, and degree distribution.

We analyze the ordering dynamics of the voter model in different classes of complex networks. We observe that whether the voter dynamics orders the system depends on the effective dimensionality of the interaction networks. We also find that when there is no ordering in the system, the average survival time of metastable states in finite networks decreases with network disorder and degree heterogeneity. The existence of hubs, i.e., highly connected nodes, in the network modifies the linear system size scaling law of the survival time. The size of an ordered domain is sensitive to the network disorder and the average degree, decreasing with both; however, it seems not to depend on network size and on the heterogeneity of the degree distribution.

Universal scaling of distances in complex networks.

Universal scaling of distances between vertices of Erdos-Rényi random graphs, scale-free Barabási-Albert models, science collaboration networks, biological networks, Internet Autonomous Systems and public transport networks are observed. A mean distance between two nodes of degrees k(i) and k(j) equals to (l(ij)) = A - B log(k(i)k(j)). The scaling is valid over several decades. A simple theory for the appearance of this scaling is presented. Parameters A and B depend on the mean value of a node degree (k)nn calculated for the nearest neighbors and on network clustering coefficients.

Finite size induces crossover temperature in growing spin chains.

We introduce a growing one-dimensional quenched spin model that bases on asymmetrical one-side Ising interactions in the presence of external field. Numerical simulations and analytical calculations based on Markov chain theory show that when the external field is smaller than the exchange coupling constant J there is a nonmonotonous dependence of the mean magnetization on the temperature in a finite system. The crossover temperature Tc corresponding to the maximal magnetization decays with system size, approximately as the inverse of the Lambert W function. The observed phenomenon can be understood as an interplay between the thermal fluctuations and the presence of the first cluster determined by initial conditions. The effect exists also when spins are not quenched but fully thermalized after the attachment to the chain. By performing tests on real data we conceive the model is in part suitable for a qualitative description of online emotional discussions arranged in a chronological order, where a spin in every node conveys emotional valence of a subsequent post.

Information slows down hierarchy growth.

We consider models of growing multilevel systems wherein the growth process is driven by rules of tournament selection. A system can be conceived as an evolving tree with a new node being attached to a contestant node at the best hierarchy level (a level nearest to the tree root). The proposed evolution reflects limited information on system properties available to new nodes. It can also be expressed in terms of population dynamics. Two models are considered: a constant tournament (CT) model wherein the number of tournament participants is constant throughout system evolution, and a proportional tournament (PT) model where this number increases proportionally to the growing size of the system itself. The results of analytical calculations based on a rate equation fit well to numerical simulations for both models. In the CT model all hierarchy levels emerge, but the birth time of a consecutive hierarchy level increases exponentially or faster for each new level. The number of nodes at the first hierarchy level grows logarithmically in time, while the size of the last, "worst" hierarchy level oscillates quasi-log-periodically. In the PT model, the occupations of the first two hierarchy levels increase linearly, but worse hierarchy levels either do not emerge at all or appear only by chance in the early stage of system evolution to further stop growing at all. The results allow us to conclude that information available to each new node in tournament dynamics restrains the emergence of new hierarchy levels and that it is the absolute amount of information, not relative, which governs such behavior.

Bistable-monostable transition in the Ising model on two connected complex networks.

In this paper, we investigate the behavior of the Ising model on two sparsely connected complex networks. The networks have the topology of a random graph or Barabási and Albert scale-free networks. We extend our previous analysis and show that a bistable-monostable phase transition occurs in such systems. During this transition, the magnetization undergoes a discontinuous jump. We calculate the critical temperature analytically for regular random graphs and study a more general case using an iterative map corresponding to mean-field dynamics. The calculations are confirmed by numeric simulations based on Monte Carlo approach.