Application of the steiner street problem to a more economical data bus

A data bus consists of the interconnection of N terminals, each of which is connected to every other terminal. There are three fundamental approaches to the topology of the network: (1) the tee network, for which the connecting nodes coincide with the communicating nodes; (2) the star network, for which there is only one connection node, which may not coincide with a communication node; and (3) the Steiner minimal tree network, for which there can be many nodes, each of which is difficult to locate in the x-y plane. The tee and star approaches are receiving most attention but the third is the only one that economizes on the use of cable (glass fiber waveguide). After a discussion of the tee and star networks, we turn to the Steiner minimal tree network and a method of locating the connecting nodes so that the total amount of cable is minimized.     

Rapid self-organised initiation of ad hoc sensor networks close above the percolation threshold

This work shows potentials for rapid self-organisation of sensor networks where nodes collaborate to relay messages to a common data collecting unit (sink node). The study problem is, in the sense of graph theory, to find a shortest path tree spanning a weighted graph. This is a well-studied problem where for example Dijkstra’s algorithm provides a solution for non-negative edge weights. The present contribution shows by simulation examples that simple modifications of known distributed approaches here can provide significant improvements in performance. Phase transition phenomena, which are known to take place in networks close to percolation thresholds, may explain these observations. An initial method, which here serves as reference, assumes the sink node starts organisation of the network (tree) by transmitting a control message advertising its availability for its neighbours. These neighbours then advertise their current cost estimate for routing a message to the sink. A node which in this way receives a message implying an improved route to the sink, advertises its new finding and remembers which neighbouring node the message came from. This activity proceeds until there are no more improvements to advertise to neighbours. The result is a tree network for cost effective transmission of messages to the sink (root). This distributed approach has potential for simple improvements which are of interest when minimisation of storage and communication of network information are a concern. Fast organisation of the network takes place when the number k of connections for each node (degree) is close above its critical value for global network percolation and at the same time there is a threshold for the nodes to decide to advertise network route updates.     

Comparison of optical network topologies for wavelength division multiplexed transport networks

In this paper, the various network topologies comprising of various nodes have been investigated and compared. The signal is analyzed as it passes through each node in each of the network topology. For the ring topology, it is shown that there is no appreciable signal degradation in the ring network. It is seen that there is increase in Quality factor i.e. signal keeps on improving as it passes through the successive nodes. For the bus topology, the quality of signal goes on decreasing with increase in the number of nodes and the power penalty goes on increasing. For the star topology, it is observed that received power values of each node at a same distance from the hub are same and the performance is same. For the tree topology, it is observed that the performance of the optical tree is almost identical to the performance of ring topology, as signal quality is improved as it passes through the successive nodes of the hierarchy but the overall length of each segment is limited by the type of cabling used and if the backbone line breaks, the entire segment goes down.     

A Three State Hard-Core Model on a Cayley Tree

Abstract

We consider a nearest-neighbor hard-core model, with three states , on a homogeneous Cayley tree of order k (with k + 1 neighbors). This model arises as a simple example of a loss network with nearest-neighbor exclusion. The state σ(x) at each node x of the Cayley tree can be 0, 1 and 2. We have Poisson flow of calls of rate λ at each site x, each call has an exponential duration of mean 1. If a call finds the node in state 1 or 2 it is lost. If it finds the node in state 0 then things depend on the state of the neighboring sites. If all neighbors are in state 0, the call is accepted and the state of the node becomes 1 or 2 with equal probability 1/2. If at least one neighbor is in state 1, and there is no neighbor in state 2 then the state of the node becomes 1. If at least one neighbor is in state 2 the call is lost. We focus on ‘splitting’ Gibbs measures for this model, which are reversible equilibrium distributions for the above process. We prove that in this model, ? λ > 0 and k ≥ 1, there exists a unique translationinvariant splitting Gibbs measure ^*. We also study periodic splitting Gibbs measures and show that the above model admits only translation - invariant and periodic with period two (chess-board) Gibbs measures. We discuss some open problems and state several related conjectures.     

激光Maxwell-Bloch 方程时空混沌网络的同步研究

研究了激光Maxwell-Bloch 方程时空混沌网络的同步问题.对单模激光Maxwell-Bloch方程进行了修正. 以N个修正后具有时空混沌特性的单模激光Maxwell-Bloch方程作为网络节点构成复杂网络. 在考虑到网络连接过程中,节点时空混沌系统中的参量可能受到某种干扰而与实际值产生微小偏差的情况下,采用网络第一个节点的时空混沌系统同时并行驱动其余N-1个时空混沌系统达到同步. 进一步通过仿真模拟验证了同步方案的有效性.     

Network models: Action formulation

We develop a technique to formulate quantum field theory on an arbitrary network, based on different randomly disposed sets of scattering points. We define the R-matrix of the whole network as a product of R-matrices attached to each scattering node. Then an action is formulated for a network in terms of fermionic fields, which allows to calculate the transition amplitudes as Green functions. On so-called bubble and triangle diagrams it is shown that the method produces the same results as the one which uses the generalized star product. The approach allows to extend network models by including multiparticle interactions at the scattering nodes.     

Ubiquitousness of link-density and link-pattern communities in real-world networks

Many networks are characterized by the presence of communities, densely intra-connected groups with sparser inter-connections between groups. We propose a community overlay network representation to capture large-scale properties of communities. A community overlay G _o can be constructed upon a network G, called the underlying network, by (a) aggregating each community in G as a node in the overlay G _o ; (b) connecting two nodes in the overlay if the corresponding two communities in the underlying network have a number of direct links in between, (c) assigning to each node/link in the overlay a node/link weight, which represents e.g. the percentage of links in/between the corresponding underlying communities. The community overlays have been constructed upon a large number of real-world networks based on communities detected via five algorithms. Surprisingly, we find the following seemingly universal properties: (i) an overlay has a smaller degree-degree correlation than its underlying network ρ _o (D _l+, D _l−) < ρ(D _l+, D _l−) and is mostly disassortative ρ _o (D _l+, D _l−) < 0; (ii) a community containing a large number W _i of nodes tends to connect to many other communities ρ _o (W _i , D _i ) > 0. We explain the generic observation (i) by two facts: (1) degree-degree correlation or assortativity tends to be positively correlated with modularity; (2) by aggregating each community as a node, the modularity in the overlay is reduced and so is the assortativity. The observation (i) implies that the assortativity of a network depends on the aggregation level of the network representation, which is illustrated by the Internet topology at router and AS level.     

Voltage distribution in growing conducting networks

We investigate by random-walk simulations and a mean-field theory how growth by biased addition of nodes affects flow of the current through the emergent conducting graph, representing a digital circuit. In the interior of a large network the voltage varies with the addition time s < t of the node as V(s) ∼ ln(s)/s ^θ when constant current enters the network at last added node t and leaves at the root of the graph which is grounded. The topological closeness of the conduction path and shortest path through a node suggests that the charged random walk determines these global graph properties by using only local search algorithms. The results agree with mean-field theory on tree structures, while the numerical method is applicable to graphs of any complexity. Received 26 August 2002 Published online 29 November 2002     

Growing random networks with fitness

Three models of growing random networks with fitness-dependent growth rates are analysed using the rate equations for the distribution of their connectivities. In the first model (A), a network is built by connecting incoming nodes to nodes of connectivity k and random additive fitness η, with rate (k−1)+η. For η>0 we find the connectivity distribution is power law with exponent γ=〈η〉+2. In the second model (B), the network is built by connecting nodes to nodes of connectivity k, random additive fitness η and random multiplicative fitness ζ with rate ζ(k−1)+η. This model also has a power law connectivity distribution, but with an exponent which depends on the multiplicative fitness at each node. In the third model (C), a directed graph is considered and is built by the addition of nodes and the creation of links. A node with fitness (α,β), i incoming links and j outgoing links gains a new incoming link with rate α(i+1), and a new outgoing link with rate β(j+1). The distributions of the number of incoming and outgoing links both scale as power laws, with inverse logarithmic corrections.     

Optimal communication schemes in a complex network: From trees to bottleneck networks

The robustness of a communication scheme in a complex network may depend on the location of distinguished nodes. We collect different approaches to the idea of vulnerability and we give methods that help us to decide the good spots for the leader nodes. More specifically, we present a constructive method that yields the best location in a communication scheme for a leader node in the case that the underlying network is tree-shaped and show how it can be used for more general networks. In order to do that we consider a local approach via the bottleneck tree associated to a given node, as well as a uniform a approach by means of the so-called bottleneck network for several communication topologies.     

波长重用-扩大基于单纤连接节点的WDM星形单跳网容量

针对可利用的有限信道波长数对基于单纤连接节点的WDM星形单跳网容量限制问题,本文提出了一种有效的解决方案-波长重用.根据该方案,在信道波长数一定的条件下,至少可使网络所支持的节点数-网络容量扩大一倍;在网络节点数不变时,则可大大减少网络节点的排队时延,缓和网络中各通信节点对数据信道波长使用权的竞争矛盾,使网络吞吐量增加1～3倍,有效地改善网络性能.本文首先论述了该基于单纤连接节点的波长重用WDM星形单跳网结构,接着分析了网络的波长重用特性,进而对所要求的光放大器增益和输出功率进行了计算;最后计算了网络的最大节点数和最大信道波长数.     

Transport in weighted networks: partition into superhighways and roads

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality--the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.     

Better synchronizability predicted by a new coupling method

In this paper, inspired by the idea that different nodes should play different roles in network synchronization, we bring forward a coupling method where the coupling strength of each node depends on its neighbors' degrees. Compared with the uniform coupled method and the recently proposed Motter-Zhou-Kurths method, the synchronizability of scale-free networks can be remarkably enhanced by using the present coupling method, and the highest network synchronizability is achieved at β=1 which is similar to a method introduced in [AIP Conf. Proc. 776, 201 (2005)].     

基于节点拓扑特征的中国基金公司共持网络持股行为波动相关性

选取2003—2012年期间半年度中国基金公司持上市公司股票份额面板数据为样本数据,以基金公司为节点,以同一时刻共持同一家上市公司股票关系为边,以同一时刻共持的上市公司数量为权重,构建中国基金公司共持关系结构等价加权网络(简称共持网络).结合统计物理学等方法,分析了共持网络的拓扑结构稳定性及具有不同拓扑特征值的节点随时间演变过程中与共持网络中三类节点集合持股行为波动相关性.三类节点集合分别为t-1时刻基于某一股票形成的共持关系完全连通子图节点集合(第一类节点集合)、t-1时刻共持网络中非完全连通子图的节点集合(第二类节点集合)、t时刻新进入共持网络的节点集合(第三类节点集合).分析结果显示:1)节点与第二类节点集合持股行为波动呈正相关,且相关系数随着节点集聚系数的增强而增大;2)只有当节点的度和点强度值较高时,节点与第一类和第二类节点集合的持股行为呈正相关;3)不同拓扑特征条件下的节点与第三类节点集合的持股行为均不存在波动相关性.本文提供了一个研究持股行为相关性的新思路,并为进一步研究股票市场结构等价网络及节点重要性差异提供了基础.     

A Single-Star Multi-Ring Structure of Self-Healing Wavelength Division Multiplexing Optical Access Network

Abstract

A simple single-star multi-ring structure of multi-wavelength optical access network for enlarging network scale and protecting distribution fiber is presented. In this scheme, the ring structure enables optical network units to switch automatically to a protection link when the distribution fiber fails, and a star structure is adopted to weaken the sphere of the distribution fiber failure's influence. The simple combination of these two structures greatly increases the number of subscribers and minimizes costs of network. The network's survivability can also be better than that of a star network or ring network. In addition, it can easily be upgraded from an existing star network, so this article also proposes a method to update the existing star network. The simulation result shows the structure is of good performance.     

虚拟网络行为对互联网整体特性的影响

虚拟网络是一种依赖Internet基础设施所提供的传输能力，但又具有独立拓扑结构和信息传递规则的应用层网络行为逻辑网络.提出了耦合虚拟网络行为与物理节点的抽象模型，对一类典型的虚拟网络逻辑拓扑给互联网整体特性带来的影响进行了分析.研究表明在虚拟网络作用下，节点数据包排队长度存在相变特性，但相变临界点比对规则网络发生了明显左移，网络性能相对恶化.当数据包注入速率小于相变临界速率时，节点数据包排队长度不相关或短程相关；在接近临界速率处，节点数据包排队长度长程相关，幂指数H增大，网络获得更强的长程相关性.同时，在注入速率大于或等于临界速率时，虚拟网络行为使网络呈现出一致的长程相关特性.     

Power control of optical CDMA star networks

In this paper, we apply the power control concept to optical CDMA star networks. Two approaches are considered, namely, centralized and distributed power control. Both approaches are used to optimize the optical transmit power and to maximize network capacity in terms of the number of users satisfying a target signal to interference (SIR) ratio. Centralized algorithms result in the optimum power vector while distributed algorithms are more suitable for practical system implementation and eliminate the need for a centralized control node. Both analytical and simulation results show significant improvement in the performance of the power controlled optical CDMA system. For instance, in a network of 31 nodes, a doubling of the capacity as compared to the non power control case is obtained. Furthermore, we show in the interference-limited case that the network performance is upper bounded by the number of nodes and the correlation properties of the employed code rather than network attenuation and optical fiber lengths. The concept of network partitioning is then introduced to simplify optimum power calculations. Using network partitioning, we find in the interference-limited case that the optical fibers after the star coupler are irrelevant to the optimum power evaluation.     

Continuum Percolation with Unreliable and Spread-Out Connections

We derive percolation results in the continuum plane that lead to what appears to be a general tendency of many stochastic network models. Namely, when the selection mechanism according to which nodes are connected to each other, is sufficiently spread out, then a lower density of nodes, or on average fewer connections per node, are sufficient to obtain an unbounded connected component. We look at two different transformations that spread-out connections and decrease the critical percolation density while preserving the average node degree. Our results indicate that real networks can exploit the presence of spread-out and unreliable connections to achieve connectivity more easily, provided they can maintain the average number of functioningconnections per node.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Synchronization of networks

We study the synchronization of coupled dynamical systems on networks. The dynamics is governed by a local nonlinear oscillator for each node of the network and interactions connecting different nodes via the links of the network. We consider existence and stability conditions for both single- and multi-cluster synchronization. For networks with time-varying topology we compare the synchronization properties of these networks with the corresponding time-average network. We find that if the different coupling matrices corresponding to the time-varying networks commute with each other then the stability of the synchronized state for both the time-varying and the time-average topologies are approximately the same. On the other hand, for non-commuting coupling matrices the stability of the synchronized state for the time-varying topology is in general better than the time-average topology.