Duplication： a Mechanism Producing Disassortative Mixing Networks in Biology

Assortative/disassortative mixing is an important topological property of a network. A network is called assortative mixing if the nodes in the network tend to connect to their connectivity peers, or disassortative mixing if nodes with low degrees are more likely to connect with high-degree nodes. We have known that biological networks such as protein-protein interaction networks （PPI）, gene regulatory networks, and metabolic networks tend to be disassortative. On the other hand, in biological evolution, duplication and divergence are two fundamental processes. In order to make the relationship between the property of disassortative mixing and the two basic biological principles clear and to study the cause of the disassortative mixing property in biological networks, we present a random duplication model and an anti-preference duplication model. Our results show that disassortative mixing networks can be obtained by both kinds of models from uncorrelated initial networks. Moreover, with the growth of the network size, the disassortative mixing property becomes more obvious.     

蛋白质相互作用网络特征的理论再现

无标度性、小世界性、功能模块结构及度负关联性是大量生物网络共同的特征. 为了理解生物网络无标度性、小世界性和度负关联性的形成机制, 研究者已经提出了各种各样基于复制和变异的网络增长模型. 在本文中,我们从生物学的角度通过引入偏爱小复制原则及变异和非均匀的异源二聚作用构建了一个简单的蛋白质相互作用网络演化模型.数值模拟结果表明,该演化模型几乎可以再现现在实测结果所公认的蛋白质相互作用网络的性质：无标度性、小世界性、度负关联性和功能模块结构. 我们的演化模型对理解蛋白质相互作用网络演化过程中的可能机制提供了一定的帮助. 关键词： 蛋白质相互作用网络 偏爱小 非均匀的异源二聚作用 功能模块结构     

Rank-based model for weighted network with hierarchical organization and disassortative mixing

In this paper, we study a rank-based model for weighted network. The evolution rule of the network is based on the ranking of node strength, which couples the topological growth and the weight dynamics. Analytically and by simulations, we demonstrate that the generated networks recover the scale-free distributions of degree and strength in the whole region of the growth dynamics parameter (α>0). Moreover, this network evolution mechanism can also produce scale-free property of weight, which adds deeper comprehension of the networks growth in the presence of incomplete information. We also characterize the clustering and correlation properties of this class of networks. It is showed that at α=1 a structural phase transition occurs, and for α>1 the generated network simultaneously exhibits hierarchical organization and disassortative degree correlation, which is consistent with a wide range of biological networks.     

Fractality and degree correlations in scale-free networks

Fractal scale-free networks are empirically known to exhibit disassortative degree mixing. It is, however, not obvious whether a negative degree correlation between nearest neighbor nodes makes a scale-free network fractal. Here we examine the possibility that disassortativity in complex networks is the origin of fractality. To this end, maximally disassortative (MD) networks are prepared by rewiring edges while keeping the degree sequence of an initial uncorrelated scale-free network. We show that there are many MD networks with different topologies if the degree sequence is the same with that of the (u,v)-flower but most of them are not fractal. These results demonstrate that disassortativity does not cause the fractal property of networks. In addition, we suggest that fractality of scale-free networks requires a long-range repulsive correlation, in the sense of the shortest path distance, in similar degrees.     

Emergence of modularity and disassortativity in protein-protein interaction networks

In this paper, we present a simple evolution model of protein-protein interaction networks by introducing a rule of small-preference duplication of a node, meaning that the probability of a node chosen to duplicate is inversely proportional to its degree, and subsequent divergence plus nonuniform heterodimerization based on some plausible mechanisms in biology. We show that our model cannot only reproduce scale-free connectivity and small-world pattern, but also exhibit hierarchical modularity and disassortativity. After comparing the features of our model with those of real protein-protein interaction networks, we believe that our model can provide relevant insights into the mechanism underlying the evolution of protein-protein interaction networks.     

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.     

Absence of epidemic threshold in scale-free networks with degree correlations

Random scale-free networks have the peculiar property of being prone to the spreading of infections. Here we provide for the susceptible-infected-susceptible model an exact result showing that a scale-free degree distribution with diverging second moment is a sufficient condition to have null epidemic threshold in unstructured networks with either assortative or disassortative mixing. Degree correlations result therefore irrelevant for the epidemic spreading picture in these scale-free networks. The present result is related to the divergence of the average nearest neighbor's degree, enforced by the degree detailed balance condition.     

Synchronization in multilayer networks through different coupling mechanisms

In recent years, most studies of complex networks have focused on a single network and ignored the interaction of multiple networks, much less the coupling mechanisms between multiplex networks. In this paper we investigate synchronization phenomena in multilayer networks with nonidentical topological structures based on three specific coupling mechanisms:assortative, disassortative, and anti-assortative couplings. We find rich and complex synchronous dynamic phenomena in coupled networks. We also study the behavior of effective frequencies for layers I and II to understand the underlying microscopic dynamics occurring under the three different coupling mechanisms. In particular, the coupling mechanisms proposed here have strong robustness and effectiveness and can produce abundant synchronization phenomena in coupled networks.     

Characteristics of real futures trading networks

Futures trading is the core of futures business, and it is considered as one of the typical complex systems. To investigate the complexity of futures trading, we employ the analytical method of complex networks. First, we use real trading records from the Shanghai Futures Exchange to construct futures trading networks, in which nodes are trading participants, and two nodes have a common edge if the two corresponding investors appear simultaneously in at least one trading record as a purchaser and a seller, respectively. Then, we conduct a comprehensive statistical analysis on the constructed futures trading networks. Empirical results show that the futures trading networks exhibit features such as scale-free behavior with interesting odd-even-degree divergence in low-degree regions, small-world effect, hierarchical organization, power-law betweenness distribution, disassortative mixing, and shrinkage of both the average path length and the diameter as network size increases. To the best of our knowledge, this is the first work that uses real data to study futures trading networks, and we argue that the research results can shed light on the nature of real futures business.     

度关联无标度网络上的有倾向随机行走

有倾向随机行走是研究网络上数据包路由策略的有效方法. 由于许多真实技术网络包括互联网都具有负的度关联特征, 因此本文研究这种网络上的有倾向随机行走性质. 研究表明: 在负关联网络上粒子可以在连接度较大的节点上均匀分布, 而连接度小的节点上粒子较少; 负关联网络上随机行走的速度比非关联网络更快; 找到了负关联网络上的最佳倾向性系数, 在此情况下负关联网络上随机行走的速度远快于非关联网络. 负关联网络既可以利用度小的节点容纳粒子, 又可以利用度大的节点快速传输, 这是负关联网络上高行走效率产生的机制.     

Jamming in complex networks with degree correlation

We study the effects of the degree-degree correlations on the pressure congestion J when we apply a dynamical process on scale free complex networks using the gradient network approach. We find that the pressure congestion for disassortative (assortative) networks is lower (bigger) than the one for uncorrelated networks which allow us to affirm that disassortative networks enhance transport through them. This result agree with the fact that many real world transportation networks naturally evolve to this kind of correlation. We explain our results showing that for the disassortative case the clusters in the gradient network turn out to be as much elongated as possible, reducing the pressure congestion J and observing the opposite behavior for the assortative case. Finally we apply our model to real world networks, and the results agree with our theoretical model.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

Effect of node deleting on network structure

The ever-increasing knowledge of the structure of various real-world networks has uncovered their complex multi-mechanism-governed evolution processes. Therefore, a better understanding of the structure and evolution of these networked complex systems requires us to describe such processes in a more detailed and realistic manner. In this paper, we introduce a new type of network growth rule which comprises addition and deletion of nodes, and propose an evolving network model to investigate the effect of node deleting on network structure. It is found that, with the introduction of node deleting, network structure is significantly transformed. In particular, degree distribution of the network undergoes a transition from scale-free to exponential forms as the intensity of node deleting increases. At the same time, nontrivial disassortative degree correlation develops spontaneously as a natural result of network evolution in the model. We also demonstrate that node deleting introduced in the model does not destroy the connectedness of a growing network so long as the increasing rate of edges is not excessively small. In addition, it is found that node deleting will weaken but not eliminate the small-world effect of a growing network, and generally it will decrease the clustering coefficient in a network.     

Age-based model for weighted network with general assortative mixing

In this paper, we propose an evolutionary model for weighted networks by introducing an age-based mutual selection mechanism. Our model generates power-law distributions of degree, weight, and strength, which are confirmed by analytical predictions and are consistent with real observations. The investigation of the relationship between clustering and the connectivity of nodes suggests hierarchical organization in the weighted networks. Furthermore, both assortative and disassortative properties can be naturally obtained by tuning a parameter α, which controls the strength of age-based preferential attachments. Since the age information of nodes is easier to acquire than the degree and strength of nodes, and almost all empirically observed structural and weighted properties can be reproduced by the simple evolutionary regulation, our model may reveal some underlying mechanisms that are key for the evolution of weighted complex networks.     

Evaluating the AS-level Internet models: beyond topological characteristics

A surge number of models has been proposed to model the Internet in the past decades. However, the issue on which models are better to model the Internet has still remained a problem. By analysing the evolving dynamics of the Internet, we suggest that at the autonomous system (AS) level, a suitable Internet model, should at least be heterogeneous and have a linearly growing mechanism. More importantly, we show that the roles of topological characteristics in evaluating and differentiating Internet models are apparently over-estimated from an engineering perspective. Also, we find that an assortative network is not necessarily more robust than a disassortative network and that a smaller average shortest path length does not necessarily mean a higher robustness, which is different from the previous observations. Our analytic results are helpful not only for the Internet, but also for other general complex networks.     

Weighted Evolving Networks with Self-organized Communities

In order to describe the self-organization of communities in the evolution of weighted networks, we propose a new evolving model for weighted community-structured networks with the preferential mechanisms functioned in different levels according to community sizes and node strengths, respectively. Theoretical analyses and numerical simulations show that our model captures power-law distributions of community sizes, node strengths, and link weights, with tunable exponents of ν≥1, γ>2, and α>2, respectively, sharing large clustering coefficients and scaling clustering spectra, and covering the range from disassortative networks to assortative networks. Finally, we apply our new model to the scientific co-authorship networks with both their weighted and unweighted datasets to verify its effectiveness.     

Incompatibility networks as models of scale-free small-world graphs

We make a mapping from Sierpinski fractals to a new class of networks, the incompatibility networks, which are scale-free, small-world, disassortative, and maximal planar graphs. Some relevant characteristics of the networks such as degree distribution, clustering coefficient, average path length, and degree correlations are computed analytically and found to be peculiarly rich. The method of network representation can be applied to some real-life systems making it possible to study the complexity of real networked systems within the framework of complex network theory.     

Inferring Users’ Social Roles with a Multi-Level Graph Neural Network Model

Users of social networks have a variety of social statuses and roles. For example, the users of Weibo include celebrities, government officials, and social organizations. At the same time, these users may be senior managers, middle managers, or workers in companies. Previous studies on this topic have mainly focused on using the categorical, textual and topological data of a social network to predict users’ social statuses and roles. However, this cannot fully reflect the overall characteristics of users’ social statuses and roles in a social network. In this paper, we consider what social network structures reflect users’ social statuses and roles since social networks are designed to connect people. Taking an Enron email dataset as an example, we analyzed a preprocessing mechanism used for social network datasets that can extract users’ dynamic behavior features. We further designed a novel social network representation learning algorithm in order to infer users’ social statuses and roles in social networks through the use of an attention and gate mechanism on users’ neighbors. The extensive experimental results gained from four publicly available datasets indicate that our solution achieves an average accuracy improvement of 2% compared with GraphSAGE-Mean, which is the best applicable inductive representation learning method.     

Methods to find community based on edge centrality

Divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method’s efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks.     

Optimal synchronizability of networks

We numerically investigate how to enhance synchronizability of coupled identical oscillators in complex networks with research focus on the roles of the high level of clustering for a given heterogeneity in the degree distribution. By using the edge-exchange method with the fixed degree sequence, we first directly maximize synchronizability measured by the eigenratio of the coupling matrix, through the use of the so-called memory tabu search algorithm developed in applied mathematics. The resulting optimal network, which turns out to be weakly disassortative, is observed to exhibit a small modularity. More importantly, it is clearly revealed that the optimally synchronizable network for a given degree sequence shows a very low level of clustering, containing much fewer small-size loops than the original network. We then use the clustering coefficient as an object function to be reduced during the edge exchanges, and find it a very efficient way to enhance synchronizability. We thus conclude that under the condition of a given degree heterogeneity, the clustering plays a very important role in the network synchronization.