Tight Bounds on the Information Rate of Secret Sharing Schemes

A secret sharing scheme is a protocol by means of which a dealer distributes a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s whereas any other subset of P, non-qualified to know s, cannot determine anything about the value of the secret.In this paper we provide a general technique to prove upper bounds on the information rate of secret sharing schemes. The information rate is the ratio between the size of the secret and the size of the largest share given to any participant. Most of the recent upper bounds on the information rate obtained in the literature can be seen as corollaries of our result. Moreover, we prove that for any integer d there exists a d-regular graph for which any secret sharing scheme has information rate upper bounded by 2/(d+1). This improves on van Dijk's result dik and matches the corresponding lower bound proved by Stinson in [22].     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

ALOHA networks: a game-theoretic approach

In this paper we consider a wireless network consisting of various nodes, where transmissions are regulated by the slotted ALOHA protocol. Nodes using the protocol behave autonomously, and decide at random whether to transmit in a particular time slot. Simultaneous transmissions by multiple nodes cause collisions, rendering the transmissions useless. Nodes can avoid collisions by cooperating, for example by exchanging control messages to coordinate their transmissions. We measure the network performance by the long-term average fraction of time slots in which a successful transmission takes place, and we are interested in how to allocate the performance gains obtained from cooperation among the nodes. To this end we define and analyze a cooperative ALOHA game. We show that this type of game is convex and we consider three solution concepts: the core, the Shapley value, and the compromise value. Furthermore, we develop a set of weighted gain splitting (WGS) allocation rules, and show that this set coincides with the core of the game. These WGS allocation rules can be used to provide an alternative characterization of the Shapley value. Finally, we analyze the sensitivity of the cooperative solution concepts with respect to changes in the wireless network.     

Gradient-Constrained Minimum Networks. III. Fixed Topology

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).     

Joint Modeling of Multiple Network Views

Latent space models (LSM) for network data rely on the basic assumption that each node of the network has an unknown position in a D-dimensional Euclidean latent space: generally the smaller the distance between two nodes in the latent space, the greater their probability of being connected. In this article, we propose a variational inference approach to estimate the intractable posterior of the LSM. In many cases, different network views on the same set of nodes are available. It can therefore be useful to build a model able to jointly summarize the information given by all the network views. For this purpose, we introduce the latent space joint model (LSJM) that merges the information given by multiple network views assuming that the probability of a node being connected with other nodes in each network view is explained by a unique latent variable. This model is demonstrated on the analysis of two datasets: an excerpt of 50 girls from “Teenage Friends and Lifestyle Study” data at three time points and the Saccharomyces cerevisiae genetic and physical protein–protein interactions. Supplementary materials for this article are available online.     

Global controllability between steady supercritical flows in channel networks

We consider a tree‐like network of open channels with outflow at the root. Controls are exerted at the boundary nodes of the network except for the root. In each channel, the flow is modelled by the de St. Venant equations. The node conditions require the conservation of mass and the conservation of energy. We show that the states of the system can be controlled within the entire network in finite time from a stationary supercritical initial state to a given supercritical terminal state with the same orientation. During this transition, the states stay in the class of C1‐functions, so no shocks occur. Copyright 2004 John Wiley & Sons, Ltd.     

Hop constrained Steiner trees with multiple root nodes

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches.     

State-Dependent Coupling in General Networks

In this paper we extend a result which holds for the class of networks of quasireversible nodes to a class of networks constructed by coupling Markov chains. We begin with a network in which the transition rates governing the stochastic behaviour of the individual nodes depend only on the state of the node. Assuming that the network has an invariant measure, we construct another network with transition rates at each node depending on the state of the entire network, and obtain its invariant measure.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

On the optimization of bipartite secret sharing schemes

Optimizing the ratio between the maximum length of the shares and the length of the secret value in secret sharing schemes for general access structures is an extremely difficult and long-standing open problem. In this paper, we study it for bipartite access structures, in which the set of participants is divided in two parts, and all participants in each part play an equivalent role. We focus on the search of lower bounds by using a special class of polymatroids that is introduced here, the tripartite ones. We present a method based on linear programming to compute, for every given bipartite access structure, the best lower bound that can be obtained by this combinatorial method. In addition, we obtain some general lower bounds that improve the previously known ones, and we construct optimal secret sharing schemes for a family of bipartite access structures.     

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

Simulation of the effect of learning on the topology of the functional connectivity of neural networks

We introduce a procedure for simulating adaptive learning in neural networks and the effect this learning has on the way in which the functional connections between the nodes of the network are established. The procedure combines two mechanisms: firstly, the gradual dilution of the network through the elimination of synaptic weights in increasing order of magnitude, thus reducing the costs of the network structure. Secondly, to train the network as it is diluted so as not to compromise its performance pursuant to the proposed task. Considering different levels of learning difficulty, we compare the topology of the functional connectivities that result from the application of this procedure with those obtained using fMRI in healthy volunteers. According to our results, the topology of functional connectivities in healthy subjects can be interpreted as the product of a learning process with a specific degree of difficulty.     

New formulation and relaxation to solve a concave-cost network flow problem

In this paper we study a minimum cost, multicommodity network flow problem in which the total cost is piecewise linear, concave of the total flow along the arcs. Specifically, the problem can be defined as follows. Given a directed network, a set of pairs of communicating nodes and a set of available capacity ranges and their corresponding variable and fixed cost components for each arc, the problem is to select for each arc a range and identify a path for each commodity between its source and destination nodes so as to minimize the total costs. We also extend the problem to the case of piecewise nonlinear, concave cost function. New mathematical programming formulations of the problems are presented. Efficient solution procedures based on Lagrangean relaxations of the problems are developed. Extensive computational results across a variety of networks are reported. These results indicate that the solution procedures are effective for a wide range of traffic loads and different cost structures. They also show that this work represents an improvement over previous work made by other authors. This improvement is the result of the introduction of the new formulations of the problems and their relaxations.     

A Practical Protocol for Advantage Distillation and Information Reconciliation

Information-theoretic secret key agreement generally consists of three phases, namely, advantage distillation information reconciliation and privacy amplification. Advantage distillation is needed in the case when two legitimate users, Alice and Bob, start in a situation which is inferior to that of the adversary Eve. The aim for them is to gain advantage over Eve in terms of mutual information between each other. Information reconciliation enables Alice and Bob to arrive at a common string by error correction techniques. Finally they distill a highly secret string from the common string in the privacy amplification phase. For the scenario where Alice and Bob as well as Eve have access to the output of a binary symmetric source by means of (three) binary symmetric channels, there are several advantage distillation and information reconciliation protocols proposed.In this paper, we present a general protocol to implement both advantage distillation and information reconciliation. Simulation results are compared with known protocols. A connection between our protocol and the known protocols is given.     

Constructions for Anonymous Secret Sharing Schemes Using Combinatorial Designs

In an anonymous secret sharing scheme the secret can be reconstructed without knowledge ofwhich participants hold which shares.In this paper some constructions of anonymous secret sharing schemeswith 2 thresholds by using combinatorial designs are given.Let v(t,w,q)denote the minimum size of the setof shares of a perfect anonymous(t,w)threshold secret sharing scheme with q secrets.In this paper we provethat v(t,w,q)=(q)if t and w are fixed and that the lower bound of the size of the set of shares in[4]is notoptimal under certain condition.     

The exact values of the optimal average information ratio of perfect secret-sharing schemes for tree-based access structures

A perfect secret-sharing scheme is a method of distributing a secret among a set of participants such that only qualified subsets of participants can recover the secret and the joint shares of the participants in any unqualified subset is statistically independent of the secret. The set of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph \(G\) represents a participant and each edge of \(G\) represents a minimal qualified subset. The information ratio of a perfect secret-sharing scheme is defined as the ratio between the maximum length of the share given to a participant and the length of the secret. The average information ratio is the ratio between the average length of the shares given to the participants and the length of the secret. The infimum of the (average) information ratios of all possible perfect secret-sharing schemes realizing a given access structure is called the (average) information ratio of the access structure. Very few exact values of the (average) information ratio of infinite families of access structures are known. Csirmaz and Tardos have found the information ratio of all trees. Based on their method, we develop our approach to determining the exact values of the average information ratio of access structures based on trees.     

A compromise weight for multi-criteria group decision making with individual preference

In a multi-criteria group decision making process, it is often hard to obtain a solution due to the possible conflict preferences from different participants and the undeterministic weights assigned to each criterion. This problem can be defined as to identify a set of weights for the given criteria to achieve a compromise of the conflict on different preferences. When such a compromise weight does not exist, we need to adjust (to reverse or to withdraw) some or all of the preferences from different participants. This paper describes a minimax principle based procedure of preference adjustments with a finite number of steps to find the compromise weight. At each iteration, we either find the weight or identify some ‘wrong’ preferences. We also define a consistency index for each participant to measure the distance between the individuals' preference and the final group decision. Corresponding theoretical work is referred to in support of the procedure, and numerical examples are provided for illustration. This study is further extended to the case of multiple assessments.     

Predicting measurements at unobserved locations in an electrical transmission system

Electrical transmission systems consist of a huge number of locations (nodes) with different types of measurements available. Our aim is to derive a subset of nodes which contains almost sufficient information to describe the whole energy network. We derive a parameter set which characterises every single measuring location or node, respectively. Via analysing the behaviour of each node with respect to its neighbours, we construct a feasible random field metamodel over the whole transmission system. The metamodel is used to smooth the measurements across the network. In the next step we work with a subset of locations to predict the unobserved ones. We derive different graph kernels to define the missing covariance matrix from the neighbourhood structures of the network. This results in a metamodel that is able to smooth observed and predict unobserved locations in a spatial domain with non-isotropic distance functions.     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian

In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes must keep a distance of at least one. We prove three main results for a slightly generalized form of this embedding problem. First, given a set of vertices partitioning the graph into several or just one part, the barycenter of each part is embedded on the same side of the affine hull of the set as the origin. Second, there is an optimal realization of dimension at most the tree-width of the graph plus one and this bound is best possible in general. Finally, bipartite graphs possess a one dimensional optimal embedding.