Properties of on-line social systems

We study properties of five different social systems: (i) internet society of friends consisting of over 10⁶ people, (ii) social network consisting of 3 × 10⁴ individuals, who interact in a large virtual world of Massive Multiplayer Online Role Playing Games (MMORPGs), (iii) over 10⁶ users of music community website, (iv) over 5 × 10⁶ users of gamers community server and (v) over 0.25 × 10⁶ users of books admirer website. Individuals included in large social network form an Internet community and organize themselves in groups of different sizes. The destiny of those systems, as well as the method of creating of new connections, are different, however we found that the properties of these networks are very similar. We have found that the network components size distribution follow the power-law scaling form. In all five systems we have found interesting scaling laws concerning human dynamics. Our research has shown how long people are interested in a single task, how much time they devote to it and how fast they are making friends. It is surprising that the time evolution of an individual connectivity is very similar in each system.     

Human behavior in online social systems

We present and study data concerning human behavior in four online social systems: (i) an Internet community of friends of over 10⁷ people, (ii) a music community website with over 10⁶ users, (iii) a gamers’ community server with over 5 × 10⁶ users and (iv) a booklovers’ website with over 2.5 × 10⁵ users. The purpose of those systems is different; however, their properties are very similar. We have found that the distribution of human activity (e.g., the sum of books read or songs played) has the form of a power law. Moreover, the relationship between human activity and time has a power-law form, too. We present a simple interest-driven model of the evolution of such systems which explains the emergence of two scaling regimes.     

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.     

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.     

Epidemic outbreaks in growing scale-free networks with local structure

The class of generative models has already attracted considerable interest from researchers in recent years and much expanded the original ideas described in BA model. Most of these models assume that only one node per time step joins the network. In this paper, we grow the network by adding n interconnected nodes as a local structure into the network at each time step with each new node emanating m new edges linking the node to the preexisting network by preferential attachment. This successfully generates key features observed in social networks. These include power-law degree distribution p_k∼k^−(3+μ), where μ=(n−1)/m is a tuning parameter defined as the modularity strength of the network, nontrivial clustering, assortative mixing, and modular structure. Moreover, all these features are dependent in a similar way on the parameter μ. We then study the susceptible-infected epidemics on this network with identical infectivity, and find that the initial epidemic behavior is governed by both of the infection scheme and the network structure, especially the modularity strength. The modularity of the network makes the spreading velocity much lower than that of the BA model. On the other hand, increasing the modularity strength will accelerate the propagation velocity.     

Opinion formation in a social network: The role of human activity

The model of opinion formation in human population based on social impact theory is investigated numerically. On the basis of a database received from the on-line game server, we examine the structure of social network and human dynamics. We calculate the activity of individuals, i.e. the relative time devoted daily to interactions with others in the artificial society. We study the influence of correlation between the activity of an individual and its connectivity on the process of opinion formation. We find that such correlations have a significant influence on the temperature of the phase transition and the effect of the mass media, modeled as an external stimulation acting on the social network.     

Local affinity in heterogeneous growing networks

In this paper we present a study of the influence of local affinity in heterogeneous preferential attachment (PA) networks. Heterogeneous PA models are a generalization of the Barabási-Albert model to heterogeneous networks, where the affinity between nodes biases the attachment probability of links. Threshold models are a class of heterogeneous PA models where the affinity between nodes is inversely related to the distance between their states. We propose a generalization of threshold models where network nodes have individual affinity functions, which are then combined to yield the affinity of each potential interaction. We analyze the influence of the affinity functions in the topological properties averaged over a network ensemble. The network topology is evaluated through the distributions of connectivity degrees, clustering coefficients and geodesic distances. We show that the relaxation of the criterion of a single global affinity still leads to a reasonable power-law scaling in the connectivity and clustering distributions under a wide spectrum of assumptions. We also show that the richer behavior of the model often exhibits a better agreement with the empirical observations on real networks.     

Robustness of heterogeneous complex networks

In this paper we study the robustness of heterogeneous preferential attachment networks. The robustness of a network measures its structural tolerance to the random removal of nodes and links. We numerically analyze the influence of the affinity parameters on a set of ensemble-averaged robustness metrics. We show that the presence of heterogeneity does not fundamentally alter the smooth nature of the fragmentation process of the models. We also show that a moderate level of locality translates into slight improvements in the robustness metrics, which prompts us to conjecture an evolutionary argument for the existence of real networks with power-law scaling in their connectivity and clustering distributions.     

Scaling relation for earthquake networks

The scaling relation, 2γ−δ=1, for the exponents of the power-law connectivity distribution, γ, and the power-law eigenvalue distribution of the adjacency matrix, δ, is theoretically predicted to be fulfilled by a locally treelike scale-free network in the “effective medium approximation” (i.e., an analog of the mean field approximation). Here, it is shown that such a relation holds well for the reduced simple earthquake networks (i.e., the network without tadpole-loops and multiple edges) constructed from the seismic data taken from California and Japan. This validates the goodness of the effective medium approximation in the earthquake networks and is consistent with the hierarchical organization of the networks. The present result may be useful for modeling seismicity on complex networks.     

Transcriptional regulatory network topology from statistics of DNA binding sites

We show that the out-degree distribution of the gene regulation network of the budding yeast, Saccharomyces cerevisiae, can be reproduced to high accuracy from the statistics of TF binding sequences. Our observation suggests a particular microscopic mechanism for the observed universal global topology in these networks. The numerical data and analytical solution of our model disagree with a simple power-law for the experimentally obtained degree distribution in the case of yeast.     

Network robustness to targeted attacks. The interplay of expansibility and degree distribution

We study the property of certain complex networks of being both sparse and highly connected, which is known as “good expansion” (GE). A network has GE properties if every subset S of nodes (up to 50% of the nodes) has a neighborhood that is larger than some “expansion factor” φ multiplied by the number of nodes in S. Using a graph spectral method we introduce here a new parameter measuring the good expansion character of a network. By means of this parameter we are able to classify 51 real-world complex networks — technological, biological, informational, biological and social — as GENs or non-GENs. Combining GE properties and node degree distribution (DD) we classify these complex networks in four different groups, which have different resilience to intentional attacks against their nodes. The simultaneous existence of GE properties and uniform degree distribution contribute significantly to the robustness in complex networks. These features appear solely in 14% of the 51 real-world networks studied here. At the other extreme we find that ∼40% of all networks are very vulnerable to targeted attacks. They lack GE properties, display skewed DD — exponential or power-law — and their topologies are changed more dramatically by targeted attacks directed at bottlenecks than by the removal of network hubs.     

Geographical dispersal of mobile communication networks

In this paper, we analyze statistical properties of a communication network constructed from the records of a mobile phone company. The network consists of 2.5 million customers that have placed 810 million communications (phone calls and text messages) over a period of 6 months and for whom we have geographical home localization information. It is shown that the degree distribution in this network has a power-law degree distribution k⁻⁵ and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases as d⁻², where d is the distance between the customers. We also consider the geographical extension of communication triangles and we show that communication triangles are not only composed of geographically adjacent nodes but that they may extend over large distances. This last property is not captured by the existing models of geographical networks and in a last section we propose a new model that reproduces the observed property. Our model, which is based on the migration and on the local adaptation of agents, is then studied analytically and the resulting predictions are confirmed by computer simulations.     

A complex network model based on the Gnutella protocol

Gnutella is one of the basic protocols for P2P software. In this paper, a novel network model based on Gnutella is introduced. The mechanism of this network is based on resource occupancy and search activities of peers. As for the structure, the power-law exponent of in-degree γ_in≈4.2, the length of the average shortest path 〈l〉=57.74, and the diameter of the network is 156; these topological properties of the proposed structure differ from known results.     

Scale-free networks by super-linear preferential attachment rule

A network growth model with geographic limitation of accessible information about the status of existing nodes is investigated. In this model, the probability Π(k) of an existing node of degree k is found to be super-linear with Π(k)∼k^α and α>1 when there are links from new nodes. The numerical results show that the constructed networks have typical power-law degree distributions P(k)∼k^−γ and the exponent γ depends on the constraint level. An analysis of local structural features shows the robust emergence of scale-free network structure in spite of the super-linear preferential attachment rule. This local structural feature is directly associated with the geographical connection constraints which are widely observed in many real networks.     

Degree distributions of the visibility graphs mapped from fractional Brownian motions and multifractal random walks

The dynamics of a complex system is usually recorded in the form of time series, which can be studied through its visibility graph from a complex network perspective. We investigate the visibility graphs extracted from fractional Brownian motions and multifractal random walks, and find that the degree distributions exhibit power-law behaviors, in which the power-law exponent α is a linear function of the Hurst index H of the time series. We also find that the degree distribution of the visibility graph is mainly determined by the temporal correlation of the original time series with minor influence from the possible multifractal nature. As an example, we study the visibility graphs constructed from three Chinese stock market indexes and unveil that the degree distributions have power-law tails, where the tail exponents of the visibility graphs and the Hurst indexes of the indexes are close to the α∼H linear relationship.     

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.     

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.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Scale-free networks without growth

In this paper, we proposed an ungrowing scale-free network model, indicating the growth may not be a necessary condition of the self-organization of a network in a scale-free structure. The analysis shows that the degree distributions of the present model can varying from the Poisson form to the power-law form with the decrease of a free parameter α. This model provides a possible mechanism for the evolution of some scale-free networks with fixed size, such as the friendship networks of school children and the functional networks of the human brain.