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.     

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.     

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.     

Cascading Failures of Complex Networks Based on Two-Step Degree

We propose a new concept, two-step degree. Defining it as the capacity of a node of complex networks, we establish a novel capacity-load model of cascading failures of complex networks where the capacity of nodes decreases during the process of cascading failures. For scale-free networks, we find that the average two-step degree increases with the increase of the heterogeneity of the degree distribution, showing that the average two- step degree can be used for measuring the heterogeneity of the degree distribution of complex networks. In addition, under the condition that the average degree of a node is given, we can design a scale-free network with the optimal robustness to random failures by maximizing the average two-step degree.     

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.     

Cumulative Laws, Team Assembling Mechanisms Determining Network Structure

A number of researching works have shed light on the field of complex networks recently. We investigate a wide range of real-world networks and find several interesting phenomena. Firstly, almost all of these networks evolve by overlapping new small graphs on former networks. Secondly, not only the degree sequence of the mature network follows a power-law distribution, but also the distribution of the cumulative occurrence times during the growing process are revealed to have a heavy tail. Existing network evolving models do not provide interpretation to these phenomena. We suggest a model based on the team assembling mechanism, which is extracted from the growing processes of real-world networks and requires simple parameters, and produces networks exhibiting these properties observed in the present study and in previous works.     

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.     

Prisoner's Dilemma on Co-Evolving Networks without Strategy Update

We investigate the game theory in a structured population with the assumption that the evolution of network structure is far faster than that of strategy update. We find that the degree distribution for the finM network consists of two distinct parts： the low degree part which is contributed to by defectors and a broadband in the regime with high degree which is formed by cooperators. The structure of the final network and the final strategy pattern have also been numerically proved to be independent of the game parameters.     

Analysis of the airport network of India as a complex weighted network

Transportation infrastructure of a country is one of the most important indicators of its economic growth. Here we study the Airport Network of India (ANI) which represents India’s domestic civil aviation infrastructure as a complex network. We find that ANI, a network of domestic airports connected by air links, is a small-world network characterized by a truncated power-law degree distribution and has a signature of hierarchy. We investigate ANI as a weighted network to explore its various properties and compare them with their topological counterparts. The traffic in ANI, as in the World-wide Airport Network (WAN), is found to be accumulated on interconnected groups of airports and is concentrated between large airports. In contrast to WAN, ANI is found to be having disassortative mixing which is offset by the traffic dynamics. The analysis indicates possible mechanism of formation of a national transportation network, which is different from that on a global scale.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

Community structure in the United States House of Representatives

We investigate the networks of committee and subcommittee assignments in the United States House of Representatives from the 101st-108th Congresses, with the committees connected by “interlocks” or common membership. We examine the community structure in these networks using several methods, revealing strong links between certain committees as well as an intrinsic hierarchical structure in the House as a whole. We identify structural changes, including additional hierarchical levels and higher modularity, resulting from the 1994 election, in which the Republican party earned majority status in the House for the first time in more than 40 years. We also combine our network approach with the analysis of roll call votes using singular value decomposition to uncover correlations between the political and organizational structure of House committees.     

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.     

Betweenness centrality in finite components of complex networks

We use generating function formalism to obtain an exact formula of the betweenness centrality in finite components of random networks with arbitrary degree distributions. The formula is obtained as a function of the degree and the component size, and is confirmed by simulations for Poisson, exponential, and power-law degree distributions. We find that the betweenness centralities for the three distributions are asymptotically power laws with an exponent 1.5 and are invariant to the particular distribution parameters.     

Statistical analysis of the Metropolitan Seoul Subway System: Network structure and passenger flows

The Metropolitan Seoul Subway system, consisting of 380 stations, provides the major transportation mode in the metropolitan Seoul area. Focusing on the network structure, we analyze statistical properties and topological consequences of the subway system. We further study the passenger flows on the system, and find that the flow weight distribution exhibits a power-law behavior. In addition, the degree distribution of the spanning tree of the flows also follows a power law.     

Interpersonal interactions and human dynamics in a large social network

We study a large social network consisting of over 10⁶ individuals, who form an Internet community and organize themselves in groups of different sizes. On the basis of the users’ list of friends and other data registered in the database we investigate the structure and time development of the network. The structure of this friendship network is very similar to the structure of different social networks. However, here a degree distribution exhibiting two scaling regimes, power-law for low connectivity and exponential for large connectivity, was found. The groups size distribution and distribution of number of groups of an individual have power-law form. We found very interesting scaling laws concerning human dynamics. Our research has shown how long people are interested in a single task.     

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.     

Limits on relief through constrained exchange on random graphs

Agents are represented by nodes on a random graph (e.g., “small world”). Each agent is endowed with a zero-mean random value that may be either positive or negative. All agents attempt to find relief, i.e., to reduce the magnitude of that initial value, to zero if possible, through exchanges. The exchange occurs only between the agents that are linked, a constraint that turns out to dominate the results. The exchange process continues until Pareto equilibrium is achieved. Only 40-90% of the agents achieved relief on small-world graphs with mean degree between 2 and 40. Even fewer agents achieved relief on scale-free-like graphs with a truncated power-law degree distribution. The rate at which relief grew with increasing degree was slow, only at most logarithmic for all of the graphs considered; viewed in reverse, the fraction of nodes that achieve relief is resilient to the removal of links.     

Universal power laws in the threshold network model: A theoretical analysis based on extreme value theory

We theoretically and numerically investigated the threshold network model with a generic weight function where there were a large number of nodes and a high threshold. Our analysis was based on extreme value theory, which gave us a theoretical understanding of the distribution of independent and identically distributed random variables within a sufficiently high range. Specifically, the distribution could be generally expressed by a generalized Pareto distribution, which enabled us to formulate the generic weight distribution function. By using the theorem, we obtained the exact expressions of degree distribution and clustering coefficient which behaved as universal power laws within certain ranges of degrees. We also compared the theoretical predictions with numerical results and found that they were extremely consistent.     

Deterministic factors of stock networks based on cross-correlation in financial market

The stock market has been known to form homogeneous stock groups with a higher correlation among different stocks according to common economic factors that influence individual stocks. We investigate the role of common economic factors in the market in the formation of stock networks, using the arbitrage pricing model reflecting essential properties of common economic factors. We find that the degree of consistency between real and model stock networks increases as additional common economic factors are incorporated into our model. Furthermore, we find that individual stocks with a large number of links to other stocks in a network are more highly correlated with common economic factors than those with a small number of links. This suggests that common economic factors in the stock market can be understood in terms of deterministic factors.     

A weighted network evolution with traffic flow

In this paper, we propose a simple weighted network model that generalizes the complex network model evolution with traffic flow previously presented to investigate the relationship between traffic flow and network structure. In the model, the nodes in the network are represented by the traffic flow states, the links in the network are represented by the transform of the traffic flow states, and the traffic flow transported when performing the transform of the traffic flow states is considered as the weight of the link. Several topological features of this generalized weighted model, such as the degree distribution and strength distribution, have been numerically studied. A scaling behavior between the strength and degree s∼klogk is obtained. By introducing some constraints to the generalized weighted model, we study its subnetworks and find that the scaling behavior between the strength and degree is conserved, though the topology properties are quite sensitive to the constraints.