Diffusive persistence on disordered lattices and random networks.

To better understand the temporal characteristics and the lifetime of fluctuations in stochastic processes in networks, we investigated diffusive persistence in various graphs. Global diffusive persistence is defined as the fraction of nodes for which the diffusive field at a site (or node) has not changed sign up to time t (or, in general, that the node remained active or inactive in discrete models). Here we investigate disordered and random networks and show that the behavior of the persistence depends on the topology of the network. In two-dimensional (2D) disordered networks, we find that above the percolation threshold diffusive persistence scales similarly as in the original 2D regular lattice, according to a power law P(t,L)∼t^{-θ} with an exponent θ≃0.186, in the limit of large linear system size L. At the percolation threshold, however, the scaling exponent changes to θ≃0.141, as the result of the interplay of diffusive persistence and the underlying structural transition in the disordered lattice at the percolation threshold. Moreover, studying finite-size effects for 2D lattices at and above the percolation threshold, we find that at the percolation threshold, the long-time asymptotic value obeys a power law P(t,L)∼L^{-zθ} with z≃2.86 instead of the value of z=2 normally associated with finite-size effects on 2D regular lattices. In contrast, we observe that in random networks without a local regular structure, such as Erdos-Rényi networks, no simple power-law scaling behavior exists above the percolation threshold.

Robust, scalable, and informative clustering for diverse biological networks.

Clustering molecular data into informative groups is a primary step in extracting robust conclusions from big data. However, due to foundational issues in how they are defined and detected, such clusters are not always reliable, leading to unstable conclusions. We compare popular clustering algorithms across thousands of synthetic and real biological datasets, including a new consensus clustering algorithm-SpeakEasy2: Champagne. These tests identify trends in performance, show no single method is universally optimal, and allow us to examine factors behind variation in performance. Multiple metrics indicate SpeakEasy2 generally provides robust, scalable, and informative clusters for a range of applications.

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.

Network Analytics Enabled by Generating a Pool of Network Variants from Noisy Data.

Mapping network nodes and edges to communities and network functions is crucial to gaining a higher level of understanding of the network structure and functions. Such mappings are particularly challenging to design for covert social networks, which intentionally hide their structure and functions to protect important members from attacks or arrests. Here, we focus on correctly inferring the structures and functions of such networks, but our methodology can be broadly applied. Without the ground truth, knowledge about the allocation of nodes to communities and network functions, no single network based on the noisy data can represent all plausible communities and functions of the true underlying network. To address this limitation, we apply a generative model that randomly distorts the original network based on the noisy data, generating a pool of statistically equivalent networks. Each unique generated network is recorded, while each duplicate of the already recorded network just increases the repetition count of that network. We treat each such network as a variant of the ground truth with the probability of arising in the real world approximated by the ratio of the count of this network's duplicates plus one to the total number of all generated networks. Communities of variants with frequently occurring duplicates contain persistent patterns shared by their structures. Using Shannon entropy, we can find a variant that minimizes the uncertainty for operations planned on the network. Repeatedly generating new pools of networks from the best network of the previous step for several steps lowers the entropy of the best new variant. If the entropy is too high, the network operators can identify nodes, the monitoring of which can achieve the most significant reduction in entropy. Finally, we also present a heuristic for constructing a new variant, which is not randomly generated but has the lowest expected cost of operating on the distorted mappings of network nodes to communities and functions caused by noisy data.

Political polarization of news media and influencers on Twitter in the 2016 and 2020 US presidential elections.

Social media has been transforming political communication dynamics for over a decade. Here using nearly a billion tweets, we analyse the change in Twitter's news media landscape between the 2016 and 2020 US presidential elections. Using political bias and fact-checking tools, we measure the volume of politically biased content and the number of users propagating such information. We then identify influencers-users with the greatest ability to spread news in the Twitter network. We observe that the fraction of fake and extremely biased content declined between 2016 and 2020. However, results show increasing echo chamber behaviours and latent ideological polarization across the two elections at the user and influencer levels.

Analyzing and predicting success of professional musicians.

The emergence of streaming services, e.g., Spotify, has changed the way people listen to music and the way professional musicians achieve fame and success. Classical music has been the backbone of Western media for a long time, but Spotify has introduced the public to a much wider variety of music, also opening a new venue for professional musicians to gain exposure. In this paper, we use open-source data from Spotify and Musicbrainz databases to construct collaboration-based and genre-based networks. We call genres defined in these databases primary genres. Our goal is to find the correlation between various features of each professional musician, the current stage of their career, and the level of their success in the music field. We build regression models using XGBoost to first analyze correlation between features provided by Spotify. We then analyze the correlation between the digital music world of Spotify and the more traditional world of Billboard charts. We find that within certain bounds, machine learning techniques such as decision tree classifiers and Q-based models perform quite well on predicting success of professional musicians from the data on their early careers. We also find features that are highly predictive of their success. The most prominent among them are the musicians' collaboration counts and the span of their career. Our findings also show that classical musicians are still very centrally placed in the general, genre-agnostic network of musicians. Using these models and success metrics, aspiring professional musicians can check if their chances for career success could be improved by increasing their specific success measures in both Spotify and Billboard charts.

Temporal network epistemology: On reaching consensus in a real-world setting.

This work develops the concept of the temporal network epistemology model enabling the simulation of the learning process in dynamic networks. The results of the research, conducted on the temporal social network generated using the CogSNet model and on the static topologies as a reference, indicate a significant influence of the network temporal dynamics on the outcome and flow of the learning process. It has been shown that not only the dynamics of reaching consensus is different compared to baseline models but also that previously unobserved phenomena appear, such as uninformed agents or different consensus states for disconnected components. It has also been observed that sometimes only the change of the network structure can contribute to reaching consensus. The introduced approach and the experimental results can be used to better understand the way how human communities collectively solve both complex problems at the scientific level and to inquire into the correctness of less complex but common and equally important beliefs' spreading across entire societies.

Modelling epidemic spread in cities using public transportation as a proxy for generalized mobility trends.

We study how public transportation data can inform the modeling of the spread of infectious diseases based on SIR dynamics. We present a model where public transportation data is used as an indicator of broader mobility patterns within a city, including the use of private transportation, walking etc. The mobility parameter derived from this data is used to model the infection rate. As a test case, we study the impact of the usage of the New York City subway on the spread of COVID-19 within the city during 2020. We show that utilizing subway transport data as an indicator of the general mobility trends within the city, and therefore as an indicator of the effective infection rate, improves the quality of forecasting COVID-19 spread in New York City. Our model predicts the two peaks in the spread of COVID-19 cases in NYC in 2020, unlike a standard SIR model that misses the second peak entirely.

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.

A network generator for covert network structures.

We focus on organizational structures in covert networks, such as criminal or terrorist networks. Their members engage in illegal activities and attempt to hide their association and interactions with these networks. Hence, data about such networks are incomplete. We introduce a novel method of rewiring covert networks parameterized by the edge connectivity standard deviation. The generated networks are statistically similar to themselves and to the original network. The higher-level organizational structures are modeled as a multi-layer network while the lowest level uses the Stochastic Block Model. Such synthetic networks provide alternative structures for data about the original network. Using them, analysts can find structures that are frequent, therefore stable under perturbations. Another application is to anonymize generated networks and use them for testing new software developed in open research facilities. The results indicate that modeling edge structure and the hierarchy together is essential for generating networks that are statistically similar but not identical to each other or the original network. In experiments, we generate many synthetic networks from two covert networks. Only a few structures of synthetics networks repeat, with the most stable ones shared by 18% of all synthetic networks making them strong candidates for the ground truth structure.

Polarization and tipping points.

Research has documented increasing partisan division and extremist positions that are more pronounced among political elites than among voters. Attention has now begun to focus on how polarization might be attenuated. We use a general model of opinion change to see if the self-reinforcing dynamics of influence and homophily may be characterized by tipping points that make reversibility problematic. The model applies to a legislative body or other small, densely connected organization, but does not assume country-specific institutional arrangements that would obscure the identification of fundamental regularities in the phase transitions. Agents in the model have initially random locations in a multidimensional issue space consisting of membership in one of two equal-sized parties and positions on 10 issues. Agents then update their issue positions by moving closer to nearby neighbors and farther from those with whom they disagree, depending on the agents' tolerance of disagreement and strength of party identification compared to their ideological commitment to the issues. We conducted computational experiments in which we manipulated agents' tolerance for disagreement and strength of party identification. Importantly, we also introduced exogenous shocks corresponding to events that create a shared interest against a common threat (e.g., a global pandemic). Phase diagrams of political polarization reveal difficult-to-predict transitions that can be irreversible due to asymmetric hysteresis trajectories. We conclude that future empirical research needs to pay much closer attention to the identification of tipping points and the effectiveness of possible countermeasures.

Characterizing Topics in Social Media Using Dynamics of Conversation.

Online social media provides massive open-ended platforms for users of a wide variety of backgrounds, interests, and beliefs to interact and debate, facilitating countless discussions across a myriad of subjects. With numerous unique voices being lent to the ever-growing information stream, it is essential to consider how the types of conversations that result from a social media post represent the post itself. We hypothesize that the biases and predispositions of users cause them to react to different topics in different ways not necessarily entirely intended by the sender. In this paper, we introduce a set of unique features that capture patterns of discourse, allowing us to empirically explore the relationship between a topic and the conversations it induces. Utilizing "microscopic" trends to describe "macroscopic" phenomena, we set a paradigm for analyzing information dissemination through the user reactions that arise from a topic, eliminating the need to analyze the involved text of the discussions. Using a Reddit dataset, we find that our features not only enable classifiers to accurately distinguish between content genre, but also can identify more subtle semantic differences in content under a single topic as well as isolating outliers whose subject matter is substantially different from the norm.

Creation, evolution, and dissolution of social groups.

Understanding why people join, stay, or leave social groups is a central question in the social sciences, including computational social systems, while modeling these processes is a challenge in complex networks. Yet, the current empirical studies rarely focus on group dynamics for lack of data relating opinions to group membership. In the NetSense data, we find hundreds of face-to-face groups whose members make thousands of changes of memberships and opinions. We also observe two trends: opinion homogeneity grows over time, and individuals holding unpopular opinions frequently change groups. These observations and data provide us with the basis on which we model the underlying dynamics of human behavior. We formally define the utility that members gain from ingroup interactions as a function of the levels of homophily of opinions of group members with opinions of a given individual in this group. We demonstrate that so-defined utility applied to our empirical data increases after each observed change. We then introduce an analytical model and show that it accurately recreates the trends observed in the NetSense data.

From data to complex network control of airline flight delays.

Many critical complex systems and networks are continuously monitored, creating vast volumes of data describing their dynamics. To understand and optimize their performance, we need to discover and formalize their dynamics to enable their control. Here, we introduce a multidisciplinary framework using network science and control theory to accomplish these goals. We demonstrate its use on a meaningful example of a complex network of U.S. domestic passenger airlines aiming to control flight delays. Using the real data on such delays, we build a flight delay network for each airline. Analyzing these networks, we uncover and formalize their dynamics. We use this formalization to design the optimal control for the flight delay networks. The results of applying this control to the ground truth data on flight delays demonstrate the low costs of the optimal control and significant reduction of delay times, while the costs of the delays unabated by control are high. Thus, the introduced here framework benefits the passengers, the airline companies and the airports.

A partial knowledge of friends of friends speeds social search.

Milgram empirically showed that people knowing only connections to their friends could locate any person in the U.S. in a few steps. Later research showed that social network topology enables a node aware of its full routing to find an arbitrary target in even fewer steps. Yet, the success of people in forwarding efficiently knowing only personal connections is still not fully explained. To study this problem, we emulate it on a real location-based social network, Gowalla. It provides explicit information about friends and temporal locations of each user useful for studies of human mobility. Here, we use it to conduct a massive computational experiment to establish new necessary and sufficient conditions for achieving social search efficiency. The results demonstrate that only the distribution of friendship edges and the partial knowledge of friends of friends are essential and sufficient for the efficiency of social search. Surprisingly, the efficiency of the search using the original distribution of friendship edges is not dependent on how the nodes are distributed into space. Moreover, the effect of using a limited knowledge that each node possesses about friends of its friends is strongly nonlinear. We show that gains of such use grow statistically significantly only when this knowledge is limited to a small fraction of friends of friends.

Heuristic assessment of choices for risk network control.

Data-driven risk networks describe many complex system dynamics arising in fields such as epidemiology and ecology. They lack explicit dynamics and have multiple sources of cost, both of which are beyond the current scope of traditional control theory. We construct the global economy risk network by combining the consensus of experts from the World Economic Forum with risk activation data to define its topology and interactions. Many of these risks, including extreme weather and drastic inflation, pose significant economic costs when active. We introduce a method for converting network interaction data into continuous dynamics to which we apply optimal control. We contribute the first method for constructing and controlling risk network dynamics based on empirically collected data. We simulate applying this method to control the spread of COVID-19 and show that the choice of risks through which the network is controlled has significant influence on both the cost of control and the total cost of keeping network stable. We additionally describe a heuristic for choosing the risks trough which the network is controlled, given a general risk network.

Modeling competitive evolution of multiple languages.

Increasing evidence demonstrates that in many places language coexistence has become ubiquitous and essential for supporting language and cultural diversity and associated with its financial and economic benefits. The competitive evolution among multiple languages determines the evolution outcome, either coexistence, or decline, or extinction. Here, we extend the Abrams-Strogatz model of language competition to multiple languages and then validate it by analyzing the behavioral transitions of language usage over the recent several decades in Singapore and Hong Kong. In each case, we estimate from data the model parameters that measure each language utility for its speakers and the strength of two biases, the majority preference for their language, and the minority aversion to it. The values of these two biases decide which language is the fastest growing in the competition and what would be the stable state of the system. We also study the system convergence time to stable states and discover the existence of tipping points with multiple attractors. Moreover, the critical slowdown of convergence to the stable fractions of language users appears near and peaks at the tipping points, signaling when the system approaches them. Our analysis furthers our understanding of evolution of various languages and the role of tipping points in behavioral transitions. These insights may help to protect languages from extinction and retain the language and cultural diversity.

A Regularized Stochastic Block Model for the robust community detection in complex networks.

The stochastic block model is able to generate random graphs with different types of network partitions, ranging from the traditional assortative structures to the disassortative structures. Since the stochastic block model does not specify which mixing pattern is desired, the inference algorithms discover the locally most likely nodes' partition, regardless of its type. Here we introduce a new model constraining nodes' internal degree ratios in the objective function to guide the inference algorithms to converge to the desired type of structure in the observed network data. We show experimentally that given the regularized model, the inference algorithms, such as Markov chain Monte Carlo, reliably and quickly find the assortative or disassortative structure as directed by the value of a single parameter. In contrast, when the sought-after assortative community structure is not strong in the observed network, the traditional inference algorithms using the degree-corrected stochastic block model tend to converge to undesired disassortative partitions.

The evolution of polarization in the legislative branch of government.

The polarization of political opinions among members of the US legislative chambers measured by their voting records is greater today than it was 30 years ago. Previous research efforts to find causes of such increase have suggested diverse contributors, like growth of online media, echo chamber effects, media biases or disinformation propagation. Yet, we lack theoretic tools to understand, quantify and predict the emergence of high political polarization among voters and their legislators. Here, we analyse millions of roll-call votes cast in the US Congress over the past six decades. Our analysis reveals the critical change of polarization patterns that started at the end of 1980s. In earlier decades, polarization within each Congress tended to decrease with time. By contrast, in recent decades, the polarization has been likely to grow within each term. To shed light on the reasons for this change, we introduce here a formal model for competitive dynamics to quantify the evolution of polarization patterns in the legislative branch of the US government. Our model represents dynamics of polarization, enabling us to successfully predict the direction of polarization changes in 28 out of 30 US Congresses elected in the past six decades. From the evolution of polarization level as measured by the Rice index, our model extracts a hidden parameter-polarization utility which determines the convergence point of the polarization evolution. The increase in the polarization utility implied by the model strongly correlates with two current trends: growing polarization of voters and increasing influence of election campaign donors. Two largest peaks of the model's polarization utility correlate with significant political or legislative changes happening at the same time.