Lattice flows in networks

We consider flows in networks analogous to numerical flows but such that values of arc capacities are elements of a lattice. We present an analog of the max-flow min-cut theorem. However, finding the value of the maximum flow for lattice flows is based on not this theorem but computations in the algebra of matrices over the lattice; in particular, the maximum flow value is found with the help of transitive closure of flow capacity functions. We show that there exists a correspondence between flows and solutions of special-form systems of linear equations over distributive lattices.     

Multicommodity flows in tree-like networks

A problem of finding multicommodity minimum-cost flows in tree-like networks is considered. To solve this problem, an algorithm based on the reduction to a problem of finding a single-commodity flow in a network of arbitrary structure is proposed. For single-commodity flows in tree-like networks, an algorithm using a procedure of border reduction is used.     

On a simple method for testing independencies in Bayesian networks

Testing independencies is a fundamental task in reasoning with Bayesian networks (BNs). In practice, d‐separation is often used for this task, since it has linear‐time complexity. However, many have had difficulties understanding d‐separation in BNs. An equivalent method that is easier to understand, called m‐separation, transforms the problem from directed separation in BNs into classical separation in undirected graphs. Two main steps of this transformation are pruning the BN and adding undirected edges. In this paper, we propose u‐separation as an even simpler method for testing independencies in a BN. Our approach also converts the problem into classical separation in an undirected graph. However, our method is based upon the novel concepts of inaugural variables and rationalization. Thereby, the primary advantage of u‐separation over m‐separation is that m‐separation can prune unnecessarily and add superfluous edges. Our experiment results show that u‐separation performs 73% fewer modifications on average than m‐separation.     

Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities.     

Decision-making and opinion formation in simple networks

In many networked decision-making settings, information about the world is distributed across multiple agents and agents’ success depends on their ability to aggregate and reason about their local information over time. This paper presents a computational model of information aggregation in such settings in which agents’ utilities depend on an unknown event. Agents initially receive a noisy signal about the event and take actions repeatedly while observing the actions of their neighbors in the network at each round. Such settings characterize many distributed systems such as sensor networks for intrusion detection and routing systems for Internet traffic. Using the model, we show that (1) agents converge in action and in knowledge for a general class of decision-making rules and for all network structures; (2) all networks converge to playing the same action regardless of the network structure; and (3) for particular network configurations, agents can converge to the correct action when using a well-defined class of myopic decision rules. These theoretical results are also supported by a new simulation-based open-source empirical test-bed for facilitating the study of information aggregation in general networks.     

On delay robustness analysis of a simple control algorithm in high-speed networks

This paper focuses on the robustness analysis of a simple (second-order) control algorithm for data transfer in high-speed networks. The model under consideration (derived using a fluid approximation technique) can be found in Izmailov (SIAM J. Contr. Optimiz. 34 (1996) 1767). The novelty of the approach lies in characterizing the stability of the scheme in the delay-parameter space (where the delays correspond to the control-time interval, and to the round-trip time, respectively). Thus, we shall compute some delay-insensitive measures for the algorithm which give upper and lower bounds for the uncertainty in the knowledge of the round-trip times.     

无穷网络流的顶点控制

本文研究了无穷网络上的传输过程并在一个顶点对其进行控制.描绘了所有的可控状态,并在最大可控的顶点给出了卡尔曼型判断标准.本文的结果是近期一个相似结果的推广.     

Quantum interference of photons in simple networks

A theoretical investigation of quantum interference of photonic multistates in simple devices like beam splitters, Mach–Zehnder interferometers and double-loop devices are presented. Variable transmission and reflection coefficients as well as variable phase shifts are included in order to calculate quantum states and mean photon numbers at the outputs. Various input states like Fock states and coherent states and a combination of both are considered as well as squeezed states. Two methods are applied: The direct matrix method and the method of unitary representation. Remarkable results appear in a double-loop interferometer where for special phase shifts equal mean photon numbers in the three output ports are obtained provided certain input states are given. A computerized simulation of general networks using various input Fock states is presented. Multistate devices will be used in future linear quantum computation and quantum information processing schemes.     

Multilamination of flows in planar networks of rotating microchannels

We describe a new multilamination technique to accelerated mixing of centrifugally pumped flows through a simple network of preferentially radial, low-aspect-ratio microchannels. Mixing by multilamination is enforced by planar split-and-recombine structures, consisting of a common inlet for two concurrent centrifugal flows, and a transient region of parallel microchannels which merge again into one common outlet. A repatterning of flow is observed in each parallel channel which is induced by the Coriolis pseudo force. In a distinct regime of the parameter space spanned by the speed of rotation, the channel geometry as the viscosity (and density) of the liquids, a multilamination of flow is achieved at the entrance of the common outlet channel. We also present parallelization and cascading strategies to further enhance the homogeneity and throughput of mixing by multilamination.     

Optimal routing of data flows in wireless sensor networks

A general approach to optimization of data packet routes in wireless sensor networks on the basis of the Ford-Bellman algorithm taking into account variations in node composition and network topology, channel throughputs, and node loads is proposed. Algorithms for calculating criterion functions for optimizing routes in terms of some set of criteria are constructed.     

区分服务网络中基于主动队列管理的病态流控制

在区分服务（Differentiated Services,DiffServ）网络中,为了消除病态流对确定性转发（Assured Forwarding,AF）服务的不良影响,提出了一种基于RIO（RED IN and OUT）的主动队列管理机制RIO SD。这种机制不需要在核心路由器维护每一个流的状态,而是通过观测虚拟队列的丢包历史记录来鉴别病态流,并通过虚拟队列的前置滤波器加大病态流的丢包率,实现对病态流的控制。仿真结果表明RIO SD可以有效抑制病态流对带宽的占用,提高其他正常流的性能。     

Integrated radial-basis-function networks for computing Newtonian and non-Newtonian fluid flows

This paper presents a radial-basis-function (RBF) collocation method for the simulation of two-dimensional fluid-flow problems. To improve the stability of a discrete solution and the quality of derivative approximations, the present RBF networks (RBFNs) are constructed through integration instead of conventional differentiation. Special attention is given to the following two topics: (i) the effective use of integration constants in the solution of the Navier–Stokes equations and (ii) the employment of “local” integrated RBFNs to handle flows with fine structures. Different types of geometries and fluids are considered. The accuracy of the present technique is demonstrated through the solution of several benchmark test problems.     

On two- and three-dimensional expansion flows

This paper gives consideration to incompressible Newtonian flows through two- and three-dimensional expansions. Through a time-stepping scheme, steady-state solutions are sought for both small and large expansion ratios. The flow structure in the two-dimensional case can be significantly different from that of the three-dimensional equivalent, depending on the expansion ratio. Both lip and salient corner vortices are reported, and comparisons are made against available experimental data.     

Some simple distributed algorithms for sparse networks

Summary. We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most colours, and maximal matchings can be computed within deterministic rounds, where is the maximum degree of the network. We also show how to find maximal independent sets and -vertex colourings within deterministic rounds. All hidden constants are very small and the algorithms are very simple. Received: August 2000 / Accepted: November 2000     

A simple algorithm for clock synchronization in transputer networks

In a distributed system based on Transputer components there is one clock for each processing element, and the definition of the global system time requires the choice of a hardware or software synchronization method. This paper describes the RING_SYNC algorithm, based on a ring-structured synchronization scheme. RING_SYNC has no provision for fault tolerance, but it introduces little overhead, thanks to the optimization of both the number of messages exchanged at sync time and the resynchronization frequency. The implementation of the algorithm together with the tests performed for measuring the synchronization error and their results are discussed extensively, and some typical applications are pointed out.     

Employing hierarchical Bayesian networks in simple and complex emotion topic analysis

Traditional emotion models, when tagging single emotions in documents, often ignore the fact that most documents convey complex human emotions. In this paper, we join emotion analysis with topic models to find complex emotions in documents, as well as the intensity of the emotions, and study how the document emotions vary with topics. Hierarchical Bayesian networks are employed to generate the latent topic variables and emotion variables. On average, our model on single emotion classification outperforms the traditional supervised machine learning models such as SVM and Naive Bayes. The other model on the complex emotion classification also achieves promising results. We thoroughly analyze the impact of vocabulary quality and topic quantity to emotion and intensity prediction in our experiments. The distribution of topics such as Friend and Job are found to be sensitive to the documents’ emotions, which we call emotion topic variation in this paper. This reveals the deeper relationship between topics and emotions.     

Computation of functions of Hamiltonian and skew-symmetric matrices

In this paper we consider numerical methods for computing functions of matrices being Hamiltonian and skew-symmetric. Analytic functions of this kind of matrices (i.e., exponential and rational functions) appear in the numerical solutions of ortho-symplectic matrix differential systems when geometric integrators are involved. The main idea underlying the presented techniques is to exploit the special block structure of a Hamiltonian and skew-symmetric matrix to gain a cheaper computation of the functions. First, we will consider an approach based on the numerical solution of structured linear systems and then another one based on the Schur decomposition of the matrix. Splitting techniques are also considered in order to reduce the computational cost. Several numerical tests and comparison examples are shown.     

A co-tree flows formulation for steady state in water distribution networks

This article describes a co-tree flows formulation for steady state simulation in water distribution networks, which reduces the original governing system of equations into a smaller set, expressed in terms of the co-tree chord flows. The formulation is derived from graph theory and matrix partitioning. The reduction in the size of the set of equations does not require any new conditions on the initial solution estimate, unlike the loop flow correction method. The proposed formulation is numerically equivalent to the link flow method. However, it requires, about 5% for the Jacobian memory storage requirements of the link flow method, thereby also drastically reducing the time of execution for solving the resulting nonlinear system, as well. Furthermore, the Jacobian matrix of the new method is symmetrical, which can reduce the memory storage by half. Thus, even for large distribution systems, there is no need for sparse matrix solvers, which trade off the storage memory with time of execution in order to manage the data requirements.     

Energy-aware QoS uplink scheduling for UGS traffic flows in WiMAX networks

This paper presents a new energy-aware QoS scheduling and call admission control algorithm for WiMAX IEEE 802.16e wireless access standard. The scheduling algorithm works at MAC layer and is designed towards minimizing power consumption at mobile stations supporting multiple Unsolicited Grant Service (UGS) connections, while meeting the QoS requirements of the connections. The algorithm uses a novel idea to fill an active OFDM frame as much as possible in order to increase the number of OFDM frames in sleep mode at mobile station. The algorithm also considers the dynamic nature of connection joining and termination. We used Voice-over-IP (VoIP) traffic connection models for UGS traffic flows to simulate and validate algorithm. The simulation model was tested using VoIP codec types with different rates and QoS requirements. Simulation results show that a power saving in the range of 50–75% can be easily achieved at the mobile station under low-to-moderate traffic intensities.