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

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

Residence Time Statistics for Normal and Fractional Diffusion in a Force Field

We investigate statistics of occupation times for an over-damped Brownian particle in an external force field, using a backward Fokker–Planck equation introduced by Majumdar and Comtet. For an arbitrary potential field the distribution of occupation times is expressed in terms of solutions of the corresponding first passage time problem. This general relationship between occupation times and first passage times, is valid for normal Markovian diffusion and for non-Markovian sub-diffusion, the latter modeled using the fractional Fokker–Planck equation. For binding potential fields we find in the long time limit ergodic behavior for normal diffusion, while for the fractional framework weak ergodicity breaking is found, in agreement with previous results of Bel and Barkai on the continuous time random walk on a lattice. For non-binding cases, rich physical behaviors are obtained, and classification of occupation time statistics is made possible according to whether or not the underlying random walk is recurrent and the averaged first return time to the origin is finite. Our work establishes a link between fractional calculus and ergodicity breaking.     

Distribution of time-averaged observables for weak ergodicity breaking

We find a general formula for the distribution of time-averaged observables for systems modeled according to the subdiffusive continuous time random walk. For Gaussian random walks coupled to a thermal bath we recover ergodicity and Boltzmann's statistics, while for the anomalous subdiffusive case a weakly nonergodic statistical mechanical framework is constructed, which is based on Lévy's generalized central limit theorem. As an example we calculate the distribution of X, the time average of the position of the particle, for unbiased and uniformly biased particles, and show that X exhibits large fluctuations compared with the ensemble average .     

Poissonian bursts in e-mail correspondence

Recent work has shown that the distribution of inter-event times for e-mail communication exhibits a heavy tail which is statistically consistent with a cascading Poisson process. In this work we extend this analysis to higher-order statistics, using the Fano and Allan factors to quantify the extent to which the empirical data are more correlated — bursty — than a Poisson process. Our analysis demonstrates that the correlations in the empirical data are indistinguishable from those of randomly reordered time series, illustrating that any correlations in the data are not due to the precise ordering of events. We further find that correlations in synthetic time series generated from a cascading Poisson process agree quite well with the correlations observed in the empirical data. Finally, we rescale the empirical time series to confirm that e-mail correspondence is no more correlated than expected from a suitably chosen Poisson process.     

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.     

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.     

Theory of rumour spreading in complex social networks

We introduce a general stochastic model for the spread of rumours, and derive mean-field equations that describe the dynamics of the model on complex social networks (in particular, those mediated by the Internet). We use analytical and numerical solutions of these equations to examine the threshold behaviour and dynamics of the model on several models of such networks: random graphs, uncorrelated scale-free networks and scale-free networks with assortative degree correlations. We show that in both homogeneous networks and random graphs the model exhibits a critical threshold in the rumour spreading rate below which a rumour cannot propagate in the system. In the case of scale-free networks, on the other hand, this threshold becomes vanishingly small in the limit of infinite system size. We find that the initial rate at which a rumour spreads is much higher in scale-free networks than in random graphs, and that the rate at which the spreading proceeds on scale-free networks is further increased when assortative degree correlations are introduced. The impact of degree correlations on the final fraction of nodes that ever hears a rumour, however, depends on the interplay between network topology and the rumour spreading rate. Our results show that scale-free social networks are prone to the spreading of rumours, just as they are to the spreading of infections. They are relevant to the spreading dynamics of chain emails, viral advertising and large-scale information dissemination algorithms on the Internet.     

Elementary models of dynamic networks

Inspecting the dynamics of networks opens a new dimension in understanding the interactions among the components of complex systems. Our goal is to understand the baseline properties expected from elementary random changes over time, in order to be able to assess the various effects found in longitudinal data. We created elementary dynamic models from classic random and preferential networks. Focusing on edge dynamics, we defined several processes for changing networks of a fixed size. We applied simple rules, including random, preferential and assortative modifications of existing edges – or a combination of these. Starting from initial Erdos-Rényi networks, we examined various basic network properties (e.g., density, clustering, average path length, number of components, degree distribution, etc.) of both snapshot and cumulative networks (for various lengths of aggregation time windows). Our results provide a baseline for changes to be expected in dynamic networks. We found universalities in the dynamic behavior of most network statistics. Furthermore, our findings suggest that certain network properties have a strong, non-trivial dependence on the length of the sampling window.     

Clustering and information in correlation based financial networks

Networks of companies can be constructed by using return correlations. A crucial issue in this approach is to select the relevant correlations from the correlation matrix. In order to study this problem, we start from an empty graph with no edges where the vertices correspond to stocks. Then, one by one, we insert edges between the vertices according to the rank of their correlation strength, resulting in a network called asset graph. We study its properties, such as topologically different growth types, number and size of clusters and clustering coefficient. These properties, calculated from empirical data, are compared against those of a random graph. The growth of the graph can be classified according to the topological role of the newly inserted edge. We find that the type of growth which is responsible for creating cycles in the graph sets in much earlier for the empirical asset graph than for the random graph, and thus reflects the high degree of networking present in the market. We also find the number of clusters in the random graph to be one order of magnitude higher than for the asset graph. At a critical threshold, the random graph undergoes a radical change in topology related to percolation transition and forms a single giant cluster, a phenomenon which is not observed for the asset graph. Differences in mean clustering coefficient lead us to conclude that most information is contained roughly within 10% of the edges.Received: 11 December 2003, Published online: 14 May 2004PACS: 89.65.-s Social and economic systems - 89.75.-k Complex systems - 89.90. + n Other topics in areas of applied and interdisciplinary physics (restricted to new topics in section 89)     

Empirical analysis of the worldwide maritime transportation network

In this paper we present an empirical study of the worldwide maritime transportation network (WMN) in which the nodes are ports and links are container liners connecting the ports. Using the different representations of network topology — the spaces L and P, we study the statistical properties of WMN including degree distribution, degree correlations, weight distribution, strength distribution, average shortest path length, line length distribution and centrality measures. We find that WMN is a small-world network with power law behavior. Important nodes are identified based on different centrality measures. Through analyzing weighted clustering coefficient and weighted average nearest neighbors degree, we reveal the hierarchy structure and rich-club phenomenon in the network.     

Evolving networks with bimodal degree distribution

Networks with bimodal degree distribution are most robust to targeted and random attacks. We present a model for constructing a network with bimodal degree distribution. The procedure adopted is to add nodes to the network with a probability p and delete the links between nodes with probability (1 − p). We introduce an additional constraint in the process through an immunity score, which controls the dynamics of the growth process based on the feedback value of the last few time steps. This results in bimodal nature for the degree distribution. We study the standard quantities which characterize the networks, like average path length and clustering coefficient in the context of our growth process and show that the resultant network is in the small world family. It is interesting to note that bimodality in degree distribution is an emergent phenomenon.     

无标度立体Koch网络的建立及其结构性质研究

根据经典Koch曲线的构造,利用四面体作为迭代基元构造了一种立体Koch网络并对其结构性质做了研究,给出了该网络的度分布函数,计算了该网络的团簇系数、平均最短路径长度以及度关联函数.结果表明,所构建的网络是无标度网络,度分布临界指数γ≈3.32;其团簇系数趋向于常数值0.870435;平均路径长度与网络尺寸的对数呈正比关系,说明该网络具有小世界网络特性.另外,计算结果表明knn(k)随k的变化而变化,说明该Koch网络具有一定的度关联性.     

New class of level statistics in correlated disordered chains

We study the properties of the level statistics of 1D disordered systems with long-range spatial correlations. We find a threshold value in the degree of correlations below which in the limit of large system size the level statistics follows a Poisson distribution (as expected for 1D uncorrelated-disordered systems), and above which the level statistics is described by a new class of distribution functions. At the threshold, we find that with increasing system size, the standard deviation of the function describing the level statistics converges to the standard deviation of the Poissonian distribution as a power law. Above the threshold we find that the level statistics is characterized by different functional forms for different degrees of correlations.     

Occupation time statistics in the quenched trap model

We investigate the distribution of the occupation time of a particle undergoing a random walk among random energy traps and in the presence of a deterministic potential field. When the distribution of energy traps is exponential with a width T(g), we find in thermal equilibrium a transition between Boltzmann statistics when T>T(g) to Lamperti statistics when T < T(g). We explain why our main results are valid for other models of quenched disorder, and discuss briefly implications on single particle experiments.     

Growth, percolation, and correlations in disordered fiber networks

This paper studies growth, percolation, and correlations in disordered fiber networks. We start by introducing a 2D continuum deposition model with effective fiber-fiber interactions represented by a parameterp which controls the degree of clustering. Forp=1 the deposited network is uniformly random, while forp=0 only a single connected cluster can grow. Forp=0 we first derive the growth law for the average size of the cluster as well as a formula for its mass density profile. Forp>0 we carry out extensive simulations on fibers, and also needles and disks, to study the dependence of the percolation threshold onp. We also derive a mean-field theory for the threshold nearp=0 andp=1 and find good qualitative agreement with the simulations. The fiber networks produced by the model display nontrivial density correlations forp<1. We study these by deriving an approximate expression for the pair distribution function of the model that reduces to the exactly known case of a uniformly random network. We also show that the two-point mass density correlation function of the model has a nontrivial form, and discuss our results in view of recent experimental data on mss density correlations in paper sheets.     

Random walks on pseudo-lattices

The problem of a Pólya (unbiased, nearest-neighbor stepping) random walk is solved for several pseudo-lattices related to the Bethe lattice (Cayley tree). In each case, the solution is derived by projecting the walk on a pseudo-lattice onto a walk on a linear chain with internal states and a point defect. Random walk statistics exhibited explicitly include the probability of return to the starting point, the mean time to return if return does occur, and the asymptotic behavior of the expected number of distinct sites visited in a walk of long duration. Conjectured relationships between random walk statistics and percolation theory are discussed in the context of pseudo-lattices.     

Adaptive random walks on the class of Web graphs

We study random walk with adaptive move strategies on a class of directed graphs with variable wiring diagram. The graphs are grown from the evolution rules compatible with the dynamics of the world-wide Web [B. Tadić, Physica A 293, 273 (2001)], and are characterized by a pair of power-law distributions of out- and in-degree for each value of the parameter β, which measures the degree of rewiring in the graph. The walker adapts its move strategy according to locally available information both on out-degree of the visited node and in-degree of target node. A standard random walk, on the other hand, uses the out-degree only. We compute the distribution of connected subgraphs visited by an ensemble of walkers, the average access time and survival probability of the walks. We discuss these properties of the walk dynamics relative to the changes in the global graph structure when the control parameter β is varied. For β≥ 3, corresponding to the world-wide Web, the access time of the walk to a given level of hierarchy on the graph is much shorter compared to the standard random walk on the same graph. By reducing the amount of rewiring towards rigidity limit β↦β_c≲ 0.1, corresponding to the range of naturally occurring biochemical networks, the survival probability of adaptive and standard random walk become increasingly similar. The adaptive random walk can be used as an efficient message-passing algorithm on this class of graphs for large degree of rewiring.     

Fluctuations of the Maximal Particle Energy of the Quantum Ideal Gas and Random Partitions

We investigate the limiting distribution of the fluctuations of the maximal summand in a random partition of a large integer with respect to a multiplicative statistics. We show that for a big family of Gibbs measures on partitions (so-called generalized Bose–Einstein statistics) this distribution is the well-known Gumbel distribution which usually appears in the context of indepedent random variables. In particular, it means that the (properly rescaled) maximal energy of an individual particle in the grand canonical ensemble of the d-dimensional quantum ideal gas has the Gumbel distribution in the limit. We also apply our result to find the fluctuations of the height of a random 3D Young diagram (plane partition) and investigate the order statistics of random partitions under generalized Bose–Einstein statistics.     

Bipartite graphs as models of complex networks

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here a model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make it possible to prove its main properties. This model consists in sampling a random bipartite graph with prescribed degree distribution. Indeed, we show that any complex network may be viewed as a bipartite graph with some specific characteristics, and that its main properties may be viewed as consequences of this underlying structure. We also propose a growing model based on this observation.     

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.