The dynamic random subgraph model for the clustering of evolving networks

In recent years, many clustering methods have been proposed to extract information from networks. The principle is to look for groups of vertices with homogenous connection profiles. Most of these techniques are suitable for static networks, that is to say, not taking into account the temporal dimension. This work is motivated by the need of analyzing evolving networks where a decomposition of the networks into subgraphs is given. Therefore, in this paper, we consider the random subgraph model (RSM) which was proposed recently to model networks through latent clusters built within known partitions. Using a state space model to characterize the cluster proportions, RSM is then extended in order to deal with dynamic networks. We call the latter the dynamic random subgraph model (dRSM). A variational expectation maximization (VEM) algorithm is proposed to perform inference. We show that the variational approximations lead to an update step which involves a new state space model from which the parameters along with the hidden states can be estimated using the standard Kalman filter and Rauch–Tung–Striebel smoother. Simulated data sets are considered to assess the proposed methodology. Finally, dRSM along with the corresponding VEM algorithm are applied to an original maritime network built from printed Lloyd’s voyage records.     

Towards a unified recurrent neural network theory: The uniformly pseudo-projection-anti-monotone net

In the past decades, various neural network models have been developed for modeling the behavior of human brain or performing problem-solving through simulating the behavior of human brain. The recurrent neural networks are the type of neural networks to model or simulate associative memory behavior of human being. A recurrent neural network (RNN) can be generally formalized as a dynamic system associated with two fundamental operators: one is the nonlinear activation operator deduced from the input-output properties of the involved neurons, and the other is the synaptic connections (a matrix) among the neurons. Through carefully examining properties of various activation functions used, we introduce a novel type of monotone operators, the uniformly pseudo-projectionanti-monotone (UPPAM) operators, to unify the various RNN models appeared in the literature. We develop a unified encoding and stability theory for the UPPAM network model when the time is discrete. The established model and theory not only unify but also jointly generalize the most known results of RNNs. The approach has lunched a visible step towards establishment of a unified mathematical theory of recurrent neural networks.     

Mining social networks using wave propagation

With the development of modern technology(communication, transportation, etc.), many new social networks have formed and influenced our life. The research of mining these new social networks has been used in many aspects. But compared with traditional networks, these new social networks are usually very large. Due to the complexity of the latter, few model can be adapted to mine them effectively. In this paper, we try to mine these new social networks using Wave Propagation process and mainly discuss two applications of our model, solving Message Broadcasting problem and Rumor Spreading problem. Our model has the following advantages: (1) We can simulate the real networks message transmitting process in time since we include a time factor in our model. (2) Our Message Broadcasting algorithm can mine the underlying relationship of real networks and represent some clustering properties. (3) We also provide an algorithm to detect social network and find the rumor makers. Complexity analysis shows our algorithms are scalable for large social network and stable analysis proofs our algorithms are stable.     

Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks

In this study we deal with network routing decisions and approximate performance evaluation approaches for generalized open queuing networks (OQN), in which commodities enter the network, receive service at one or more arcs and then leave the network. Exact performance evaluation has been applied for the analysis of Jackson OQN, where the arrival and service processes of the commodities are assumed to be Poisson. However, the Poisson processes’ hypotheses are not a plausible or acceptable assumption for the analysis of generalized OQN, as their arrival and service processes can be much less variable than Poisson processes, resulting in overestimated system performance measures and inappropriate flow routing solutions. In this paper we merge network routing algorithms and network decomposition methods to solve multicommodity flow problems in generalized OQN. Our focus is on steady-state performance measures as average delays and waiting times in queue. The main contributions are twofold: (i) to highlight that solving the corresponding multicommodity flow problem by representing the generalized OQN as a Jackson OQN may be a poor approximation and may lead to inaccurate estimates of the system performance measures, and (ii) to present a multicommodity flow algorithm based on a routing step and on an approximate decomposition step, which leads to much more accurate solutions. Computational results are presented in order to show the effectiveness of the proposed approach.     

Optimal egress time calculation and path generation for large evacuation networks

Finding the optimal clearance time and deciding the path and schedule of evacuation for large networks have traditionally been computationally intensive. In this paper, we propose a new method for finding the solution for this dynamic network flow problem with considerably lower computation time. Using a three phase solution method, we provide solutions for required clearance time for complete evacuation, minimum number of evacuation paths required for evacuation in least possible time and the starting schedules on those paths. First, a lower bound on the clearance time is calculated using minimum cost dynamic network flow model on a modified network graph representing the transportation network. Next, a solution pool of feasible paths between all O-D pairs is generated. Using the input from the first two models, a flow assignment model is developed to select the best paths from the pool and assign flow and decide schedule for evacuation with lowest clearance time possible. All the proposed models are mixed integer linear programing models and formulation is done for System Optimum (SO) scenario where the emphasis is on complete network evacuation in minimum possible clearance time without any preset priority. We demonstrate that the model can handle large size networks with low computation time. A numerical example illustrates the applicability and effectiveness of the proposed approach for evacuation.     

Stochastic resonance in feedforward acupuncture networks

Effects of noises and some other network properties on the weak signal propagation are studied systematically in feedforward acupuncture networks (FFN) based on FitzHugh–Nagumo neuron model. It is found that noises with medium intensity can enhance signal propagation and this effect can be further increased by the feedforward network structure. Resonant properties in the noisy network can also be altered by several network parameters, such as heterogeneity, synapse features, and feedback connections. These results may also provide a novel potential explanation for the propagation of acupuncture signal.     

Exploring express delivery networks in China based on complex network theory

Based on the complex network theory, we explore an express delivery system in China, which consists of two delivery networks, namely, the air delivery network (ADN) and the ground delivery network (GDN). Systematic structural analysis indicates that both delivery networks exhibit small‐world phenomenon, disassortative mixing behavior, and rich‐club phenomenon. However, there are significant differences between ADN and GDN in terms of degree distribution property and community structure. On the basis of the Barabási‐Albert model, we have proposed a network model incorporating the structural features of the two delivery networks to reveal their evolutionary mechanisms. Lastly, the parcel strength and the distance strength are analyzed, which, respectively, reflect the number of parcels and the long‐haul delivery distance handled by a node city. The strengths are highly heterogeneous in both delivery networks and have intense correlations with topological structures. These works are beneficial for express enterprises to construct or extend their express delivery networks, and provide some useful insights on improving parcel delivery service. © 2014 Wiley Periodicals, Inc. Complexity 21: 166–179, 2015     

Synchronization of a growing chaotic network model

Synchronization in large ensembles of coupled interacting units is a fundamental phenomenon, which is helpful for the understanding of working mechanisms in neuronal networks, social network, etc. In this paper, we will investigate the synchronization phenomenon in a network model. A feedback control scheme is proposed for the synchronization of the given complex networks. The obtained result indicates that synchronization can be achieved for growing chaotic network model. Method enhance the synchronizability of the given model are given at the same time. Finally, numerical simulations are given to show the effectiveness of obtained results.     

Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models

In this paper models and algorithms for the optimization of signal settings on urban networks are proposed. Two different approaches to the solution of the problem may be identified: a global approach (optimization of intersection signal settings on the whole network) and a local approach (optimization of signal settings intersection by intersection). For each approach a different optimization model and some solution algorithms are proposed; both models and algorithms are based on the assumptions of within-day static system and stochastic user equilibrium assignment models. The paper includes numerical results on test networks and a comparison between the two approaches.     

Node Features Adjusted Stochastic Block Model

Stochastic block model (SBM) and its variants are popular models used in community detection for network data. In this article, we propose a feature-adjusted stochastic block model (FASBM) to capture the impact of node features on the network links as well as to detect the residual community structure beyond that explained by the node features. The proposed model can accommodate multiple node features and estimate the form of feature impacts from the data. Moreover, unlike many existing algorithms that are limited to binary-valued interactions, the proposed FASBM model and inference approaches are easily applied to relational data that generate from any exponential family distribution. We illustrate the methods on simulated networks and on two real-world networks: a brain network and an US air-transportation network.     

When does data envelopment analysis outperform a naïve efficiency measurement model?

This paper compares the results from data envelopment analysis (DEA) to a naïve efficiency measurement model, which generates a scalar efficiency score by averaging all output–input ratios. Random data and real-life data are used to test the relative performance of the naïve model against various DEA models. The results suggest that the proposed the naïve model replicates DEA efficiency scores almost perfectly for constant return-to-scales and low heterogeneity in output–input data. It is therefore concluded that heterogeneity in output–input data is important to take advantage of the capability of DEA. It is also shown that heterogeneity is more relevant to efficiency measurement than the number of dimensions.     

离散型指数族非线性模型的变离差检验

It is necessary to test for varying dispersion in generalized nonlinear models. Wei,et al (1998) developed a likelihood ratio test,a score test and their adjustments to test for varying dispersion in continuous exponential family nonlinear models. This type of problem in the framework of general discrete exponential family nonlinear models is discussed. Two types of varying dispersion, which are random coefficients model and random effects model, are proposed ,and corresponding score test statistics are constructed and expressed in simple ,easy to use ,matrix formulas.     

TESTING FOR VARYING DISPERSION IN DISCRETE EXPONENTIAL FAMILY NONLINEAR MODELS

§ 1　 Introduction and modelsThe general form of exponential family nonlinear models isg(μi) =f(xi,﹀) , (1 )where,g(· ) is a monotonic link function,f is a known differentiable nonlinear functionand﹀ is a p-vectoroffixed population parameters;μi=E(yi) and the density of response yiisp(yi) =exp{[yiθi -b(θi) -c(yi) ] -12 a(yi,) } ,(2 )whereθi is the natural parameter, is the dispersion parameter.From [1 1 ] ,μi=b(θi) ,Vi=Var(yi) =- 1 b(θi) .If f(xi,β) =x Ti ﹀,then mod…     

A matrix-based VaR model for risk identification in power supply networks

This paper presents a value-at-risk (VaR) model based on the singular value decomposition (SVD) of a sparsity matrix for voltage risk identification in power supply networks. The matrix-based model provides a more computationally efficient risk assessment method than conventional models such as probability analysis and sensitivity analysis, for example, and provides decision makers in the power supply industry with sufficient information to minimize the risk of network collapse or blackouts. The VaR model is incorporated into a risk identification system (RIS) programmed in the MATLAB environment. The feasibility of the proposed approach is confirmed by performing a series of risk assessment simulations using the standard American Electric Power (AEP) test models (i.e. 14-, 30- and 57-node networks) and a real-world power network (Taiwan power network), respectively. In general, the simulated results confirm the ability of the matrix-based model VaR model to efficient identify risk of power supply networks.     

Vulnerability of complex networks

We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.     

Strict Nash networks and partner heterogeneity

This paper extends the two-way flow model of network formation initiated by Bala and Goyal (Econometrica 68(5):1181–1230, 2000) by allowing for partner heterogeneity. In our model if a player i forms a link with player j, then she pays a cost of c _j and gets benefits of V _j . Our main result consists of the characterization of strict Nash networks. We find that the introduction of partner heterogeneity plays a major role in dramatically increasing the set of strict Nash equilibria. This result differs substantially from what Galeotti et al. (Games Econ Behav 54(2):353–372, 2006) find in the two-way flow connections model of network formation with player heterogeneity.     

Engineering graph-based models for dynamic timetable information systems

In the last years we have witnessed remarkable progress in providing efficient algorithmic solutions to the problem of computing best journeys (or routes) in schedule-based public transportation systems. We have now models to represent timetables that allow us to answer queries for optimal journeys in a few milliseconds, also at a very large scale. Such models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. Array-based models have been shown to be very effective in terms of query time, while graph-based ones usually answer queries by computing shortest paths, and hence they are suitable to be combined with the speed-up techniques developed for road networks.In this paper, we study the behavior of graph-based models in the prominent case of dynamic scenarios, i.e., when delays might occur to the original timetable. In particular, we make the following contributions. First, we consider the graph-based reduced time-expanded model and give a simplified and optimized routine for handling delays, and a re-engineered and fine-tuned query algorithm. Second, we propose a new graph-based model, namely the dynamic timetable model, natively tailored to efficiently incorporate dynamic updates, along with a query algorithm and a routine for handling delays. Third, we show how to adapt the ALT algorithm to such graph-based models. We have chosen this speed-up technique since it supports dynamic changes, and a careful implementation of it can significantly boost its performance. Finally, we provide an experimental study to assess the effectiveness of all proposed models and algorithms, and to compare them with the array-based state of the art solution for the dynamic case. We evaluate both new and existing approaches by implementing and testing them on real-world timetables subject to synthetic delays.Our experimental results show that: (i) the dynamic timetable model is the best model for handling delays; (ii) graph-based models are competitive to array-based models with respect to query time in the dynamic case; (iii) the dynamic timetable model compares favorably with both the original and the reduced time-expanded model regarding space; (iv) combining the graph-based models with speed-up techniques designed for road networks, such as ALT, is a very promising approach.     

Primary care network development: the regulator’s perspective

Our research is motivated by the proliferation of primary care models in Ontario, Canada. Currently, primary care is mainly provided by facilities belonging to six models of care. These models are remunerated by various schemes—a mixture of fee-for-service, capitation and salary. In addition, they provide different levels of care and several are better adjusted than others to treat complex health needs. The proposed mixed integer programming model allows the regulator to test the outcomes of locating different types of primary care facilities on the overall cost, accessibility and appropriateness of provided care. The network design is fitted to the heterogeneity of the population residing in a defined geographical area, directly using an index (deprivation index) that was found to correlate with increased health needs and barriers to care. The model capabilities are illustrated on the geographical area of Kingston, Ontario.     

A decision making procedure for robust train rescheduling based on mixed integer linear programming and Data Envelopment Analysis

This paper presents a self-learning decision making procedure for robust real-time train rescheduling in case of disturbances. The procedure is applicable to aperiodic timetables of mixed-tracked networks and it consists of three steps. The first two are executed in real-time and provide the rescheduled timetable, while the third one is executed offline and guarantees the self-learning part of the method. In particular, in the first step, a robust timetable is determined, which is valid for a finite time horizon. This robust timetable is obtained solving a mixed integer linear programming problem aimed at finding the optimal compromise between two objectives: the minimization of the delays of the trains and the maximization of the robustness of the timetable. In the second step, a merging procedure is first used to join the obtained timetable with the nominal one. Then, a heuristics is applied to identify and solve all conflicts eventually arising after the merging procedure. Finally, in the third step an offline cross-efficiency fuzzy Data Envelopment Analysis technique is applied to evaluate the efficiency of the rescheduled timetable in terms of delays minimization and robustness maximization when different relevance weights (defining the compromise between the two optimization objectives) are used in the first step. The procedure is thus able to determine appropriate relevance weights to employ when disturbances of the same type affect again the network. The railway service provider can take advantage of this procedure to automate, optimize, and expedite the rescheduling process. Moreover, thanks to the self-learning capability of the procedure, the quality of the rescheduling is improved at each reapplication of the method. The technique is applied to a real data set related to a regional railway network in Southern Italy to test its effectiveness.     

具有结构变化的非线性回归模型的阶段异方差检验

对于具有结构变化的非线性回归模型,两阶段的随机误差同时具有方差齐性是一个基本假设,但是该假设未必正确．本文研究该模型阶段异方差的检验问题．首先探讨了两阶段异方差的同时检验,然后构造了两阶段异方差的两个单个检验,分别得到了同时检验和单个检验的score统计量以及相应的调整形式．然后应用得到的检验统计量分析了南澳大利亚洋葱数据的阶段异方差性(Ratkowsky,1983),并用AIC,SBC进行模型比较,得到的结果与检验结果非常吻合．最后,用Monte Carlo模拟方法研究了统计量的检验功效．