Structural heterogeneity mediates the effect of community structure on cooperation

Emergence of cooperation in evolutionary prisoner's dilemma game strongly depends on the topology of underlying interaction network. We explore this dependence using community networks with different levels of structural heterogeneity, which are generated by a tunable upper‐bound on the total number of links that any vertex can have. We study the effect of community structure on cooperation by analyzing a finite population analogue of the evolutionary replicator dynamics. We find that structural heterogeneity mediates the effect of community structure on cooperation. In the community networks with low level of structural heterogeneity, community structure has negative effect on cooperation. However, the positive effect of community structure on cooperation appears and enhances with increasing structural heterogeneity. Our work may be helpful for understanding the complexity of cooperative behaviors in social networks. © 2011 Wiley Periodicals, Inc. Complexity, 2012     

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.     

Stable and emergent network topologies: A structural approach

Economic, social and military networks have at least one thing in common: they change over time. For various reasons, nodes form and terminate links, thereby rearranging the network. In this paper, we present a structural network mechanism that formalizes a possible incentive that guides nodes in constructing their local network structure. The mechanism assumes that nodes deliberately form and terminate links as they attempt to gain network advantage and/or an identifiable position in the network. Reiteration of this mechanism, which only uses local network characteristics, results in emergent, stable network topologies. Examples are uni-polar networks, bi-polar networks and cycle-networks. This process illustrates that local, binary decisions shape global network structures. These results may be used to derive some rules of thumb for designing networks.     

二元稳定网络的算法及模型

通过建立JW(Jackson-Wolinsky)规则之下二元稳定网络的等价条件, 给出其完整算法. 引入边支付后, 证明了增连接情形具有边支付的二元稳定网络集合是二元稳定网络集合与具有边支付的二元稳定网络集合的交集. 考察两个特定的网络模型, 系统分析了它们的二元稳定性.     

Optimized network structure for full-synchronization

A network of Kuramoto oscillators with different natural frequencies is optimized for enhanced synchronizability. All node inputs are normalized by the node connectivity and some important properties of the network structure are determined in this case: (i) optimized networks present a strong anti-correlation between natural frequencies of adjacent nodes; (ii) this anti-correlation should be as high as possible since the average path length between nodes is maintained as small as in random networks; and (iii) high anti-correlation is obtained without any relation between nodes natural frequencies and the degree of connectivity. We also propose a network construction model with which it is shown that high anti-correlation and small average paths may be achieved by randomly rewiring a fraction of the links of a totally anti-correlated network, and that these networks present optimal synchronization properties.     

Cluster synchronization in nonlinearly coupled delayed networks of non-identical dynamic systems

In the real world, many networks show community structure, i.e., clusters of nodes, which have a high density of links within the same cluster but a lower density of links between different clusters. In this paper, nonlinearly coupled networks with community structure and non-identical nodes and with time-varying delay are considered. By applying pinning control to a fraction of network nodes, and using a suitable Lyapunov function, we obtain some new and useful synchronization criteria, which guarantee that various clusters are synchronized independently. An example is presented to show the application of the criteria obtained in this paper.     

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.     

Structural balance in fully signed networks

Node attributes play an important role in shaping network structures, but are generally ignored in transformations of structural balance. A fully signed network consisting of signs of edges and nodes expresses both properties of relationship and node attributes. In this article, we generalize the definition of structural balance in fully signed networks. We transform the unbalanced fully signed network by not only changing signs of edges but also changing the signs of nodes. We propose a memetic algorithm to transform unbalanced networks at the lowest cost. Experiments show that our algorithm can solve this problem efficiently, and different node attribute assignments may lead to different optimized structures. © 2016 Wiley Periodicals, Inc. Complexity 21: 497–511, 2016     

A Tabu Search Algorithm for Access Network Design

We present a fast tabu search method for the design of access tree networks. We connect a population of users to a set of switches using a variety of SONET channels on fiber optics links and ADM equipment at the nodes. We specifically take into account the economies of scale provided by the transmission systems and the transmission hierarchy of SONET systems.We describe in detail the parameters used for defining neighborhoods, penalty parameters, data structure and indicate how this can lead to substantial improvements of the overall computational time while providing costs lower than those of a more straightforward method. Results are provided for a set of random cases as well as for a real network.     

Generalized function projective (lag, anticipated and complete) synchronization between two different complex networks with nonidentical nodes

Generalized function projective (lag, anticipated and complete) synchronization between two different complex networks with nonidentical nodes is investigated in this paper. Based on Barbalat’s lemma, some sufficient synchronization criteria are derived by applying the nonlinear feedback control. Although previous work studied function projective synchronization on complex dynamical networks, the dynamics of the nodes are coupled partially linear chaotic systems. In our work, the dynamics of the nodes of the complex networks are any chaotic systems without the limitation of the partial linearity. In addition, each network can be undirected or directed, connected or disconnected, and nodes in either network may have identical or different dynamics. The proposed strategy is applicable to almost all kinds of complex networks. Numerical simulations further verify the effectiveness and feasibility of the proposed synchronization method. Numeric evidence shows that the synchronization rate is sensitively influenced by the feedback strength, the time delay, the network size and the network topological structure.     

An evaluation of the adequacy of project network generators with systematically sampled networks

This paper evaluates and compares different network generators to generate project scheduling problem instances based on indicators measuring the topological network structure. We review six topological network indicators in order to describe the detailed structure of a project network. These indicators were originally developed by [L.V. Tavares, J.A. Ferreira and J.S. Coelho, The risk of delay of a project in terms of the morphology of its network, European Journal of Operational Research 119 (1999), 510–537] and have been modified, or sometimes completely replaced, by alternative indicators to describe the network topology. The contribution of this paper is twofold. Firstly, we generate a large amount of different networks with four project network generators. Our general conclusions are that none of the network generators are able to capture the complete feasible domain of all networks. Additionally, each network generator covers its own network-specific domain and, consequently, contributes to the generation of data sets. Secondly, we perform computational results on the well-known resource-constrained project scheduling problem to prove that our indicators are reliable and have significant, predictive power to serve as complexity indicators.     

Node Features Adjusted Stochastic Block Model

Stochastic block model (SBM) and its variants are popular models used in community detection for network data. In this article, we propose a feature-adjusted stochastic block model (FASBM) to capture the impact of node features on the network links as well as to detect the residual community structure beyond that explained by the node features. The proposed model can accommodate multiple node features and estimate the form of feature impacts from the data. Moreover, unlike many existing algorithms that are limited to binary-valued interactions, the proposed FASBM model and inference approaches are easily applied to relational data that generate from any exponential family distribution. We illustrate the methods on simulated networks and on two real-world networks: a brain network and an US air-transportation network.     

On the semi-discretization of optimal control problems for networks of elastic strings: global optimality systems and domain decomposition

We consider a star-graph as an examplary network, with elastic strings stretched along the edges. The network is allowed to perform out-of-the plane displacements. We consider such networks as being controlled at its simple nodes via Dirichlet conditions. The objective is to steer given initial data to final target data in a given time T with minimal control costs. This problem is discussed in the continuous as well as in the discrete case. We discuss an iterative domain decomposition technique and its discrete analogue. We prove convergence and show some numerical results.     

Dynamic network reliability modeling under nonhomogeneous Poisson processes

In this paper, we consider a two-state (up and down) network consisting of n links. We study the D-spectrum based dynamic reliability of the network under the assumption that the links are subject to failure according to a nonhomogeneous Poisson process. Several mixture representations are provided for the reliability function of residual lifetime of used networks, under different conditions on the status of the network or its links. These representations enable us to explore the residual reliability of operating networks in terms of the reliability functions of residual lifetimes of upper record values. The distribution function of inactivity time of a network is examined under the condition that the network has failed by inspection time t. Stochastic ordering properties of the residual lifetimes of networks under conditional D-spectra are investigated. Several examples and graphs are also provided to illustrate the established results.     

基于复杂网络的中国股市房地产板块股票强相关性研究

为分析中国股市房地产板块股票的强相关特性,以101只股票为结点,以近17年股票对数回报的相关系数为加权边,建立复杂网络模型,通过对网络拓扑参数计算,发现该网络为无尺度网络,结点度分布P(s)~s-|s|δ,在不同相关系数阈值下,δ值介于0.8~1.6之间.网络平均集聚系数为0.53.文章也对网络中心性进行测量和子群划分,发现代码为000592和601588的结点在网络中具有很高的中介性,网络中大部分结点都受其影响较大.     

A PC algorithm variation for ordinal variables

Bayesian networks are graphical models that represent the joint distribution of a set of variables using directed acyclic graphs. The graph can be manually built by domain experts according to their knowledge. However, when the dependence structure is unknown (or partially known) the network has to be estimated from data by using suitable learning algorithms. In this paper, we deal with a constraint-based method to perform Bayesian networks structural learning in the presence of ordinal variables. We propose an alternative version of the PC algorithm, which is one of the most known procedures, with the aim to infer the network by accounting for additional information inherent to ordinal data. The proposal is based on a nonparametric test, appropriate for ordinal variables. A comparative study shows that, in some situations, the proposal discussed here is a slightly more efficient solution than the PC algorithm.     

Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks

The optimal path-finding algorithm which is an important module in developing route guidance systems and traffic control systems has to provide correct paths to consider U-turns, P-turns, and no-left-turns in urban transportation networks.Traditional methods which have been used to consider those regulations on urban transportation networks can be categorized into network representation and algorithmic methods like the vine-building algorithm. First, network representation methods use traditional optimal path-finding algorithms with modifications to the network structure: for example, just adding dummy nodes and links to the existing network allows constraint-search in the network. This method which creates large networks is hard to implement and introduces considerable difficulties in network coding. With the increased number of nodes and links, the memory requirement tremendously increases, which causes the processing speed to slow down. For these reasons, the method has not been widely accepted for incorporating turning regulations in optimal path-finding problems in transportation networks. Second, algorithmic methods, as they are mainly based on the vine-building algorithm, have been suggested for determining optimal path for networks with turn penalties and prohibitions. However, the algorithms, although they nicely reflect the characteristics of urban transportation networks, frequently provide infeasible or suboptimal solutions.The algorithm to be suggested in this research is a method which is basically based on Dijkstra's algorithm [1] and the tree-building algorithm used to construct optimal paths. Unlike the traditional node labeling algorithms which label each node with minimum estimated cost, this algorithm labels each link with minimum estimated cost.Comparison with the vine-building algorithm shows that the solution of the link-labeling algorithm is better than that of the vine-building algorithm which very frequently provides suboptimal solutions. As a result, the algorithm allows turning regulations, while providing an optimal solution within a reasonable time limit.     

Measuring agility of networked organizational structures via network entropy and mutual information

While the agility of networked organizational structures is important for organizational performance, studies on how to evaluate it remain scant, probably because the difficulty in measuring network evolution. In this conceptual paper, we propose two measures - network entropy and mutual information - to characterize the agility of networked organizational structure. Rooted in graph theory and information theory, these two measures capture network evolution in a comprehensive and parsimonious way. They indicate the uncertainty (or disorder) at the network level as well as the degree distribution at the individual level. We also propose an algorithm for applying them in the scenario of adding links to a network while holding the number of nodes fixed. Both simulated and real networks are used for demonstration. Implications and areas for future research are discussed in the end.     

Unequal connections

Empirical work suggests that social and economic networks are characterized by an unequal distribution of connections across individuals. This paper explores the circumstances under which networks will or will not exhibit inequality. Two specific models of network formation are explored. The first is a playing the field game in which the aggregate payoffs of an individual depend only on the number of his links and the aggregate number of links of the rest of the population. The second is a local spillovers game in which the aggregate payoffs of an individual depend on the distribution of links of all players and the identity of neighbors. For both class of games we develop results on existence and characterize equilibrium networks under different combinations of externalities/spillovers. We also examine conditions under which having more connections implies a higher payoff.