A new method for constructing infinite families of k-tight optimal double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. DLN has been widely used in the designing of local area networks and distributed systems. In this paper, a new method for constructing infinite families of k-tight optimal DLN is presented. For k = 0, 1, ..., 40, the infinite families of k-tight optimal DLN can be constructed by the new method, where the number n _k (t, a) of their nodes is a polynomial of degree 2 in t and contains a parameter a. And a conjecture is proposed.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is: for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained: (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

MC-based Algorithm for a telecommunication network under node and budget constraints

It is an important issue to design some performance indexes in order to measure the performance for a telecommunication network. Network analysis is an available approach to solve the performance problem for a real-life system. We construct a two-commodity stochastic-flow network with unreliable nodes (arcs and nodes all have several possible capacities and may fail) to model the telecommunication network. In which, all types of commodity are transmitted through the same network simultaneously and compete the capacities. This paper defines the system capacity as a 2-tuple vector, and then proposes a performance index, the probability that the upper bound of the system capacity equals a demand vector subject to the budget constraint. An upper boundary point is a vector representing the capacities of arcs and nodes, and is the maximal vector exactly meeting the demand vector. A simple algorithm based on minimal cuts (or named MC-based algorithm) is then presented to generate all upper boundary points in order to evaluate the performance index. The storage and computational time complexity of this algorithm are also analyzed. The performance evaluation for the multicommodity case can be extended easily.     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

基于网络拓扑结构的重要节点发现算法

复杂网络中的重要节点发现在现实生活中有着广泛的应用价值。传统重要节点发现方法可分为局部发现和全局发现两类算法,全局发现算法中最具代表性的是特征向量中心性算法(Eigenvector Centrality, EC),EC算法将所有节点归为一个社区并利用邻居节点重要性反馈计算节点的影响力大小,具有较高的计算效率和识别精度。但是,EC算法忽略了网络的拓扑结构,未考虑到真实网络中节点所在社区的结构特征。为此,本文提出一种基于网络拓扑结构的可达中心性算法(Accessibility Centrality, AC),首先利用邻接矩阵作为反馈路径,在反馈过程中计算不同路径下的节点整体影响力。同时,利用影响力传递过程中的噪音干扰特性,修正每一路径长度下节点整体影响力大小,最后利用修正结果得到AC值。为评估AC算法,本文利用两种传染病模型模拟节点影响力在四组真实网络中的传播过程,并引入其他四种算法进行对比验证。实验结果表明,与其他算法相比,AC算法可以更准确、有效地识别出有具有影响力的重要节点。     

A method for maximizing the reliability coefficient of a communications network

The most common idea of network reliability in the literature is a numerical parameter calledoverall network reliability, which is the probability that the network will be in a successful state in which all nodes can mutually communicate. Most papers concentrate on the problem of calculating the overall network reliability which is known to be an NP hard problem. In the present paper, the question asked is how to find a method for determining a reliable subnetwork of a given network. Givenn terminals and one central computer, the problem is to construct a network that links each terminal to the central computer, subject to the following conditions: (1) each link must be economically feasible; (2) the minimum number of links should be used; and (3) the reliability coefficient should be maximized. We argue that the network satisfying condition (2) is a spanning arborescence of the network defined by condition (1). We define the idea of thereliability coefficient of a spanning arborescence of a network, which is the probability that a node at average distance from the root of the arborescence can communicate with the root. We show how this coefficient can be calculated exactly when there are no degree constraints on nodes of the spanning arborescence, or approximately when such degree constraints are present. Computational experience for networks consisting of up to 900 terminals is given.This report was prepared as part of the activities of the Management Science Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047–048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

基于失效边数概率分布的K-终端网络重要度计算方法

重要度是现代网络薄弱环节识别的常用工具,其能量化网络不同的边对网络可靠性的影响程度。以往的K-终端网络重要度计算方法需已知网络边的可靠性以及边发生失效相互独立的条件,不能满足现实网络对于网络重要度计算的需求。鉴于此,为了突破这些条件的限制,本文在给定失效边数目的概率分布的背景下,发展K-终端网络重要度的计算方法,并提供一个十二面体网络的算例,验证了该计算方法的有效性和正确性。     

A hybrid algorithm to optimize RBF network architecture and parameters for nonlinear time series prediction

This paper proposes a novel hybrid algorithm for automatic selection of the proper input variables, the number of hidden nodes of the radial basis function (RBF) network, and optimizing network parameters (weights, centers and widths) simultaneously. In the proposed algorithm, the inputs and the number of hidden nodes of the RBF network are represented by binary-coded strings and evolved by a genetic algorithm (GA). Simultaneously, for each chromosome with fixed inputs and number of hidden nodes, the corresponding parameters of the network are real-coded and optimized by a gradient-based fast-converging parameter estimation method. Performance of the presented hybrid approach is evaluated by several benchmark time series modeling and prediction problems. Experimental results show that the proposed approach produces parsimonious RBF networks, and obtains better modeling accuracy than some other algorithms.     

基于TOPSIS模型的机场网络节点重要度评估

在机场网络中单个机场节点的失效往往会对其他的节点产生影响,特别是关键节点的失效会波及整个网络.准确客观的识别重要节点机场关乎整个机场网络的安全运营.本文分析了机场网络拓扑特性中的度、集聚系数和接近度指标,考虑了机场旅客吞吐量和所在城市人口等交通经济特性指标,使用熵权法确定权重的基础上,应用TOPSIS法构建综合评价体系模型,最后以华东地区机场网络为例进行节点重要度排序.结果表明与单一指标的评估结果相比,该方法更加全面客观的确定不同属性指标的权重,避免了不同指标取值的差异性,使评价更加全面,更符合机场网络实际运营情况.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

一种基于tit-for-tat策略的伪度优先算法

复杂网络中的两个节点,随着时间的推移,由于利益冲突,可能会采取一些行动,合作或者背叛,对于背叛过多的节点,需要断开重连,这也恰好反映了现实情况.根据重复博弈中的tit-for-tat策略,提出了一种伪度优先算法,研究了在不改变节点个数情况下,复杂网络的统计特性.仿真结果表明,该算法并不改变网络的无标度特征,但是改变了最大度的节点分布,并且大大提高了网络的聚集系数.另外,还研究了对网络社团结构的影响,结果表明可以优化网络的社团结构.     

Design of Stacked Self-Healing Rings Using a Genetic Algorithm

Ring structures in telecommunications are taking on increasing importance because of their self-healing properties. We consider a ring design problem in which several stacked self-healing rings (SHRs) follow the same route, and, thus, pass through the same set of nodes. Traffic can be exchanged among these stacked rings at a designated hub node. Each non-hub node may be connected to multiple rings. It is necessary to determine to which rings each node should be connected, and how traffic should be routed on the rings. The objective is to optimize the tradeoff between the costs for connecting nodes to rings and the costs for routing demand on multiple rings. We describe a genetic algorithm that finds heuristic solutions for this problem. The initial generation of solutions includes randomly-generated solutions, complemented by seed solutions obtained by applying a greedy randomized adaptive search procedure (GRASP) to two related problems. Subsequent generations are created by recombining pairs of parent solutions. Computational experiments compare the genetic algorithm with a commercial integer programming package.     

基于网络结构特征的大规模虚假评论群组识别

目前识别虚假评论的方法主要基于评论内容的文本特征和评论者的行为特征,然而评论文本与评论者行为容易被伪造和模仿,且这两类方法只能对虚假评论逐个识别,本文考虑了虚假评论的网络结构特征,通过分析评论者的网络行为及评论者节点间的网络结构特征定义相邻节点多样性与自相似性,利用累积分布函数估计其概率并合成网络行为得分,以得分高的可疑产品为种子建立2-hop子图,筛选子图中高度相似的虚假评论候选群组,利用GroupStrainer、HDBSCAN等算法对其进行聚类合并,以发现隐藏的虚假评论群组。以亚马逊四类最畅销的产品数据集为样本进行实证分析的结果表明,文中提出的方法能够有效识别隐藏较深的大规模虚假评论群组,综合群组内容的统计特征分析发现,虚假评论群组对目标产品的攻击模式存在产品类别差异,虚假评论群组比真实评论者对目标产品具有更强的集中度,但同时也会利用其它非目标产品对自身进行伪装以弱化其可疑性。     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Shortest Path Auction Algorithm Without Contractions Using Virtual Source Concept

In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a virtual source.We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n ²), where n is the number of nodes.Numerical experimentsare reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.     

High-Dimensional Covariance Matrix Estimation Based on Network

A new method for estimating high-dimensional covariance matrix based on network structure with heteroscedasticity of response variables is proposed in this paper. This method greatly reduces the computational complexity by transforming the high-dimensional covariance matrix estimation problem into a low-dimensional linear regression problem. Even if the size of sample is finite, the estimation method is still effective. The error of estimation will decrease with the increase of matrix dimension. In addition, this paper presents a method of identifying influential nodes in network via covariance matrix. This method is very suitable for academic cooperation networks by taking into account both the contribution of the node itself and the impact of the node on other nodes.     

Cluster mixed synchronization via pinning control and adaptive coupling strength in community networks with nonidentical nodes

In this paper, complex networks with community structure and nonidentical nodes are investigated. The cluster mixed synchronization of these networks is studied by using some linear pinning control schemes. Only the nodes in one community which have direct connections to the nodes in other communities are controlled. Adaptive coupling strength method is adopted to achieve the synchronization as well. According to Lyapunov stability theory, several sufficient conditions for the network to achieve cluster mixed synchronization are derived. Numerical simulations are provided to verify the correctness and the effectiveness of the theoretical results.     

Virtual Path Design in Service-Specific ATM Networks

This paper addresses the problem of virtual path management in ATM networks, which is the problem of jointly selecting efficient virtual trunk routes and sizing them to meet end-to-end grade-of-service requirements. The problem is posed over capacitated networks and is formulated as a two-level multi-commodity network flow problem with linear side-constraints (physical layer capacity) and non-linear side constraints (end-to-end/link blocking). Through a variety of examples we show the method (i) generates solutions that agree with engineering judgement, (ii) can solve VP layout management for realistic size networks (of up to 200 nodes) in reasonable time and (iii) provides upper bounds on how far the solution strays from the mathematically optimal design.