A new information dimension of complex networks

The fractal and self-similarity properties are revealed in many complex networks. The classical information dimension is an important method to study fractal and self-similarity properties of planar networks. However, it is not practical for real complex networks. In this Letter, a new information dimension of complex networks is proposed. The nodes number in each box is considered by using the box-covering algorithm of complex networks. The proposed method is applied to calculate the fractal dimensions of some real networks. Our results show that the proposed method is efficient when dealing with the fractal dimension problem of complex networks.     

Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling

Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395] have recently used a version of the box-counting method, called the node-covering method, to quantify the self-similar properties of 43 cellular networks: the minimal number _NV$N_V$ of boxes of size ?$?$ needed to cover all the nodes of a cellular network was found to scale as the power-law _NV∼(?+1)^-_DV$N_V\sim (?+1{)}^{-D_V}$ with a fractal dimension _DV=3.53±0.26$D_V=3.53\pm 0.26$. We implement an alternative box-counting method in terms of the minimum number _NE$N_E$ of edge-covering boxes which is well-suited to cellular networks, where the search over different covering sets is performed with the simulated annealing algorithm. The method also takes into account a possible discrete scale symmetry to optimize the sampling rate and minimize possible biases in the estimation of the fractal dimension. With this methodology, we find that _NE$N_E$ scales with respect to ?$?$ as a power-law _NE∼?^-_DE$N_E\sim {?}^{-D_E}$ with _DE=2.67±0.15$D_E=2.67\pm 0.15$ for the 43 cellular networks previously analyzed by Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395]. Bootstrap tests suggest that the analyzed cellular networks may have a significant log-periodicity qualifying a discrete hierarchy with a scaling ratio close to 2.     

Self-similar scaling of density in complex real-world networks

Despite their diverse origin, networks of large real-world systems reveal a number of common properties including small-world phenomena, scale-free degree distributions and modularity. Recently, network self-similarity as a natural outcome of the evolution of real-world systems has also attracted much attention within the physics literature. Here we investigate the scaling of density in complex networks under two classical box-covering renormalizations–network coarse-graining–and also different community-based renormalizations. The analysis on over 50 real-world networks reveals a power-law scaling of network density and size under adequate renormalization technique, yet irrespective of network type and origin. The results thus advance a recent discovery of a universal scaling of density among different real-world networks [P.J. Laurienti, K.E. Joyce, Q.K. Telesford, J.H. Burdette, S. Hayasaka, Universal fractal scaling of self-organized networks, Physica A 390 (20) (2011) 3608–3613] and imply an existence of a scale-free density also within–among different self-similar scales of–complex real-world networks. The latter further improves the comprehension of self-similar structure in large real-world networks with several possible applications.     

Emergence of complex networks from diffusion on fractal lattices. A special case of the Sierpinski gasket and tetrahedron

A new approach to the assemblage of complex networks displaying the scale-free architecture is proposed. While the growth and the preferential attachment of incoming nodes assure an emergence of such networks according to the Barabási–Albert model, it is argued here that the preferential linking condition needs not to be a principal rule. To assert this statement a simple computer model based on random walks on fractal lattices is introduced. It is shown that the model successfully reproduces the degree distributions, the ultra-small-worldness and the high clustering arising from the topology of scale-free networks.     

A framework to approach problems of forensic anthropology using complex networks

We have developed a method to analyze and interpret emerging structures in a set of data which lacks some information. It has been conceived to be applied to the problem of getting information about people who disappeared in the Argentine state of Tucumán from 1974 to 1981. Even if the military dictatorship formally started in Argentina had begun in 1976 and lasted until 1983, the disappearance and assassination of people began some months earlier. During this period several circuits of Illegal Detention Centres (IDC) were set up in different locations all over the country. In these secret centres, disappeared people were illegally kept without any sort of constitutional guarantees, and later assassinated. Even today, the final destination of most of the disappeared people’s remains is still unknown. The fundamental hypothesis in this work is that a group of people with the same political affiliation whose disappearances were closely related in time and space shared the same place of captivity (the same IDC or circuit of IDCs). This hypothesis makes sense when applied to the systematic method of repression and disappearances which was actually launched in Tucumán, Argentina (2007) [11]. In this work, the missing individuals are identified as nodes on a network and connections are established among them based on the individuals’ attributes while they were alive, by using rules to link them. In order to determine which rules are the most effective in defining the network, we use other kind of knowledge available in this problem: previous results from the anthropological point of view (based on other sources of information, both oral and written, historical and anthropological data, etc.); and information about the place (one or more IDCs) where some people were kept during their captivity. For these best rules, a prediction about these people’s possible destination is assigned (one or more IDCs where they could have been kept), and the success of the prediction is evaluated. By applying this methodology, we have been successful in 71% of the cases. The best rules take into account the proximity of the locations where the kidnappings took place, and link events which occurred in periods of time from 5 to 7 days. Finally, we used one of the best rules to build a network of IDCs in an attempt to formalize the relation between the illegal detention centres. We found that this network makes sense because there are survivors’ testimonies which confirm some of these connections.     

A complex networks approach for data clustering

This work proposes a method for data clustering based on complex networks theory. A data set is represented as a network by considering different metrics to establish the connection between each pair of objects. The clusters are obtained by taking into account five community detection algorithms. The network-based clustering approach is applied in two real-world databases and two sets of artificially generated data. The obtained results suggest that the exponential of the Minkowski distance is the most suitable metric to quantify the similarities between pairs of objects. In addition, the community identification method based on the greedy optimization provides the best cluster solution. We compare the network-based clustering approach with some traditional clustering algorithms and verify that it provides the lowest classification error rate.     

复杂网络研究概述

近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮．复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么?物理学家研究复杂网络的终极问题是什么?物理过程以及相关的物理现象对拓扑结构是否敏感?物理学家进入这一研究领域的原因和意义何在?复杂网络研究领域将来可能会向着什么方向发展?文章围绕上述问题，从整体上概述了复杂网络的研究进展．     

Reducing congestion on complex networks by dynamic relaxation processes

We study the effects of relaxational dynamics on the congestion pressure in general transport networks. We show that the congestion pressure is reduced in scale-free networks if a relaxation mechanism is utilized, while this is in general not the case for non-scale-free graphs such as random graphs. We also present evidence supporting the idea that the emergence of scale-free networks arise from optimization mechanisms to balance the load of the networks nodes.     

Ranking spreaders by decomposing complex networks

Ranking the nodes? ability of spreading in networks is crucial for designing efficient strategies to hinder spreading in the case of diseases or accelerate spreading in the case of information dissemination. In the well-known k-shell method, nodes are ranked only according to the links between the remaining nodes (residual links) while the links connecting to the removed nodes (exhausted links) are entirely ignored. In this Letter, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic spreading process on real networks, we show that the MDD method can outperform the k-shell and degree methods in ranking spreaders.     

Social power and opinion formation in complex networks

In this paper we investigate the effects of social power on the evolution of opinions in model networks as well as in a number of real social networks. A continuous opinion formation model is considered and the analysis is performed through numerical simulation. Social power is given to a proportion of agents selected either randomly or based on their degrees. As artificial network structures, we consider scale-free networks constructed through preferential attachment and Watts–Strogatz networks. Numerical simulations show that scale-free networks with degree-based social power on the hub nodes have an optimal case where the largest number of the nodes reaches a consensus. However, given power to a random selection of nodes could not improve consensus properties. Introducing social power in Watts–Strogatz networks could not significantly change the consensus profile.     

Spectral reconstruction of complex networks

In this paper we study the reconstruction of a network topology from the eigenvalues of its Laplacian matrix. We introduce a simple cost function and consider the tabu search combinatorial optimization method, while comparing its performance when reconstructing different categories of networks-random, regular, small-world, scale-free and clustered-from their eigenvalues. We show that this combinatorial optimization method, together with the information contained in the Laplacian spectrum, allows an exact reconstruction of small networks and leads to good approximations in the case of networks with larger orders. We also show that the method can be used to generate a quasi-optimal topology for a network associated to a dynamic process (like in the case of metabolic or protein-protein interaction networks of organisms).     

Link prediction in complex networks: A survey

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.     

Quantum inspired evolutionary algorithm for community detection in complex networks

Community structure is indispensable to discover the potential property of complex network systems. In this paper we propose two algorithms (QIEA-net and iQIEA-net) to discover communities in social networks by optimizing modularity. Unlike many existing methods, the proposed algorithms adopt quantum inspired evolutionary algorithm (QIEA) to optimize a population of solutions and do not need to give the number of community beforehand, which is determined by optimizing the value of modularity function and needs no human intervention. In order to accelerate the convergence speed, in iQIEA-net, we apply the result of classical partitioning algorithm as a guiding quantum individual, which can instruct other quantum individuals' evolution. We demonstrate the potential of two algorithms on five real social networks. The results of comparison with other community detection algorithms prove our approaches have very competitive performance.     

Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

Cluster synchronization in fractional-order complex dynamical networks

Cluster synchronization of complex dynamical networks with fractional-order dynamical nodes is discussed in the Letter. By using the stability theory of fractional-order differential system and linear pinning control, a sufficient condition for the stability of the synchronization behavior in complex networks with fractional order dynamics is derived. Only the nodes in one community which have direct connections to the nodes in other communities are needed to be controlled, resulting in reduced control cost. A numerical example is presented to demonstrate the validity and feasibility of the obtained result. Numerical simulations illustrate that cluster synchronization performance for fractional-order complex dynamical networks is influenced by inner-coupling matrix, control gain, coupling strength and topological structures of the networks.     

Synchronization in complex networks with switching topology

This Letter investigates synchronization issues of complex dynamical networks with switching topology. By constructing a common Lyapunov function, we show that local and global synchronization for a linearly coupled network with switching topology can be evaluated by the time average of second smallest eigenvalues corresponding to the Laplacians of switching topology. This result is quite powerful and can be further used to explore various switching cases for complex dynamical networks. Numerical simulations illustrate the effectiveness of the obtained results in the end.     

Mixing search on complex networks

In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.     

Epidemic spreading on weighted complex networks

Nowadays, the emergence of online services provides various multi-relation information to support the comprehensive understanding of the epidemic spreading process. In this Letter, we consider the edge weights to represent such multi-role relations. In addition, we perform detailed analysis of two representative metrics, outbreak threshold and epidemic prevalence, on SIS and SIR models. Both theoretical and simulation results find good agreements with each other. Furthermore, experiments show that, on fully mixed networks, the weight distribution on edges would not affect the epidemic results once the average weight of whole network is fixed. This work may shed some light on the in-depth understanding of epidemic spreading on multi-relation and weighted networks.     

Dynamical robustness analysis of weighted complex networks

Robustness of weighted complex networks is analyzed from nonlinear dynamical point of view and with focus on different roles of high-degree and low-degree nodes. We find that the phenomenon for the low-degree nodes being the key nodes in the heterogeneous networks only appears in weakly weighted networks and for weak coupling. For all other parameters, the heterogeneous networks are always highly vulnerable to the failure of high-degree nodes; this point is the same as in the structural robustness analysis. We also find that with random inactivation, heterogeneous networks are always more robust than the corresponding homogeneous networks with the same average degree except for one special parameter. Thus our findings give an integrated picture for the dynamical robustness analysis on complex networks.     

Novel criteria of synchronization stability in complex networks with coupling delays

Complex networks are wide spread in the real world, arising in fields as disparate as sociology, physics and biology. The information spreading through a complex network is often associated with time delays due to the finite speeds of signal transmission over a distance. Hence, complex networks with coupling delays have gained increasing attention in various fields of science and engineering today. In this paper, based on the theory of asymptotic stability of linear time-delay systems, synchronization stability in complex dynamical networks with coupling delays is investigated, and we derive novel criteria of synchronization state for both delay-independent and delay-dependent stabilities. As illustrative examples, we use the networks with coupling delays and a given coupling scheme to test the theoretical results.