Four correlates of complex behavioral networks: Differentiation,behavior, connectivity,and compartmentalization: Carving networks at their joints

Some of the most complex networks are those that (i) have been engineered under selective pressure (either economic or evolutionary), and (ii) are capable of eliciting network‐level behaviors. Some examples are nervous systems, ant colonies, electronic circuits and computer software. Here we provide evidence that many such selected, behavioral networks are similar in at least four respects. (1) Differentiation: Nodes of different types are used in a combinatorial fashion to build network structures through local connections, and networks accommodate more structure types via increasing the number of node types in the network (i.e., increasing differentiation), not via increasing the length of structures. (2) Behavior: Structures are themselves combined globally to implement behaviors, and networks accommodate a greater behavioral repertoire via increasing the number of lower‐level behavior types (including structures), not via increasing the length of behaviors. (3) Connectivity: In order for structures in behavioral networks to combine with other structures within a fixed behavior length, the network must maintain an invariant network diameter, and this is accomplished via increasing network connectivity in larger networks. (4) Compartmentalization: Finally, for reasons of economical wiring, behavioral networks become increasingly parcellated. Special attention is given to nervous systems and computer software, but data from a variety of other behavioral selected networks are also provided, including ant colonies, electronic circuits, web sites and businesses. A general framework is introduced illuminating why behavioral selected networks share these four correlates. Because the four above features appear to apply to computer software as well as to biological networks, computer software provides a useful framework for comprehending the large‐scale function and organization of biological networks. © 2005 Wiley Periodicals, Inc. Complexity 10: 13–40, 2005     

Dynamics of Coupled Cell Networks: Synchrony, Heteroclinic Cycles and Inflation

We consider the dynamics of small networks of coupled cells. We usually assume asymmetric inputs and no global or local symmetries in the network and consider equivalence of networks in this setting; that is, when two networks with different architectures give rise to the same set of possible dynamics. Focussing on transitive (strongly connected) networks that have only one type of cell (identical cell networks) we address three questions relating the network structure to dynamics. The first question is how the structure of the network may force the existence of invariant subspaces (synchrony subspaces). The second question is how these invariant subspaces can support robust heteroclinic attractors. Finally, we investigate how the dynamics of coupled cell networks with different structures and numbers of cells can be related; in particular we consider the sets of possible “inflations” of a coupled cell network that are obtained by replacing one cell by many of the same type, in such a way that the original network dynamics is still present within a synchrony subspace. We illustrate the results with a number of examples of networks of up to six cells.     

The realization of positive definite matrices via planar networks and mixing-type sub-cluster algebras

As an improvement of the combinatorial realization of totally positive matrices via the essential positive weightings of certain planar network by S.Fomin and A.Zelevinsky [7], in this paper,we give a test method of positive definite matrices via the planar networks and the so-called mixing-type sub-cluster algebras respectively,introduced here originally.This work firstly gives a combinatorial realization of all matrices through planar network,and then sets up a test method for positive definite matrices by LDU-decompositions and the horizontal weightings of all lines in their planar networks.On the other hand,mainly the relationship is built between positive definite matrices and mixing-type sub-cluster algebras.     

Statistical analysis of the intermediate filament network in cells of mesenchymal lineage by greyvalue-oriented image segmentation

Intermediate filament networks are part of the cytoskeleton and protect cellular integrity during large deformations. In cells from mesenchymal lineage the cytoskeleton is centrally involved in signal transduction, thereby influencing differentiation. We study the ultrastructure of IF networks in three human mesenchymal cell types, namely undifferentiated mesenchymal stem cells, chondrocytes, and osteoblasts. In order to capture the high morphological variability of IF networks we apply techniques from image analysis to extract the network graph from 2D scanning electron microscopy (SEM) images in a fully automatic way, which allows for a high-throughput analysis of SEM data. The extracted network graphs are analyzed by techniques from spatial statistics to detect differences in network morphology between different cell types and infer strategies of network remodeling used by the cells to adapt their mechanical properties during migration and differentiation.     

Integrity of Total Graphs via Certain Parameters

Communication networks have been characterized by high levels of service reliability. Links cuts, node interruptions, software errors or hardware failures, and transmission failures at various points can interrupt service for long periods of time. In communication networks, greater degrees of stability or less vulnerability is required. The vulnerability of communication network measures the resistance of the network to the disruption of operation after the failure of certain stations or communication links. If we think of a graph G as modeling a network, many graph-theoretic parameters can be used to describe the stability of communication networks, including connectivity, integrity, and tenacity. We consider two graphs with the same connectivity, but with unequal orders of theirs largest components. Then these two graphs must be different in respect to stability. How can we measure that property? The idea behind the answer is the concept of integrity, which is different from connectivity. Total graphs constitute a large class of graphs. In this paper, we study the integrity of total graphs via some graph parameters.

     

The Lattice of Synchrony Subspaces of a Coupled Cell Network: Characterization and Computation Algorithm

Coupled cell systems are networks of dynamical systems (the cells), where the links between the cells are described through the network structure, the coupled cell network. Synchrony subspaces are spaces defined in terms of equalities of certain cell coordinates that are flow-invariant for all coupled cell systems associated with a given network structure. The intersection of synchrony subspaces of a network is also a synchrony subspace of the network. It follows, then, that, given a coupled cell network, its set of synchrony subspaces, taking the inclusion partial order relation, forms a lattice. In this paper we show how to obtain the lattice of synchrony subspaces for a general network and present an algorithm that generates that lattice. We prove that this problem is reduced to obtain the lattice of synchrony subspaces for regular networks. For a regular network we obtain the lattice of synchrony subspaces based on the eigenvalue structure of the network adjacency matrix.     

On Multivariate Markov Chains for Common and Non-Common Objects in Multiple Networks

Node importance or centrality evaluation is an important methodology for network analysis. In this paper, we are interested in the study of objects appearing in several networks. Such common objects are important in network-network interactions via object-object interactions. The main contribution of this paper is to model multiple networks where there are some common objects in a multivariate Markov chain framework, and to develop a method for solving common and non-common objects' stationary probability distributions in the networks. The stationary probability distributions can be used to evaluate the importance of common and non-common objects via network-network interactions. Our experimental results based on examples of co-authorship of researchers in different conferences and paper citations in different categories have shown that the proposed model can provide useful information for researcher-researcher interactions in networks of different conferences and for paper-paper interactions in networks of different categories.     

A stochastic fluid model for an ad hoc mobile network

In conventional mobile telephone networks, users communicate directly with a base station, via which their call is transferred to the recipient. In an ad hoc mobile network, there is no base-station infrastructure and users need to communicate between themselves, either directly if they are close enough, or via transit nodes if they are not. A number of interesting questions immediately arise in the modeling of ad hoc mobile networks. One that has received attention in the literature concerns how to encourage users to act as transit nodes for calls that they are not partaking in. Solutions to this problem have involved each user maintaining a ‘credit balance’ which is increased by forwarding transit calls and decreased by transmitting one’s own calls. A second question concerns the ‘amount of resource’ that a network needs in order to be able to operate with a reasonable quality of service. We shall consider this question by modeling each user’s battery energy and credit balance as fluids, the rate of increase or decrease of which is modulated by the network occupancy. This results in a network of stochastic fluid models, each modulated by the same background process. In this paper, we shall assume that there is no bound on the energy or the credit that a user’s handset can accumulate. Using this model, we can calculate the critical rates of recharge that are necessary and sufficient to guarantee that no calls are lost. For recharge rates less than the critical values, we propose a reduced-load approach to the analysis of the network.     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

A Bayesian record linkage model incorporating relational data

In this article, we introduce a novel Bayesian approach for linking multiple social networks in order to discover the same real world person having different accounts across networks. In particular, we develop a latent model that allows us to jointly characterize the network and linkage structures relying on both relational and profile data. In contrast to other existing approaches in the machine learning literature, our Bayesian implementation naturally provides uncertainty quantification via posterior probabilities for the linkage structure itself or any function of it. Our findings clearly suggest that our methodology can produce accurate point estimates of the linkage structure even in the absence of profile information, and also, in an identity resolution setting, our results confirm that including relational data into the matching process improves the linkage accuracy. We illustrate our methodology using real data from popular social networks such as Twitter , Facebook , and YouTube .     

A unified network performance measure with importance identification and the ranking of network components

In this paper, we propose the first network performance measure that can be used to assess the efficiency of a network in the case of either fixed or elastic demands. Such a measure is needed for many different applications since only when the performance of a network can be quantifiably measured can the network be appropriately managed. Moreover, as we demonstrate, the proposed performance measure, which captures flow information and behavior, allows one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking. We present specific networks for which the performance/efficiency is computed along with the importance rankings of the nodes and links. The new measure can be applied to transportation networks, supply chains, financial networks, electric power generation and distribution networks as well as to the Internet and can be used to assess the vulnerability of a network to disruptions.     

有脉冲影响的κ-值逻辑网络的不动点与稳定性

讨论了有脉冲影响的κ-值逻辑网络的不动点及稳定性问题.利用矩阵的半张量积方法,首先将有脉冲影响的κ-值逻辑网络转化成基于矩阵的离散时间动态系统.然后,给出一点是系统不动点的充要条件.最后,给出了两种不同类型控制下系统稳定的充要条件.     

Massively parallel analog tabu search using neural networks applied to simple plant location problems

Neural networks and tabu search are two very significant techniques which have emerged recently for the solution of discrete optimization problems. Neural networks possess the desirable quality of implementability in massively parallel hardware while the tabu search metaheuristic shows great promise as a powerful global search method. Tabu Neural Network (TANN) integrates an analog version of the short term memory component of tabu search with neural networks to generate a massively parallel, analog global search strategy that is hardware implementable. In TANN, both the choice of the element to enter the tabu list as well as the maintenance of the decision elements in tabu status is accomplished via neuronal activities. In this paper we apply TANN to the simple plant location problem. Comparisons with the Hopfield-Tank network show an average improvement of about 85% in the quality of solutions obtained.     

Network design for time-constrained delivery using subgraphs

Delivery companies are offering an increasing number of time-definite services. Yet, little research has been done that explores the design of delivery networks that can support these types of services. In this paper, we explore such design problems for networks with a specified number of edges $B > n-1$ , where $n$ is the number of nodes in the problem. We present a two-phase heuristic solution approach that first constructs a network and then improves the network via local search. For the improvement phase, we extend neighborhood structures that have proven effective for tree-structured solutions and also identify a new search neighborhood that takes advantage of specific features of subgraph solutions. We present a computational analysis of our solution approach as well as managerial insights.     

Domain Decomposition of Optimal Control Problems for Dynamic Networks of Elastic Strings

We consider optimal control problems related to exact- and approximate controllability of dynamic networks of elastic strings. In this note we concentrate on problems with linear dynamics, no state and no control constraints. The emphasis is on approximating target states and velocities in part of the network using a dynamic domain decomposition method (d³m) for the optimality system on the network. The decomposition is established via a Uzawa-type saddle-point iteration associated with an augmented Lagrangian relaxation of the transmission conditions at multiple joints. We consider various cost functions and prove convergence of the infinite dimensional scheme for an exemplaric choice of the cost. We also give numerical evidence in the case of simple exemplaric networks.     

Blocking Probabilities in Mobile Communications Networks with Time-Varying Rates and Redialing Subscribers

Call-blocking probabilities are among the key performance measures in mobile communications networks. For their analysis, mobile networks can be modelled as networks of Erlang loss queues with common capacity restrictions dictated by the allocation of frequencies to the cells of the network. However, due to the time-varying load offered to the cells of such networks, blocking probabilities usually cannot be obtained in closed form. The relation between networks of Erlang loss queues and networks of infinite server queues, for which the time-dependent occupancy distribution is multidimensional Poisson, suggests to use that distribution as approximate distribution for the network of Erlang loss queues. This paper extends this so-called Modified Offered Load (MOL) approximation to networks of Erlang loss queues, and also allows subscribers that find their call blocked to redial to continue their call. For GSM networks operating under Fixed Channel Allocation, it is shown that blocking probabilities are increasing in the redial rates so that the MOL approximation that is most accurate for maximal redial rates turns out to be fairly accurate for the resulting upper bound for blocking probabilities. The accuracy is explicitly evaluated in an application of the results towards blocking probabilities in a hot spot travelling along a road through a GSM network.     

Coupled cell networks: minimality

Non-isomorphic coupled cell networks with the same number of cells and with equivalent dynamics are said to be ODE-equivalent. Moreover, they are all related by a linear algebra condition involving their graph adjacency matrices. A network in an ODE-class is said to be minimal if it has a minimum number of edges among all the networks of the class. In this short paper we review the characterization of the minimal networks of an ODE-equivalence class and we present an example for the case of non-homogeneous networks. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Tradeoffs between quality-of-control and quality-of-service in large-scale nonlinear networked control systems

In this paper we study input-to-state stability (ISS) of large-scale networked control systems (NCSs) in which sensors, controllers and actuators are connected via multiple (local) communication networks which operate asynchronously and independently of each other. We model the large-scale NCS as an interconnection of hybrid subsystems, and establish rather natural conditions which guarantee that all subsystems are ISS, and have an associated ISS Lyapunov function. An ISS Lyapunov function for the overall system is constructed based on the ISS Lyapunov functions of the subsystems and the interconnection gains. The control performance, or “quality-of-control”, of the overall system is then viewed in terms of the convergence rate and ISS gain of the associated ISS Lyapunov function. Additionally, the “quality-of-service” of the communication networks is viewed in terms of the maximum allowable transmission interval (MATI) and the maximum allowable delay (MAD) of the network, and we show that the allowable quality-of-service of the communication networks is constrained by the required ISS gains and convergence rate of the hybrid subsystem corresponding to that network. Our results show that the quality-of-control of the overall system can be improved (or degraded) by improving (or relaxing) the quality-of-service of the communication networks. Alternatively, when relaxing the quality-of-service of one communication network, we can retain the quality-of-control of the overall system by improving the quality-of-service of one or more of the other communication networks. Our general framework will formally show these intuitive and insightful tradeoffs.     

Generalized loopy 2U: A new algorithm for approximate inference in credal networks

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.