The network of scientific collaborations within the European framework programme

We use the emergent field of complex networks to analyze the network of scientific collaborations between entities (universities, research organizations, industry related companies,…) which collaborate in the context of the so-called framework programme. We demonstrate here that it is a scale-free network with an accelerated growth, which implies that the creation of new collaborations is encouraged. Moreover, these collaborations possess hierarchical modularity. Likewise, we find that the information flow depends on the size of the participants but not on geographical constraints.     

A new deterministic complex network model with hierarchical structure

We introduce a new simple pseudo tree-like network model, deterministic complex network (DCN). The proposed DCN model may simulate the hierarchical structure nature of real networks appropriately and have the unique property of ‘skipping the levels’, which is ubiquitous in social networks. Our results indicate that the DCN model has a rather small average path length and large clustering coefficient, leading to the small-world effect. Strikingly, our DCN model obeys a discrete power-law degree distribution P(k)∝k^−γ, with exponent γ approaching 1.0. We also discover that the relationship between the clustering coefficient and degree follows the scaling law C(k)∼k⁻¹, which quantitatively determines the DCN's hierarchical structure.     

An empirical study of Chinese language networks

Chinese is spoken by the largest number of people in the world, and it is regarded as one of the most important languages. In this paper, we explore the statistical properties of Chinese language networks (CLNs) within the framework of complex network theory. Based on one of the largest Chinese corpora, i.e. People’s Daily Corpus, we construct two networks (CLN1 and CLN2) from two different respects, with Chinese words as nodes. In CLN1, a link between two nodes exists if they appear next to each other in at least one sentence; in CLN2, a link represents that two nodes appear simultaneously in a sentence. We show that both networks exhibit small-world effect, scale-free structure, hierarchical organization and disassortative mixing. These results indicate that in many topological aspects Chinese language shapes complex networks with organizing principles similar to other previously studied language systems, which shows that different languages may have some common characteristics in their evolution processes. We believe that our research may shed some new light into the Chinese language and find some potentially significant implications.     

Modeling network growth with assortative mixing

We propose a model of an underlying mechanism responsible for the formation of assortative mixing in networks between “similar” nodes or vertices based on generic vertex properties. Existing models focus on a particular type of assortative mixing, such as mixing by vertex degree, or present methods of generating a network with certain properties, rather than modeling a mechanism driving assortative mixing during network growth. The motivation is to model assortative mixing by non-topological vertex properties, and the influence of these non-topological properties on network topology. The model is studied in detail for discrete and hierarchical vertex properties, and we use simulations to study the topology of resulting networks. We show that assortative mixing by generic properties directly drives the formation of community structure beyond a threshold assortativity of r ∼0.5, which in turn influences other topological properties. This direct relationship is demonstrated by introducing a new measure to characterise the correlation between assortative mixing and community structure in a network. Additionally, we introduce a novel type of assortative mixing in systems with hierarchical vertex properties, from which a hierarchical community structure is found to result. Electronic supplementary material Supplementary Online Material     

From unweighted to weighted networks with local information

In this paper, we analyze an evolving model with local information which can generate a class of networks by choosing different values of the parameter p. The model introduced exhibits the transition from unweighted networks to weighted networks because the distribution of the edge weight can be widely tuned. With the increase in the local information, the degree correlation of the network transforms from assortative to disassortative. We also study the distribution of the degree, strength and edge weight, which all show crossover between exponential and scale-free. Finally, an application of the proposed model to the study of the synchronization is considered. It is concluded that the synchronizability is enhanced when the heterogeneity of the edge weight is reduced.     

From regular to growing small-world networks

We propose a growing model which interpolates between one-dimensional regular lattice and small-world networks. The model undergoes an interesting phase transition from large to small worlds. We investigate the structural properties by both theoretical predictions and numerical simulations. Our growing model is a complementarity for the important static Watts-Strogatz network model.     

Networks of interactions in the secondary and tertiary structure of ribosomal RNA

We construct four different structural networks for both the secondary and tertiary structures of the 16S and 23S ribosomal RNAs (rRNAs) in the high-resolution crystal structures of the Thermus thermophilus 30S and Haloarcula marismortui 50S ribosomal subunits, and investigate topological characteristics of the rRNA structures by determining relevant measures, such as the characteristic path length, the clustering coefficient, and the helix betweenness. This study reveals that the 23S rRNA network is more compact than the 16S rRNA networks, reflecting the more globular overall structure of the 23S rRNA relative to the 16S rRNA. In particular, the large number of tertiary interactions in the 23S rRNA tends to cluster, accounting for its small-world network properties. In addition, although the rRNA networks are not the scale-free network, their helix betweenness has a power-law distribution and is correlated with the phylogenetic conservation of helices. The higher the helix betweenness, the more conserved the helix. These results suggest a potential role of the rRNA network as a new quantitative approach in rRNA research.     

Inevitable self-similar topology of binary trees and their diverse hierarchical density

Self-similar topology, which can be characterized as power law size distribution, has been found in diverse tree networks ranging from river networks to taxonomic trees. In this study, we find that the statistical self-similar topology is an inevitable consequence of any full binary tree organization. We show this by coding a binary tree as a unique bifurcation string. This coding scheme allows us to investigate trees over the realm from deterministic to entirely random trees. To obtain partial random trees, partial random perturbation is added to the deterministic trees by an operator similar to that used in genetic algorithms. Our analysis shows that the hierarchical density of binary trees is more diverse than has been described in earlier studies. We find that the connectivity structure of river networks is far from strict self-similar trees. On the other hand, organization of some social networks is close to deterministic supercritical trees.     

On the spreading and localization of risky information in social networks

We propose a model for the localization of risky information in social (scale free) networks where we assume that risky information can propagate only between “mutually trusted nodes” (MTN). We propose an algorithm to construct the MTN network and show that there is a critical value of trusted nodes below which information localizes. This critical value increases drastically if a fraction p of nodes does not transfer information at all. We study the fraction of initial messengers needed to inform a desired fraction of the network as a function of the average number of trusted nodes and discuss possible applications of the model also to marketing and to the spreading of a disease with very short incubation time.     

Community structure in Congressional cosponsorship networks

We study the United States Congress by constructing networks between Members of Congress based on the legislation that they cosponsor. Using the concept of modularity, we identify the community structure of Congressmen, who are connected via sponsorship/cosponsorship of the same legislation. This analysis yields an explicit and conceptually clear measure of political polarization, demonstrating a sharp increase in partisan polarization which preceded and then culminated in the 104th Congress (1995-1996), when Republicans took control of both chambers of Congress. Although polarization has since waned in the U.S. Senate, it remains at historically high levels in the House of Representatives.     

A very fast algorithm for detecting community structures in complex networks

In this paper, a new algorithm is proposed, which uses only local information to analyze community structures in complex networks. The algorithm is based on a table that describes a network and a virtual cache similar to the cache in the computer structure. When being tested on some typical computer-generated and real-world networks, this algorithm demonstrates excellent detection results and very fast processing performance, much faster than the existing comparable algorithms of the same kind.     

Immunization of susceptible-infected model on scale-free networks

In this paper, we investigate two major immunization strategies, random immunization and targeted immunization, of the susceptible-infected (SI) model on the Barabási-Albert (BA) networks. For the heterogeneous structure, the random strategy is quite ineffective if the vaccinated proportion is small, while the targeted one which prefers to vaccinate the individuals with the largest degree can sharply depress the epidemic spreading even only a tiny fraction of population are vaccinated. The analytical solution is also obtained, which can capture the trend of velocity change vs. the amount of vaccinated population.     

Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices

In this paper, firstly, we study analytically the topological features of a family of hierarchical lattices (HLs) from the view point of complex networks. We derive some basic properties of HLs controlled by a parameter q: scale-free degree distribution with exponent γ=2+ln 2/(ln q), null clustering coefficient, power-law behavior of grid coefficient, exponential growth of average path length (non-small-world), fractal scaling with dimension d_B=ln (2q)/(ln 2), and disassortativity. Our results show that scale-free networks are not always small-world, and support the conjecture that self-similar scale-free networks are not assortative. Secondly, we define a deterministic family of graphs called small-world hierarchical lattices (SWHLs). Our construction preserves the structure of hierarchical lattices, including its degree distribution, fractal architecture, clustering coefficient, while the small-world phenomenon arises. Finally, the dynamical processes of intentional attacks and collective synchronization are studied and the comparisons between HLs and Barabási-Albert (BA) networks as well as SWHLs are shown. We find that the self-similar property of HLs and SWHLs significantly increases the robustness of such networks against targeted damage on hubs, as compared to the very vulnerable non fractal BA networks, and that HLs have poorer synchronizability than their counterparts SWHLs and BA networks. We show that degree distribution of scale-free networks does not suffice to characterize their synchronizability, and that networks with smaller average path length are not always easier to synchronize.     

Ensemble inequivalence in random graphs

We present a complete analytical solution of a system of Potts spins on a random k-regular graph in both the canonical and microcanonical ensembles, using the Large Deviation Cavity Method (LDCM). The solution is shown to be composed of three different branches, resulting in a non-concave entropy function. The analytical solution is confirmed with numerical Metropolis and Creutz simulations and our results clearly demonstrate the presence of a region with negative specific heat and, consequently, ensemble inequivalence between the canonical and microcanonical ensembles.     

Multi-directed Eulerian growing networks

We introduce and analyze a model of a multi-directed Eulerian network, that is a directed and weighted network where a path exists that passes through all the edges of the network once and only once. Networks of this type can be used to describe information networks such as human language or DNA chains. We are able to calculate the strength and degree distribution in this network and find that they both exhibit a power law with an exponent between 2 and 3. We then analyze the behavior of the accelerated version of the model and find that the strength distribution has a double slope power-law behavior. Finally we introduce a non-Eulerian version of the model and find that the statistical topological properties remain unchanged. Our analytical results are compared with numerical simulations.     

Empirical analysis of the evolution of a scientific collaboration network

We present an analysis of the temporal evolution of a scientific coauthorship network, the genetic programming network. We find evidence that the network grows according to preferential attachment, with a slightly sublinear rate. We empirically find how a giant component forms and develops, and we characterize the network by several other time-varying quantities: the mean degree, the clustering coefficient, the average path length, and the degree distribution. We find that the first three statistics increase over time in the growing network; the degree distribution tends to stabilize toward an exponentially truncated power-law. We finally suggest an effective network interpretation that takes into account the aging of collaboration relationships.     

Unified index to quantifying heterogeneity of complex networks

Although recent studies have revealed that degree heterogeneity of a complex network has significant impact on the network performance and function, a unified definition of the heterogeneity of a network with any degree distribution is absent. In this paper, we define a heterogeneity index 0≤H<1 to quantify the degree heterogeneity of any given network. We analytically show the existence of an upper bound of H=0.5 for exponential networks, thus explain why exponential networks are homogeneous. On the other hand, we also analytically show that the heterogeneity index of an infinite power law network is between 1 and 0.5 if and only if its degree exponent is between 2 and 2.5. We further show that for any power law network with a degree exponent greater than 2.5, there always exists an exponential network such that both networks have the same heterogeneity index. This may help to explain why 2.5 is a critical degree exponent for some dynamic behaviors on power law networks.     

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.     

Synchronization in complex networks

Synchronization processes in populations of locally interacting elements are the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understanding synchronization phenomena in natural systems now take advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also take an overview of the new emergent features coming out from the interplay between the structure and the function of the underlying patterns of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.