Scale-free networks are ultrasmall

We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k) proportional, variant k(-lambda), i.e., the probability of having k links outgoing from a site. In contrast to the diameter of regular random networks or small-world networks, which is known to be d approximately ln(N, we show, using analytical arguments, that scale-free networks with 23, d approximately ln(N. We also show that, for any lambda>2, one can construct a deterministic scale-free network with d approximately ln(ln(N, which is the lowest possible diameter.     

Entropic rigidity of randomly diluted two- and three-dimensional networks

In recent work, we presented evidence that site-diluted triangular central-force networks, at finite temperatures, have a nonzero shear modulus for all concentrations of particles above the geometric percolation concentration p(c). This is in contrast to the zero-temperature case where the (energetic) shear modulus vanishes at a concentration of particles p(r)>p(c). In the present paper we report on analogous simulations of bond-diluted triangular lattices, site-diluted square lattices, and site-diluted simple-cubic lattices. We again find that these systems are rigid for all p>p(c) and that near p(c) the shear modulus mu approximately (p-p(c))(f), where the exponent f approximately 1.3 for two-dimensional lattices and f approximately 2 for the simple-cubic case. These results support the conjecture of de Gennes that the diluted central-force network is in the same universality class as the random resistor network. We present approximate renormalization group calculations that also lead to this conclusion.     

D2D-assisted user-centric adaptive video transmission in next generation cellular networks

Next-generation cellular networks need to provide seamless connectivity with higher data rates, increased capacity, and enhanced network coverage. As multimedia service demands in various heterogeneous devices grow rapidly compared to the underlying network’s capacity and bandwidth, the adaptation in multimedia streaming services is essential for providing satisfactory Quality of Experience (QoE). This paper develops a Device-to-Device (D2D)-assisted Utility-based Adaptive Multimedia (video) Streaming scheme (UAMS) using D2D communication in a 5th Generation (5G) cellular network where low-battery users may extend their streaming duration by spending lower reception energy with the help of D2D-assisted communication. The adaptation algorithm considers four utility functions: quality, power consumption, packet error ratio, and remaining battery of the user devices to adapt the bitrate dynamically and augment viewers’ experience. We formulate an optimization problem to maximize the joint utility function to provide the best adaptive multimedia content selected for transmission to the end-users either directly or via D2D Relay Nodes (DRNs) in every scheduling interval. We use a graph theoretic approach for choosing the best DRNs. Extensive simulations show the efficacy of the proposed scheme in terms of saved battery energy, churn rate, and QoE metrics compared to a few well-known existing schemes in the literature that do not use D2D communication.     

Community structure in the United Nations General Assembly

We study the community structure of networks representing voting on resolutions in the United Nations General Assembly. We construct networks from the voting records of the separate annual sessions between 1946 and 2008 in three different ways: (1) by considering voting similarities as weighted unipartite networks; (2) by considering voting similarities as weighted, signed unipartite networks; and (3) by examining signed bipartite networks in which countries are connected to resolutions. For each formulation, we detect communities by optimizing network modularity using an appropriate null model. We compare and contrast the results that we obtain for these three different network representations. We thereby illustrate the need to consider multiple resolution parameters and explore the effectiveness of each network representation for identifying voting groups amidst the large amount of agreement typical in General Assembly votes.     

两相流流型复杂网络社团结构及其统计特性

利用气液两相流电导波动信号构建了流型复杂网络. 基于K均值聚类的社团探寻算法对该网络的社团结构进行了分析,发现该网络存在分别对应于泡状流、段塞流及混状流的三个社团,并且两个社团间联系紧密的点分别对应于相应的过渡流型. 基于复杂网络理论从全新的角度探讨了两相流流型复杂网络社团结构及统计特性问题,并取得了满意的流型识别效果,与此同时,在对该网络特性进一步分析的基础上,发现了对两相流流动参数变化敏感的相关复杂网络统计量,为更好地理解两相流流型动力学特性提供了参考. 关键词： 两相流流型 复杂网络 社团探寻算法 网络统计特性     

On the topology of synchrony optimized networks of a Kuramoto-model with non-identical oscillators

We study synchrony optimized networks. In particular, we focus on the Kuramoto model with non-identical native frequencies on a random graph. In a first step, we generate synchrony optimized networks using a dynamic breeding algorithm, whereby an initial network is successively rewired toward increased synchronization. These networks are characterized by a large anti-correlation between neighbouring frequencies. In a second step, the central part of our paper, we show that synchrony optimized networks can be generated much more cost efficiently by minimization of an energy-like quantity E and subsequent random rewires to control the average path length. We demonstrate that synchrony optimized networks are characterized by a balance between two opposing structural properties: A large number of links between positive and negative frequencies of equal magnitude and a small average path length. Remarkably, these networks show the same synchronization behaviour as those networks generated by the dynamic rewiring process. Interestingly, synchrony-optimized network also exhibit significantly enhanced synchronization behaviour for weak coupling, below the onset of global synchronization, with linear growth of the order parameter with increasing coupling strength. We identify the underlying dynamical and topological structures, which give rise to this atypical local synchronization, and provide a simple analytical argument for its explanation.     

Resilience of the internet to random breakdowns

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, P(k) = ck(-alpha). We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, p(c), that needs to be removed before the network disintegrates. We show analytically and numerically that for alpha0.99.     

Hierarchy Depth in Directed Networks

In this study, we explore the depth measures for flow hierarchy in directed networks. Two simple measures are defined—rooted depth and relative depth—and their properties are discussed. The method of loop collapse is introduced, allowing investigation of networks containing directed cycles. The behavior of the two depth measures is investigated in Erdös-Rényi random graphs, directed Barabási-Albert networks, and in Gnutella p2p share network. A clear distinction in the behavior between non-hierarchical and hierarchical networks is found, with random graphs featuring unimodal distribution of depths dependent on arc density, while for hierarchical systems the distributions are similar for different network densities. Relative depth shows the same behavior as existing trophic level measure for tree-like networks, but is only statistically correlated for more complex topologies, including acyclic directed graphs.     

From topology to dynamics in biochemical networks

Abstract formulations of the regulation of gene expression as random Boolean switching networks have been studied extensively over the past three decades. These models have been developed to make statistical predictions of the types of dynamics observed in biological networks based on network topology and interaction bias, p. For values of mean connectivity chosen to correspond to real biological networks, these models predict disordered dynamics. However, chaotic dynamics seems to be absent from the functioning of a normal cell. While these models use a fixed number of inputs for each element in the network, recent experimental evidence suggests that several biological networks have distributions in connectivity. We therefore study randomly constructed Boolean networks with distributions in the number of inputs, K, to each element. We study three distributions: delta function, Poisson, and power law (scale free). We analytically show that the critical value of the interaction bias parameter, p, above which steady state behavior is observed, is independent of the distribution in the limit of the number of elements N--> infinity. We also study these networks numerically. Using three different measures (types of attractors, fraction of elements that are active, and length of period), we show that finite, scale-free networks are more ordered than either the Poisson or delta function networks below the critical point. Thus the topology of scale-free biochemical networks, characterized by a wide distribution in the number of inputs per element, may provide a source of order in living cells. (c) 2001 American Institute of Physics.     

Communities of minima in local optima networks of combinatorial spaces

In this work, we present a new methodology to study the structure of the configuration spaces of hard combinatorial problems. It consists in building the network that has as nodes the locally optimal configurations and as edges the weighted oriented transitions between their basins of attraction. We apply the approach to the detection of communities in the optima networks produced by two different classes of instances of a hard combinatorial optimization problem: the quadratic assignment problem (QAP). We provide evidence indicating that the two problem instance classes give rise to very different configuration spaces. For the so-called real-like class, the networks possess a clear modular structure, while the optima networks belonging to the class of random uniform instances are less well partitionable into clusters. This is convincingly supported by using several statistical tests. Finally, we briefly discuss the consequences of the findings for heuristically searching the corresponding problem spaces.     

Temperature dependence of heat conduction coefficient in nanotube/nanowire networks

Studies on heat conduction are so far mainly focused on regular systems such as the one-dimensional(1D) and twodimensional(2D) lattices where atoms are regularly connected and temperatures of atoms are homogeneously distributed.However, realistic systems such as the nanotube/nanowire networks are not regular but heterogeneously structured, and their heat conduction remains largely unknown. We present a model of quasi-physical networks to study heat conduction in such physical networks and focus on how the network structure influences the heat conduction coefficient κ. In this model,we for the first time consider each link as a 1D chain of atoms instead of a spring in the previous studies. We find that κ is different from link to link in the network, in contrast to the same constant in a regular 1D or 2D lattice. Moreover, for each specific link, we present a formula to show how κ depends on both its link length and the temperatures on its two ends.These findings show that the heat conduction in physical networks is not a straightforward extension of 1D and 2D lattices but seriously influenced by the network structure.     

Detecting Communities by Revised Max-flow Method in Networks

A ubiquitous phenomenon in networks is the presence of communities within which the network connections are dense and between which they are sparser.This paper proposes a max-flow algorithm in bipartite networks to detect communities in general networks.Firstly,we construct a bipartite network in accordance with a general network and derive a revised max-flow problem in order to uncover the community structure.Then we present a local heuristic algorithm to find the optimal solution of the revised max-flow problem.This method is applied to a variety of real-world and artificial complex networks,and the partition results confirm its effectiveness and accuracy.     

Breakdown of the internet under intentional attack

We study the tolerance of random networks to intentional attack, whereby a fraction p of the most connected sites is removed. We focus on scale-free networks, having connectivity distribution P(k) approximately k(-alpha), and use percolation theory to study analytically and numerically the critical fraction p(c) needed for the disintegration of the network, as well as the size of the largest connected cluster. We find that even networks with alpha < or = 3, known to be resilient to random removal of sites, are sensitive to intentional attack. We also argue that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.     

A Path-Based Distribution Measure for Network Comparison

As network data increases, it is more common than ever for researchers to analyze a set of networks rather than a single network and measure the difference between networks by developing a number of network comparison methods. Network comparison is able to quantify dissimilarity between networks by comparing the structural topological difference of networks. Here, we propose a kind of measures for network comparison based on the shortest path distribution combined with node centrality, capturing the global topological difference with local features. Based on the characterized path distributions, we define and compare network distance between networks to measure how dissimilar the two networks are, and the network entropy to characterize a typical network system. We find that the network distance is able to discriminate networks generated by different models. Combining more information on end nodes along a path can further amplify the dissimilarity of networks. The network entropy is able to detect tipping points in the evolution of synthetic networks. Extensive numerical simulations reveal the effectivity of the proposed measure in network reduction of multilayer networks, and identification of typical system states in temporal networks as well.     

对等网络应用中的网络统计特征分析

本文基于实测数据抽象出用户网络与资源网络,探讨了对等网络中用户、资源及其内部的相互作用关系,发掘并分析了其内在的网络统计特征. 分析结果表明,用户节点度值及权值呈分段分布,体现了其各异的活跃性;网络资源的流行度差异明显,度值和权值近似呈幂律分布. 用户网络与资源网络存在分簇结构,少数簇中含大量节点,多数簇所含节点数量较少. 用户网络中,同簇内的用户有着相似的兴趣趋向,不同簇用户间兴趣趋向存在着差异,资源网络各簇中不同类别的资源间呈现出明显的关联性.     

Robustness of a network of networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of n interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of n fully dependent Erd?s-Rényi (ER) networks, each of average degree k, we find that the giant component is P∞ =p[1-exp(-kP∞)](n) where 1-p is the initial fraction of removed nodes. This general result coincides for n = 1 with the known second-order phase transition for a single network. For any n>1 cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, P∞ depends also on the topology-in contrast to case (i). (iii) For a looplike network formed by n partially dependent ER networks, P∞ is independent of n.     

Stochastic modelling and analysis of mobility models for intelligent software defined internet of vehicles

Data traffic forwarding and network optimization is essential to effective congestion management in software-defined vehicular networks, and it is necessary for software-defined vehicle networks (SDVN). SDVN is needed to optimize connection performance and network controls in dense and sparse networks to govern data flow between nodes as effectively as possible. Intelligent software-defined internet of vehicles (iSDIoVs) has recently emerged as a potential technology for future vehicular networks. It manages the vehicular ad hoc networks systematically. The link connection of moving vehicles from the central SDN controller may fail. It impacts the efficiency and communication performance because of the lack of connection between vehicles and infrastructure (V2I). The researchers have analyzed the network performance and mobility models in a dense and sparse network to maximize network performance by iSDIoVs. By integrating heterogeneous systems such as IEEE 802.11p and cellular networks into vehicular ad-hoc networks, it is possible to reduce buffer occupancy in iSDIoV and control the mobility and delay bound analysis in V2V communication. The SDN will provide flexibility and reliability to the vehicular networks. An SDN controller manages the data flow in the vehicular network and controls the flow matching rules in the control plane. The iSDIoV and queuing models improve the response time and resource utilization and enhance the network complexity analysis for traffic management services.     

有倾向性重连产生的反匹配网络

在具有网络结构的系统中度关联属性对于动力学行为具有重要的影响, 所以产生适当度关联网络的方法对于大量网络系统的研究具有重要的作用. 尽管产生正匹配网络的方法已经得到很好的验证, 但是产生反匹配网络的方法还没有被系统的讨论过. 重新连接网络中的边是产生度关联网络的一个常用方法. 这里我们研究使用重连方法产生反匹配无标度网络的有效性. 我们的研究表明, 有倾向的重连可以增强网络的反匹配属性. 但是有倾向重连不能使皮尔森度相关系数下降到-1, 而是存在一个依赖于网络参数的最小值. 我们研究了网络的主要参数对于网络度相关系数的影响, 包括网络尺寸, 网络的连接密度和网络节点的度差异程度. 研究表明在网络尺寸大的情况下和节点度差异性强的情况下, 重连的效果较差. 我们研究了真实Internet网络, 发现模型产生的网络经过重连不能达到真实网络的度关联系数.     

Topological properties of stock networks based on minimal spanning tree and random matrix theory in financial time series

We investigated the topological properties of stock networks constructed by a minimal spanning tree. We compared the original stock network with the estimated network; the original network is obtained by the actual stock returns, while the estimated network is the correlation matrix created by random matrix theory. We found that the consistency between the two networks increases as more eigenvalues are considered. In addition, we suggested that the largest eigenvalue has a significant influence on the formation of stock networks.     

Cascading failure in multilayer networks with dynamic dependency groups

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism.In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.