Navigation in large subway networks: An informational approach

The structural properties of the subway network are crucial in effective transportation in cities. This paper presents an information perspective of navigation in four different subway networks: New York City, Paris, Barcelona and Moscow. We addressed our study to investigate what is that makes it complicated to navigate in these kinds of networks and we carried out a comparison between them and their intrinsic constraints. Our methodological approach is based on a set of cost/efficiency indicators which are defined in the complex networks literature. We find that the overall complexity in finding stations measured by the average search information S linearly increases as a function of the network size N. The direct implication of this finding is that from these basic levels of required information, the average value H(k) can be represented as a function of the node degree k. Finally, through analyzing subway networks in space P, we reveal the existing service modularity among subway routes using a rescaled expression of S.     

复杂交通运输网络上的拥挤与效率问题研究

本文研究复杂交通运输网络上的拥挤与效率问题. 在无标度网络、随机网络以及小世界网络等不同拓扑结构中, 探讨了不同的能力分配方式和不同的OD (Origin-Destination) 交通需求分布对网络拥挤度和效率的影响. 随着平均交通需求的增加, 分析无标度网络、随机网络以及小世界网络从自由流状态到交通拥堵状态的变化规律. 为便于比较, 本文侧重研究网络拥挤度的倒数, 并将其定义为通畅度. 研究发现网络中的通畅度与效率之间存在线性相关关系, 并且不同网络中的线性比例系数 (或斜率)是不同的, 从而体现了不同网络具有不同的运输性能. 关键词： 复杂网络 拥挤 效率     

Effects of the cascading failures on scale-free traffic networks

In this paper, we consider the artificial scale-free traffic network with dynamic weights (cost) and focus on how the removal strategies (flow-based removal, betweenness-based removal and mix-based removal) affect the damage of cascading failures based on the user-equilibrium (UE) assignment, which ensures the balance of flow on the traffic network. Experiment simulation shows that different removal strategies can bring large dissimilarities of the efficiency and damage after the intentional removal of an edge. We show that the mix-based removal of a single edge might reduce the damage of cascading failures and delay the breakdown time, especially for larger reserve capacity coefficient α. This is particularly important for real-world networks with a highly hetereogeneous distribution of flow, i.e., traffic and transportation networks, logistics networks and electrical power grids.     

Jamming in complex networks with degree correlation

We study the effects of the degree-degree correlations on the pressure congestion J when we apply a dynamical process on scale free complex networks using the gradient network approach. We find that the pressure congestion for disassortative (assortative) networks is lower (bigger) than the one for uncorrelated networks which allow us to affirm that disassortative networks enhance transport through them. This result agree with the fact that many real world transportation networks naturally evolve to this kind of correlation. We explain our results showing that for the disassortative case the clusters in the gradient network turn out to be as much elongated as possible, reducing the pressure congestion J and observing the opposite behavior for the assortative case. Finally we apply our model to real world networks, and the results agree with our theoretical model.     

基于休眠机理的三维小基站蜂窝网络能效优化

小基站通常部署在写字楼、商贸区等城市密集区域以弥补传统宏基站在覆盖和传输方面的不足.小基站的分布一般是根据高峰时的网络负荷设计的,这必然导致网络负荷较低时的资源浪费.讨论了在平均接入率和信道容量双重约束下基于休眠机理的三维小基站蜂窝网络的能效优化问题.借助泊松点过程理论推导了三维小基站网络下行信道容量和平均接入率的数学表达式.通过分析下行信道容量和平均接入率的单调性得出同时满足传输信道容量和接入率要求的最佳休眠概率.分析了小基站最大用户连接数的最佳值,通过对该参数的合理配置,可以在满足通信指标的前提下最大程度地降低网络能耗.仿真结果表明,设计的基站休眠机理可以使小基站网络的能耗下降约21%.     

Novel hybrid mitigation strategy for improving the resiliency of hierarchical networks subjected to attacks

This paper studies the resiliency of hierarchical networks when subjected to random errors, static attacks, and cascade attacks. The performance is compared with existing Erdös–Rényi (ER) random networks and Barabasi and Albert (BA) scale-free networks using global efficiency as the common performance metric. The results show that critical infrastructures modeled as hierarchical networks are intrinsically efficient and are resilient to random errors, however they are more vulnerable to targeted attacks than scale-free networks. Based on the response dynamics to different attack models, we propose a novel hybrid mitigation strategy that combines discrete levels of critical node reinforcement with additional edge augmentation. The proposed modified topology takes advantage of the high initial efficiency of the hierarchical network while also making it resilient to attacks. Experimental results show that when the level of damage inflicted on a critical node is low, the node reinforcement strategy is more effective, and as the level of damage increases, the additional edge augmentation is highly effective in maintaining the overall network resiliency.     

A matching-theoretic approach to resource allocation in D2D-enabled downlink NOMA cellular networks

This paper investigates the resource allocation problem in non-orthogonal multiple-access (NOMA) cellular networks underlaid with OMA-based device-to-device (D2D) communication. This network architecture enjoys the intrinsic features of NOMA and D2D communications; namely, spectral efficiency, massive connectivity, and low-latency. Despite these indispensable features, the combination of NOMA and D2D communications exacerbates the resource allocation problem in cellular networks due to the tight coupling among their constraints and conflict over access to shared resources. The aim of our work is to maximize the downlink network sum-rate, while meeting the minimum rate requirements of the cellular tier and underlay D2D communication, and incorporating interference management as well as other practical constraints. To this end, many-to-many matching and difference-of-convex programming are employed to develop a holistic sub-channels and power allocation algorithmic solution. In addition to analyzing the properties of the proposed solution, its performance is benchmarked against an existing solution and the traditional OMA-based algorithm. The proposed solution demonstrates superiority in terms of network sum-rate, users’ connectivity, minimum rate satisfaction, fairness, and interference management, while maintaining acceptable computational complexity.     

Blocking probability analysis of pruned optical banyan networks on vertical stacking scheme with extra banyan planes

Vertically stacked pruned optical banyan networks with extra planes (in short, EP-VSOB networks) have lower switch count and optimal time complexity (O(log₂ N)) for routing N input requests. However, blocking probability is relatively higher than that of a VSOB networks using regular banyan planes. In the EP-VSOB architecture, the number of pruned planes has always been considered as , and a few extra planes (regular banyan) have been added with these pruned planes. In this paper we present the results of blocking analysis of a more generalized architecture in which the number of pruned planes can be 2^x, where x ? 0 in addition to the variable extra planes. This generalization helps us make a compromise between different constraints and performance metrics. Our simulation results show that for some given performance requirements (e.g. cost, speed or blocking probability) we can choose a network that has lower switch count compared to -plane pruned crosstalk-free optical banyan networks. For example, to ensure blocking probability <0.02, previously we would chose a pruned network of 32 pruned planes and 1 extra planes (a regular banyan); however, our simulations results show that a network of 16 pruned planes and 2 extra planes is enough to ensure the same performance. It is notable that, the hardware cost decreases by 28.65% in this new combination of pruned and extra planes. We believe our results will provide more flexibility in choosing a particular EP-VSOB network satisfying given requirements.     

Network evolution by nonlinear preferential rewiring of edges

The mathematical framework for small-world networks proposed in a seminal paper by Watts and Strogatz sparked a widespread interest in modeling complex networks in the past decade. However, most of research contributing to static models is in contrast to real-world dynamic networks, such as social and biological networks, which are characterized by rearrangements of connections among agents. In this paper, we study dynamic networks evolved by nonlinear preferential rewiring of edges. The total numbers of vertices and edges of the network are conserved, but edges are continuously rewired according to the nonlinear preference. Assuming power-law kernels with exponents α and β, the network structures in stationary states display a distinct behavior, depending only on β. For β>1, the network is highly heterogeneous with the emergence of starlike structures. For β<1, the network is widely homogeneous with a typical connectivity. At β=1, the network is scale free with an exponential cutoff.     

Efficiency and robustness in ant networks of galleries

Recent theoretical and empirical studies have focused on the topology of large networks of communication/interactions in biological, social and technological systems. Most of them have been studied in the scope of the small-world and scale-free networks theory. Here we analyze the characteristics of ant networks of galleries produced in a 2-D experimental setup. These networks are neither small-worlds nor scale-free networks and belong to a particular class of network, i.e. embedded planar graphs emerging from a distributed growth mechanism. We compare the networks of galleries with both minimal spanning trees and greedy triangulations. We show that the networks of galleries have a path system efficiency and robustness to disconnections closer to the one observed in triangulated networks though their cost is closer to the one of a tree. These networks may have been prevented to evolve toward the classes of small-world and scale-free networks because of the strong spatial constraints under which they grow, but they may share with many real networks a similar trend to result from a balance of constraints leading them to achieve both path system efficiency and robustness at low cost.Received: 16 July 2004, Published online: 26 November 2004PACS: 89.75.Fb Structures and organization in complex systems - 89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems     

Survivable routing and spectrum allocation algorithm based on p-cycle protection in elastic optical networks

With the number of large capacity applications in core network increasing, the bandwidth requirement of optical connections in conventional Wavelength Division Multiplexing (WDM) networks keeps enhancing, so that the Orthogonal Frequency Division Multiplexing (OFDM) technology is adopted to provide higher spectrum efficiency and flexibility in the future elastic optical networks. Meanwhile, survivability in the conventional WDM optical networks has been widely studied as an important issue to ensure the service continuity. However, survivability in OFDM-based elastic optical networks is more challenging than that in conventional WDM optical networks because each fiber usually carries even more connections. Therefore, it is necessary to study the new lightpath protection algorithm in elastic optical networks. Since p-cycle protection scheme has short restoration time and simple protection switching procedure, in this paper, we study the static Survivable p-Cycle Routing and Spectrum Allocation (SC-RSA) problem with providing an Integer Linear Programming (ILP) formulation. Since RSA is a NP-hard problem, we propose a new heuristic algorithm called Elastic p-Cycle Protection (ECP) to tolerate the single-fiber link failure. For each demand, ECP scheme can compute highly-efficient p-cycles to provide protection for all of the on-cycle links and the straddling links. We also consider the load balancing and choose the proper working path for each demand. Simulation results show that the proposed ECP scheme achieves better performances than traditional single-line-rate survivable schemes.     

Identifying influential nodes in complex networks

Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. The degree centrality method is very simple but of little relevance. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but are incapable to be applied in large-scale networks due to the computational complexity. In order to design an effective ranking method, we proposed a semi-local centrality measure as a tradeoff between the low-relevant degree centrality and other time-consuming measures. We use the Susceptible-Infected-Recovered (SIR) model to evaluate the performance by using the spreading rate and the number of infected nodes. Simulations on four real networks show that our method can well identify influential nodes.     

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

A study on small-world brain functional networks altered by postherpetic neuralgia

Understanding the effect of postherpetic neuralgia (PHN) pain on brain activity is important for clinical strategies. This is the first study, to our knowledge, to relate PHN pain to small-world properties of brain functional networks. Functional magnetic resonance imaging (fMRI) was used to construct functional brain networks of the subjects during the resting state. Sixteen patients with PHN pain and 16 (8 males, 8 females for both groups) age-matched controls were studied. The PHN patients exhibited decreased local efficiency along with non-significant changes of global efficiency in comparison with the healthy controls. Moreover, regional nodal efficiency was found to be significantly affected by PHN pain in the areas related to sense (postcentral gyrus, inferior parietal gyrus and thalamus), memory/affective processes (parahippocampal gyrus) and emotional activities (putamen). Significant correlation (p < 0.05) was also found between the nodal efficiency of putamen and pain intensity in PHN patients. Our results suggest that PHN modulates the local efficiency, and the small-world properties of brain networks may have potentials to objectively evaluate pain information in clinic.     

Multifractal analysis of complex networks

Complex networks have recently attracted much attention in diverse areas of science and technology.Many networks such as the WWW and biological networks are known to display spatial heterogeneity which can be characterized by their fractal dimensions.Multifractal analysis is a useful way to systematically describe the spatial heterogeneity of both theoretical and experimental fractal patterns.In this paper,we introduce a new box-covering algorithm for multifractal analysis of complex networks.This algorithm is used to calculate the generalized fractal dimensions D q of some theoretical networks,namely scale-free networks,small world networks,and random networks,and one kind of real network,namely protein-protein interaction networks of different species.Our numerical results indicate the existence of multifractality in scale-free networks and protein-protein interaction networks,while the multifractal behavior is not clear-cut for small world networks and random networks.The possible variation of D q due to changes in the parametersof the theoretical network models is also discussed.     

New network architecture for stoichiometrically,thermodynamically and kinetically balanced metabolic reaction systems

The conventional way of assembling the metabolic reactions into networks by placing the metabolites on the nodes and associating the edges with reactions is shown to violate the mass balance, thermodynamics and kinetics. A new type of metabolic networks referred to as reaction route (RR) networks is discussed. The distinct feature of the RR networks is that both the nodes and edges are subject to mass balance, thermodynamic and kinetic constraints. To satisfy these constraints, it is necessary to introduce two different types of nodes. One of these, referred to as terminal nodes, satisfy the mass balance conditions for external metabolites. The other type of nodes, referred to as intermediate nodes, satisfy the quasi steady-state conditions for internal metabolites. It is further required that every cycle in the network be thermodynamically consistent in that the sum of affinities (Gibbs free energy changes) of the reactions comprising the cycle should add up to zero. A balanced RR metabolic network possesses a remarkable property, namely, every conceivable walk between two terminal nodes involves a sequence of metabolic reaction steps that produce an overall reaction (OR), i.e., a reaction comprising only external metabolites. A key result is that many metabolic reaction networks may be balanced if and only if the network is allowed to be infinite and periodic.     

Why Dilated Convolutional Neural Networks: A Proof of Their Optimality

One of the most effective image processing techniques is the use of convolutional neural networks that use convolutional layers. In each such layer, the value of the layer’s output signal at each point is a combination of the layer’s input signals corresponding to several neighboring points. To improve the accuracy, researchers have developed a version of this technique, in which only data from some of the neighboring points is processed. It turns out that the most efficient case—called dilated convolution—is when we select the neighboring points whose differences in both coordinates are divisible by some constant ℓ. In this paper, we explain this empirical efficiency by proving that for all reasonable optimality criteria, dilated convolution is indeed better than possible alternatives.     

Error rate analysis of AF-relay wireless networks under different SNR levels

This paper presents a new method for analyzing the Bit Error Rate (BER) performance of two-hop Amplify-and-Forward Multiple Relay (AF-MR) networks. This paper considers, a flat-fading channel and a relay selection scheme to select a relay with the highest Signal-to-Noise Ratio (SNR). The method aims to unify the BER calculation under low, high and optimal SNR levels. Asymptotic BER (ABER) performance at high SNR value is calculated first, and standard expressions for exact BER (EBER) performance at low and optimal SNRs are then derived. The analytic method depends on the conventional BER (CBER) approach of one-hop communication systems. The optimal SNR is obtained by balancing energy efficiency and spectral efficiency. The proposed method is found to be effective for calculating the BER of AF-MR network performance under any SNR conditions. Moreover, it improves the accuracy of ABER performance by reducing disparity computation errors between ABER and EBER performances and this allows the BER of AF-MR networks to be accurately calculated using either ABER or EBER. The outcome expressions for the method are validated by simulation results.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.