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.

Homophily Based on Few Attributes Can Impede Structural Balance.

Homophily between agents and structural balance in connected triads of agents are complementary mechanisms thought to shape social groups leading to, for instance, consensus or polarization. To capture both processes in a unified manner, we propose a model of pair and triadic interactions. We consider N fully connected agents, where each agent has G underlying attributes, and the similarity between agents in attribute space (i.e., homophily) is used to determine the link weight between them. For structural balance we use a triad-updating rule where only one attribute of one agent is changed intentionally in each update, but this also leads to accidental changes in link weights and even link polarities. The link weight dynamics in the limit of large G is described by a Fokker-Planck equation from which the conditions for a phase transition to a fully balanced state with all links positive can be obtained. This "paradise state" of global cooperation is, however, difficult to achieve requiring G>O(N^{2}) and p>0.5, where the parameter p captures a willingness for consensus. Allowing edge weights to be a consequence of attributes naturally captures homophily and reveals that many real-world social systems would have a subcritical number of attributes necessary to achieve structural balance.

Why understanding multiplex social network structuring processes will help us better understand the evolution of human behavior.

Social scientists have long appreciated that relationships between individuals cannot be described from observing a single domain, and that the structure across domains of interaction can have important effects on outcomes of interest (e.g., cooperation; Durkheim, 1893). One debate explicitly about this surrounds food sharing. Some argue that failing to find reciprocal food sharing means that some process other than reciprocity must be occurring, whereas others argue for models that allow reciprocity to span domains in the form of trade (Kaplan and Hill, 1985.). Multilayer networks, high-dimensional networks that allow us to consider multiple sets of relationships at the same time, are ubiquitous and have consequences, so processes giving rise to them are important social phenomena. The analysis of multi-dimensional social networks has recently garnered the attention of the network science community (Kivelä et al., 2014). Recent models of these processes show how ignoring layer interdependencies can lead one to miss why a layer formed the way it did, and/or draw erroneous conclusions (Górski et al., 2018). Understanding the structuring processes that underlie multiplex networks will help understand increasingly rich data sets, giving more accurate and complete pictures of social interactions.

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.

Multidimensional attributes expose Heider balance dynamics to measurements.

Most of studied social interactions arise from dyadic relations. An exception is Heider Balance Theory that postulates the existence of triad dynamics, which however has been elusive to observe. Here, we discover a sufficient condition for the Heider dynamics observability: assigning the edge signs according to multiple opinions of connected agents. Using longitudinal records of university student mutual contacts and opinions, we create a coevolving network on which we introduce models of student interactions. These models account for: multiple topics of individual student opinions, influence of such opinions on dyadic relations, and influence of triadic relations on opinions. We show that the triadic influence is empirically measurable for static and dynamic observables when signs of edges are defined by multidimensional differences between opinions on all topics. Yet, when these signs are defined by a difference between opinions on each topic separately, the triadic interactions' influence is indistinguishable from noise.

Mean-field approximation for structural balance dynamics in heat bath.

A critical temperature for a complete signed graph of N agents where the time-dependent polarization of links tends towards the Heider (structural) balance is found analytically using the heat-bath approach and the mean-field approximation as T^{c}=(N-2)/a^{c}, where a^{c}≈1.71649. The result is in perfect agreement with numerical simulations starting from the paradise state where all links are positively polarized as well as with the estimation of this temperature received earlier with much more sophisticated methods. When heating the system, one observes a discontinuous and irreversible phase transition at T^{c} from a nearly balanced state when the mean link polarization is about x_{c}=0.796388 to a disordered and unbalanced state where the polarization vanishes. When the initial conditions for the polarization of links are random, then at low temperatures a balanced bipolar state of two mutually hostile cliques exists that decays towards the disorder and there is a discontinuous phase transition at a temperature T^{d} that is lower than T^{c}. The system phase diagram corresponds to the so-called fold catastrophe when a stable solution of the mean-field equation collides with a separatrix, and as a result a hysteresislike loop is observed.

Transitions between polarization and radicalization in a temporal bilayer echo-chamber model.

Echo chambers and polarization dynamics are, as of late, a very prominent topic in scientific communities around the world. As these phenomena directly affect our lives, seemingly more and more as our societies and communication channels evolve, it becomes ever so important for us to understand the intricacies of opinion dynamics in the modern era. Here we extend an existing echo-chamber model with activity-driven agents to a bilayer topology and study the dynamics of the polarized state as a function of interlayer couplings. Different cases of such couplings are presented: unidirectional coupling that can be reduced to a monolayer facing an external bias and symmetric and nonsymmetric couplings. We have assumed that initial conditions impose system polarization and agent opinions are different for both layers. Such a preconditioned polarized state can persist without explicit homophilic interactions provided the coupling strength between agents belonging to different layers is weak enough. For a strong unidirectional or attractive coupling between two layers a discontinuous transition to a radicalized state takes place when mean opinions in both layers are the same. When coupling constants between the layers are of different signs, the system exhibits sustained or decaying oscillations. Transitions between these states are analyzed using a mean field approximation and classified in the framework of bifurcation theory.

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.

Discovering hidden layers in quantum graphs.

Finding hidden layers in complex networks is an important and a nontrivial problem in modern science. We explore the framework of quantum graphs to determine whether concealed parts of a multilayer system exist and if so then what is their extent, i.e., how many unknown layers are there. Assuming that the only information available is the time evolution of a wave propagation on a single layer of a network it is indeed possible to uncover that which is hidden by merely observing the dynamics. We present evidence on both synthetic and real-world networks that the frequency spectrum of the wave dynamics can express distinct features in the form of additional frequency peaks. These peaks exhibit dependence on the number of layers taking part in the propagation and thus allowing for the extraction of said number. We show that, in fact, with sufficient observation time, one can fully reconstruct the row-normalized adjacency matrix spectrum. We compare our propositions to a machine learning approach using a wave packet signature method modified for the purposes of multilayer systems.

A calibrated measure to compare fluctuations of different entities across timescales.

A common way to learn about a system's properties is to analyze temporal fluctuations in associated variables. However, conclusions based on fluctuations from a single entity can be misleading when used without proper reference to other comparable entities or when examined only on one timescale. Here we introduce a method that uses predictions from a fluctuation scaling law as a benchmark for the observed standard deviations. Differences from the benchmark (residuals) are aggregated across multiple timescales using Principal Component Analysis to reduce data dimensionality. The first component score is a calibrated measure of fluctuations-the reactivity RA of a given entity. We apply our method to activity records from the media industry using data from the Event Registry news aggregator-over 32M articles on selected topics published by over 8000 news outlets. Our approach distinguishes between different news outlet reporting styles: high reactivity points to activity fluctuations larger than expected, reflecting a bursty reporting style, whereas low reactivity suggests a relatively stable reporting style. Combining our method with the political bias detector Media Bias/Fact Check we quantify the relative reporting styles for different topics of mainly US media sources grouped by political orientation. The results suggest that news outlets with a liberal bias tended to be the least reactive while conservative news outlets were the most reactive.

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.

Kauffman Boolean model in undirected scale-free networks.

We investigate analytically and numerically the critical line in undirected random Boolean networks with arbitrary degree distributions, including the scale-free topology of connections P(k) ~ k(-gamma). We explain that the unattainability of the critical line in numerical simulations of classical random graphs is due to percolation phenomena. We suggest that recent findings of discrepancy between simulations and theory in directed random Boolean networks might have the same reason. We also show that in infinite scale-free networks the transition between frozen and chaotic phases occurs for 3

Hierarchical partitions of social networks between rivaling leaders.

A model algorithm is proposed to imitate a series of of consecutive conflicts between leaders in social groups. The leaders are represented by local hubs, i.e., nodes with highest node degrees. We simulate subsequent hierarchical partitions of a complex connected network which represents a social structure. The partitions are supposed to appear as actions of members of two conflicted groups surrounding two strongest leaders. According to the model, links at the shortest path between the rival leaders are successively removed. When the group is split into two disjoint parts then each part is further divided as the initial network. The algorithm is stopped, if in all parts a distance from a local leader to any node in his group is shorter than three links. The numerically calculated size distribution of resulting fragments of scale-free Barabási-Albert networks reveals one largest fragment which contains the original leader (hub of the network) and a number of small fragments with opponents that are described by two Weibull distributions. A mean field calculation of the size of the largest fragment is in a good agreement with numerical results. The model assumptions are validated by an application of the algorithm to the data on political blogs in U.S. (L. Adamic and N. Glance, Proc. WWW-2005). The obtained fragments are clearly polarized; either they belong to Democrats, or to Republicans. This result confirms that during conflicts, hubs are centers of polarization.

Categorical and Geographical Separation in Science.

We study scientific collaboration at the level of universities. The scope of this study is to answer two fundamental questions: (i) can one indicate a category (i.e., a scientific discipline) that has the greatest impact on the rank of the university and (ii) do the best universities collaborate with the best ones only? Restricting ourselves to the 100 best universities from year 2009 we show how the number of publications in certain categories correlates with the university rank. Strikingly, the expected negative trend is not observed in all cases - for some categories even positive values are obtained. After applying Principal Component Analysis we observe clear categorical separation of scientific disciplines, dividing the papers into almost separate clusters connected to natural sciences, medicine and arts and humanities. Moreover, using complex networks analysis, we give hints that the scientific collaboration is still embedded in the physical space and the number of common papers decays with the geographical distance between them.

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.

Thermodynamic forces, flows, and Onsager coefficients in complex networks.

In this paper the linear theory of nonequilibrium thermodynamics, developed by Onsager and others, is applied to random networks with arbitrary degree distribution. Using the well-known methods of nonequilibrium thermodynamics we identify thermodynamic forces and their conjugated flows induced in networks as a result of single node degree perturbation. The forces and the flows can be understood as a response of the system to events, such as random removal of nodes or intentional attacks on them. Finally, we show that cross effects (such as thermodiffusion, or thermoelectric phenomena), in which one force may not only give rise to its own conjugated flow, but to many other flows, can be observed also in complex networks.

Log-periodic oscillations due to discrete effects in complex networks.

We show how discretization affects two major characteristics in complex networks: internode distances (measured as the shortest number of edges between network sites) and average path length, and as a result there are log-periodic oscillations of the above quantities. The effect occurs both in numerical network models as well as in such real systems as coauthorship, language, food, and public transport networks. Analytical description of these oscillations fits well numerical simulations. We consider a simple case of the network optimization problem, arguing that discrete effects can lead to a nontrivial solution.

Analysis of scientific productivity using maximum entropy principle and fluctuation-dissipation theorem.

Using data retrieved from the INSPEC database we have quantitatively discussed a few syndromes of the publish-or-perish phenomenon, including the continuous growth of the rate of scientific productivity, and the continuously decreasing percentage of those scientists who stay in science for a long time. Making use of the maximum entropy principle and fluctuation-dissipation theorem, we have shown that the observed fat-tailed distributions of the total number of papers x authored by scientists may result from the density-of-states function g(x;tau) underlying the scientific community. Although different generations of scientists are characterized by different productivity patterns, the function g(x;tau) is inherent to researchers of a given seniority tau , whereas the publish-or-perish phenomenon is caused only by an external field theta influencing researchers.