Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

The Tutte polynomial of an infinite family of outerplanar,small-world and self-similar graphs

In this paper we recursively describe the Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs. In particular, we study the Abelian Sandpile Model on these graphs and obtain the generating function of the recurrent configurations. Further, we give some exact analytical expression for the Tutte polynomial at several special points     

The number of spanning trees of an infinite family of outerplanar,small-world and self-similar graphs

In this paper we give an exact analytical expression for the number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. This number is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. The calculation of the number of spanning trees is a demanding and difficult task, in particular for large graphs, and thus there is much interest in obtaining closed expressions for relevant infinite graph families. We have also calculated the spanning tree entropy of the graphs which we have compared with those for graphs with the same average degree.     

Deterministic self-similar models of complex networks based on very symmetric graphs

Using very symmetric graphs we generalize several deterministic self-similar models of complex networks and we calculate the main network parameters of our generalization. More specifically, we calculate the order, size and the degree distribution, and we give an upper bound for the diameter and a lower bound for the clustering coefficient. These results yield conditions under which the network is a self-similar and scale-free small world network. We remark that all these conditions are posed on a small base graph which is used in the construction. As a consequence, we can construct complex networks having prescribed properties. We demonstrate this fact on the clustering coefficient. We propose eight new infinite classes of complex networks. One of these new classes is so rich that it is parametrized by three independent parameters.     

Characterizing emerging European stock markets through complex networks: From local properties to self-similar characteristics

We investigate the properties of the returns of the main emerging stock markets from Europe by means of complex networks. We transform the series of daily returns into complex networks, and analyze the local properties of these networks with respect to degree distributions, clustering, or average line length. We further use the clustering coefficients as quantities describing the local structure of the network, and approach them by using multifractal analysis. We find evidence of scale-free networks and multifractality of clustering coefficients.     

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.     

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.     

Approaching human language with complex networks

The interest in modeling and analyzing human language with complex networks is on the rise in recent years and a considerable body of research in this area has already been accumulated. We survey three major lines of linguistic research from the complex network approach: 1) characterization of human language as a multi-level system with complex network analysis; 2) linguistic typological research with the application of linguistic networks and their quantitative measures; and 3) relationships between the system-level complexity of human language (determined by the topology of linguistic networks) and microscopic linguistic (e.g., syntactic) features (as the traditional concern of linguistics). We show that the models and quantitative tools of complex networks, when exploited properly, can constitute an operational methodology for linguistic inquiry, which contributes to the understanding of human language and the development of linguistics. We conclude our review with suggestions for future linguistic research from the complex network approach: 1) relationships between the system-level complexity of human language and microscopic linguistic features; 2) expansion of research scope from the global properties to other levels of granularity of linguistic networks; and 3) combination of linguistic network analysis with other quantitative studies of language (such as quantitative linguistics).     

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.     

A review of fractality and self-similarity in complex networks

We review recent findings of self-similarity in complex networks. Using the box-covering technique, it was shown that many networks present a fractal behavior, which is seemingly in contrast to their small-world property. Moreover, even non-fractal networks have been shown to present a self-similar picture under renormalization of the length scale. These results have an important effect in our understanding of the evolution and behavior of such systems. A large number of network properties can now be described through a set of simple scaling exponents, in analogy with traditional fractal theory.     

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.     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

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).     

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.     

Study of a market model with conservative exchanges on complex networks

Many models of market dynamics make use of the idea of conservative wealth exchanges among economic agents. A few years ago an exchange model using extremal dynamics was developed and a very interesting result was obtained: a self-generated minimum wealth or poverty line. On the other hand, the wealth distribution exhibited an exponential shape as a function of the square of the wealth. These results have been obtained both considering exchanges between nearest neighbors or in a mean field scheme. In the present paper we study the effect of distributing the agents on a complex network. We have considered archetypical complex networks: Erdös–Rényi random networks and scale-free networks. The presence of a poverty line with finite wealth is preserved but spatial correlations are important, particularly between the degree of the node and the wealth. We present a detailed study of the correlations, as well as the changes in the Gini coefficient, that measures the inequality, as a function of the type and average degree of the considered networks.     

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.     

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.     

Analyzing open-source software systems as complex networks

Software systems represent one of the most complex man-made artifacts. Understanding the structure of software systems can provide useful insights into software engineering efforts and can potentially help the development of complex system models applicable to other domains. In this paper, we analyze one of the most popular open-source Linux meta packages/distributions called the Gentoo Linux. In our analysis, we model software packages as nodes and dependencies among them as edges. Our empirical results show that the resulting Gentoo network cannot be easily explained by existing complex network models. This in turn motivates our research in developing two new network growth models in which a new node is connected to an old node with the probability that depends not only on the degree but also on the “age” of the old node. Through computational and empirical studies, we demonstrate that our models have better explanatory power than the existing ones. In an effort to further explore the properties of these new models, we also present some related analytical results.     

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.