Competing Markov decision processes

A class of discounted Markov decision processes (MDPs) is formed by bringing together individual MDPs sharing the same discount rate. These are in competition in the sense that at each decision epoch a single action is chosen from the union of the action sets of the individual MDPs. Such families of competing MDPs have been used to model a variety of problems in stochastic resource allocation and in the sequential design of experiments. Suppose thatS is a stationary strategy for such a family, thatS* is an optimal strategy and thatR(S),R(S*) denote the respective rewards earned. The paper extends (and explains) existing theory based on the Gittins index to give bounds onR(S*)-R(S) for this important class of processes. The procedures are illustrated by examples taken from the fields of stochastic scheduling and research planning.     

Towards effective visual analytics on multiplex and multilayer networks

In this article we discuss visualisation strategies for multiplex networks. Since Moreno’s early works on network analysis, visualisation has been one of the main ways to understand networks thanks to its ability to summarise a complex structure into a single representation highlighting multiple properties of the data. However, despite the large renewed interest in the analysis of multiplex networks, no study has proposed specialised visualisation approaches for this context and traditional methods are typically applied instead. In this paper we initiate a critical and structured discussion of this topic, and claim that the development of specific visualisation methods for multiplex networks will be one of the main drivers pushing current research results into daily practice.     

Epidemic spreading of an SEIRS model in scale-free networks

An SEIRS epidemic model on the scale-free networks is presented, where the active contact number of each vertex is assumed to be either constant or proportional to its degree for this model. Using the analytical method, we obtain the two threshold values for above two cases and find that the threshold value for constant contact is independent of the topology of the underlying networks. The existence of positive equilibrium is determined by threshold value. For a finite size of scale-free network, we prove the local stability of disease-free equilibrium and the permanence of the disease on the network. Furthermore, we investigate two major immunization strategies, random immunization and targeted immunization, some similar results are obtained. The simulation shows the positive equilibrium is stable.     

Link overlap,viability, and mutual percolation in multiplex networks

Many real-world complex systems are best modeled by multiplex networks. The multiplexity has proved to have broad impact on the system’s structure and function. Most theoretical studies on multiplex networks to date, however, have largely ignored the effect of the link overlap across layers despite strong empirical evidences for its significance. In this article, we investigate the effect of the link overlap in the viability of multiplex networks, both analytically and numerically. After a short recap of the original multiplex viability study, the distinctive role of overlapping links in viability and mutual connectivity is emphasized and exploited for setting up a proper analytic framework. A rich phase diagram for viability is obtained and greatly diversified patterns of hysteretic behavior in viability are observed in the presence of link overlap. Mutual percolation with link overlap is revisited as a limit of multiplex viability problem, and the controversy between existing results is clarified. The distinctive role of overlapping links is further demonstrated by the different responses of networks under random removals of overlapping and non-overlapping links, respectively, as well as under several link-removal strategies. Our results show that the link overlap facilitates the viability and mutual percolation; at the same time, the presence of link overlap poses a challenge in analytical approaches to the problem.     

Epidemic spreading with time delay on complex networks

In this paper, we propose a susceptible-infected-susceptible (SIS) model on complex networks, small-world (WS) networks and scale-free (SF) networks, to study the epidemic spreading behavior with time delay which is added into the infected phase. Considering the uniform delay, the basic reproduction number R ₀ on WS networks and \(\bar R_0\) on SF networks are obtained respectively. On WS networks, if R ₀ ≤ 1, there is a disease-free equilibrium and it is locally asymptotically stable; if R ₀ > 1, there is an epidemic equilibrium and it is locally asymptotically stable. On SF networks, if \(\bar R_0 \leqslant 1\), there is a disease-free equilibrium; if \(\bar R_0 > 1\), there is an epidemic equilibrium. Finally, we carry out simulations to verify the conclusions and analyze the effect of the time delay τ, the effective rate λ, average connectivity 〈k〉 and the minimum connectivity m on the epidemic spreading.     

Prediction of brand stories spreading on social networks

Advances in Data Analysis and Classification - Online social network is a major media for many types of information communication. Although the primary purpose of social networks is to connect...     

Critical branching processes in neural networks

Self-organized criticality generates complex behavior in systems of simple elements. It is observed in various biological neural systems and has been analyzed in simplified model systems. Branching processes often considered to be a mean-field approximation to the dynamics of critical systems. Here we study the validity of such an approximation for the case of a neural network. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Performance analysis of multi-frame message spreading in delay tolerant networks

Communication opportunities in delay tolerant networks are uncertain, so the message is transmitted in a store-carry-forward way, which depends on the contact between nodes. To use the contact efficiently, the message is often divided into many bundles, which are very small and can be transmitted successfully in one contact. Such multi-frame spreading algorithm is very important, but state of the art works just assume that the message is very small and has only one bundle. This paper proposes a theoretical framework based on mean field limit to evaluate the epidemic-like multi-frame spreading algorithm for the first time. In addition, the selfish behaviors can have certain impact on the store-carry-forward communication mode, so we extend our model to the case that nodes are selfish. Simulations show the accuracy of our model. Numerical results show that the more bundles the message has, the lower the average delivery ratio will be. In addition, the selfish behaviors can make the performance be worse.     

Contact processes on scale-free networks

We investigate the contact process on random graphs generated from the configuration model for scale-free complex networks with the power law exponent β E （2, 3]. Using the neighborhood expansion method, we show that, with positive probability, any disease with an infection rate λ 〉 0 can survive for exponential time in the number of vertices of the graph. This strongly supports the view that stochastic scale-free networks are remarkably different from traditional regular graphs, such as, Z^d and classical Erdos-Renyi random graphs.     

Randomized rumor spreading in poorly connected small‐world networks

The Push‐Pull protocol is a well‐studied round‐robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze the behavior of this protocol on random ‐trees, a class of power law graphs, which are small‐world and have large clustering coefficients, built as follows: initially we have a ‐clique. In every step a new node is born, a random ‐clique of the current graph is chosen, and the new node is joined to all nodes of the ‐clique. When is fixed, we show that if initially a random node is aware of the rumor, then with probability after rounds the rumor propagates to nodes, where is the number of nodes and is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion and constant treewidth, these results demonstrate that Push‐Pull can be efficient even on poorly connected networks. On the negative side, we prove that with probability the protocol needs at least rounds to inform all nodes. This exponential dichotomy between time required for informing almost all and all nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound successfully carries over to a closely related class of graphs, the random ‐Apollonian networks, for which we prove an upper bound of rounds for informing nodes with probability when is fixed. Here, © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 185–208, 2016     

On PageRank versatility for multiplex networks: properties and some useful bounds

In this paper, some results concerning the PageRank versatility measure for multiplex networks are given. This measure extends to the multiplex setting the well-known classic PageRank. Particularly, we focus on some spectral properties of the Laplacian matrix of the multiplex and on obtaining boundaries for the ranking value of a given node when some personalization vector is added, as in the classic setting.     

Analysis of epidemic spreading of an SIRS model in complex heterogeneous networks

In this paper, we study the spreading of infections in complex heterogeneous networks based on an SIRS epidemic model with birth and death rates. We find that the dynamics of the network-based SIRS model is completely determined by a threshold value. If the value is less than or equal to one, then the disease-free equilibrium is globally attractive and the disease dies out. Otherwise, the disease-free equilibrium becomes unstable and in the meantime there exists uniquely an endemic equilibrium which is globally asymptotically stable. A series of numerical experiments are given to illustrate the theoretical results. We also consider the SIRS model in the clustered scale-free networks to examine the effect of network community structure on the epidemic dynamics.     

An individual-based modeling framework for infectious disease spreading in clustered complex networks

We introduce an individual-based model with dynamical equations for susceptible-infected-susceptible (SIS) epidemics on clustered networks. Linking the mean-field and quenched mean-field models, a general method for deriving a cluster approximation for three-node loops in complex networks is proposed. The underlying epidemic threshold condition is derived by using the quasi-static approximation. Our method thus extends the pair quenched mean-field (pQMF) approach for SIS disease spreading in unclustered networks to the scenario of epidemic outbreaks in clustered systems with abundant transitive relationships.We found that clustering can significantly alter the epidemic threshold, depending nontrivially on topological details of the underlying population structure. The validity of our method is verified through the existence of bounded solutions to the clustered pQMF model equations, and is further attested via stochastic simulations on homogeneous small-world artificial networks and growing scale-free synthetic networks with tunable clustering, as well as on real-world complex networked systems. Our method has vital implications for the future policy development and implementation of intervention measures in highly clustered networks, especially in the early stages of an epidemic in which clustering can decisively alter the growth of a contagious outbreak.     

Contagion processes on urban bus networks in Indian cities

Bus transportation is the most convenient and cheapest way of public transportation in Indian cities. Due to cost‐effectiveness and wide reachability, buses bring people to their destinations every day. Although the bus transportation has numerous advantages over other ways of public transportation, this mode of transportation also poses a serious threat of spreading contagious diseases throughout the city. It is extremely difficult to predict the extent and spread of such an epidemic. Earlier studies have focused on the contagion processes on scale‐free network topologies; whereas, real‐world networks such as bus networks exhibit a wide‐spectrum of network topology. Therefore, we aim in this study to understand this complex dynamical process of epidemic outbreak and information diffusion on the bus networks for six different Indian cities using SI and SIR models. We identify epidemic thresholds for these networks which help us in controlling outbreaks by developing node‐based immunization techniques. © 2016 Wiley Periodicals, Inc. Complexity 21: 451–458, 2016     

Knowledge exchange processes in Industrial Districts and the emergence of networks

This paper aims at exploring conditions under which the need for knowledge exchange within a small firms?? cluster generates a structure of links between firms. We focus in particular on small firms?? clusters called Industrial Districts (IDs). Specifically, we analyze IDs with flexible specialization, in which knowledge exchange is driven by the search for complementary knowledge assets. Previous works of the authors proposed an agent-based model of IDs to explore the properties of networks emerging from the interaction of firms prompted by the search and exchange of complementary specialized knowledge. This model showed that limited relational capability, due to the small size, and an exchange mechanism solely based on the barter of complementary knowledge are structural conditions that limit individual firms?? growth in IDs with flexible specialization. This paper presents a new version of this model to analyze the role of embeddedness of relationships among IDs firms in shaping the emergent network structures. The aim of the paper is to answer to the following research questions: Can knowledge complementariness explain the emergence of a stable network of firms within a small firms?? cluster? What are the structural properties of these networks? Which role does the embeddedness of relationships among firms play in shaping the structure of emerging networks?     

Large deviations ordering of point processes in some queueing networks

Given a stochastic ordering between point processes, say that a p.p. N is smooth if it is less than the Poisson process with the same average intensity for this ordering. In this article we investigate whether initially smooth processes retain their smoothness as they cross a network of FIFO ·/D/1 queues along fixed routes. For the so-called strong variability ordering we show that point processes remain smooth as they proceed through a tandem of quasi-saturated (i.e., loaded to 1) M+·/D/1 queues. We then introduce the Large Deviations ordering, which involves comparison of the rate functions associated with Large Deviations Principles satisfied by the point processes. For this ordering, we show that smoothness is retained when the processes cross a feed-forward network of unsaturated ·/D/1 queues. We also examine the LD characteristics of a deterministic p.p. at the output of an M+·/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.