Maximal planar networks with large clustering coefficient and power-law degree distribution

Random Apollonian networks with tailored clustering coefficient

We introduce a family of complex networks that interpolates between the Apollonian network and its binary version, recently introduced in E. M. K. Souza et al. [Phys. Rev. E 107, 024305 (2023)2470-004510.1103/PhysRevE.107.024305], via random removal of nodes. The dilution process allows the clustering coefficient to vary from C=0.828 to C=0 while maintaining the behavior of average path length and other relevant quantities as in the deterministic Apollonian network. Robustness against the random deletion of nodes is also reported on spectral quantities such as the ground-state localization degree and its energy gap to the first excited state. The loss of the 2π/3 rotation symmetry as a treelike network emerges is investigated in the light of the hub wavefunction amplitude. Our findings expose the interplay between the small-world property and other distinctive traits exhibited by Apollonian networks, as well as their resilience against random attacks.

Nearest-neighbor directed random hyperbolic graphs

Undirected hyperbolic graph models have been extensively used as models of scale-free small-world networks with high clustering coefficient. Here we presented a simple directed hyperbolic model where nodes randomly distributed on a hyperbolic disk are connected to a fixed number m of their nearest spatial neighbors. We introduce also a canonical version of this network (which we call "network with varied connection radius"), where maximal length of outgoing bond is space dependent and is determined by fixing the average out-degree to m. We study local bond length, in-degree, and reciprocity in these networks as a function of spacial coordinates of the nodes and show that the network has a distinct core-periphery structure. We show that for small densities of nodes the overall in-degree has a truncated power-law distribution. We demonstrate that reciprocity of the network can be regulated by adjusting an additional temperature-like parameter without changing other global properties of the network.

EasyGraph: A multifunctional, cross-platform, and effective library for interdisciplinary network analysis

Networks are powerful tools for representing the relationships and interactions between entities in various disciplines. However, existing network analysis tools and packages either lack powerful functionality or are not scalable for large networks. In this descriptor, we present EasyGraph, an open-source network analysis library that supports several network data formats and powerful network mining algorithms. EasyGraph provides excellent operating efficiency through a hybrid Python/C++ implementation and multiprocessing optimization. It is applicable to various disciplines and can handle large-scale networks. We demonstrate the effectiveness and efficiency of EasyGraph by applying crucial metrics and algorithms to random and real-world networks in domains such as physics, chemistry, and biology. The results demonstrate that EasyGraph improves the network analysis efficiency for users and reduces the difficulty of conducting large-scale network analysis. Overall, it is a comprehensive and efficient open-source tool for interdisciplinary network analysis.

Globally learning gene regulatory networks based on hidden atomic regulators from transcriptomic big data

BACKGROUND

Genes are regulated by various types of regulators and most of them are still unknown or unobserved. Current gene regulatory networks (GRNs) reverse engineering methods often neglect the unknown regulators and infer regulatory relationships in a local and sub-optimal manner.

RESULTS

This paper proposes a global GRNs inference framework based on dictionary learning, named dlGRN. The method intends to learn atomic regulators (ARs) from gene expression data using a modified dictionary learning (DL) algorithm, which reflects the whole gene regulatory system, and predicts the regulation between a known regulator and a target gene in a global regression way. The modified DL algorithm fits the scale-free property of biological network, rendering dlGRN intrinsically discern direct and indirect regulations.

CONCLUSIONS

Extensive experimental results on simulation and real-world data demonstrate the effectiveness and efficiency of dlGRN in reverse engineering GRNs. A novel predicted transcription regulation between a TF TFAP2C and an oncogene EGFR was experimentally verified in lung cancer cells. Furthermore, the real application reveals the prevalence of DNA methylation regulation in gene regulatory system. dlGRN can be a standalone tool for GRN inference for its globalization and robustness.

Scale-Free Loopy Structure is Resistant to Noise in Consensus Dynamics in Complex Networks

The vast majority of real-world networks are scale-free, loopy, and sparse, with a power-law degree distribution and a constant average degree. In this paper, we study first-order consensus dynamics in binary scale-free networks, where vertices are subject to white noise. We focus on the coherence of networks characterized in terms of the H ₂ -norm, which quantifies how closely the agents track the consensus value. We first provide a lower bound of coherence of a network in terms of its average degree, which is independent of the network order. We then study the coherence of some sparse, scale-free real-world networks, which approaches a constant. We also study numerically the coherence of Barabási-Albert networks and high-dimensional random Apollonian networks, which also converges to a constant when the networks grow. Finally, based on the connection of coherence and the Kirchhoff index, we study analytically the coherence of two deterministically growing sparse networks and obtain the exact expressions, which tend to small constants. Our results indicate that the effect of noise on the consensus dynamics in power-law networks is negligible. We argue that scale-free topology, together with loopy structure, is responsible for the strong robustness with respect to noisy consensus dynamics in power-law networks.

Synchronization Stability Model of Complex Brain Networks: An EEG Study

In this paper, from the perspective of complex network dynamics we investigated the formation of the synchronization state of the brain networks. Based on the Lyapunov stability theory of complex networks, a synchronous steady-state model suitable for application to complex dynamic brain networks was proposed. The synchronization stability problem of brain network state equation was transformed into a convex optimization problem with Block Coordinate Descent (BCD) method. By using Random Apollo Network (RAN) method as a node selection rule, the brain network constructs its subnet work dynamically. We also analyzes the change of the synchronous stable state of the subnet work constructed by this method with the increase of the size of the network. Simulation EEG data from alcohol addicts patients and Real experiment EEG data from schizophrenia patients were used to verify the robustness and validity of the proposed model. Differences in the synchronization characteristics of the brain networks between normal and alcoholic patients were analyzed, so as differences between normal and schizophrenia patients. The experimental results indicated that the establishment of a synchronous steady state model in this paper could be used to verify the synchronization of complex dynamic brain networks and potentially be of great value in the further study of the pathogenic mechanisms of mental illness.

Coevolution spreading in complex networks

The propagations of diseases, behaviors and information in real systems are rarely independent of each other, but they are coevolving with strong interactions. To uncover the dynamical mechanisms, the evolving spatiotemporal patterns and critical phenomena of networked coevolution spreading are extremely important, which provide theoretical foundations for us to control epidemic spreading, predict collective behaviors in social systems, and so on. The coevolution spreading dynamics in complex networks has thus attracted much attention in many disciplines. In this review, we introduce recent progress in the study of coevolution spreading dynamics, emphasizing the contributions from the perspectives of statistical mechanics and network science. The theoretical methods, critical phenomena, phase transitions, interacting mechanisms, and effects of network topology for four representative types of coevolution spreading mechanisms, including the coevolution of biological contagions, social contagions, epidemic-awareness, and epidemic-resources, are presented in detail, and the challenges in this field as well as open issues for future studies are also discussed.

The N-star network evolution model

A new network evolution model is introduced in this paper. The model is based on cooperations of N units. The units are the nodes of the network and the cooperations are indicated by directed links. At each evolution step N units cooperate, which formally means that they form a directed N-star subgraph. At each step either a new unit joins the network and it cooperates with N − 1 old units, or N old units cooperate. During the evolution both preferential attachment and uniform choice are applied. Asymptotic power law distributions are obtained both for in-degrees and for out-degrees.

Participation shifts explain degree distributions in a human communications network

Human interpersonal communications drive political, technological, and economic systems, placing importance on network link prediction as a fundamental problem of the sciences. These systems are often described at the network-level by degree counts —the number of communication links associated with individuals in the network—that often follow approximate Pareto distributions, a divergence from Poisson-distributed counts associated with random chance. A defining challenge is to understand the inter-personal dynamics that give rise to such heavy-tailed degree distributions at the network-level; primarily, these distributions are explained by preferential attachment, which, under certain conditions, can create power law distributions; preferential attachment’s prediction of these distributions breaks down, however, in conditions with no network growth. Analysis of an organization’s email network suggests that these degree distributions may be caused by the existence of individual participation-shift dynamics that are necessary for coherent communication between humans. We find that the email network’s degree distribution is best explained by turn-taking and turn-continuing norms present in most social network communication. We thus describe a mechanism to explain a long-tailed degree distribution in conditions with no network growth.

Statistics of the network of organic chemistry

A comprehensive analysis of statistical properties of a network of organic reactions reveals several generic traits. This knowledge can be used in the development of optimal reaction sequences.

Weighted growing simplicial complexes

Simplicial complexes describe collaboration networks, protein interaction networks, and brain networks and in general network structures in which the interactions can include more than two nodes. In real applications, often simplicial complexes are weighted. Here we propose a nonequilibrium model for weighted growing simplicial complexes. The proposed dynamics is able to generate weighted simplicial complexes with a rich interplay between weights and topology emerging not just at the level of nodes and links, but also at the level of faces of higher dimension.

Lower bound of assortativity coefficient in scale-free networks

The degree-degree correlation is important in understanding the structural organization of a network and dynamics upon a network. Such correlation is usually measured by the assortativity coefficient r, with natural bounds r∈[-1,1]. For scale-free networks with power-law degree distribution p(k)∼k^-γ, we analytically obtain the lower bound of assortativity coefficient in the limit of large network size, which is not -1 but dependent on the power-law exponent γ. This work challenges the validation of the assortativity coefficient in heterogeneous networks, suggesting that one cannot judge whether a network is positively or negatively correlated just by looking at its assortativity coefficient alone.

On the Fractality of Complex Networks: Covering Problem, Algorithms and Ahlfors Regularity

In this paper, we revisit the fractality of complex network by investigating three dimensions with respect to minimum box-covering, minimum ball-covering and average volume of balls. The first two dimensions are calculated through the minimum box-covering problem and minimum ball-covering problem. For minimum ball-covering problem, we prove its NP-completeness and propose several heuristic algorithms on its feasible solution, and we also compare the performance of these algorithms. For the third dimension, we introduce the random ball-volume algorithm. We introduce the notion of Ahlfors regularity of networks and prove that above three dimensions are the same if networks are Ahlfors regular. We also provide a class of networks satisfying Ahlfors regularity.

Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees

Let r and d be positive integers with r<d. Consider a random d-ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random leaf and give it d newly created offspring. Let 𝒯d,t be the tree produced after t steps. We show that there exists a fixed δ<1 depending on d and r such that almost surely for all large t, every r-ary subtree of 𝒯d,t has less than tδ vertices. The proof involves analysis that also yields a related result. Consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. In this way, one face is destroyed and three new faces are created. After t steps, we obtain a random triangulated plane graph with t+3 vertices, which is called a random Apollonian network. We prove that there exists a fixed δ<1, such that eventually every path in this graph has length less than t𝛿, which verifies a conjecture of Cooper and Frieze (2015).

Degrees and distances in random and evolving apollonian networks

In this paper we study random Apollonian networks (RANs) and evolving Apollonian networks (EANs), in d dimensions for any d≥2, i.e. dynamically evolving random d-dimensional simplices, looked at as graphs inside an initial d-dimensional simplex. We determine the limiting degree distribution in RANs and show that it follows a power-law tail with exponent τ=(2d-1)/(d-1). We further show that the degree distribution in EANs converges to the same degree distribution if the simplex-occupation parameter in the nth step of the dynamics tends to 0 but is not summable in n. This result gives a rigorous proof for the conjecture of Zhang et al. (2006) that EANs tend to exhibit similar behaviour as RANs once the occupation parameter tends to 0. We also determine the asymptotic behaviour of the shortest paths in RANs and EANs for any d≥2. For RANs we show that the shortest path between two vertices chosen u.a.r. (typical distance), the flooding time of a vertex chosen uniformly at random, and the diameter of the graph after n steps all scale as a constant multiplied by log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar central limit theorem for typical distances in EANs.

Evolving Scale-Free Networks by Poisson Process: Modeling and Degree Distribution

Since the great mathematician Leonhard Euler initiated the study of graph theory, the network has been one of the most significant research subject in multidisciplinary. In recent years, the proposition of the small-world and scale-free properties of complex networks in statistical physics made the network science intriguing again for many researchers. One of the challenges of the network science is to propose rational models for complex networks. In this paper, in order to reveal the influence of the vertex generating mechanism of complex networks, we propose three novel models based on the homogeneous Poisson, nonhomogeneous Poisson and birth death process, respectively, which can be regarded as typical scale-free networks and utilized to simulate practical networks. The degree distribution and exponent are analyzed and explained in mathematics by different approaches. In the simulation, we display the modeling process, the degree distribution of empirical data by statistical methods, and reliability of proposed networks, results show our models follow the features of typical complex networks. Finally, some future challenges for complex systems are discussed.

Network geometry with flavor: From complexity to quantum geometry

Network geometry is attracting increasing attention because it has a wide range of applications, ranging from data mining to routing protocols in the Internet. At the same time advances in the understanding of the geometrical properties of networks are essential for further progress in quantum gravity. In network geometry, simplicial complexes describing the interaction between two or more nodes play a special role. In fact these structures can be used to discretize a geometrical d-dimensional space, and for this reason they have already been widely used in quantum gravity. Here we introduce the network geometry with flavor s=-1,0,1 (NGF) describing simplicial complexes defined in arbitrary dimension d and evolving by a nonequilibrium dynamics. The NGF can generate discrete geometries of different natures, ranging from chains and higher-dimensional manifolds to scale-free networks with small-world properties, scale-free degree distribution, and nontrivial community structure. The NGF admits as limiting cases both the Bianconi-Barabási models for complex networks, the stochastic Apollonian network, and the recently introduced model for complex quantum network manifolds. The thermodynamic properties of NGF reveal that NGF obeys a generalized area law opening a new scenario for formulating its coarse-grained limit. The structure of NGF is strongly dependent on the dimensionality d. In d=1 NGFs grow complex networks for which the preferential attachment mechanism is necessary in order to obtain a scale-free degree distribution. Instead, for NGF with dimension d>1 it is not necessary to have an explicit preferential attachment rule to generate scale-free topologies. We also show that NGF admits a quantum mechanical description in terms of associated quantum network states. Quantum network states evolve by a Markovian dynamics and a quantum network state at time t encodes all possible NGF evolutions up to time t. Interestingly the NGF remains fully classical but its statistical properties reveal the relation to its quantum mechanical description. In fact the δ-dimensional faces of the NGF have generalized degrees that follow either the Fermi-Dirac, Boltzmann, or Bose-Einstein statistics depending on the flavor s and the dimensions d and δ.

Network analysis in the identification of special mechanisms between small cell lung cancer and non-small cell lung cancer

BACKGROUND

To explore the similar and different pathogenesis between non-small cell lung cancer (NSCLC) and small cell lung cancer (SCLC).

METHODS

This study used bioinformatics methods, including functional enrichment analysis, compared the topological features of SCLC and NSCLC in the human protein interaction network in a system aspect, and analyzed the highly intense modules from an integrated network.

RESULTS

This study included 5082 and 2781 significantly different expression genes for NSCLC and SCLC, respectively. The differently expressed genes of NSCLC are mainly distributed in the extracellular region and synapse. By contrast, the genes of SCLC are located in the organelle, macromolecular complex, membrane-enclosed lumen, cell part, envelope, and synapse. Compared with SCLC, the differently expressed genes of NSCLC act in the biological regulation, multicellular organismal process, and viral reproduction and locomotion, which show that NSCLC is more likely to cause a wide range of cancer cell proliferation and virus infection than SCLC. The network topological properties of SCLC and NSCLC are similar, except the average shortest path length, which indicates that most of the genes of the two lung cancers play a similar function in the entire body. The commonly expressed genes show that all of the genes in the module may also cause NSCLC and SCLC, simultaneously.

CONCLUSIONS

The proteins in module will involve the same or similar biological functions and the interactions among them induce the occurrence of lung cancer. Moreover, a potential biomarker of SCLC is the interaction between APIP and apoptotic protease activating factor (APAF)1, which share a common module.

Identifying influential nodes in large-scale directed networks: the role of clustering

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about nodes, more than 15 times faster than PageRank.

Social Communications Assisted Epidemic Disease Influence Minimization

This work explores the use of social communications for epidemic disease control. Since the most infectious diseases spread through human contacts, we focus on modeling the diffusion of diseases by analyzing the social relationship among individuals. In other words, we try to capture the interaction pattern among human beings using the social contact information, and investigate its impact on the spread of diseases. Particularly, we investigate the problem of minimizing the expected number of infected persons by treating a small fraction of the population with vaccines. We prove that this problem is NP-hard, and propose an approximate algorithm representing a preventive disease control strategy based on the social patterns. Simulation results confirm the superiority of our strategy over existing ones.

Exploring complex networks via topological embedding on surfaces

We demonstrate that graphs embedded on surfaces are a powerful and practical tool to generate, to characterize, and to simulate networks with a broad range of properties. Any network can be embedded on a surface with sufficiently high genus and therefore the study of topologically embedded graphs is non-restrictive. We show that the local properties of the network are affected by the surface genus which determines the average degree, which influences the degree distribution, and which controls the clustering coefficient. The global properties of the graph are also strongly affected by the surface genus which is constraining the degree of interwovenness, changing the scaling properties of the network from large-world kind (small genus) to small- and ultrasmall-world kind (large genus). Two elementary moves allow the exploration of all networks embeddable on a given surface and naturally introduce a tool to develop a statistical mechanics description for these networks. Within such a framework, we study the properties of topologically embedded graphs which dynamically tend to lower their energy towards a ground state with a given reference degree distribution. We show that the cooling dynamics between high and low "temperatures" is strongly affected by the surface genus with the manifestation of a glass-like transition occurring when the distance from the reference distribution is low. We prove, with examples, that topologically embedded graphs can be built in a way to contain arbitrary complex networks as subgraphs. This method opens a new avenue to build geometrically embedded networks on hyperbolic manifolds.

Building complex networks with Platonic solids

We propose a unified model to build planar graphs with diverse topological characteristics which are of relevance in real applications. Here convex regular polyhedra (Platonic solids) are used as the building blocks for the construction of a variety of complex planar networks. These networks are obtained by merging polyhedra face by face on a tree-structure leading to planar graphs. We investigate two different constructions: (1) a fully deterministic construction where a self-similar fractal structure is built by using a single kind of polyhedron which is iteratively attached to every face and (2) a stochastic construction where at each step a polyhedron is attached to a randomly chosen face. These networks are scale-free, small-world, clustered, and sparse, sharing several characteristics of real-world complex networks. We derive analytical expressions for the degree distribution, the clustering coefficient, and the mean degree of nearest neighbors showing that these networks have power-law degree distributions with tunable exponents associated with the building polyhedron, and they possess a hierarchical organization that is determined by planarity.

Geographical networks stochastically constructed by a self-similar tiling according to population

In real communication and transportation networks, the geographical positions of nodes are very important for the efficiency and the tolerance of connectivity. Considering spatially inhomogeneous positions of nodes according to a population, we introduce a multiscale quartered (MSQ) network that is stochastically constructed by recursive subdivision of polygonal faces as a self-similar tiling. It has several advantages: the robustness of connectivity, the bounded short path lengths, and the shortest distance routing algorithm in a distributive manner. Furthermore, we show that the MSQ network is more efficient with shorter link lengths and more suitable with lower load for avoiding traffic congestion than other geographical networks which have various topologies ranging from river to scale-free networks. These results will be useful for providing an insight into the future design of ad hoc network infrastructures.

Evolution of Chinese airport network

With the rapid development of the economy and the accelerated globalization process, the aviation industry plays a more and more critical role in today's world, in both developed and developing countries. As the infrastructure of aviation industry, the airport network is one of the most important indicators of economic growth. In this paper, we investigate the evolution of the Chinese airport network (CAN) via complex network theory. It is found that although the topology of CAN has remained steady during the past few years, there are many dynamic switchings inside the network, which have changed the relative importance of airports and airlines. Moreover, we investigate the evolution of traffic flow (passengers and cargoes) on CAN. It is found that the traffic continues to grow in an exponential form and has evident seasonal fluctuations. We also found that cargo traffic and passenger traffic are positively related but the correlations are quite different for different kinds of cities.

Efficient immunization strategies on complex networks

In this paper, we proposed an efficient immunization-"high-risk immunization". The standard SIRS model was modified, respectively, on WS small-world network and BA scale-free network. Based on our new SIRS model, the density of infected individuals was analyzed from a theoretical point of view, and computer simulation was implemented on different networks. The results indicate that the high-risk immunization is effective, and it is economic and feasible in practice.

Infinitely robust order and local order-parameter tulips in Apollonian networks with quenched disorder

For a variety of quenched random spin systems on an Apollonian network, including ferromagnetic and antiferromagnetic bond percolation and the Ising spin glass, we find the persistence of ordered phases up to infinite temperature over the entire range of disorder. We develop a renormalization-group technique that yields highly detailed information, including the exact distributions of local magnetizations and local spin-glass order parameters, which turn out to exhibit, as function of temperature, complex and distinctive tulip patterns.

Finite-size effects for percolation on Apollonian networks

We study the percolation problem on the Apollonian network model. The Apollonian networks display many interesting properties commonly observed in real network systems, such as small-world behavior, scale-free distribution, and a hierarchical structure. By taking advantage of the deterministic hierarchical construction of these networks, we use the real-space renormalization-group technique to write exact iterative equations that relate percolation network properties at different scales. More precisely, our results indicate that the percolation probability and average mass of the percolating cluster approach the thermodynamic limit logarithmically. We suggest that such ultraslow convergence might be a property of hierarchical networks. Since real complex systems are certainly finite and very commonly hierarchical, we believe that taking into account finite-size effects in real-network systems is of fundamental importance.

Analytical solution of average path length for Apollonian networks

With the help of recursion relations derived from the self-similar structure, we obtain the solution of average path length, d[over ]_(t) , for Apollonian networks. In contrast to the well-known numerical result d[over ]_{t} proportional, variant(ln N_(t));(3/4) [J. S. Andrade, Jr., Phys. Rev. Lett. 94, 018702 (2005)], our rigorous solution shows that the average path length grows logarithmically as d[over ]_(t) proportional, variantln N_(t) in the infinite limit of network size N_(t) . The extensive numerical calculations completely agree with our closed-form solution.

Empirical study on clique-degree distribution of networks

The community structure and motif-modular-network hierarchy are of great importance for understanding the relationship between structures and functions. We investigate the distribution of clique degrees, which are an extension of degree and can be used to measure the density of cliques in networks. Empirical studies indicate the extensive existence of power-law clique-degree distributions in various real networks, and the power-law exponent decreases with an increase of clique size.

Geographical networks evolving with an optimal policy

In this article we propose a growing network model based on an optimal policy involving both topological and geographical measures. In this model, at each time step, a node, having randomly assigned coordinates in a 1x1 square, is added and connected to a previously existing node i, which minimizes the quantity ri2/kialpha, where ri is the geographical distance, ki the degree, and alpha a free parameter. The degree distribution obeys a power-law form when alpha=1, and an exponential form when alpha=0. When alpha is in the interval (0, 1), the network exhibits a stretched exponential distribution. We prove that the average topological distance increases in a logarithmic scale of the network size, indicating the existence of the small-world property. Furthermore, we obtain the geographical edge length distribution, the total geographical length of all edges, and the average geographical distance of the whole network. Interestingly, we found that the total edge length will sharply increase when alpha exceeds the critical value alphac=1, and the average geographical distance has an upper bound independent of the network size. All the results are obtained analytically with some reasonable approximations, which are well verified by simulations.

Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity

In this paper, we propose a susceptible-infected model with identical infectivity, in which, at every time step, each node can only contact a constant number of neighbors. We implemented this model on scale-free networks, and found that the infected population grows in an exponential form with the time scale proportional to the spreading rate. Furthermore, by numerical simulation, we demonstrated that the targeted immunization of the present model is much less efficient than that of the standard susceptible-infected model. Finally, we investigate a fast spreading strategy when only local information is available. Different from the extensively studied path-finding strategy, the strategy preferring small-degree nodes is more efficient than that preferring large-degree nodes. Our results indicate the existence of an essential relationship between network traffic and network epidemic on scale-free networks.

Universal scaling behavior of clustering coefficient induced by deactivation mechanism

We propose a model of network growth that generalizes the deactivation model previously suggested for complex networks. Several topological features of this generalized model, such as the degree distribution and clustering coefficient, have been investigated analytically and by simulations. A scaling behavior of clustering coefficient C approximately 1/M is theoretically obtained, where M refers to the number of active nodes in the network. We discuss the relationship between the recently observed numerical behavior of clustering coefficient in the coauthor and paper citation networks and our theoretical result. It shows that both of them are induced by deactivation mechanism. By introducing a perturbation, the generated network undergoes a transition from large to small world, meanwhile the scaling behavior of C is conserved. It indicates that C approximately 1/M is a universal scaling behavior induced by deactivation mechanism.

Evolving Apollonian networks with small-world scale-free topologies

We propose two types of evolving networks: evolutionary Apollonian networks (EANs) and general deterministic Apollonian networks (GDANs), established by simple iteration algorithms. We investigate the two networks by both simulation and theoretical prediction. Analytical results show that both networks follow power-law degree distributions, with distribution exponents continuously tuned from 2 to 3. The accurate expression of clustering coefficient is also given for both networks. Moreover, the investigation of the average path length of EAN and the diameter of GDAN reveals that these two types of networks possess small-world feature. In addition, we study the collective synchronization behavior on some limitations of the EAN.

Nonequilibrium dynamics of language games on complex networks

The naming game is a model of nonequilibrium dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pairwise local interactions. We present an extensive study of its dynamics on complex networks, that can be considered as the most natural topological embedding for agents involved in language games and opinion dynamics. Except for some community structured networks on which metastable phases can be observed, agents playing the naming game always manage to reach a global consensus. This convergence is obtained after a time generically scaling with the population's size N as t(conv) approximately N(1.4+/-0.1), i.e., much faster than for agents embedded on regular lattices. Moreover, the memory capacity required by the system scales only linearly with its size. Particular attention is given to heterogeneous networks, in which the dynamical activity pattern of a node depends on its degree. High-degree nodes have a fundamental role, but require larger memory capacity. They govern the dynamics acting as spreaders of (linguistic) conventions. The effects of other properties, such as the average degree and the clustering, are also discussed.

Geographical effects on the path length and the robustness in complex networks

The short paths between any two nodes and the robustness of connectivity are advanced properties of scale-free (SF) networks; however, they may be affected by geographical constraints in realistic situations. We consider geographical networks with the SF structure based on planar triangulation for online routings, and suggest scaling relations between the average distance or number of hops on the optimal paths and the network size. We also show that the tolerance to random failures and attacks on hubs is weakened in geographical networks, and that even then it is possible for the extremely vulnerable ones to be improved by adding with the local exchange of links.

Inverted Berezinskii-Kosterlitz-Thouless singularity and high-temperature algebraic order in an Ising model on a scale-free hierarchical-lattice small-world network

We have obtained exact results for the Ising model on a hierarchical lattice incorporating three key features characterizing many real-world networks--a scale-free degree distribution, a high clustering coefficient, and the small-world effect. By varying the probability p of long-range bonds, the entire spectrum from an unclustered, non-small-world network to a highly clustered, small-world system is studied. Using the self-similar structure of the network, we obtain analytic expressions for the degree distribution P(k) and clustering coefficient C for all p, as well as the average path length l for p = 0 and 1. The ferromagnetic Ising model on this network is studied through an exact renormalization-group transformation of the quenched bond probability distribution, using up to 562,500 renormalized probability bins to represent the distribution. For p < 0.494, we find power-law critical behavior of the magnetization and susceptibility, with critical exponents continuously varying with p, and exponential decay of correlations away from Tc. For p > or = 0.494, in fact where the network exhibits small-world character, the critical behavior radically changes: We find a highly unusual phase transition, namely an inverted Berezinskii-Kosterlitz-Thouless singularity, between a low-temperature phase with nonzero magnetization and finite correlation length and a high-temperature phase with zero magnetization and infinite correlation length, with power-law decay of correlations throughout the phase. Approaching Tc from below, the magnetization and the susceptibility, respectively, exhibit the singularities of exp(-C/square root of Tc - T) and exp(D/square root of Tc - T), with C and D positive constants. With long-range bond strengths decaying with distance, we see a phase transition with power-law critical singularities for all p, and evaluate an unusually narrow critical region and important corrections to power-law behavior that depend on the exponent characterizing the decay of long-range interactions.

Comment on "Maximal planar networks with large clustering coefficient and power-law degree distribution"

This Comment corrects the error which appeared in the calculation of the degree distribution of random Apollonian networks [T. Zhou, G. Yan, and B. H. Wang, Phys. Rev. E. 71, 046141 (2005)]. As a result, the expression of P(k), which gives the probability that a randomly selected node has exactly k edges, has the form P(k) alpha 1/[k(k + 1)(k + 2)].

Enhanced synchronizability by structural perturbations

In this Brief Report, we investigate the collective synchronization of a system of coupled oscillators on a Barabási-Albert scale-free network. We propose an approach of structural perturbations aiming at those nodes with maximal betweenness. This method can markedly enhance the network synchronizability, and is easy to realize. The simulation results show that the eigenratio will sharply decrease by one-half when only 0.6% of those hub nodes occur under three-division processes when the network size . In addition, the present study also provides numerical evidence that the maximal betweenness plays a major role in network synchronization.

Synchronous and asynchronous recursive random scale-free nets

We investigate the differences between scale-free recursive nets constructed by a synchronous, deterministic updating rule (e.g., Apollonian nets), versus an asynchronous, random sequential updating rule (e.g., random Apollonian nets). We show that the dramatic discrepancies observed recently for the degree exponent in these two cases result from a biased choice of the units to be updated sequentially in the asynchronous version.

Mutual selection model for weighted networks

For most networks, the connection between two nodes is the result of their mutual affinity and attachment. In this paper, we propose a mutual selection model to characterize the weighted networks. By introducing a general mechanism of mutual selection, the model can produce power-law distributions of degree, weight, and strength, as confirmed in many real networks. Moreover, we also obtained the nontrivial clustering coefficient C, degree assortativity coefficient r, and degree-strength correlation depending on a single parameter m. These results are supported by present empirical evidence. Studying the degree-dependent average clustering coefficient C(k) and the degree-dependent average nearest neighbors' degree k(nn)(k) also provide us with a better description of the hierarchies and organizational architecture of weighted networks.