Search

The population structure often impacts evolutionary dynamics. In constant-selection evolutionary dynamics between two types, amplifiers of selection are networks that promote the fitter mutant to take over the entire population, and suppressors of selection do the opposite. It has been shown that most undirected and unweighted networks are amplifiers of selection under a common updating rule and initial condition. Here, we extensively investigate how edge weights influence selection on undirected networks. We show that random edge weights make small networks less amplifying than the corresponding unweighted networks in a majority of cases and also make them suppressors of selection (i.e., less amplifying than the complete graph, or equivalently, the Moran process) in many cases. Qualitatively, the same result holds true for larger empirical networks. These results suggest that amplifiers of selection are not as common for weighted networks as for unweighted counterparts.

We present a nation-wide network analysis of non-fatal opioid-involved overdose journeys in the United States. Leveraging a unique proprietary dataset of Emergency Medical Services incidents, we construct a journey-to-overdose geospatial network capturing nearly half a million opioid-involved overdose events spanning 2018-2023. We analyze the structure and sociological profile of the nodes, which are counties or their equivalents, characterize the distribution of overdose journey lengths, and investigate changes in the journey network between 2018 and 2023. Our findings include that authority and hub nodes identified by the HITS algorithm tend to be located in urban areas and involved in overdose journeys with particularly long geographical distances.

Recent developments of eco-evolutionary models have shown that evolving feedbacks between behavioral strategies and the environment of game interactions, leading to changes in the underlying payoff matrix, can impact the underlying population dynamics in various manners. We propose and analyze an eco-evolutionary game dynamics model on a network with two communities such that players interact with other players in the same community and those in the opposite community at different rates. In our model, we consider two-person matrix games with pairwise interactions occurring on individual edges and assume that the environmental state depends on edges rather than on nodes or being globally shared in the population. We analytically determine the equilibria and their stability under a symmetric population structure assumption, and we also numerically study the replicator dynamics of the general model. The model shows rich dynamical behavior, such as multiple transcritical bifurcations, multistability, and anti-synchronous oscillations. Our work offers insights into understanding how the presence of community structure impacts the eco-evolutionary dynamics within and between niches., Comment: 8 figures, 2 tables

Manga, Japanese comics, has been popular on a global scale. Social networks among characters, which are often called character networks, may be a significant contributor to their popularity. We collected data from 162 popular manga that span over 70 years and analyzed their character networks. First, we found that many of static and temporal properties of the character networks are similar to those of real human social networks. Second, the character networks of most manga are protagonist-centered such that a single protagonist interacts with the majority of other characters. Third, the character networks for manga mainly targeting boys have shifted to denser and less protagonist-centered networks and with fewer characters over decades. Manga mainly targeting girls showed the opposite trend except for the downward trend in the number of characters. The present study, which relies on manga data sampled on an unprecedented scale, paves the way for further population studies of character networks and other aspects of comics., Comment: 17 pages, 9 figures, 1 table

Gender imbalance in academia has been confirmed in terms of a variety of indicators, and its magnitude often varies from country to country. Europe and North America, which cover a large fraction of research workforce in the world, have been the main geographical regions for research on gender imbalance in academia. However, the academia in East Asia, which accounts for a substantial fraction of research, may be exposed to strong gender imbalance because Asia has been facing persistent and stronger gender imbalance in society at large than Europe and North America. Here we use publication data between 1950 and 2020 to analyze gender imbalance in academia in China, Japan, and South Korea in terms of the number of researchers, their career, and citation practice. We found that, compared to the average of the other countries, gender imbalance is larger in these three East Asian countries in terms of the number of researchers and their citation practice and additionally in Japan in terms of research career. Moreover, we found that Japan has been exposed to the larger gender imbalance than China and South Korea in terms of research career and citation practice., Comment: 31 pages, 8 figures, 10 tables

Understanding the dynamics of financial transactions among people is critically important for various applications such as fraud detection. One important aspect of financial transaction networks is temporality. The order and repetition of transactions can offer new insights when considered within the graph structure. Temporal motifs, defined as a set of nodes that interact with each other in a short time period, are a promising tool in this context. In this work, we study three unique temporal financial networks: transactions in Mercari, an online marketplace, payments in a synthetic network generated by J.P. Morgan Chase, and payments and friendships among Venmo users. We consider the fraud detection problem on the Mercari and J.P. Morgan Chase networks, for which the ground truth is available. We show that temporal motifs offer superior performance than a previous method that considers simple graph features. For the Venmo network, we investigate the interplay between financial and social relations on three tasks: friendship prediction, vendor identification, and analysis of temporal cycles. For friendship prediction, temporal motifs yield better results than general heuristics, such as Jaccard and Adamic-Adar measures. We are also able to identify vendors with high accuracy and observe interesting patterns in rare motifs, like temporal cycles. We believe that the analysis, datasets, and lessons from this work will be beneficial for future research on financial transaction networks.

Inverse Ising inference allows pairwise interactions of complex binary systems to be reconstructed from empirical correlations. Typical estimators used for this inference, such as Pseudo-likelihood maximization (PLM), are biased. Using the Sherrington-Kirkpatrick (SK) model as a benchmark, we show that these biases are large in critical regimes close to phase boundaries, and may alter the qualitative interpretation of the inferred model. In particular, we show that the small-sample bias causes models inferred through PLM to appear closer-to-criticality than one would expect from the data. Data-driven methods to correct this bias are explored and applied to a functional magnetic resonance imaging (fMRI) dataset from neuroscience. Our results indicate that additional care should be taken when attributing criticality to real-world datasets.

Population structure has been known to substantially affect evolutionary dynamics. Networks that promote the spreading of fitter mutants are called amplifiers of natural selection, and those that suppress the spreading of fitter mutants are called suppressors. Research in the past two decades has found various families of amplifiers while suppressors still remain somewhat elusive. It has also been discovered that most networks are amplifiers under the birth-death updating combined with uniform initialization, which is a standard condition assumed widely in the literature. In the present study, we extend the birth-death processes to temporal (i.e., time-varying) networks. For the sake of tractability, we restrict ourselves to switching temporal networks, in which the network structure alternates between two static networks at constant time intervals. We show that, in a majority of cases, switching networks are less amplifying than both of the two static networks constituting the switching networks. Furthermore, most small switching networks are suppressors, which contrasts to the case of static networks.

Network structure has a large impact on constant-selection evolutionary dynamics, with which multiple types of different fitnesses (i.e., strengths) compete on the network. Here we study constant-selection dynamics on two-layer networks in which the fitness of a node in one layer affects that in the other layer, under birth-death processes and uniform initialization, which are commonly assumed. We show mathematically and numerically that two-layer networks are suppressors of selection, which suppresses the effects of the different fitness values between the different types on final outcomes of the evolutionary dynamics (called fixation probability), relative to the constituent one-layer networks. In fact, many two-layer networks are suppressors of selection relative to the most basic baseline, the Moran process. This result is in stark contrast with the results for conventional one-layer networks for which most networks are amplifiers of selection., Comment: 9 figures

Many empirical networks originate from correlational data, arising in domains as diverse as psychology, neuroscience, genomics, microbiology, finance, and climate science. Specialized algorithms and theory have been developed in different application domains for working with such networks, as well as in statistics, network science, and computer science, often with limited communication between practitioners in different fields. This leaves significant room for cross-pollination across disciplines. A central challenge is that it is not always clear how to best transform correlation matrix data into networks for the application at hand, and probably the most widespread method, i.e., thresholding on the correlation value to create either unweighted or weighted networks, suffers from multiple problems. In this article, we review various methods of constructing and analyzing correlation networks, ranging from thresholding and its improvements to weighted networks, regularization, dynamic correlation networks, threshold-free approaches, and more. Finally, we propose and discuss a variety of key open questions currently confronting this field., Comment: 1 figure

Modern scientific work, including writing papers and submitting research grant proposals, increasingly involves researchers from different institutions. In grant collaborations, it is known that institutions involved in many collaborations tend to densely collaborate with each other, forming rich clubs. Here we investigate higher-order rich-club phenomena in collaborative research grants among institutions and their associations with research productivity. Using publicly available data from the National Science Foundation in the US, we construct a bipartite network of institutions and collaborative grants, which distinguishes among the collaboration with different numbers of institutions. By extending the concept and algorithms of the rich club for dyadic networks to the case of bipartite networks, we find rich clubs both in the entire bipartite network and the bipartite subnetwork induced by the collaborative grants involving a given number of institutions up to five. We also find that the collaborative grants within rich clubs tend to be more productive in a per-dollar sense than the control. Our results highlight advantages of collaborative grants among the institutions in the rich clubs., Comment: 18 pages, 6 figures, 2 tables

Many multiagent dynamics, including various collective dynamics occurring on networks, can be modeled as a stochastic process in which the agents in the system change their state over time in interaction with each other. The Gillespie algorithms are popular algorithms that exactly simulate such stochastic multiagent dynamics when each state change is driven by a discrete event, the dynamics is defined in continuous time, and the stochastic law of event occurrence is governed by independent Poisson processes. In the first main part of this volume, we provide a tutorial on the Gillespie algorithms focusing on simulation of social multiagent dynamics occurring in populations and networks. We do not assume advanced knowledge of mathematics (or computer science or physics). We clarify why one should use the continuous-time models and the Gillespie algorithms in many cases, instead of easier-to-understand discrete-time models. In the remainder of this volume, we review recent extensions of the Gillespie algorithms aiming to add more reality to the model (i.e., non-Poissonian cases) or to speed up the simulations., Comment: 25 figures. Elements in the Structure and Dynamics of Complex Networks. Cambridge: Cambridge University Press (2023)

Patents are intellectual properties that reflect innovative activities of companies and organizations. The literature is rich with the studies that analyze the citations among the patents and the collaboration relations among companies that own the patents. However, the adversarial relations between the patent owners are not as well investigated. One proxy to model such relations is the patent opposition, which is a legal activity in which a company challenges the validity of a patent. Characterizing the patent oppositions, collaborations, and the interplay between them can help better understand the companies' business strategies. Temporality matters in this context as the order and frequency of oppositions and collaborations characterize their interplay. In this study, we construct a two-layer temporal network to model the patent oppositions and collaborations among the companies. We utilize temporal motifs to analyze the oppositions and collaborations from structural and temporal perspectives. We first characterize the frequent motifs in patent oppositions and investigate how often the companies of different sizes attack other companies. We show that large companies tend to engage in opposition with multiple companies. Then we analyze the temporal interplay between collaborations and oppositions. We find that two adversarial companies are more likely to collaborate in the future than two collaborating companies oppose each other in the future.

Successful on-time delivery of projects is a key enabler in resolving major societal challenges, such as wasted resources and stagnated economic growth. However, projects are notoriously hard to deliver successfully, partly due to their interconnected and temporal complexity which makes them prone to cascading failures. Here, we develop a cascading failure model and test it on a temporal activity network, extracted from a large-scale engineering project. We evaluate the effectiveness of six mitigation strategies, in terms of the impact of task failure cascading throughout the project. In contrast to theoretical arguments, our results indicate that in the majority of cases, the temporal properties of the activities are more relevant than their structural properties in preventing large-scale cascading failures. In practice, these findings could stimulate new pathways for designing and scheduling projects that naturally limit the extent of cascading failures.

Many complex systems involve direct interactions among more than two entities and can be represented by hypergraphs, in which hyperedges encode higher-order interactions among an arbitrary number of nodes. To analyze structures and dynamics of given hypergraphs, a solid practice is to compare them with those for randomized hypergraphs that preserve some specific properties of the original hypergraphs. In the present study, we propose a family of such reference models for hypergraphs, called the hyper dK-series, by extending the so-called dK-series for dyadic networks to the case of hypergraphs. The hyper dK-series preserves up to the individual node's degree, node's degree correlation, node's redundancy coefficient, and/or the hyperedge's size depending on the parameter values. We also apply the hyper dK-series to numerical simulations of epidemic spreading and evolutionary game dynamics on empirical hypergraphs., Comment: 28 pages, 9 figures, 10 tables. Our code is available at "https://github.com/kazuibasou/hyper-dk-series"

Link prediction can be used to extract missing information, identify spurious interactions as well as forecast network evolution. Network embedding is a methodology to assign coordinates to nodes in a low-dimensional vector space. By embedding nodes into vectors, the link prediction problem can be converted into a similarity comparison task. Nodes with similar embedding vectors are more likely to be connected. Classic network embedding algorithms are random-walk-based. They sample trajectory paths via random walks and generate node pairs from the trajectory paths. The node pair set is further used as the input for a Skip-Gram model, a representative language model that embeds nodes (which are regarded as words) into vectors. In the present study, we propose to replace random walk processes by a spreading process, namely the susceptible-infected (SI) model, to sample paths. Specifically, we propose two susceptible-infected-spreading-based algorithms, i.e., Susceptible-Infected Network Embedding (SINE) on static networks and Temporal Susceptible-Infected Network Embedding (TSINE) on temporal networks. The performance of our algorithms is evaluated by the missing link prediction task in comparison with state-of-the-art static and temporal network embedding algorithms. Results show that SINE and TSINE outperform the baselines across all six empirical datasets. We further find that the performance of SINE is mostly better than TSINE, suggesting that temporal information does not necessarily improve the embedding for missing link prediction. Moreover, we study the effect of the sampling size, quantified as the total length of the trajectory paths, on the performance of the embedding algorithms. The better performance of SINE and TSINE requires a smaller sampling size in comparison with the baseline algorithms. Hence, SI-spreading-based embedding tends to be more applicable to large-scale networks., Multimedia Computing, Web Information Systems

Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyze random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyze the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both back-tracking and visiting a neighbor of the previously visited node but do not avoid them completely., Comment: 9 figures, 2 tables

Changes in air transport networks over time may be induced by competition among carriers, changes in regulations on airline industry, and socioeconomic events such as terrorist attacks and epidemic outbreaks. Such network changes may reflect corporate strategies of each carrier. In the present study, we propose a framework for analyzing evolution patterns in temporal networks in discrete time from the viewpoint of recurrence. Recurrence implies that the network structure returns to one relatively close to that in the past. We applied the proposed methods to four major carriers in the US from 1987 to 2019. We found that the carriers were different in terms of the autocorrelation, strength of periodicity, and changes in these quantities across decades. We also found that the network structure of the individual carriers abruptly changes from time to time. Such a network change reflects changes in their operation at their hub airports rather than famous socioeconomic events that look closely related to airline industry. The proposed methods are expected to be useful for revealing, for example, evolution of airline alliances and responses to natural disasters or infectious diseases, as well as characterizing evolution of social, biological, and other networks over time., Comment: 17 pages, 12 figures, 2 tables

The organisation of a network in a maximal set of nodes having at least $k$ neighbours within the set, known as $k$-core decomposition, has been used for studying various phenomena. It has been shown that nodes in the innermost $k$-shells play a crucial role in contagion processes, emergence of consensus, and resilience of the system. It is known that the $k$-core decomposition of many empirical networks cannot be explained by the degree of each node alone, or equivalently, random graph models that preserve the degree of each node (i.e., configuration model). Here we study the $k$-core decomposition of some empirical networks as well as that of some randomised counterparts, and examine the extent to which the $k$-shell structure of the networks can be accounted for by the community structure. We find that preserving the community structure in the randomisation process is crucial for generating networks whose $k$-core decomposition is close to the empirical one. We also highlight the existence, in some networks, of a concentration of the nodes in the innermost $k$-shells into a small number of communities., Comment: 34 pages, 4 tables, and 15 figures. Main + supplementary. Final version accepted for publication

Maritime shipping is a backbone of international trade and, thus, the world economy. Cargo-loaded vessels travel from one country's port to another via an underlying port-to-port transport network, contributing to international trade values of countries en route. We hypothesize that ports that involve trans-shipment activities serve as a third-party broker to mediate trade between two foreign countries and contribute to the corresponding country's status in international trade. We test this hypothesis using a port-level dataset of global liner shipping services. We propose two indices that quantify the importance of countries in the global liner shipping network and show that they explain a large amount of variation in individual countries' international trade values and related measures. These results support a long-standing view in maritime economics, which has yet to be directly tested, that countries that are strongly integrated into the global maritime transportation network have enhanced access to global markets and trade opportunities., Comment: 2 figures, 3 tables, SI with 1 figure and 6 tables

Diseases spread over temporal networks of interaction events between individuals. Structures of these temporal networks hold the keys to understanding epidemic propagation. One early concept of the literature to aid in discussing these structures is concurrency -- quantifying individuals' tendency to form time-overlapping "partnerships". Although conflicting evaluations and an overabundance of operational definitions have marred the history of concurrency, it remains important, especially in the area of sexually transmitted infections. Today, much of theoretical epidemiology uses more direct models of contact patterns, and there is an emerging body of literature trying to connect methods to the concurrency literature. In this review, we will cover the development of the concept of concurrency and these new approaches., Comment: 5 figures

In social networks, interaction patterns typically change over time. We study opinion dynamics on tie-decay networks in which tie strength increases instantaneously when there is an interaction and decays exponentially between interactions. Specifically, we formulate continuous-time Laplacian dynamics and a discrete-time DeGroot model of opinion dynamics on these tie-decay networks, and we carry out numerical computations for the continuous-time Laplacian dynamics. We examine the speed of convergence by studying the spectral gaps of combinatorial Laplacian matrices of tie-decay networks. First, we compare the spectral gaps of the Laplacian matrices of tie-decay networks that we construct from empirical data with the spectral gaps for corresponding randomized and aggregate networks. We find that the spectral gaps for the empirical networks tend to be smaller than those for the randomized and aggregate networks. Second, we study the spectral gap as a function of the tie-decay rate and time. Intuitively, we expect small tie-decay rates to lead to fast convergence because the influence of each interaction between two nodes lasts longer for smaller decay rates. Moreover, as time progresses and more interactions occur, we expect eventual convergence. However, we demonstrate that the spectral gap need not decrease monotonically with respect to the decay rate or increase monotonically with respect to time. Our results highlight the importance of the interplay between the times that edges strengthen and decay in temporal networks., Comment: 15 pages, 8 figures, 2 tables

The concept of temporal networks provides a framework to understand how the interaction between system components changes over time. In empirical communication data, we often detect non-Poissonian, so-called bursty behavior in the activity of nodes as well as in the interaction between nodes. However, such reconciliation between node burstiness and link burstiness cannot be explained if the interaction processes on different links are independent of each other. This is because the activity of a node is the superposition of the interaction processes on the links incident to the node and the superposition of independent bursty point processes is not bursty in general. Here we introduce a temporal network model based on bursty node activation and show that it leads to heavy-tailed inter-event time distributions for both node dynamics and link dynamics. Our analysis indicates that activation processes intrinsic to nodes give rise to dynamical correlations across links. Our framework offers a way to model competition and correlation between links, which is key to understanding dynamical processes in various systems., Comment: 9 pages, 5 figures

Tiny perturbations may trigger large responses in systems near criticality, shifting them across equilibria. Committed minorities are suggested to be responsible for the emergence of collective behaviors in many physical, social, and biological systems. Using evolutionary game theory, we address the question whether a finite fraction of zealots can drive the system to large-scale coordination. We find that a tipping point exists in coordination games, whereas the same phenomenon depends on the selection pressure, update rule, and network structure in other types of games. Our study paves the way to understand social systems driven by the individuals' benefit in presence of zealots, such as human vaccination behavior or cooperative transports in animal groups., Comment: 15 pages, 11 figures. Final version accepted for publication

Providers of online marketplaces are constantly combatting against problematic transactions, such as selling illegal items and posting fictive items, exercised by some of their users. A typical approach to detect fraud activity has been to analyze registered user profiles, user's behavior, and texts attached to individual transactions and the user. However, this traditional approach may be limited because malicious users can easily conceal their information. Given this background, network indices have been exploited for detecting frauds in various online transaction platforms. In the present study, we analyzed networks of users of an online consumer-to-consumer marketplace in which a seller and the corresponding buyer of a transaction are connected by a directed edge. We constructed egocentric networks of each of several hundreds of fraudulent users and those of a similar number of normal users. We calculated eight local network indices based on up to connectivity between the neighbors of the focal node. Based on the present descriptive analysis of these network indices, we fed twelve features that we constructed from the eight network indices to random forest classifiers with the aim of distinguishing between normal users and fraudulent users engaged in each one of the four types of problematic transactions. We found that the classifier accurately distinguished the fraudulent users from normal users and that the classification performance did not depend on the type of problematic transaction., Comment: 10 figures and 3 tables

We study the stochastic susceptible-infected-susceptible model of epidemic processes on finite directed and weighted networks with arbitrary structure. We present a new lower bound on the exponential rate at which the probabilities of nodes being infected decay over time. This bound is directly related to the leading eigenvalue of a matrix that depends on the non-backtracking and incidence matrices of the network. The dimension of this matrix is N+M, where N and M are the number of nodes and edges, respectively. We show that this new lower bound improves on an existing bound corresponding to the so-called quenched mean-field theory. Although the bound obtained from a recently developed second-order moment-closure technique requires the computation of the leading eigenvalue of an N^2 x N^2 matrix, we illustrate in our numerical simulations that the new bound is tighter, while being computationally less expensive for sparse networks. We also present the expression for the corresponding epidemic threshold in terms of the adjacency matrix of the line graph and the non-backtracking matrix of the given network., Comment: 1 figure

Feature sparseness is a problem common to cross-domain and short-text classification tasks. To overcome this feature sparseness problem, we propose a novel method based on graph decomposition to find candidate features for expanding feature vectors. Specifically, we first create a feature-relatedness graph, which is subsequently decomposed into core-periphery (CP) pairs and use the peripheries as the expansion candidates of the cores. We expand both training and test instances using the computed related features and use them to train a text classifier. We observe that prioritising features that are common to both training and test instances as cores during the CP decomposition to further improve the accuracy of text classification. We evaluate the proposed CP-decomposition-based feature expansion method on benchmark datasets for cross-domain sentiment classification and short-text classification. Our experimental results show that the proposed method consistently outperforms all baselines on short-text classification tasks, and perform competitively with pivot-based cross-domain sentiment classification methods.

Resolving major societal challenges, such as stagnated economic growth or wasted resources, heavily relies on successful project delivery. However, projects are notoriously hard to deliver successfully, partly due to their interconnected nature which makes them prone to cascading failures. We deploy a model of cascading failure to temporal network data obtained from an engineering project, where tasks constituting the entire project and inter-dependencies between tasks correspond to time-stamped nodes and edges, respectively. We numerically evaluate the performance of six strategies to mitigate cascading failures. It is assumed that increased time between a pair of inter-connected tasks acts as a buffer, preventing a failure to propagate from one task to another. We show that, in a majority of cases that we explored, temporal properties of the activities (i.e., start and end date of each task in the project) are more relevant than their structural properties (i.e., out-degree and the size of the out-component of the task) to preventing large-scale cascading failures. Our results suggest potential importance of changing timings of tasks, apart from the static structure of the same network of tasks, for containing project failure., Comment: 6 figures; Supplementary Information with 2 figures is included after the main text

Correlation matrices are a major type of multivariate data. To examine properties of a given correlation matrix, a common practice is to compare the same quantity between the original correlation matrix and reference correlation matrices, such as those derived from random matrix theory, that partially preserve properties of the original matrix. We propose a model to generate such reference correlation and covariance matrices for the given matrix. Correlation matrices are often analysed as networks, which are heterogeneous across nodes in terms of the total connectivity to other nodes for each node. Given this background, the present algorithm generates random networks that preserve the expectation of total connectivity of each node to other nodes, akin to configuration models for conventional networks. Our algorithm is derived from the maximum entropy principle. We will apply the proposed algorithm to measurement of clustering coefficients and community detection, both of which require a null model to assess the statistical significance of the obtained results., Comment: 8 figures, 4 tables

Many time-evolving systems in nature, society and technology leave traces of the interactions within them. These interactions form temporal networks that reflect the states of the systems. In this work, we pursue a coarse-grained description of these systems by proposing a method to assign discrete states to the systems and inferring the sequence of such states from the data. Such states could, for example, correspond to a mental state (as inferred from neuroimaging data) or the operational state of an organization (as inferred by interpersonal communication). Our method combines a graph distance measure and hierarchical clustering. Using several empirical data sets of social temporal networks, we show that our method is capable of inferring the system's states such as distinct activities in a school and a weekday state as opposed to a weekend state. We expect the methods to be equally useful in other settings such as temporally varying protein interactions, ecological interspecific interactions, functional connectivity in the brain and adaptive social networks., Comment: 7 figures and 1 table

In this paper, we study the dynamics of epidemic processes taking place in temporal and adaptive networks. Building on the activity-driven network model, we propose an adaptive model of epidemic processes, where the network topology dynamically changes due to both exogenous factors independent of the epidemic dynamics as well as endogenous preventive measures adopted by individuals in response to the state of the infection. A direct analysis of the model using Markov processes involves the spectral analysis of a transition probability matrix whose size grows exponentially with the number of nodes. To overcome this limitation, we derive an upper-bound on the decay rate of the number of infected nodes in terms of the eigenvalues of a $2 \times 2$ matrix. Using this upper bound, we propose an efficient algorithm to tune the parameters describing the endogenous preventive measures in order to contain epidemics over time. We confirm our theoretical results via numerical simulations.

In this paper, we investigate asymptotic properties of a consensus protocol taking place in a class of temporal (i.e., time-varying) networks called the activity driven network. We first show that a standard methodology provides us with an estimate of the convergence rate toward the consensus, in terms of the eigenvalues of a matrix whose computational cost grows exponentially fast in the number of nodes in the network. To overcome this difficulty, we then derive alternative bounds involving the eigenvalues of a matrix that is easy to compute. Our analysis covers the regimes of 1) sparse networks and 2) fast-switching networks. We numerically confirm our theoretical results by numerical simulations.

Infectious diseases have been modelled on networks that summarise physical contacts or close proximity of individuals. These networks are known to be complex in both their structure and how they change over time. We present an overview of recent progress in numerically determining the epidemic threshold in temporally-switching networks, and illustrate that slower switching of snapshots relative to epidemic dynamics lowers the epidemic threshold. Therefore, ignoring the temporally-varying nature of networks may underestimate endemicity. We also identify a predictor for the magnitude of this shift which is based on the commutator norm of snapshot adjacency matrices.

Temporal networks have been increasingly used to model a diversity of systems that evolve in time; for example human contact structures over which dynamic processes such as epidemics take place. A fundamental aspect of real-life networks is that they are sampled within temporal and spatial frames. Furthermore, one might wish to subsample networks to reduce their size for better visualization or to perform computationally intensive simulations. The sampling method may affect the network structure and thus caution is necessary to generalize results based on samples. In this paper, we study four sampling strategies applied to a variety of real-life temporal networks. We quantify the biases generated by each sampling strategy on a number of relevant statistics such as link activity, temporal paths and epidemic spread. We find that some biases are common in a variety of networks and statistics, but one strategy, uniform sampling of nodes, shows improved performance in most scenarios. Our results help researchers to better design network data collection protocols and to understand the limitations of sampled temporal network data., Comment: 10 pages, 8 figures, comments welcome

Evolutionary game theory predicts that cooperation in social dilemma games is promoted when agents are connected as a network. However, when networks are fixed over time, humans do not necessarily show enhanced mutual cooperation. Here we show that reinforcement learning (specifically, the so-called Bush-Mosteller model) approximately explains the experimentally observed network reciprocity and the lack thereof in a parameter region spanned by the benefit-to-cost ratio and the node's degree. Thus, we significantly extend previously obtained numerical results., Comment: 13 pages, 3 figures

With a core-periphery structure of networks, core nodes are densely interconnected, peripheral nodes are connected to core nodes to different extents, and peripheral nodes are sparsely interconnected. Core-periphery structure composed of a single core and periphery has been identified for various networks. However, analogous to the observation that many empirical networks are composed of densely interconnected groups of nodes, i.e., communities, a network may be better regarded as a collection of multiple cores and peripheries. We propose a scalable algorithm to detect multiple non-overlapping groups of core-periphery structure in a network. We illustrate our algorithm using synthesised and empirical networks. For example, we find distinct core-periphery pairs with different political leanings in a network of political blogs and separation between international and domestic subnetworks of airports in some single countries in a world-wide airport network., Comment: 11 figures and 9 tables. MATLAB codes are available at www.naokimasuda.net/cp_codes.zip

Social contact networks underlying epidemic processes in humans and animals are highly dynamic. The spreading of infections on such temporal networks can differ dramatically from spreading on static networks. We theoretically investigate the effects of concurrency, the number of neighbors that a node has at a given time point, on the epidemic threshold in the stochastic susceptible-infected-susceptible dynamics on temporal network models. We show that network dynamics can suppress epidemics (i.e., yield a higher epidemic threshold) when the nodes' concurrency is low, but can also enhance epidemics when the concurrency is high. We analytically determine different phases of this concurrency-induced transition, and confirm our results with numerical simulations., Comment: 12 pages, 10 figures

Many empirical networks have community structure, in which nodes are densely interconnected within each community (i.e., a group of nodes) and sparsely across different communities. Like other local and meso-scale structure of networks, communities are generally heterogeneous in various aspects such as the size, density of edges, connectivity to other communities and significance. In the present study, we propose a method to statistically test the significance of individual communities in a given network. Compared to the previous methods, the present algorithm is unique in that it accepts different community-detection algorithms and the corresponding quality function for single communities. The present method requires that a quality of each community can be quantified and that community detection is performed as optimisation of such a quality function summed over the communities. Various community detection algorithms including modularity maximisation and graph partitioning meet this criterion. Our method estimates a distribution of the quality function for randomised networks to calculate a likelihood of each community in the given network. We illustrate our algorithm by synthetic and empirical networks., Comment: 20 pages, 4 figures and 4 tables

A network with core-periphery structure consists of core nodes that are densely interconnected. In contrast to community structure, which is a different meso-scale structure of networks, core nodes can be connected to peripheral nodes and peripheral nodes are not densely interconnected. Although core-periphery structure sounds reasonable, we argue that it is merely accounted for by heterogeneous degree distributions, if one partitions a network into a single core block and a single periphery block, which the famous Borgatti-Everett algorithm and many succeeding algorithms assume. In other words, there is a strong tendency that high-degree and low-degree nodes are judged to be core and peripheral nodes, respectively. To discuss core-periphery structure beyond the expectation of the node's degree (as described by the configuration model), we propose that one needs to assume at least one block of nodes apart from the focal core-periphery structure, such as a different core-periphery pair, community or nodes not belonging to any meso-scale structure. We propose a scalable algorithm to detect pairs of core and periphery in networks, controlling for the effect of the node's degree. We illustrate our algorithm using various empirical networks., Comment: 56 pages, 25 figures and 4 tables. C++ and MATLAB codes are available at https://github.com/skojaku/km_config

Respondent-driven sampling (RDS) is often used to estimate population properties (e.g., sexual risk behavior) in hard-to-reach populations. In RDS, already sampled individuals recruit population members to the sample from their social contacts in an efficient snowball-like sampling procedure. By assuming a Markov model for the recruitment of individuals, asymptotically unbiased estimates of population characteristics can be obtained. Current RDS estimation methodology assumes that the social network is undirected, that is, all edges are reciprocal. However, empirical social networks in general also include a substantial number of nonreciprocal edges. In this article, we develop an estimation method for RDS in populations connected by social networks that include reciprocal and nonreciprocal edges. We derive estimators of the selection probabilities of individuals as a function of the number of outgoing edges of sampled individuals. The proposed estimators are evaluated on artificial and empirical networks and are shown to generally perform better than existing estimators. This is the case in particular when the fraction of directed edges in the network is large.

Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models., Comment: 12 figures, 2 tables; [v3] reflects the corrections we made in the two corrigenda (Physics Reports, 745, 96 (2018) and ibid., 851, 37-39 (2020))

A practical approach to protecting networks against epidemic processes such as spreading of infectious diseases, malware, and harmful viral information is to remove some influential nodes beforehand to fragment the network into small components. Because determining the optimal order to remove nodes is a computationally hard problem, various approximate algorithms have been proposed to efficiently fragment networks by sequential node removal. Morone and Makse proposed an algorithm employing the non-backtracking matrix of given networks, which outperforms various existing algorithms. In fact, many empirical networks have community structure, compromising the assumption of local tree-like structure on which the original algorithm is based. We develop an immunization algorithm by synergistically combining the Morone-Makse algorithm and coarse graining of the network in which we regard a community as a supernode. In this way, we aim to identify nodes that connect different communities at a reasonable computational cost. The proposed algorithm works more efficiently than the Morone-Makse and other algorithms on networks with community structure., Comment: 5 figures, 3 tables, and SI included

Data of physical contacts and face-to-face communications suggest temporally varying networks as the media on which infections take place among humans and animals. Epidemic processes on temporal networks are complicated by complexity of both network structure and temporal dimensions. Theoretical approaches are much needed for identifying key factors that affect dynamics of epidemics. In particular, what factors make some temporal networks stronger media of infection than other temporal networks is under debate. We develop a theory to understand the susceptible-infected-susceptible epidemic model on arbitrary temporal networks, where each contact is used for a finite duration. We show that temporality of networks lessens the epidemic threshold such that infections persist more easily in temporal networks than in their static counterparts. We further show that the Lie commutator bracket of the adjacency matrices at different times is a key determinant of the epidemic threshold in temporal networks. The effect of temporality on the epidemic threshold, which depends on a data set, is approximately predicted by the magnitude of a commutator norm.

The basic reproduction number R-0-the number of individuals directly infected by an infectious person in an otherwise susceptible population-is arguably the most widely used estimator of how severe an epidemic outbreak can be. This severity can be more directly measured as the fraction of people infected once the outbreak is over, Omega. In traditional mathematical epidemiology and common formulations of static network epidemiology, there is a deterministic relationship between R-0 and Omega. However, if one considers disease spreading on a temporal contact network-where one knows when contacts happen, not only between whom-then larger R-0 does not necessarily imply larger Omega. In this paper, we numerically investigate the relationship between R-0 and Omega for a set of empirical temporal networks of human contacts. Among 31 explanatory descriptors of temporal network structure, we identify those that make R-0 an imperfect predictor of Omega. We find that descriptors related to both temporal and topological aspects affect the relationship between R-0 and Omega, but in different ways.

The conditions for synchronization (equivalently, consensus) in linear and nonlinear switching dynamical systems have been extensively studied. In a previous study, we examined the speed of convergence of linear dynamical systems on switching networks in which each snapshot network defining interaction between dynamical elements is a network Laplacian. We showed that temporal dynamics (i.e., switching) of networks slowed down synchronization processes as compared to the case of aggregate dynamics, i.e., synchronization dynamics occurring on the corresponding static network obtained by the aggregation of the temporal network over time. Here we theoretically extend the results in two ways. First, we derive the conditions imposed on the interaction matrices under which the analytical slowing-down results hold true. The condition turns out to be essentially the same as that for the optimal network, which is known as the condition for the fastest local convergence of nonlinear dynamics on networks. Second, we examine the effect of correlation between different snapshots; in actual temporal networks, the same contact tends to be used consecutively in time. We argue that such temporal correlation further slows down temporal dynamics.

Social dynamics on a network may be accelerated or decelerated depending on which pairs of individuals in the network communicate early and which pairs do later. The order with which the links in a given network are sequentially used, which we call the link order, may be a strong determinant of dynamical behaviour on networks, potentially adding a new dimension to effects of temporal networks relative to static networks. Here we study the effect of the link order on linear coordination (i.e., synchronisation) dynamics. We show that the coordination speed considerably depends on specific orders of links. In addition, applying each single link for a long time to ensure strong pairwise coordination before moving to a next pair of individuals does not often enhance coordination of the entire network. We also implement a simple greedy algorithm to optimise the link order in favour of fast coordination., Comment: 5 figures

© 2015 Eguíluz et al. Here we focus on the description of the mechanisms behind the process of information aggregation and decision making, a basic step to understand emergent phenomena in society, such as trends, information spreading or the wisdom of crowds. In many situations, agents choose between discrete options.We analyze experimental data on binary opinion choices in humans. The data consists of two separate experiments in which humans answer questions with a binary response, where one is correct and the other is incorrect. The questions are answered without and with information on the answers of some previous participants. We find that a Bayesian approach captures the probability of choosing one of the answers. The influence of peers is uncorrelated with the difficulty of the question. The data is inconsistent with Weber's law, which states that the probability of choosing an option depends on the proportion of previous answers choosing that option and not on the total number of those answers. Last, the present Bayesian model fits reasonably well to the data as compared to some other previously proposed functions although the latter sometime perform slightly better than the Bayesian model. The asset of the present model is the simplicity and mechanistic explanation of the behavior.

Some temporal networks, most notably citation networks, are naturally represented as directed acyclic graphs (DAGs). To detect communities in DAGs, we propose a modularity for DAGs by defining an appropriate null model (i.e., randomized network) respecting the order of nodes. We implement a spectral method to approximately maximize the proposed modularity measure and test the method on citation networks and other DAGs. We find that the attained values of the modularity for DAGs are similar for partitions that we obtain by maximizing the proposed modularity (designed for DAGs), the modularity for undirected networks and that for general directed networks. In other words, if we neglect the order imposed on nodes (and the direction of links) in a given DAG and maximize the conventional modularity measure, the obtained partition is close to the optimal one in the sense of the modularity for DAGs., Comment: 2 figures, 7 tables

In many instances of election, the electorate appears to be a composite of partisan and independent voters. Given that partisans are not likely to convert to a different party, a main goal for a party could be to mobilize independent voters toward the party with the help of strong leadership, mass media, partisans, and effects of peer-to-peer influence. Based on the exact solution of the classical voter model dynamics in the presence of perfectly partisan voters (i.e., zealots), we propose a computational method to maximize the share of the party in a social network of independent voters by pinning control strategy. The party, corresponding to the controller or zealots, optimizes the nodes to be controlled given the information about the connectivity of independent voters and the set of nodes that the opponent party controls. We show that controlling hubs is generally a good strategy, whereas the optimized strategy is even better. The superiority of the optimized strategy is particularly eminent when the independent voters are connected as directed rather than undirected networks., Comment: 7 figures, 1 table

Nodes can be ranked according to their relative importance within the network. Ranking algorithms based on random walks are particularly useful because they connect topological and diffusive properties of the network. Previous methods based on random walks, as for example the PageRank, have focused on static structures. However, several realistic networks are indeed dynamic, meaning that their structure changes in time. In this paper, we propose a centrality measure for temporal networks based on random walks which we call TempoRank. While in a static network, the stationary density of the random walk is proportional to the degree or the strength of a node, we find that in temporal networks, the stationary density is proportional to the in-strength of the so-called effective network. The stationary density also depends on the sojourn probability q which regulates the tendency of the walker to stay in the node. We apply our method to human interaction networks and show that although it is important for a node to be connected to another node with many random walkers at the right moment (one of the principles of the PageRank), this effect is negligible in practice when the time order of link activation is included., Comment: main text + supplementary material