M-G-P型复杂网络中有寿命节点的进入退出机制

现实中复杂网络结构复杂,形式多样,处在高度动态变化的过程.为了更好地理解真实网络的演化,基于复杂网络的特性进行分析,建立了Poissotn连续时间增长节点具有寿命的M-G-P型复杂网络模型,模型中包括:新节点加入、节点老化和老节点退出等,基于齐次马尔可夫链对模型的度分布进行计算,得出M-G-P型网络的度分布符合幂律分布,模型和BA模型一样能产生指数γ=3的无标度网络,验证了导致无标度网络度分布特征起关键性作用的是链接的偏好特性.     

A new Branch and Bound method for a discrete truss topology design problem

Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas.     

一组一点外推的数值积分公式的提出与验证

通过利用拉格朗日多项式对等间距的离散采样数据进行函数逼近,就相等间距外推一点进行积分,得到了具有一定未来预测能力的一组一点外推的数值积分公式.计算机数值实验的结果表明了公式的有效性,即应用公式预测的积分结果可以达到一个较高的精度.     

Summing over a network without revealing summands

Consider a network in which each node possesses a secret member of a finite abelian group. In this paper we present a protocol by which the nodes can compute the sums of their secret elements without revealing them to each other. The security against discovery of the secret values as a result of conspiracies among nodes or compromise of channels between nodes is shown to depend on the connectivity of the graph defined by the network. Moreover, we are able to quantify exactly the amount of information revealed as a result of a conspiracy of a given set of nodes or compromise of a given set of channels.     

Modeling cooperation on a class of distribution problems

In this paper we study models of cooperation between the nodes of a network that represents a distribution problem. The distribution problem we propose arises when, over a graph, a group of nodes offers certain commodity, some other nodes require it and a third group of nodes neither need this material nor offer it but they are strategically relevant to the distribution plan. The delivery of one unit of material to a demand node generates a fixed profit, and the shipping of the material through the arcs has an associated cost. We show that in such a framework cooperation is beneficial for the different parties. We prove that the cooperative situation arising from this distribution problem is totally balanced by finding a set of stable allocations (in the core of an associated cooperative game). In order to overcome certain fairness problems of these solutions, we introduce two new solution concepts and study their properties.     

Routeing in a Network with Multi-Class Links

Consider a communication network with certain nodes and different types of links. In addition to the normal link cost, a transformation cost is charged if the incoming link and the outgoing link are of different types. An optimal routeing from a given node to its destination node is sought. The major difficulty in handling this problem is that the principle of optimality does not hold. A model with node separation is built to overcome this difficulty. By using the new model, the original routeing problem is no more than a shortest-path problem. Hence, we can implement this model to current electronic switching machines.     

Synchronization for a class of complex dynamical networks with time-delay

In this study, the synchronization problem is addressed for a class of complex dynamical networks in which every identical node is a time-delayed Lur’e system. Delay-dependent and delay-independent synchronization criteria are established through a decoupling technique, which reduces a group of high-dimensional linear matrix inequalities (LMIs) to the test of two groups of lower-dimensional LMIs. An extension to the synchronization of discrete-time Lur’e networks with time delay is also studied. The efficiency and applicability of the proposed methodology is demonstrated by a numerical example through simulation.     

On a matrix-based measure of the degree of coreness of a node in a network

The paper focuses on the right and left eigenvectors of a network matrix that belong to the largest eigenvalue. It is shown that each of vector entries measures the walk centrality of the corresponding node’s position in the network’s link structure and of the positions of the node’s adjacent nodes; as a result, it indicates to which degree the node can be associated with the structure’s core, i.e., the structural coreness of the node. The relationship between the vectors’ coordinates and the position of the nodes, as well as the actual computation of the coordinates, is based on an iterative computational scheme known as the power method. The paper studies the method’s convergence for networks of different structure. Some possible applications are discussed. The paper also includes a numerical example dealing with a real network of 197 nodes and 780 links.     

基于关系网络的大规模交互式群体评价方法

针对大规模交互式群体评价中如何实现群体意见的有效集结问题,以关系网络为切入点,提出了一种基于关系网络结构的群体评价方法。首先,将评价者视为网络节点,并通过计算节点之间的正负相关系数来构造关系矩阵;其次,设计节点中心度和子群凝聚度,以度量节点和子群的重要性;然后,测量群体评价信息的一致性和稳定性,以此确定交互终止条件;最后,引入阶段权重以集结交互阶段的评价信息,并对最终结果排序。算例验证了该方法的适用性和有效性。     

Computing a graph's period quadratically by node condensation

A condensation algorithm for finding the period and cyclic classes of an n node strongly connected graph (or equivalently, the period of an n state irreducible Marcov chain) is given for which an upper bound on the number of operations is proportional to n². This substantially improves upon the upper bounds of the two existing algorithms known to us, both of which are proportional to n⁴. The idea of our method is this. The set of nodes accessible in one step from some node 1, say, belong to a common cyclic class and so can be “condensed” into a single node. Similarly, the set of nodes accessible in one step from that condensed node belong to a common cyclic class and so can be condensed into a single node. After at most 2n?2 repetitions of this procedure, the resulting graph is a circuit whose length is the period of the original graph and each of whose nodes is a condensation of a cyclic class in the original graph.     

基于同步模型的查办群体性腐败案件策略研究

为了更有效地查办群体性腐败案件,首先论述了引入同步理论进行研究的可行性.其次对腐败群体各节点的决策同步过程进行了定量分析,阐释了腐败群体规避调查的决策机理.最后提出了查办群体性腐败案件的相关策略,为腐败问题的研究提供了新的视角.     

多源点多汇点网络系统可靠度的解析表示

本文研究了基于最小路径描述的多源点多汇点网络系统可靠性问题。定义了最小路径矩阵的几种运算,利用所定义的运算,将多源点多汇点网络系统转化为等价的单源点单汇点网络系统,并给出了由子系统可靠度精确表示网络系统可靠度的解析表达式。这种解析表达是非常重要的,它是系统可靠性的理论研究与实际应用的一个极为有效的工具。     

The competitive salesman problem on a network: a worst-case approach

We provide a complexity analysis of the problem of optimal routing of a server on a transportation network in the presence of a competing server. The server that reaches a node first gets the profit from the node. The objective is to maximize the worst-case profit.     

Modeling a supply chain using a network of queues

In this paper, a supply chain is represented as a two-input, three-stage queuing network. An input order to the supply chain is represented by two stochastic variables, one for the occurrence time and the other for the quantity of items to be delivered in each order. The objective of this paper is to compute the minimum response time for the delivery of items to the final destination along the three stages of the network. The average number of items that can be delivered with this minimum response time constitute the optimum capacity of the queuing network. After getting serviced by the last node (a queue and its server) in each stage of the queuing network, a decision is made to route the items to the appropriate node in the next stage which can produce the least response time.     

A decomposition approach for solving a broadcast domination network design problem

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f _i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f _k -value whose shortest distance to node j is no more than f _k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

Synchronization of chaotic dynamical network with unknown generally time-delayed couplings via a simple adaptive feedback control

In this paper, based on the principle of functional differential equations, a simple adaptive feedback controller is proposed to synchronize the network with unknown generally time-delayed coupling functions. Unlike the other control schemes, we design the controllers by the output of each node. The advantage of this scheme is that we need not to know the concrete structure of coupling functions or a solution of node system in advance. Moreover, an illustrative example is considered and numerical simulations are performed to demonstrate the effectiveness of this control scheme. The numerical simulation results show that our method is valid and robust against the weak noise.     

Probabilistic consensus via polling and majority rules

In this paper, we consider lightweight decentralised algorithms for achieving consensus in distributed systems. Each member of a distributed group has a private value from a fixed set consisting of, say, two elements, and the goal is for all members to reach consensus on the majority value. We explore variants of the voter model applied to this problem. In the voter model, each node polls a randomly chosen group member and adopts its value. The process is repeated until consensus is reached. We generalise this so that each member polls a (deterministic or random) number of other group members and changes opinion only if a suitably defined super-majority has a different opinion. We show that this modification greatly speeds up the convergence of the algorithm, as well as substantially reducing the probability of it reaching consensus on the incorrect value.     

Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication

We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.     

Minimal spanning trees with a constraint on the number of leaves

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a “degree-1” terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in “degree-1” terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of “degree-1” terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.