Source author record

Naoki Masuda

Naoki Masuda appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

physics.soc-ph Social and Information Networks Populations and Evolution cond-mat.dis-nn cond-mat.stat-mech nlin.AO Computer Science and Game Theory Neurons and Cognition Biological Physics physics.data-an Applications Cell Behavior math.OC math.PR Methodology nlin.CD physics.gen-ph stat.OT

Catalog footprint

What is connected

72works

18topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Non-dilemmatic social dynamics promote cooperation in multilayer networks

Various theoretical and empirical studies have accounted for why humans cooperate in competitive environments. Although prior work has revealed that network structure and multiplex interactions can promote cooperation, most theory assumes that individuals play similar dilemma games in all social contexts. However, real-world agents may participate in a diversity of interactions, not all of which present dilemmas. We develop an evolutionary game model on multilayer networks in which one layer supports the prisoner's dilemma game, while the other follows constant-selection dynamics, representing biased but non-dilemmatic competition, akin to opinion or fad spreading. Our theoretical analysis reveals that coupling a social dilemma layer to a non-dilemmatic constant-selection layer robustly enhances cooperation in many cases, across different multilayer networks, updating rules, and payoff schemes. These findings suggest that embedding individuals within diverse networked settings -- even those unrelated to direct social dilemmas -- can be a principled approach to engineering cooperation in socio-ecological and organizational systems.

preprint2022arXiv

Accuracy of a one-dimensional reduction of dynamical systems on networks

Resilience is an ability of a system with which the system can adjust its activity to maintain its functionality when it is perturbed. To study resilience of dynamics on networks, Gao et al. proposed a theoretical framework to reduce dynamical systems on networks, which are high dimensional in general, to one-dimensional dynamical systems. The accuracy of this one-dimensional reduction relies on several assumption in addition to the assumption that the network has a negligible degree correlation. In the present study, we analyze the accuracy of the one-dimensional reduction assuming networks without degree correlation. We do so mainly through examining the validity of the individual assumptions underlying the method. Across five dynamical system models, we find that the accuracy of the one-dimensional reduction hinges on the spread of the equilibrium value of the state variable across the nodes in most cases. Specifically, the one-dimensional reduction tends to be accurate when the dispersion of the node's state is small. We also find that the correlation between the node's state and the node's degree, which is common for various dynamical systems on networks, is unrelated to the accuracy of the one-dimensional reduction.

preprint2022arXiv

Dimension reduction of dynamical systems on networks with leading and non-leading eigenvectors of adjacency matrices

Dimension reduction techniques for dynamical systems on networks are considered to promote our understanding of the original high-dimensional dynamics. One strategy of dimension reduction is to derive a low-dimensional dynamical system whose behavior approximates the observables of the original dynamical system that are weighted linear summations of the state variables at the different nodes. Recently proposed methods use the leading eigenvector of the adjacency matrix of the network as the mixture weights to obtain such observables. In the present study, we explore performances of this type of one-dimensional reductions of dynamical systems on networks when we use non-leading eigenvectors of the adjacency matrix as the mixture weights. Our theory predicts that non-leading eigenvectors can be more efficient than the leading eigenvector and enables us to select the eigenvector minimizing the error. We numerically verify that the optimal non-leading eigenvector outperforms the leading eigenvector for some dynamical systems and networks. We also argue that, despite our theory, it is practically better to use the leading eigenvector as the mixture weights to avoid misplacing the bifurcation point too distantly and to be resistant against dynamical noise.

preprint2022arXiv

Metapopulation models imply non-Poissonian statistics of interevent times

Interevent times in temporal contact data from humans and animals typically obey heavy-tailed distributions, and this property impacts contagion and other dynamical processes on networks. We theoretically show that distributions of interevent times heavier-tailed than exponential distributions are a consequence of the most basic metapopulation model used in epidemiology and ecology, in which individuals move from a patch to another according to the simple random walk. Our results hold true irrespectively of the network structure and also for more realistic mobility rules such as high-order random walks and the recurrent mobility patterns used for modeling human dynamics.

preprint2022arXiv

Temporal Motifs in Patent Opposition and Collaboration Networks

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.

preprint2020arXiv

A Gillespie algorithm for non-Markovian stochastic processes

The Gillespie algorithm provides statistically exact methods for simulating stochastic dynamics modelled as interacting sequences of discrete events including systems of biochemical reactions or earthquake occurrences, networks of queuing processes or spiking neurons, and epidemic and opinion formation processes on social networks. Empirically, the inter-event times of various phenomena obey long-tailed distributions. The Gillespie algorithm and its variants either assume Poisson processes (i.e., exponentially distributed inter-event times), use particular functions for time courses of the event rate, or work for non-Poissonian renewal processes, including the case of long-tailed distributions of inter-event times, but at a high computational cost. In the present study, we propose an innovative Gillespie algorithm for renewal processes on the basis of the Laplace transform. The algorithm makes use of the fact that a class of point processes is represented as a mixture of Poisson processes with different event rates. The method is applicable to multivariate renewal processes whose survival function of inter-event times is completely monotone. It is an exact algorithm and works faster than a recently proposed Gillespie algorithm for general renewal processes, which is exact only in the limit of infinitely many processes. We also propose a method to generate sequences of event times with a tunable amount of positive correlation between inter-event times. We demonstrate our algorithm with exact simulations of epidemic processes on networks, finding that a realistic amount of positive correlation in inter-event times only slightly affects the epidemic dynamics.

preprint2020arXiv

Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix

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.

preprint2020arXiv

Critical mass effect in evolutionary games triggered by zealots

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.

preprint2020arXiv

Interplay between $k$-core and community structure in complex networks

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.

preprint2020arXiv

Long-tailed distributions of inter-event times as mixtures of exponential distributions

Inter-event times of various human behavior are apparently non-Poissonian and obey long-tailed distributions as opposed to exponential distributions, which correspond to Poisson processes. It has been suggested that human individuals may switch between different states in each of which they are regarded to generate events obeying a Poisson process. If this is the case, inter-event times should approximately obey a mixture of exponential distributions with different parameter values. In the present study, we introduce the minimum description length principle to compare mixtures of exponential distributions with different numbers of components (i.e., constituent exponential distributions). Because these distributions violate the identifiability property, one is mathematically not allowed to apply the Akaike or Bayes information criteria to their maximum likelihood estimator to carry out model selection. We overcome this theoretical barrier by applying a minimum description principle to joint likelihoods of the data and latent variables. We show that mixtures of exponential distributions with a few components are selected as opposed to more complex mixtures in various data sets and that the fitting accuracy is comparable to that of state-of-the-art algorithms to fit power-law distributions to data. Our results lend support to Poissonian explanations of apparently non-Poissonian human behavior.

preprint2020arXiv

Random walks and diffusion on networks

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.

preprint2020arXiv

Recurrence Quantification Analysis of Dynamic Brain Networks

Evidence suggests that brain network dynamics is a key determinant of brain function and dysfunction. Here we propose a new framework to assess the dynamics of brain networks based on recurrence analysis. Our framework uses recurrence plots and recurrence quantification analysis to characterize dynamic networks. For resting-state magnetoencephalographic dynamic functional networks (dFNs), we have found that functional networks recur more quickly in people with epilepsy than healthy controls. This suggests that recurrence of dFNs may be used as a biomarker of epilepsy. For stereo electroencephalography data, we have found that dFNs involved in epileptic seizures emerge before seizure onset, and recurrence analysis allows us to detect seizures. We further observe distinct dFNs before and after seizures, which may inform neurostimulation strategies to prevent seizures. Our framework can also be used for understanding dFNs in healthy brain function and in other neurological disorders besides epilepsy.

preprint2020arXiv

Small inter-event times govern epidemic spreading on temporal networks

Just like the degrees of human and animal interaction networks, the distribution of the times between interactions is known to often be right-skewed and fat-tailed. Both these distributions affect epidemic dynamics strongly, but, as we show in this Letter, for very different reasons. Whereas the high degrees of the tail are critical for facilitating epidemics, it is the small interevent times that control the dynamics of epidemics. We investigate this effect both analytically and numerically for different versions of the Susceptible-Infected-Recovered model on different types of networks.

preprint2020arXiv

Waiting-time paradox in 1922

We present an English translation and discussion of an essay that a Japanese physicist, Torahiko Terada, wrote in 1922. In the essay, he described the waiting-time paradox, also called the bus paradox, which is a known mathematical phenomenon in queuing theory, stochastic processes, and modern temporal network analysis. He also observed and analyzed data on Tokyo City trams to verify the relevance of the waiting-time paradox to busy passengers in Tokyo at the time. This essay seems to be one of the earliest documentations of the waiting-time paradox in a sufficiently scientific manner.

preprint2020arXiv

Winning by hiding behind others: An analysis of speed skating data

In some athletic races, such as cycling and types of speed skating races, athletes have to complete a relatively long distance at a high speed in the presence of direct opponents. To win such a race, athletes are motivated to hide behind others to suppress energy consumption before a final moment of the race. This situation seems to produce a social dilemma: players want to hide behind others, whereas if a group of players attempts to do so, they may all lose to other players that overtake them. To support that speed skaters are involved in such a social dilemma, we analyzed video footage data for 14 mass start skating races to find that skaters that hid behind others to avoid air resistance for a long time before the final lap tended to win. Furthermore, the finish rank of the skaters in mass start races was independent of the record of the same skaters in time-trial races measured in the absence of direct opponents. The results suggest that how to strategically cope with a skater's dilemma may be a key determinant for winning long-distance and high-speed races with direct opponents.

preprint2019arXiv

Constructing networks by filtering correlation matrices: A null model approach

Network analysis has been applied to various correlation matrix data. Thresholding on the value of the pairwise correlation is probably the most straightforward and common method to create a network from a correlation matrix. However, there have been criticisms on this thresholding approach such as an inability to filter out spurious correlations, which have led to proposals of alternative methods to overcome some of the problems. We propose a method to create networks from correlation matrices based on optimisation with regularization, where we lay an edge between each pair of nodes if and only if the edge is unexpected from a null model. The proposed algorithm is advantageous in that it can be combined with different types of null models. Moreover, the algorithm can select the most plausible null model from a set of candidate null models using a model selection criterion. For three economic data sets, we find that the configuration model for correlation matrices is often preferred to standard null models. For country-level product export data, the present method better predicts main products exported from countries than sample correlation matrices do.

preprint2019arXiv

Modeling temporal networks with bursty activity patterns of nodes and links

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.

preprint2016arXiv

Accelerating coordination in temporal networks by engineering the link order

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.

preprint2016arXiv

Evolutionary dynamics in finite populations with zealots

We investigate evolutionary dynamics of two-strategy matrix games with zealots in finite populations. Zealots are assumed to take either strategy regardless of the fitness. When the strategy selected by the zealots is the same, the fixation of the strategy selected by the zealots is a trivial outcome. We study fixation time in this scenario. We show that the fixation time is divided into three main regimes, in one of which the fixation time is short, and in the other two the fixation time is exponentially long in terms of the population size. Different from the case without zealots, there is a threshold selection intensity below which the fixation is fast for an arbitrary payoff matrix. We illustrate our results with examples of various social dilemma games.

preprint2016arXiv

Fragmenting networks by targeting collective influencers at a mesoscopic level

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.

preprint2016arXiv

Temporal interactions facilitate endemicity in the susceptible-infected-susceptible epidemic model

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.

preprint2015arXiv

Community detection in directed acyclic graphs

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.

preprint2015arXiv

Individual-based approach to epidemic processes on arbitrary dynamic contact networks

The dynamics of contact networks and epidemics of infectious diseases often occur on comparable time scales. Ignoring one of these time scales may provide an incomplete understanding of the population dynamics of the infection process. We develop an individual-based approximation for the susceptible-infected-recovered epidemic model applicable to arbitrary dynamic networks. Our framework provides, at the individual-level, the probability flow over time associated with the infection dynamics. This computationally efficient framework discards the correlation between the states of different nodes, yet provides accurate results in approximating direct numerical simulations. It naturally captures the temporal heterogeneities and correlations of contact sequences, fundamental ingredients regulating the timing and size of an epidemic outbreak. Using real-life data, we show that the static network model overestimates the reproduction number but underestimates the infection potential of super-spreading individuals. The high accuracy of our approximation further allows us to detect the index individual of an epidemic outbreak.

preprint2015arXiv

Opinion control in complex networks

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.

preprint2015arXiv

Steady state and mean recurrence time for random walks on stochastic temporal networks

Random walks are basic diffusion processes on networks and have applications in, for example, searching, navigation, ranking, and community detection. Recent recognition of the importance of temporal aspects on networks spurred studies of random walks on temporal networks. Here we theoretically study two types of event-driven random walks on a stochastic temporal network model that produces arbitrary distributions of interevent-times. In the so-called active random walk, the interevent-time is reinitialized on all links upon each movement of the walker. In the so-called passive random walk, the interevent-time is only reinitialized on the link that has been used last time, and it is a type of correlated random walk. We find that the steady state is always the uniform density for the passive random walk. In contrast, for the active random walk, it increases or decreases with the node's degree depending on the distribution of interevent-times. The mean recurrence time of a node is inversely proportional to the degree for both active and passive random walks. Furthermore, the mean recurrence time does or does not depend on the distribution of interevent-times for the active and passive random walks, respectively.

preprint2015arXiv

Win-stay lose-shift strategy in formation changes in football

Managerial decision making is likely to be a dominant determinant of performance of teams in team sports. Here we use Japanese and German football data to investigate correlates between temporal patterns of formation changes across matches and match results. We found that individual teams and managers both showed win-stay lose-shift behavior, a type of reinforcement learning. In other words, they tended to stick to the current formation after a win and switch to a different formation after a loss. In addition, formation changes did not statistically improve the results of succeeding matches.The results indicate that a swift implementation of a new formation in the win-stay lose-shift manner may not be a successful managerial rule of thumb.

preprint2014arXiv

Evolution via imitation among like-minded individuals

In social situations with which evolutionary game is concerned, individuals are considered to be heterogeneous in various aspects. In particular, they may differently perceive the same outcome of the game owing to heterogeneity in idiosyncratic preferences, fighting abilities, and positions in a social network. In such a population, an individual may imitate successful and similar others, where similarity refers to that in the idiosyncratic fitness function. I propose an evolutionary game model with two subpopulations on the basis of multipopulation replicator dynamics to describe such a situation. In the proposed model, pairs of players are involved in a two-person game as a well-mixed population, and imitation occurs within subpopulations in each of which players have the same payoff matrix. It is shown that the model does not allow any internal equilibrium such that the dynamics differs from that of other related models such as the bimatrix game. In particular, even a slight difference in the payoff matrix in the two subpopulations can make the opposite strategies to be stably selected in the two subpopulations in the snowdrift and coordination games.

preprint2014arXiv

Global network structure of dominance hierarchy of ant workers

Dominance hierarchy among animals is widespread in various species and believed to serve to regulate resource allocation within an animal group. Unlike small groups, however, detection and quantification of linear hierarchy in large groups of animals are a difficult task. Here, we analyse aggression-based dominance hierarchies formed by worker ants in Diacamma sp. as large directed networks. We show that the observed dominance networks are perfect or approximate directed acyclic graphs, which are consistent with perfect linear hierarchy. The observed networks are also sparse and random but significantly different from networks generated through thinning of the perfect linear tournament (i.e., all individuals are linearly ranked and dominance relationship exists between every pair of individuals). These results pertain to global structure of the networks, which contrasts with the previous studies inspecting frequencies of different types of triads. In addition, the distribution of the out-degree (i.e., number of workers that the focal worker attacks), not in-degree (i.e., number of workers that attack the focal worker), of each observed network is right-skewed. Those having excessively large out-degrees are located near the top, but not the top, of the hierarchy. We also discuss evolutionary implications of the discovered properties of dominance networks.

preprint2014arXiv

Iterated crowdsourcing dilemma game

The Internet has enabled the emergence of collective problem solving, also known as crowdsourcing, as a viable option for solving complex tasks. However, the openness of crowdsourcing presents a challenge because solutions obtained by it can be sabotaged, stolen, and manipulated at a low cost for the attacker. We extend a previously proposed crowdsourcing dilemma game to an iterated game to address this question. We enumerate pure evolutionarily stable strategies within the class of so-called reactive strategies, i.e., those depending on the last action of the opponent. Among the 4096 possible reactive strategies, we find 16 strategies each of which is stable in some parameter regions. Repeated encounters of the players can improve social welfare when the damage inflicted by an attack and the cost of attack are both small. Under the current framework, repeated interactions do not really ameliorate the crowdsourcing dilemma in a majority of the parameter space.

preprint2014arXiv

Networks maximizing the consensus time of voter models

We explore the networks that yield the largest mean consensus time of voter models under different update rules. By analytical and numerical means, we show that the so-called lollipop graph, barbell graph, and double star graph maximise the mean consensus time under the update rules called the link dynamics, voter model, and invasion process, respectively. For each update rule, the largest mean consensus time scales as O(N^3), where N is the number of nodes in the network.

preprint2014arXiv

Random walk centrality for temporal networks

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.

preprint2014arXiv

The basic reproduction number as a predictor for epidemic outbreaks in temporal networks

The basic reproduction number R0 -- 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 people infected once the outbreak is over, Ω. In traditional mathematical epidemiology and common formulations of static network epidemiology, there is a deterministic relationship between R0 and Ω. However, if one considers disease spreading on a temporal contact network -- where one knows when contacts happen, not only between whom -- then larger R0 does not necessarily imply larger Ω. In this paper, we numerically investigate the relationship between R0 and Ω for a set of empirical temporal networks of human contacts. Among 31 explanatory descriptors of temporal network structure, we identify those that make R0 an imperfect predictor of Ω. We find that descriptors related to both temporal and topological aspects affect the relationship between R0 and Ω, but in different ways.

preprint2014arXiv

Two types of well followed users in the followership networks of Twitter

In the Twitter blogosphere, the number of followers is probably the most basic and succinct quantity for measuring popularity of users. However, the number of followers can be manipulated in various ways; we can even buy follows. Therefore, alternative popularity measures for Twitter users on the basis of, for example, users' tweets and retweets, have been developed. In the present work, we take a purely network approach to this fundamental question. First, we find that two relatively distinct types of users possessing a large number of followers exist, in particular for Japanese, Russian, and Korean users among the seven language groups that we examined. A first type of user follows a small number of other users. A second type of user follows approximately the same number of other users as the number of follows that the user receives. Then, we compare local (i.e., egocentric) followership networks around the two types of users with many followers. We show that the second type, which is presumably uninfluential users despite its large number of followers, is characterized by high link reciprocity, a large number of friends (i.e., those whom a user follows) for the followers, followers' high link reciprocity, large clustering coefficient, large fraction of the second type of users among the followers, and a small PageRank. Our network-based results support that the number of followers used alone is a misleading measure of user's popularity. We propose that the number of friends, which is simple to measure, also helps us to assess the popularity of Twitter users.

preprint2014arXiv

Voter model on the two-clique graph

I examine the mean consensus time (i.e., exit time) of the voter model in the so-called two-clique graph. The two-clique graph is composed of two cliques interconnected by some links and considered as a toy model of networks with community structure or multilayer networks. I analytically show that, as the number of interclique links per node is varied, the mean consensus time experiences a crossover between a fast consensus regime [i.e., O(N)] and a slow consensus regime [i.e., O(N^2)], where N is the number of nodes. The fast regime is consistent with the result for homogeneous well-mixed graphs such as the complete graph. The slow regime appears only when the entire network has O(1) interclique links. The present results suggest that the effect of community structure on the consensus time of the voter model is fairly limited.

preprint2013arXiv

A collective opinion formation model under Bayesian updating and confirmation bias

We propose a collective opinion formation model with a so-called confirmation bias. The confirmation bias is a psychological effect with which, in the context of opinion formation, an individual in favor of an opinion is prone to misperceive new incoming information as supporting the current belief of the individual. Our model modifies a Bayesian decision-making model for single individuals [M. Rabin and J. L. Schrag, Q. J. Econ. 114, 37 (1999)] for the case of a well-mixed population of interacting individuals in the absence of the external input. We numerically simulate the model to show that all the agents eventually agree on one of the two opinions only when the confirmation bias is weak. Otherwise, the stochastic population dynamics ends up creating a disagreement configuration (also called polarization), particularly for large system sizes. A strong confirmation bias allows various final disagreement configurations with different fractions of the individuals in favor of the opposite opinions.

preprint2013arXiv

Application of semidefinite programming to maximize the spectral gap produced by node removal

The smallest positive eigenvalue of the Laplacian of a network is called the spectral gap and characterizes various dynamics on networks. We propose mathematical programming methods to maximize the spectral gap of a given network by removing a fixed number of nodes. We formulate relaxed versions of the original problem using semidefinite programming and apply them to example networks.

preprint2013arXiv

Complex dynamics of a nonlinear voter model with contrarian agents

We investigate mean-field dynamics of a nonlinear opinion formation model with congregator and contrarian agents. Each agent assumes one of the two possible states. Congregators imitate the state of other agents with a rate that increases with the number of other agents in the opposite state, as in the linear voter model and nonlinear majority voting models. Contrarians flip the state with a rate that increases with the number of other agents in the same state. The nonlinearity controls the strength of the majority voting and is used as a main bifurcation parameter. We show that the model undergoes a rich bifurcation scenario comprising the egalitarian equilibrium, two symmetric lopsided equilibria, limit cycle, and coexistence of different types of stable equilibria with intertwining attrative basins.

preprint2013arXiv

Observability transitions in correlated networks

Yang, Wang, and Motter [Phys. Rev. Lett. 109, 258701 (2012)] analyzed a model for network observability transitions in which a sensor placed on a node makes the node and the adjacent nodes observable. The size of the connected components comprising the observable nodes is a major concern of the model. We analyze this model in random heterogeneous networks with degree correlation. With numerical simulations and analytical arguments based on generating functions, we find that negative degree correlation makes networks more observable. This result holds true both when the sensors are placed on nodes one by one in a random order and when hubs preferentially receive the sensors. Finally, we numerically optimize networks with a fixed degree sequence with respect to the size of the largest observable component. Optimized networks have negative degree correlation induced by the resulting hub-repulsive structure; the largest hubs are rarely connected to each other, in contrast to the rich-club phenomenon of networks.

preprint2013arXiv

Random Walks on Directed Networks: Inference and Respondent-driven Sampling

Respondent driven sampling (RDS) is a method often used to estimate population properties (e.g. sexual risk behavior) in hard-to-reach populations. It combines an effective modified snowball sampling methodology with an estimation procedure that yields unbiased population estimates under the assumption that the sampling process behaves like a random walk on the social network of the population. Current RDS estimation methodology assumes that the social network is undirected, i.e. that all edges are reciprocal. However, empirical social networks in general also have non-reciprocated edges. To account for this fact, we develop a new estimation method for RDS in the presence of directed edges on the basis of random walks on directed networks. We distinguish directed and undirected edges and consider the possibility that the random walk returns to its current position in two steps through an undirected edge. We derive estimators of the selection probabilities of individuals as a function of the number of outgoing edges of sampled individuals. We evaluate the performance of the proposed estimators on artificial and empirical networks to show that they generally perform better than existing methods. This is in particular the case when the fraction of directed edges in the network is large.

preprint2013arXiv

Self-exciting point process modeling of conversation event sequences

Self-exciting processes of Hawkes type have been used to model various phenomena including earthquakes, neural activities, and views of online videos. Studies of temporal networks have revealed that sequences of social interevent times for individuals are highly bursty. We examine some basic properties of event sequences generated by the Hawkes self-exciting process to show that it generates bursty interevent times for a wide parameter range. Then, we fit the model to the data of conversation sequences recorded in company offices in Japan. In this way, we can estimate relative magnitudes of the self excitement, its temporal decay, and the base event rate independent of the self excitation. These variables highly depend on individuals. We also point out that the Hawkes model has an important limitation that the correlation in the interevent times and the burstiness cannot be independently modulated.

preprint2013arXiv

State Concentration Exponent as a Measure of Quickness in Kauffman-type Networks

We study the dynamics of randomly connected networks composed of binary Boolean elements and those composed of binary majority vote elements. We elucidate their differences in both sparsely and densely connected cases. The quickness of large network dynamics is usually quantified by the length of transient paths, an analytically intractable measure. For discrete-time dynamics of networks of binary elements, we address this dilemma with an alternative unified framework by using a concept termed state concentration, defined as the exponent of the average number of t-step ancestors in state transition graphs. The state transition graph is defined by nodes corresponding to network states and directed links corresponding to transitions. Using this exponent, we interrogate the dynamics of random Boolean and majority vote networks. We find that extremely sparse Boolean networks and majority vote networks with arbitrary density achieve quickness, owing in part to long-tailed in-degree distributions. As a corollary, only relatively dense majority vote networks can achieve both quickness and robustness.

preprint2013arXiv

Suicide ideation of individuals in online social networks

Suicide explains the largest number of death tolls among Japanese adolescents in their twenties and thirties. Suicide is also a major cause of death for adolescents in many other countries. Although social isolation has been implicated to influence the tendency to suicidal behavior, the impact of social isolation on suicide in the context of explicit social networks of individuals is scarcely explored. To address this question, we examined a large data set obtained from a social networking service dominant in Japan. The social network is composed of a set of friendship ties between pairs of users created by mutual endorsement. We carried out the logistic regression to identify users' characteristics, both related and unrelated to social networks, which contribute to suicide ideation. We defined suicide ideation of a user as the membership to at least one active user-defined community related to suicide. We found that the number of communities to which a user belongs to, the intransitivity (i.e., paucity of triangles including the user), and the fraction of suicidal neighbors in the social network, contributed the most to suicide ideation in this order. Other characteristics including the age and gender contributed little to suicide ideation. We also found qualitatively the same results for depressive symptoms.

preprint2013arXiv

Temporal networks: slowing down diffusion by long lasting interactions

Interactions among units in complex systems occur in a specific sequential order thus affecting the flow of information, the propagation of diseases, and general dynamical processes. We investigate the Laplacian spectrum of temporal networks and compare it with that of the corresponding aggregate network. First, we show that the spectrum of the ensemble average of a temporal network has identical eigenmodes but smaller eigenvalues than the aggregate networks. In large networks without edge condensation, the expected temporal dynamics is a time-rescaled version of the aggregate dynamics. Even for single sequential realizations, diffusive dynamics is slower in temporal networks. These discrepancies are due to the noncommutability of interactions. We illustrate our analytical findings using a simple temporal motif, larger network models and real temporal networks.

preprint2013arXiv

Voter models with contrarian agents

In the voter and many other opinion formation models, agents are assumed to behave as congregators (also called the conformists); they are attracted to the opinions of others. In this study, I investigate linear extensions of the voter model with contrarian agents. An agent is either congregator or contrarian and assumes a binary opinion. I investigate three models that differ in the behavior of the contrarian toward other agents. In model 1, contrarians mimic the opinions of other contrarians and oppose (i.e., try to select the opinion opposite to) those of congregators. In model 2, contrarians mimic the opinions of congregators and oppose those of other contrarians. In model 3, contrarians oppose anybody. In all models, congregators are assumed to like anybody. I show that even a small number of contrarians prohibits the consensus in the entire population to be reached in all three models. I also obtain the equilibrium distributions using the van Kampen small-fluctuation approximation and the Fokker-Planck equation for the case of many contrarians and a single contrarian, respectively. I show that the fluctuation around the symmetric coexistence equilibrium is much larger in model 2 than in models 1 and 3 when contrarians are rare.

preprint2012arXiv

A network-based dynamical ranking system for competitive sports

From the viewpoint of networks, a ranking system for players or teams in sports is equivalent to a centrality measure for sports networks, whereby a directed link represents the result of a single game. Previously proposed network-based ranking systems are derived from static networks, i.e., aggregation of the results of games over time. However, the score of a player (or team) fluctuates over time. Defeating a renowned player in the peak performance is intuitively more rewarding than defeating the same player in other periods. To account for this factor, we propose a dynamic variant of such a network-based ranking system and apply it to professional men's tennis data. We derive a set of linear online update equations for the score of each player. The proposed ranking system predicts the outcome of the future games with a higher accuracy than the static counterparts.

preprint2012arXiv

Bursty communication patterns facilitate spreading in a threshold-based epidemic dynamics

Records of social interactions provide us with new sources of data for understanding how interaction patterns affect collective dynamics. Such human activity patterns are often bursty, i.e., they consist of short periods of intense activity followed by long periods of silence. This burstiness has been shown to affect spreading phenomena; it accelerates epidemic spreading in some cases and slows it down in other cases. We investigate a model of history-dependent contagion. In our model, repeated interactions between susceptible and infected individuals in a short period of time is needed for a susceptible individual to contract infection. We carry out numerical simulations on real temporal network data to find that bursty activity patterns facilitate epidemic spreading in our model.

preprint2012arXiv

Coevolution of trustful buyers and cooperative sellers in the trust game

Many online marketplaces enjoy great success. Buyers and sellers in successful markets carry out cooperative transactions even if they do not know each other in advance and a moral hazard exists. An indispensable component that enables cooperation in such social dilemma situations is the reputation system. Under the reputation system, a buyer can avoid transacting with a seller with a bad reputation. A transaction in online marketplaces is better modeled by the trust game than other social dilemma games, including the donation game and the prisoner's dilemma. In addition, most individuals participate mostly as buyers or sellers; each individual does not play the two roles with equal probability. Although the reputation mechanism is known to be able to remove the moral hazard in games with asymmetric roles, competition between different strategies and population dynamics of such a game are not sufficiently understood. On the other hand, existing models of reputation-based cooperation, also known as indirect reciprocity, are based on the symmetric donation game. We analyze the trust game with two fixed roles, where trustees (i.e., sellers) but not investors (i.e., buyers) possess reputation scores. We study the equilibria and the replicator dynamics of the game. We show that the reputation mechanism enables cooperation between unacquainted buyers and sellers under fairly generous conditions, even when such a cooperative equilibrium coexists with an asocial equilibrium in which buyers do not buy and sellers cheat. In addition, we show that not many buyers may care about the seller's reputation under cooperative equilibrium. Buyers' trusting behavior and sellers' reputation-driven cooperative behavior coevolve to alleviate the social dilemma.

preprint2012arXiv

Evolution of cooperation driven by zealots

Recent experimental results with humans involved in social dilemma games suggest that cooperation may be a contagious phenomenon and that the selection pressure operating on evolutionary dynamics (i.e., mimicry) is relatively weak. I propose an evolutionary dynamics model that links these experimental findings and evolution of cooperation. By assuming a small fraction of (imperfect) zealous cooperators, I show that a large fraction of cooperation emerges in evolutionary dynamics of social dilemma games. Even if defection is more lucrative than cooperation for most individuals, they often mimic cooperation of fellows unless the selection pressure is very strong. Then, zealous cooperators can transform the population to be even fully cooperative under standard evolutionary dynamics.

preprint2012arXiv

Formation of feedforward networks and frequency synchrony by spike-timing-dependent plasticity

Spike-timing-dependent plasticity (STDP) with asymmetric learning windows is commonly found in the brain and useful for a variety of spike-based computations such as input filtering and associative memory. A natural consequence of STDP is establishment of causality in the sense that a neuron learns to fire with a lag after specific presynaptic neurons have fired. The effect of STDP on synchrony is elusive because spike synchrony implies unitary spike events of different neurons rather than a causal delayed relationship between neurons. We explore how synchrony can be facilitated by STDP in oscillator networks with a pacemaker. We show that STDP with asymmetric learning windows leads to self-organization of feedforward networks starting from the pacemaker. As a result, STDP drastically facilitates frequency synchrony. Even though differences in spike times are lessened as a result of synaptic plasticity, the finite time lag remains so that perfect spike synchrony is not realized. In contrast to traditional mechanisms of large-scale synchrony based on mutual interaction of coupled neurons, the route to synchrony discovered here is enslavement of downstream neurons by upstream ones. Facilitation of such feedforward synchrony does not occur for STDP with symmetric learning windows.

preprint2012arXiv

Groupwise information sharing promotes ingroup favoritism in indirect reciprocity

Indirect reciprocity is a mechanism for cooperation in social dilemma situations, in which an individual is motivated to help another to acquire a good reputation and receive help from others afterwards. Ingroup favoritism is another aspect of human cooperation, whereby individuals help members in their own group more often than those in other groups. Ingroup favoritism is a puzzle for the theory of cooperation because it is not easily evolutionarily stable. In the context of indirect reciprocity, ingroup favoritism has been shown to be a consequence of employing a double standard when assigning reputations to ingroup and outgroup members; e.g., helping an ingroup member is regarded as good, whereas the same action toward an outgroup member is regarded as bad. We analyze a model of indirect reciprocity in which information sharing is conducted groupwise. In our model, individuals play social dilemma games within and across groups, and the information about their reputations is shared within each group. We show that evolutionarily stable ingroup favoritism emerges even if all the players use the same reputation assignment rule regardless of group (i.e., a single standard). Two reputation assignment rules called simple standing and stern judging yield ingroup favoritism. Stern judging induces much stronger ingroup favoritism than does simple standing. Simple standing and stern judging are evolutionarily stable against each other when groups employing different assignment rules compete and the number of groups is sufficiently large. In addition, we analytically show as a limiting case that homogeneous populations of reciprocators that use reputations are unstable when individuals independently infer reputations of individuals, which is consistent with previously reported numerical results.

preprint2012arXiv

Importance of individual events in temporal networks

Records of time-stamped social interactions between pairs of individuals (e.g., face-to-face conversations, e-mail exchanges, and phone calls) constitute a so-called temporal network. A remarkable difference between temporal networks and conventional static networks is that time-stamped events rather than links are the unit elements generating the collective behavior of nodes. We propose an importance measure for single interaction events. By generalizing the concept of the advance of event proposed by [Kossinets G, Kleinberg J, and Watts D J (2008) Proceeding of the 14th ACM SIGKDD International conference on knowledge discovery and data mining, p 435], we propose that an event is central when it carries new information about others to the two nodes involved in the event. We find that the proposed measure properly quantifies the importance of events in connecting nodes along time-ordered paths. Because of strong heterogeneity in the importance of events present in real data, a small fraction of highly important events is necessary and sufficient to sustain the connectivity of temporal networks. Nevertheless, in contrast to the behavior of scale-free networks against link removal, this property mainly results from bursty activity patterns and not heterogeneous degree distributions.

preprint2012arXiv

Indirect reciprocity with trinary reputations

Indirect reciprocity is a reputation-based mechanism for cooperation in social dilemma situations when individuals do not repeatedly meet. The conditions under which cooperation based on indirect reciprocity occurs have been examined in great details. Most previous theoretical analysis assumed for mathematical tractability that an individual possesses a binary reputation value, i.e., good or bad, which depends on their past actions and other factors. However, in real situations, reputations of individuals may be multiple valued. Another puzzling discrepancy between the theory and experiments is the status of the so-called image scoring, in which cooperation and defection are judged to be good and bad, respectively, independent of other factors. Such an assessment rule is found in behavioral experiments, whereas it is known to be unstable in theory. In the present study, we fill both gaps by analyzing a trinary reputation model. By an exhaustive search, we identify all the cooperative and stable equilibria composed of a homogeneous population or a heterogeneous population containing two types of players. Some results derived for the trinary reputation model are direct extensions of those for the binary model. However, we find that the trinary model allows cooperation under image scoring under some mild conditions.

preprint2012arXiv

Ingroup favoritism and intergroup cooperation under indirect reciprocity based on group reputation

Indirect reciprocity in which players cooperate with unacquainted other players having good reputations is a mechanism for cooperation in relatively large populations subjected to social dilemma situations. When the population has group structure, as is often found in social networks, players in experiments are considered to show behavior that deviates from existing theoretical models of indirect reciprocity. First, players often show ingroup favoritism (i.e., cooperation only within the group) rather than full cooperation (i.e., cooperation within and across groups), even though the latter is Pareto efficient. Second, in general, humans approximate outgroup members' personal characteristics, presumably including the reputation used for indirect reciprocity, by a single value attached to the group. Humans use such a stereotypic approximation, a phenomenon known as outgroup homogeneity in social psychology. I propose a model of indirect reciprocity in populations with group structure to examine the possibility of ingroup favoritism and full cooperation. In accordance with outgroup homogeneity, I assume that players approximate outgroup members' personal reputations by a single reputation value attached to the group. I show that ingroup favoritism and full cooperation are stable under different social norms (i.e., rules for assigning reputations) such that they do not coexist in a single model. If players are forced to consistently use the same social norm for assessing different types of interactions (i.e., ingroup versus outgroup interactions), only full cooperation survives. The discovered mechanism is distinct from any form of group selection. The results also suggest potential methods for reducing ingroup bias to shift the equilibrium from ingroup favoritism to full cooperation.

preprint2011arXiv

Can Partisan Voting Lead to Truth?

We study an extension of the voter model in which each agent is endowed with an innate preference for one of two states that we term as "truth" or "falsehood". Due to interactions with neighbors, an agent that innately prefers truth can be persuaded to adopt a false opinion (and thus be discordant with its innate preference) or the agent can possess an internally concordant "true" opinion. Parallel states exist for agents that inherently prefer falsehood. We determine the conditions under which a population of such agents can ultimately reach a consensus for the truth, a consensus for falsehood, or reach an impasse where an agent tends to adopt the opinion that is in internal concordance with its innate preference so that consensus is never achieved.

preprint2011arXiv

Clustering in large networks does not promote upstream reciprocity

Upstream reciprocity (also called generalized reciprocity) is a putative mechanism for cooperation in social dilemma situations with which players help others when they are helped by somebody else. It is a type of indirect reciprocity. Although upstream reciprocity is often observed in experiments, most theories suggest that it is operative only when players form short cycles such as triangles, implying a small population size, or when it is combined with other mechanisms that promote cooperation on their own. An expectation is that real social networks, which are known to be full of triangles and other short cycles, may accommodate upstream reciprocity. In this study, I extend the upstream reciprocity game proposed for a directed cycle by Boyd and Richerson to the case of general networks. The model is not evolutionary and concerns the conditions under which the unanimity of cooperative players is a Nash equilibrium. I show that an abundance of triangles or other short cycles in a network does little to promote upstream reciprocity. Cooperation is less likely for a larger population size even if triangles are abundant in the network. In addition, in contrast to the results for evolutionary social dilemma games on networks, scale-free networks lead to less cooperation than networks with a homogeneous degree distribution.

preprint2011arXiv

Evolution of cooperation facilitated by reinforcement learning with adaptive aspiration levels

Repeated interaction between individuals is the main mechanism for maintaining cooperation in social dilemma situations. Variants of tit-for-tat (repeating the previous action of the opponent) and the win-stay lose-shift strategy are known as strong competitors in iterated social dilemma games. On the other hand, real repeated interaction generally allows plasticity (i.e., learning) of individuals based on the experience of the past. Although plasticity is relevant to various biological phenomena, its role in repeated social dilemma games is relatively unexplored. In particular, if experience-based learning plays a key role in promotion and maintenance of cooperation, learners should evolve in the contest with nonlearners under selection pressure. By modeling players using a simple reinforcement learning model, we numerically show that learning enables the evolution of cooperation. We also show that numerically estimated adaptive dynamics appositely predict the outcome of evolutionary simulations. The analysis of the adaptive dynamics enables us to capture the obtained results as an affirmative example of the Baldwin effect, where learning accelerates the evolution to optimality.

preprint2011arXiv

Evolution of cooperation is a robust outcome in the prisoner's dilemma on dynamic networks

Dynamics of evolutionary games strongly depend on underlying networks. We study the coevolutionary prisoner's dilemma in which players change their local networks as well as strategies (i.e., cooperate or defect). This topic has been increasingly explored by many researchers. On the basis of active linking dynamics [J. M. Pacheco et al., J. Theor. Biol. 243, 437 (2006), J. M. Pacheco et al., Phys. Rev. Lett. 97, 258103 (2006)], we show that cooperation is enhanced fairly robustly. In particular, cooperation evolves when the payoff of the player is normalized by the number of neighbors; this is not the case in the evolutionary prisoner's dilemma on static networks.

preprint2011arXiv

Numerical analysis of a reinforcement learning model with the dynamic aspiration level in the iterated Prisoner's Dilemma

Humans and other animals can adapt their social behavior in response to environmental cues including the feedback obtained through experience. Nevertheless, the effects of the experience-based learning of players in evolution and maintenance of cooperation in social dilemma games remain relatively unclear. Some previous literature showed that mutual cooperation of learning players is difficult or requires a sophisticated learning model. In the context of the iterated Prisoner's Dilemma, we numerically examine the performance of a reinforcement learning model. Our model modifies those of Karandikar et al. (1998), Posch et al. (1999), and Macy and Flache (2002) in which players satisfice if the obtained payoff is larger than a dynamic threshold. We show that players obeying the modified learning mutually cooperate with high probability if the dynamics of threshold is not too fast and the association between the reinforcement signal and the action in the next round is sufficiently strong. The learning players also perform efficiently against the reactive strategy. In evolutionary dynamics, they can invade a population of players adopting simpler but competitive strategies. Our version of the reinforcement learning model does not complicate the previous model and is sufficiently simple yet flexible. It may serve to explore the relationships between learning and evolution in social dilemma situations.

preprint2011arXiv

Numerical study of a three-state host-parasite system on the square lattice

We numerically study the phase diagram of a three-state host-parasite model on the square lattice motivated by population biology. The model is an extension of the contact process, and the three states correspond to an empty site, a host, and a parasite. We determine the phase diagram of the model by scaling analysis. In agreement with previous results, three phases are identified: the phase in which both hosts and parasites are extinct (S_{0}), the phase in which hosts survive but parasites are extinct (S_{01}), and the phase in which both hosts and parasites survive (S_{012}). We argue that both the S_{0}-S_{01} and S_{01}-S_{012} boundaries belong to the directed percolation class. In this model, it has been suggested that an excessively large reproduction rate of parasites paradoxically extinguishes hosts and parasites and results in S_{0}. We show that this paradoxical extinction is a finite size effect; the corresponding parameter region is likely to disappear in the limit of infinite system size.

preprint2011arXiv

Predictability of conversation partners

Recent developments in sensing technologies have enabled us to examine the nature of human social behavior in greater detail. By applying an information theoretic method to the spatiotemporal data of cell-phone locations, [C. Song et al. Science 327, 1018 (2010)] found that human mobility patterns are remarkably predictable. Inspired by their work, we address a similar predictability question in a different kind of human social activity: conversation events. The predictability in the sequence of one's conversation partners is defined as the degree to which one's next conversation partner can be predicted given the current partner. We quantify this predictability by using the mutual information. We examine the predictability of conversation events for each individual using the longitudinal data of face-to-face interactions collected from two company offices in Japan. Each subject wears a name tag equipped with an infrared sensor node, and conversation events are marked when signals are exchanged between sensor nodes in close proximity. We find that the conversation events are predictable to some extent; knowing the current partner decreases the uncertainty about the next partner by 28.4% on average. Much of the predictability is explained by long-tailed distributions of interevent intervals. However, a predictability also exists in the data, apart from the contribution of their long-tailed nature. In addition, an individual's predictability is correlated with the position in the static social network derived from the data. Individuals confined in a community - in the sense of an abundance of surrounding triangles - tend to have low predictability, and those bridging different communities tend to have high predictability.

preprint2011arXiv

Robustness of networks against propagating attacks under vaccination strategies

We study the effect of vaccination on robustness of networks against propagating attacks that obey the susceptible-infected-removed model.By extending the generating function formalism developed by Newman (2005), we analytically determine the robustness of networks that depends on the vaccination parameters. We consider the random defense where nodes are vaccinated randomly and the degree-based defense where hubs are preferentially vaccinated. We show that when vaccines are inefficient, the random graph is more robust against propagating attacks than the scale-free network. When vaccines are relatively efficient, the scale-free network with the degree-based defense is more robust than the random graph with the random defense and the scale-free network with the random defense.

preprint2011arXiv

Structure of Cell Networks Critically Determines Oscillation Regularity

Biological rhythms are generated by pacemaker organs, such as the heart pacemaker organ (the sinoatrial node) and the master clock of the circadian rhythms (the suprachiasmatic nucleus), which are composed of a network of autonomously oscillatory cells. Such biological rhythms have notable periodicity despite the internal and external noise present in each cell. Previous experimental studies indicate that the regularity of oscillatory dynamics is enhanced when noisy oscillators interact and become synchronized. This effect, called the collective enhancement of temporal precision, has been studied theoretically using particular assumptions. In this study, we propose a general theoretical framework that enables us to understand the dependence of temporal precision on network parameters including size, connectivity, and coupling intensity; this effect has been poorly understood to date. Our framework is based on a phase oscillator model that is applicable to general oscillator networks with any coupling mechanism if coupling and noise are sufficiently weak. In particular, we can manage general directed and weighted networks. We quantify the precision of the activity of a single cell and the mean activity of an arbitrary subset of cells. We find that, in general undirected networks, the standard deviation of cycle-to-cycle periods scales with the system size $N$ as $1/\sqrt{N}$, but only up to a certain system size $N^*$ that depends on network parameters. Enhancement of temporal precision is ineffective when $N>N^*$. We also reveal the advantage of long-range interactions among cells to temporal precision.

preprint2011arXiv

Voter model with non-Poissonian interevent intervals

Recent analysis of social communications among humans has revealed that the interval between interactions for a pair of individuals and for an individual often follows a long-tail distribution. We investigate the effect of such a non-Poissonian nature of human behavior on dynamics of opinion formation. We use a variant of the voter model and numerically compare the time to consensus of all the voters with different distributions of interevent intervals and different networks. Compared with the exponential distribution of interevent intervals (i.e., the standard voter model), the power-law distribution of interevent intervals slows down consensus on the ring. This is because of the memory effect; in the power-law case, the expected time until the next update event on a link is large if the link has not had an update event for a long time. On the complete graph, the consensus time in the power-law case is close to that in the exponential case. Regular graphs bridge these two results such that the slowing down of the consensus in the power-law case as compared to the exponential case is less pronounced as the degree increases.

preprint2010arXiv

Collective fluctuations in networks of noisy components

Collective dynamics result from interactions among noisy dynamical components. Examples include heartbeats, circadian rhythms, and various pattern formations. Because of noise in each component, collective dynamics inevitably involve fluctuations, which may crucially affect functioning of the system. However, the relation between the fluctuations in isolated individual components and those in collective dynamics is unclear. Here we study a linear dynamical system of networked components subjected to independent Gaussian noise and analytically show that the connectivity of networks determines the intensity of fluctuations in the collective dynamics. Remarkably, in general directed networks including scale-free networks, the fluctuations decrease more slowly with the system size than the standard law stated by the central limit theorem. They even remain finite for a large system size when global directionality of the network exists. Moreover, such nontrivial behavior appears even in undirected networks when nonlinear dynamical systems are considered. We demonstrate it with a coupled oscillator system.

preprint2010arXiv

Dynamics-based centrality for general directed networks

Determining the relative importance of nodes in directed networks is important in, for example, ranking websites, publications, and sports teams, and for understanding signal flows in systems biology. A prevailing centrality measure in this respect is the PageRank. In this work, we focus on another class of centrality derived from the Laplacian of the network. We extend the Laplacian-based centrality, which has mainly been applied to strongly connected networks, to the case of general directed networks such that we can quantitatively compare arbitrary nodes. Toward this end, we adopt the idea used in the PageRank to introduce global connectivity between all the pairs of nodes with a certain strength. Numerical simulations are carried out on some networks. We also offer interpretations of the Laplacian-based centrality for general directed networks in terms of various dynamical and structural properties of networks. Importantly, the Laplacian-based centrality defined as the stationary density of the continuous-time random walk with random jumps is shown to be equivalent to the absorption probability of the random walk with sinks at each node but without random jumps. Similarly, the proposed centrality represents the importance of nodes in dynamics on the original network supplied with sinks but not with random jumps.

preprint2010arXiv

Effects of diffusion rates on epidemic spreads in metapopulation networks

It is often useful to represent the infectious dynamics of mobile agents by metapopulation models. In such a model, metapopulations form a static network, and individuals migrate from one metapopulation to another. It is known that heterogeneous degree distributions of metapopulation networks decrease the epidemic threshold above which epidemic spreads can occur. We investigate the combined effect of heterogeneous degree distributions and diffusion on epidemics in metapopulation networks. We show that for arbitrary heterogeneous networks, diffusion suppresses epidemics in the sense of an increase in the epidemic threshold. On the other hand, some diffusion rates are needed to elicit epidemic spreads on a global scale. As a result of these opposing effects of diffusion, epidemic spreading near the epidemic threshold is the most pronounced at an intermediate diffusion rate. The result that diffusion can suppress epidemics contrasts with that for diffusive SIS dynamics and its variants when individuals are fixed at nodes on static networks.

preprint2010arXiv

Enhancing the spectral gap of networks by node removal

Dynamics on networks are often characterized by the second smallest eigenvalue of the Laplacian matrix of the network, which is called the spectral gap. Examples include the threshold coupling strength for synchronization and the relaxation time of a random walk. A large spectral gap is usually associated with high network performance, such as facilitated synchronization and rapid convergence. In this study, we seek to enhance the spectral gap of undirected and unweighted networks by removing nodes because, practically, the removal of nodes often costs less than the addition of nodes, addition of links, and rewiring of links. In particular, we develop a perturbative method to achieve this goal. The proposed method realizes better performance than other heuristic methods on various model and real networks. The spectral gap increases as we remove up to half the nodes in most of these networks.

preprint2010arXiv

Heterogeneous Voter Models

We introduce the heterogeneous voter model (HVM), in which each agent has its own intrinsic rate to change state, reflective of the heterogeneity of real people, and the partisan voter model (PVM), in which each agent has an innate and fixed preference for one of two possible opinion states. For the HVM, the time until consensus is reached is much longer than in the classic voter model. For the PVM in the mean-field limit, a population evolves to a "selfish" state, where each agent tends to be aligned with its internal preference. For finite populations, discrete fluctuations ultimately lead to consensus being reached in a time that scales exponentially with population size.

preprint2010arXiv

Long-tail Behavior in Locomotion of Caenorhabditis elegans

The locomotion of Caenorhabditis elegans exhibits complex patterns. In particular, the worm combines mildly curved runs and sharp turns to steer its course. Both runs and sharp turns of various types are important components of taxis behavior. The statistics of sharp turns have been intensively studied. However, there have been few studies on runs, except for those on klinotaxis (also called weathervane mechanism), in which the worm gradually curves toward the direction with a high concentration of chemicals; this phenomenon was discovered recently. We analyzed the data of runs by excluding sharp turns. We show that the curving rate obeys long-tail distributions, which implies that large curving rates are relatively frequent. This result holds true for locomotion in environments both with and without a gradient of NaCl concentration; it is independent of klinotaxis. We propose a phenomenological computational model on the basis of a random walk with multiplicative noise. The assumption of multiplicative noise posits that the fluctuation of the force is proportional to the force exerted. The model reproduces the long-tail property present in the experimental data.

preprint2010arXiv

Synchronization Transition of Identical Phase Oscillators in a Directed Small-World Network

We numerically study a directed small-world network consisting of attractively coupled, identical phase oscillators. While complete synchronization is always stable, it is not always reachable from random initial conditions. Depending on the shortcut density and on the asymmetry of the phase coupling function, there exists a regime of persistent chaotic dynamics. By increasing the density of shortcuts or decreasing the asymmetry of the phase coupling function, we observe a discontinuous transition in the ability of the system to synchronize. Using a control technique, we identify the bifurcation scenario of the order parameter. We also discuss the relation between dynamics and topology and remark on the similarity of the synchronization transition to directed percolation.

preprint2009arXiv

Immunization of networks with community structure

In this study, an efficient method to immunize modular networks (i.e., networks with community structure) is proposed. The immunization of networks aims at fragmenting networks into small parts with a small number of removed nodes. Its applications include prevention of epidemic spreading, intentional attacks on networks, and conservation of ecosystems. Although preferential immunization of hubs is efficient, good immunization strategies for modular networks have not been established. On the basis of an immunization strategy based on the eigenvector centrality, we develop an analytical framework for immunizing modular networks. To this end, we quantify the contribution of each node to the connectivity in a coarse-grained network among modules. We verify the effectiveness of the proposed method by applying it to model and real networks with modular structure.

preprint2007arXiv

Statistical properties of a generalized threshold network model

The threshold network model is a type of finite random graphs. In this paper, we introduce a generalized threshold network model. A pair of vertices with random weights is connected by an edge when real-valued functions of the pair of weights belong to given Borel sets. We extend several known limit theorems for the number of prescribed subgraphs to show that the strong law of large numbers can be uniform convergence. We also prove two limit theorems for the local and global clustering coefficients.

Naoki Masuda

What is connected

Connect this record

See the researcher in context

Building this map preview

72 published item(s)

Non-dilemmatic social dynamics promote cooperation in multilayer networks

Accuracy of a one-dimensional reduction of dynamical systems on networks

Dimension reduction of dynamical systems on networks with leading and non-leading eigenvectors of adjacency matrices

Metapopulation models imply non-Poissonian statistics of interevent times

Temporal Motifs in Patent Opposition and Collaboration Networks

A Gillespie algorithm for non-Markovian stochastic processes

Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix

Critical mass effect in evolutionary games triggered by zealots

Interplay between $k$-core and community structure in complex networks

Long-tailed distributions of inter-event times as mixtures of exponential distributions

Random walks and diffusion on networks

Recurrence Quantification Analysis of Dynamic Brain Networks

Small inter-event times govern epidemic spreading on temporal networks

Waiting-time paradox in 1922

Winning by hiding behind others: An analysis of speed skating data

Constructing networks by filtering correlation matrices: A null model approach

Modeling temporal networks with bursty activity patterns of nodes and links

Accelerating coordination in temporal networks by engineering the link order

Evolutionary dynamics in finite populations with zealots

Fragmenting networks by targeting collective influencers at a mesoscopic level

Temporal interactions facilitate endemicity in the susceptible-infected-susceptible epidemic model

Community detection in directed acyclic graphs

Individual-based approach to epidemic processes on arbitrary dynamic contact networks

Opinion control in complex networks

Steady state and mean recurrence time for random walks on stochastic temporal networks

Win-stay lose-shift strategy in formation changes in football

Evolution via imitation among like-minded individuals

Global network structure of dominance hierarchy of ant workers

Iterated crowdsourcing dilemma game

Networks maximizing the consensus time of voter models

Random walk centrality for temporal networks

The basic reproduction number as a predictor for epidemic outbreaks in temporal networks

Two types of well followed users in the followership networks of Twitter

Voter model on the two-clique graph

A collective opinion formation model under Bayesian updating and confirmation bias

Application of semidefinite programming to maximize the spectral gap produced by node removal

Complex dynamics of a nonlinear voter model with contrarian agents

Observability transitions in correlated networks

Random Walks on Directed Networks: Inference and Respondent-driven Sampling

Self-exciting point process modeling of conversation event sequences

State Concentration Exponent as a Measure of Quickness in Kauffman-type Networks

Suicide ideation of individuals in online social networks

Temporal networks: slowing down diffusion by long lasting interactions

Voter models with contrarian agents

A network-based dynamical ranking system for competitive sports

Bursty communication patterns facilitate spreading in a threshold-based epidemic dynamics

Coevolution of trustful buyers and cooperative sellers in the trust game

Evolution of cooperation driven by zealots

Formation of feedforward networks and frequency synchrony by spike-timing-dependent plasticity

Groupwise information sharing promotes ingroup favoritism in indirect reciprocity

Importance of individual events in temporal networks

Indirect reciprocity with trinary reputations

Ingroup favoritism and intergroup cooperation under indirect reciprocity based on group reputation

Can Partisan Voting Lead to Truth?

Clustering in large networks does not promote upstream reciprocity

Evolution of cooperation facilitated by reinforcement learning with adaptive aspiration levels

Evolution of cooperation is a robust outcome in the prisoner's dilemma on dynamic networks

Numerical analysis of a reinforcement learning model with the dynamic aspiration level in the iterated Prisoner's Dilemma

Numerical study of a three-state host-parasite system on the square lattice

Predictability of conversation partners

Robustness of networks against propagating attacks under vaccination strategies

Structure of Cell Networks Critically Determines Oscillation Regularity

Voter model with non-Poissonian interevent intervals

Collective fluctuations in networks of noisy components

Dynamics-based centrality for general directed networks

Effects of diffusion rates on epidemic spreads in metapopulation networks

Enhancing the spectral gap of networks by node removal

Heterogeneous Voter Models

Long-tail Behavior in Locomotion of Caenorhabditis elegans

Synchronization Transition of Identical Phase Oscillators in a Directed Small-World Network

Immunization of networks with community structure

Statistical properties of a generalized threshold network model