The Dynamics of Power laws: Fitness and Aging in Preferential Attachment Trees

Continuous-time branching processes describe the evolution of a population whose individuals generate a random number of children according to a birth process. Such branching processes can be used to understand preferential attachment models in which the birth rates are linear functions. We are motivated by citation networks, where power-law citation counts are observed as well as aging in the citation patterns. To model this, we introduce fitness and age-dependence in these birth processes. The multiplicative fitness moderates the rate at which children are born, while the aging is integrable, so that individuals receives a finite number of children in their lifetime. We show the existence of a limiting degree distribution for such processes. In the preferential attachment case, where fitness and aging are absent, this limiting degree distribution is known to have power-law tails. We show that the limiting degree distribution has exponential tails for bounded fitnesses in the presence of integrable aging, while the power-law tail is restored when integrable aging is combined with fitness with unbounded support with at most exponential tails. In the absence of integrable aging, such processes are explosive.     

Modeling complex networks with accelerating growth and aging effect

Numerous empirical studies have revealed that a large number of real networks exhibit the property of accelerating growth, i.e. network size (nodes) increases superlinearly with time. Examples include the size of social networks, the output of scientists, the population of cities, and so on. In the literature, these real systems are widely represented by complex networks for analysis, and many network models have been proposed to explain the observed properties in these systems such as power-law degree distribution. However, most of these models (e.g. the well-known BA model) are based on linear growth of these systems. In this paper, we propose a network model with accelerating growth and aging effect, resulting in an emergence of super hubs which is consistent with the empirical observation in citation networks.     

Synchronization in Triangled Complex Networks

Using a tunable clustering coefficient model without changing the degree distribution, we investigate the effect of clustering coefficient on synchronization of networks with both unweighted and weighted couplings. For several typical categories of complex networks, the more triangles are in the networks, the worse the synchronizability of the networks is.     

Evolving hypernetwork model

Complex hypernetworks are ubiquitous in real-life systems. While a substantial body of previous research has only focused on the applications of hypernetworks, relatively little work has investigated the evolving models of hypernetworks. Considering the formations of many real world networks, we propose two evolving mechanisms of the hyperedge growth and the hyperedge preferential attachment, then construct an evolving hypernetwork model. We introduce some basic topological quantities, such as a variety of degree distributions, clustering coefficients as well as average path length. We numerically investigate these quantities in the limit of large hypernetwork size and find that our hypernetwork model shares similar qualitative features with the majority of complex networks that have been previously studied, such as the scale-free property of the degree distribution and a high degree of clustering, as well as the small-world property. It is expected that our attempt in the hypernetwork model can bring the upsurge in the study of the hypernetwork model in further.     

Influence of a network structure on the network effect in the communication service market

In this study, we analyze the network effect in a model of a personal communication market, by using a multi-agent based simulation approach. We introduce into the simulation model complex network structures as the interaction patterns of agents. With complex network models, we investigate the dynamics of a market in which two providers are competing. We also examine the structure of networks that affect the complex behavior of the market. By a series of simulations, we show that the structural properties of complex networks, such as the clustering coefficient and degree correlation, have a major influence on the dynamics of the market. We find that the network effect is increased if the interaction pattern of agents is characterized by a high clustering coefficient, or a positive degree correlation. We also discuss a suitable model of the interaction pattern for reproducing market dynamics in the real world, by performing simulations using real data of a social network.     

Organization of networks with tagged nodes and biased links: A priori distinct communities: The case of intelligent design proponents and Darwinian evolution defenders

Among the topics of opinion formation it is of interest to observe the characteristics of networks with a priori distinct communities. The citation network(s) between selected members of the Neocreationist and Intelligent Design and the Darwinian Evolution communities are unfolded through the available internet citations. The resulting adjacency matrix is not symmetric. A generalization of considerations pertaining to the case of networks with tagged nodes and biased links, directed or undirected, is presented. The main characteristic coefficients describing the structure of such networks are outlined. The structural features are discussed searching for statistical aspects of the communities. The degree distributions, each network’s assortativity, specific global and local clustering coefficients and the Average Overlap Indices are especially calculated since the distribution of elements in the rectangular submatrices represent inter-community connections. The various closed and open triangles made from nodes, distinguishing the community, are listed. The z-scores of patterns are calculated. One can distinguish between opinion leaders, followers and main rivals and briefly interpret their relationships through intuitively expected behavior in defence of an opinion. Suggestions for more elaborate models describing such communities and their subsequent structures are found in conclusions.     

A longitudinal analysis of nanotechnology literature: 1976–2004

Nanotechnology research and applications have experienced rapid growth in recent years. We assessed the status of nanotechnology research worldwide by applying bibliographic, content map, and citation network analysis to a data set of about 200,000 nanotechnology papers published in the Thomson Science Citation Index Expanded database (SCI) from 1976 to 2004. This longitudinal study shows a quasi-exponential growth of nanotechnology articles with an average annual growth rate of 20.7% after 1991. The United States had the largest contribution of nanotechnology research and China and Korea had the fastest growth rates. The largest institutional contributions were from the Chinese Academy of Sciences and the Russian Academy of Sciences. The high-impact papers generally described tools, theories, technologies, perspectives, and overviews of nanotechnology. From the top 20 institutions, based on the average number of paper citations in 1976–2004, 17 were in the Unites States, 2 in France and 1 in Germany. Content map analysis identified the evolution of the major topics researched from 1976 to 2004, including investigative tools, physical phenomena, and experiment environments. Both the country citation network and the institution citation network had relatively high clustering, indicating the existence of citation communities in the two networks, and specific patterns in forming citation communities. The United States, Germany, Japan, and China were major citation centers in nanotechnology research with close inter-citation relationships.     

交通流驱动的含权网络

文章对含权复杂网络研究的最近进展给予了评述，特别报道了文章作者最近提出的一个交通流驱动的含权技术网络模型。这一模型能够同时给出网络连接度分布的幂函数律、网络强度分布的幂函数律、网络权重分布的幂函数律，以及高聚集性和非相称混合性等五大特征，因此成功地刻画了真实技术网络的无尺度性质和小世界效应     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

An evolutionary model of social networks

Social networks in communities, markets, and societies self-organise through the interactions of many individuals. In this paper we use a well-known mechanism of social interactions — the balance of sentiment in triadic relations — to describe the development of social networks. Our model contrasts with many existing network models, in that people not only establish but also break up relations whilst the network evolves. The procedure generates several interesting network features such as a variety of degree distributions and degree correlations. The resulting network converges under certain conditions to a steady critical state where temporal disruptions in triangles follow a power-law distribution.     

Detection of community overlap according to belief propagation and conflict

Most existing methods for detection of community overlap cannot balance efficiency and accuracy for large and densely overlapping networks. To quickly identify overlapping communities for such networks, we propose a new method that uses belief propagation and conflict (PCB) to occupy communities. We first identify triangles with maximal clustering coefficients as seed nodes and sow a new type of belief to the seed nodes. Then the beliefs explore their territory by occupying nodes with high assent ability. The beliefs propagate their strength along the graph to consolidate their territory, and conflict with each other when they encounter the same node simultaneously. Finally, the node membership is judged from the belief vectors. The PCB time complexity is nearly linear and its space complexity is linear. The algorithm was tested in extensive experiments on three real-world social networks and three computer-generated artificial graphs. The experimental results show that PCB is very fast and highly reliable. Tests on real and artificial networks give excellent results compared with three newly proposed overlapping community detection algorithms.     

Triadic Closure in Configuration Models with Unbounded Degree Fluctuations

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for \(k=\varOmega (\sqrt{n})\) settles on a power law \(c(k)\sim n^{5-2\tau }k^{-2(3-\tau )}\) with \(\tau \in (2,3)\) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.     

Correlations and clustering in a scale-free network in Euclidean space

Empirical study shows that many real networks in nature and society share two generic properties: they are scale-free and they display a high degree of clustering. Quite often they are modular in nature also, implying occurrences of several small tightly linked groups which are connected in a hierarchical manner among themselves. Recently, we have introduced a model of spatial scale-free network where nodes pop-up at randomly located positions in the Euclidean space and are connected to one end of the nearest link of the existing network. It has been already argued that the large scale behaviour of this network is like the Barabási-Albert model. In the present paper we briefly review these results as well as present additional results on the study of non-trivial correlations present in this model which are found to have similar behaviours as in the real-world networks. Moreover, this model naturally possesses the hierarchical characteristics lacked by most of the models of the scale-free networks.      

手机短信网络的生长过程研究

模拟了短信网络的生长过程并研究其拓扑结构.发现短信网络在生长过程中，度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与先前的模型有所不符.根据短信网络的数据分析，提出了短信网络的生长机制——局部优先连接机制.结果表明，模拟以短信网络为代表的实际网络时，局部优先连接模型优于其他网络模型. 关键词： 复杂网络 短信网络 局部优先连接     

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.     

Failure tolerance of spike phase synchronization in coupled neural networks

Neuronal synchronization plays an important role in the various functionality of nervous system such as binding, cognition, information processing, and computation. In this paper, we investigated how random and intentional failures in the nodes of a network influence its phase synchronization properties. We considered both artificially constructed networks using models such as preferential attachment, Watts-Strogatz, and Erdo?s-Re?nyi as well as a number of real neuronal networks. The failure strategy was either random or intentional based on properties of the nodes such as degree, clustering coefficient, betweenness centrality, and vulnerability. Hindmarsh-Rose model was considered as the mathematical model for the individual neurons, and the phase synchronization of the spike trains was monitored as a function of the percentage∕number of removed nodes. The numerical simulations were supplemented by considering coupled non-identical Kuramoto oscillators. Failures based on the clustering coefficient, i.e., removing the nodes with high values of the clustering coefficient, had the least effect on the spike synchrony in all of the networks. This was followed by errors where the nodes were removed randomly. However, the behavior of the other three attack strategies was not uniform across the networks, and different strategies were the most influential in different network structure.     

A model of the effects of authority on consensus formation in adaptive networks: Impact on network topology and robustness

Opinions of individuals in real social networks are arguably strongly influenced by external determinants, such as the opinions of those perceived to have the highest levels of authority. In order to model this, we have extended an existing model of consensus formation in an adaptive network by the introduction of a parameter representing each agent’s level of ‘authority’, based on their opinion relative to the overall opinion distribution. We found that introducing this model, along with a randomly varying opinion convergence factor, significantly impacts the final state of converged opinions and the number of interactions required to reach that state. We also determined the relationship between initial and final network topologies for this model, and whether the final topology is robust to node removals. Our results indicate firstly that the process of consensus formation with a model of authority consistently transforms the network from an arbitrary initial topology to one with distinct measurements in mean shortest path, clustering coefficient, and degree distribution. Secondly, we found that subsequent to the consensus formation process, the mean shortest path and clustering coefficient are less affected by both random and targeted node disconnection. Speculation on the relevance of these results to real world applications is provided.     

Clustering gene expression data analysis using an improved EM algorithm based on multivariate elliptical contoured mixture models

Clustering gene expression data is an important research topic in bioinformatics because knowing which genes act similarly can lead to the discovery of important biological information. Many clustering algorithms have been used in the field of gene clustering. The multivariate Gaussian mixture distribution function was frequently used as the component of the finite mixture model for clustering, however the clustering cannot be restricted to the normal distribution in the real dataset. In order to make the cluster algorithm strong adaptability, this paper proposes a new scheme for clustering gene expression data based on the multivariate elliptical contoured mixture models (MECMMs). To solve the problem of over-reliance on the initialization, we propose an improved expectation maximization (EM) algorithm by adding and deleting initial value for the classical EM algorithm, and the number of clusters can be treated as a known parameter and inferred with the QAIC criterion. The improved EM algorithm based on the MECMMs is tested and compared with some other clustering algorithms, the performance of our clustering algorithm has been extensively compared over several simulated and real gene expression datasets. Our results indicated that improved EM clustering algorithm is superior to the classical EM algorithm and the support vector machines (SVMs) algorithm, and can be widely used for gene clustering.     

Modular and hierarchical structure of social contact networks

Social contact networks exhibit overlapping qualities of communities, hierarchical structure and spatial-correlated nature. We propose a mixing pattern of modular and growing hierarchical structures to reconstruct social contact networks by using an individual’s geospatial distribution information in the real world. The hierarchical structure of social contact networks is defined based on the spatial distance between individuals, and edges among individuals are added in turn from the modular layer to the highest layer. It is a gradual process to construct the hierarchical structure: from the basic modular model up to the global network. The proposed model not only shows hierarchically increasing degree distribution and large clustering coefficients in communities, but also exhibits spatial clustering features of individual distributions. As an evaluation of the method, we reconstruct a hierarchical contact network based on the investigation data of a university. Transmission experiments of influenza H1N1 are carried out on the generated social contact networks, and results show that the constructed network is efficient to reproduce the dynamic process of an outbreak and evaluate interventions. The reproduced spread process exhibits that the spatial clustering of infection is accordant with the clustering of network topology. Moreover, the effect of individual topological character on the spread of influenza is analyzed, and the experiment results indicate that the spread is limited by individual daily contact patterns and local clustering topology rather than individual degree.     

Local assortativity and growth of Internet

Local assortativity has been recently proposed as a measure to analyse complex networks. It has been noted that the Internet Autonomous System level networks show a markedly different local assortativity profile to most biological and social networks. In this paper we show that, even though several Internet growth models exist, none of them produce the local assortativity profile that can be observed in the real AS networks. We introduce a new generic growth model which can produce a linear local assortativity profile similar to that of the Internet. We verify that this model accurately depicts the local assortativity profile criteria of Internet, while also satisfactorily modelling other attributes of AS networks already explained by existing models.