Models of random graph hierarchies

We introduce two models of inclusion hierarchies: Random Graph Hierarchy (RGH) and Limited Random Graph Hierarchy (LRGH). In both models a set of nodes at a given hierarchy level is connected randomly, as in the ErdH{o}s-R{e}nyi random graph, with a fixed average degree equal to a system parameter $c$. Clusters of the resulting network are treated as nodes at the next hierarchy level and they are connected again at this level and so on, until the process cannot continue. In the RGH model we use all clusters, including those of size $1$, when building the next hierarchy level, while in the LRGH model clusters of size $1$ stop participating in further steps. We find that in both models the number of nodes at a given hierarchy level $h$ decreases approximately exponentially with $h$. The height of the hierarchy $H$, i.e. the number of all hierarchy levels, increases logarithmically with the system size $N$, i.e. with the number of nodes at the first level. The height $H$ decreases monotonically with the connectivity parameter $c$ in the RGH model and it reaches a maximum for a certain $c_{max}$ in the LRGH model. The distribution of separate cluster sizes in the LRGH model is a power law with an exponent about $-1.25$. The above results follow from approximate analytical calculations and have been confirmed by numerical simulations.

Hierarchical Cont-Bouchaud model

We extend the well-known Cont-Bouchaud model to include a hierarchical topology of agents interactions. The influence of hierarchy on system dynamics is investigated by two models. The first one is based on a multi-level, nested Erdos-Renyi random graph and individual decisions by agents according to Potts dynamics. This approach does not lead to a broad return distribution outside a parameter regime close to the original Cont-Bouchaud model. In the second model we introduce a limited hierarchical Erdos-Renyi graph, where merging of clusters at a level h+1 involves only clusters that have merged at the previous level h and we use the original Cont-Bouchaud agent dynamics on resulting clusters. The second model leads to a heavy-tail distribution of cluster sizes and relative price changes in a wide range of connection densities, not only close to the percolation threshold.

Information slows down hierarchy growth

We consider models of growing multi-level 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 early stage of system evolution to further stop growing at all. The results allow 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.

Is the Voter Model a model for voters?

The voter model has been studied extensively as a paradigmatic opinion dynamics model. However, its ability for modeling real opinion dynamics has not been addressed. We introduce a noisy voter model (accounting for social influence) with agents recurrent mobility (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 anysotropic coupling topology given by population and mobility heterogeneity. The model captures statistical features of the US 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 a real-space renormalization is performed by coarse-graining the geographical scale from 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.

Hierarchy depth in directed networks

We explore depth measures for flow hierarchy in directed networks. We define two measures -- rooted depth and relative depth, and discuss differences between them. We investigate how the two measures behave in random Erdos-Renyi graphs of different sizes and densities and explain obtained results.

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 non-monotonous dependence of the mean magnetization on the temperature in a finite system. The crossover temperature $T_c$ corresponding to the maximal magnetization decays with system size, approximately as the inverse of the W Lambert 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. We conceive the model is 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.

Evolution of Wikipedias Category Structure

Wikipedia, as a social phenomenon of collaborative knowledge creating, has been studied extensively from various points of views. The category system of Wikipedia, introduced in 2004, has attracted relatively little attention. In this study, we focus on the documentation of knowledge, and the transformation of this documentation with time. We take Wikipedia as a proxy for knowledge in general and its category system as an aspect of the structure of this knowledge. We investigate the evolution of the category structure of the English Wikipedia from its birth in 2004 to 2008. We treat the category system as if it is a hierarchical Knowledge Organization System, capturing the changes in the distributions of the top categories. We investigate how the clustering of articles, defined by the category system, matches the direct link network between the articles and show how it changes over time. We find the Wikipedia category network mostly stable, but with occasional reorganization. We show that the clustering matches the link structure quite well, except short periods preceding the reorganizations.

Need to categorize: A comparative look at the categories of the Universal Decimal Classification system (UDC) and Wikipedia

This study analyzes the differences between the category structure of the Universal Decimal Classification (UDC) system (which is one of the widely used library classification systems in Europe) and Wikipedia. In particular, we compare the emerging structure of category-links to the structure of classes in the UDC. With this comparison we would like to scrutinize the question of how do knowledge maps of the same domain differ when they are created socially (i.e. Wikipedia) as opposed to when they are created formally (UDC) using classificatio theory. As a case study, we focus on the category of Arts.

First order phase transition in Ising model on two connected Barabasi-Albert networks

We investigate the behavior of the Ising model on two connected Barabasi-Albert scale-free networks. We extend previous analysis and show that a first order temperature-driven phase transition occurs in such system. The transition between antiparalelly ordered networks to paralelly ordered networks is shown to be discontinuous. We calculate the critical temperature. We confirm the calculations with numeric simulations using Monte-Carlo methods.