The role of syntax in complex networks: Local and global importance of verbs in a syntactic dependency network

Syntax of natural language has been the focus of linguistics for decades. The complex network theory, being one of new research tools, opens new perspectives on syntax properties of the language. Despite numerous partial achievements, some fundamental problems remain unsolved. Specifically, although statistical properties typical for complex networks can be observed in all syntactic networks, the impact of syntax itself on these properties is still unclear. The aim of the present study is to shed more light on the role of syntax in the syntactic network structure. In particular, we concentrate on the impact of the syntactic function of a verb in the sentence on the complex network structure. Verbs play the decisive role in the sentence structure (“local” importance). From this fact we hypothesize the importance of verbs in the complex network (“global” importance). The importance of verb in the complex network is assessed by the number of links which are directed from the node representing verb to other nodes in the network. Six languages (Catalan, Czech, Dutch, Hungarian, Italian, Portuguese) were used for testing the hypothesis.     

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.     

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.     

Analysis of networks using generalized mutual entropies

Generalized mutual entropy is defined for networks and applied in the analysis of complex network structures. The method is tested for the case of computer simulated scale-free networks, random networks, and their mixtures. The possible applications for real network analysis are discussed.     

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.     

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.     

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

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.     

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

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.     

Analyzing complex networks evolution through Information Theory quantifiers

A methodology to analyze dynamical changes in complex networks based on Information Theory quantifiers is proposed. The square root of the Jensen-Shannon divergence, a measure of dissimilarity between two probability distributions, and the MPR Statistical Complexity are used to quantify states in the network evolution process. Three cases are analyzed, the Watts-Strogatz model, a gene network during the progression of Alzheimer's disease and a climate network for the Tropical Pacific region to study the El Niño/Southern Oscillation (ENSO) dynamic. We find that the proposed quantifiers are able not only to capture changes in the dynamics of the processes but also to quantify and compare states in their evolution.     

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.     

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.     

Detecting the structure of complex networks by quantum bosonic dynamics

In this paper, we introduce a non-interacting boson model to investigate the topological structure of complex networks. By exactly solving this model, we show that it provides a powerful analytical tool in uncovering the important properties of realistic networks. We find that the ground-state degeneracy of this model is equal to the number of connected components in a network and the square of each coefficient in the expansion of the ground state gives the average time that a random walker spends at each node in the infinite time limit. To show the usefulness of this approach in practice, we also carry out numerical simulations on some concrete complex networks. Our results are completely consistent with the previous conclusions derived by graph theory methods. Furthermore, we show that the first excited state appears always on the largest connected component of the network. The relationship between the first excited energy and the average shortest path length in networks is also discussed.     

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.