Identifying the community structure of the international-trade multi-network

We study the community structure of the multi-network of commodity-specific trade relations among world countries over the 1992-2003 period. We compare structures across commodities and time by means of the normalized mutual information index (NMI). We also compare them with exogenous community structures induced by geography and regional trade agreements. We find that commodity-specific community structures are very heterogeneous and much more fragmented than that characterizing the aggregate ITN. This shows that the aggregate properties of the ITN may result (and be very different) from the aggregation of very diverse commodity-specific layers of the multi-network. We also show that commodity-specific community structures, especially those related to the chemical sector, are becoming more and more similar to the aggregate one. Finally, our findings suggest that geography-induced partitions of our set of countries are much more correlated with observed community structures than partitions induced by regional-trade agreements. This result strengthens previous findings from the empirical literature on trade.     

Asymmetric flow networks

This paper provides a new model of network formation that bridges the gap between the two benchmark game-theoretic models by Bala and Goyal (2000a) – the one-way flow model, and the two-way flow model – and includes both as limiting cases. As in both the said models, a link can be initiated unilaterally by any player with any other in what we call an “asymmetric flow” network, and the flow through a link towards the player who supports it is perfect. Unlike those models, there is friction or decay in the opposite direction. When this decay is complete there is no flow and this corresponds to the one-way flow model. The limit case when the decay in the opposite direction (and asymmetry) disappears corresponds to the two-way flow model. We characterize stable and strictly stable architectures for the whole range of parameters of this “intermediate” and more general model. A study of the efficiency of these architectures shows that in general stability and efficiency do not go together. We also prove the convergence of Bala and Goyal’s dynamic model in this context.     

Inclusion–exclusion principle for belief functions

The inclusion–exclusion principle is a well-known property in probability theory, and is instrumental in some computational problems such as the evaluation of system reliability or the calculation of the probability of a Boolean formula in diagnosis. However, in the setting of uncertainty theories more general than probability theory, this principle no longer holds in general. It is therefore useful to know for which families of events it continues to hold. This paper investigates this question in the setting of belief functions. After exhibiting original sufficient and necessary conditions for the principle to hold, we illustrate its use on the uncertainty analysis of Boolean and non-Boolean systems in reliability.     

线性函数的性质及其应用 线性函数的性质及其应用

给出了线性函数、部分线性函数和线性变量的定义,提出了它们的性质.根据上述定义,利用布尔代数中的基本定理和公式以及自双反函数和对称函数的定义对这些性质给出了证明.最后讨论了它们在逻辑综合以及计算逻辑函数的布尔差分中的应用.     

Complete on Average Boolean Satisfiability

We present in this paper a dynamic binary coding scheme α on CNF formulas ψ, and show that under a uniform distribution μ_α on binary string α(ψ), SAT is complete on average, where μ_α(ψ) is proportional to α(ψ)⁻²2^−α(ψ). We then show that there is k₀>2 such that for all kk₀, kSAT under μ_α is complete on average.     

A note on the paper “characterization of all optimal solutions and parametric maximal flows in networks” of G. Ruhe (optimization 16 (1985) 1, 51-61)

First it is shown that the implementation of the algorithm proposed in the considered paper may cause some problems if no further specification is made as to one of its steps. Secondly, such a specification is suggested.     

Formulation and computation of general financial equilibrium

In this paper a model of competitive financial equilibrium is introduced, which yields the optimal composition of assets and liabilities in each sector's portfolio, as well as the market clearing prices for each instrument. The variational inequality formulation of the equilibrium conditions is then utilized to establish existence and uniqueness properties of the solution pattern. Finally, an algorithm is proposed for the computation of the equilibrium pattern; the algorithm resolves the problem into simple network subproblems which can then be solved in closed form. The algorithm is then applied to an example.     

Term rank preservers of Boolean matrices

We obtain some characterizations of linear operators that preserve the term rank of Boolean matrices. That is, a linear operator over Boolean matrices preserves the term rank if and only if it preserves the term ranks 1 and k(≠1) if and only if it preserves the term ranks 2 and l(≠2). Other characterizations of term rank preservers are given.     

Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.     

Information spreading in Delay Tolerant Networks based on nodes’ behaviors

Information spreading in DTNs (Delay Tolerant Networks) adopts a store–carry–forward method, and nodes receive the message from others directly. However, it is hard to judge whether the information is safe in this communication mode. In this case, a node may observe other nodes’ behaviors. At present, there is no theoretical model to describe the varying rule of the nodes’ trusting level. In addition, due to the uncertainty of the connectivity in DTN, a node is hard to get the global state of the network. Therefore, a rational model about the node’s trusting level should be a function of the node’s own observing result. For example, if a node finds k nodes carrying a message, it may trust the information with probability p(k). This paper does not explore the real distribution of p(k), but instead presents a unifying theoretical framework to evaluate the performance of the information spreading in above case. This framework is an extension of the traditional SI (susceptible-infected) model, and is useful when p(k) conforms to any distribution. Simulations based on both synthetic and real motion traces show the accuracy of the framework. Finally, we explore the impact of the nodes’ behaviors based on certain special distributions through numerical results.