Search

In network science, the non-homogeneity of node degrees has been a concerned issue for study. Yet, with the modern web technologies today, the traditional social communication topologies have evolved from node-central structures to online cycle-based communities, urgently requiring new network theories and tools. Switching the focus from node degrees to network cycles, it could reveal many interesting properties from the perspective of totally homogeneous networks, or sub-networks in a complex network, especially basic simplexes (cliques) such as links and triangles. Clearly, comparing to node degrees it is much more challenging to deal with network cycles. For studying the latter, a new clique vector space framework is introduced in this paper, where the vector space with a basis consisting of links has the dimension equal to the number of links, that with a basis consisting of triangles has the dimension equal to the number of triangles, and so on. These two vector spaces are related through a boundary operator, e.g., mapping the boundary of a triangle in one space to the sun of three links in the other space. Under the new framework, some important concepts and methodologies from algebraic topology, such as characteristic number, homology group and Betti number, will have a play in network science leading to foreseeable new research directions. As immediate applications, the paper illustrates some important characteristics affecting the collective behaviors of complex networks, some new cycle-dependent importance indexes of nodes, and implications for network synchronization and brain network analysis., 13 pages, 5 figures

In this paper, we study a T-IPH/Geo/1 queue model, where T-IPH denotes the discrete-time phase type distribution defined on a birth and death process with countably many states. The queue model can be described by a quasi-birth-and-death process with countably phases. Using operator-geometric solution method, we first give the expression of the operator and the joint stationary distribution. Then we obtain the steady-state distributions for the number of customers in the system, and waiting time for an arbitrary customer.

In this paper we study a Geo/T-IPH/1 queue model, where T-IPH denotes the discrete time phase type distribution defined on a birth-and-death process with countably many states. The queue model can be described by a quasi-birth-and-death (QBD) process with countably phases. Using the operator-geometric solution method, we first give the expression of the operator and the joint stationary distribution. Then we obtain the probability generating function (PGF) for stationary queue length distribution and sojourn time distribution, respectively.

A large number of real-world complex networks or their subnetworks possess excellent dynamical properties such as high dynamic synchronizability, optimal controllability, strong resistance to attacks, fast information transmission capability, and natural emergence of cooperation in evolutionary games, etc., but existing network models are unable to well represent these intrinsic features and ubiquitous phenomena. this paper examines an optimal homogeneous network model which can well describe at least one of such optimal dynamical behaviors-the best possible synchronizability.

Congruence theory has many applications in physical, social, biological and technological systems. Congruence arithmetic has been a fundamental tool for data security and computer algebra. However, much less attention was devoted to the topological features of congruence relations among natural numbers. Here, we explore the congruence relations in the setting of a multiplex network and unveil some unique and outstanding properties of the multiplex congruence network. Analytical results show that every layer therein is a sparse and heterogeneous subnetwork with a scale-free topology. Counterintuitively, every layer has an extremely strong controllability in spite of its scale-free structure that is usually difficult to control. Another amazing feature is that the controllability is robust against targeted attacks to critical nodes but vulnerable to random failures, which also differs from normal scale-free networks. The multi-chain structure with a small number of chain roots arising from each layer accounts for the strong controllability and the abnormal feature. The multiplex congruence network offers a graphical solution to the simultaneous congruences problem, which may have implication in cryptography based on simultaneous congruences. Our work also gains insight into the design of networks integrating advantages of both heterogeneous and homogeneous networks without inheriting their limitations., Comment: 8 pages, 3 figures

We have introduced a vector Markov chain of the vertex number with degree k in network evolving process as a framework of theoretical analysis and proved the stability of the BA-1 model and the LCD-1 model. In this paper, we use the vertex-number-evolving Markov chain to prove rigorously the existence of the steady-state degree distribution P(k) for a special case of the initial attraction model allowing multiple edges. The application of our approach to the LCD-m model, the result shows that it is more simpler than Bollobas’ method.

In this paper, we develop a general analytical method to compute clustering coefficients of growing networks. This method can be applied to any network as long as we can construct and solve the dynamic equation for the degree of any node. We also verify the accuracy of the method through simulation.

In this paper, we propose a simple evolving network model with link and node removals as well as additions and show that this evolving network is scale free with a degree exponent varying in (1,4] depending on the network parameter values. By establishing a relation between the network evolution and a set of non-homogeneous birth-and-death processes, we develop an efficient algorithm to compute the network degree distribution. Our numerical results match simulation well and show how the network evolves into the scale-free state.

This paper proposes a Markov chain method to predict the growth dynamics of the individual nodes in scale-free networks, and uses this to calculate numerically the degree distribution. We first find that the degree evolution of a node in the BA model is a nonhomogeneous Markov chain. An efficient algorithm to calculate the degree distribution is developed by the theory of Markov chains. The numerical results for the BA model are consistent with those of the analytical approach. A directed network with the logarithmic growth is introduced. The algorithm is applied to calculate the degree distribution for the model. The numerical results show that the system self-organizes into a scale-free network.

Following up Neuts' idea, the SPH-distribution class associated with bounded Q matrices for infinite Markov chains is defined. The main result in this paper is to characterize the SPH class through the derivatives of the distribution functions. Based on the characterization theorem, closure properties, the expansion, uniform approximation, and the matrix representations of the SPH class are also discussed by the derivatives of the distribution functions at origin.

In order to explore further the mechanism responsible for scale-free networks, we introduce two extended models of the BA model. The model A, where the system incorporates the addition of new links between existing nodes, a new node with new links and the rewiring of some links at every time step, all sites are born with some initial attractiveness. We calculate analytically the degree distribution. The system self-organizes into a scale-free network, the scaling exponent γ >2. The model B is a new model; we consider that some old links are deleted with the anti-preferential probability. The result indicates that the system evolves itself into a scale-free network, the scaling exponent γ varies from 2 to 3.

In this paper, we give a new proof of the transition frequency formula for the state transition counting process in a vector Markov process (VMP). The formula was first presented by the author in the early eighties. We also derive the absorbing distribution, the renewal distribution and the entering probability formulas from the formula. As an application, we use derived results to reduce the analysis of a fluid model with random disruptions.

This note introduces reliability issues to the analysis of queueing systems. We consider an M/G/1 queue with Bernoulli vacations and server breakdowns. The server uptimes are assumed to be exponential, and the server repair times are arbitrarily distributed. Using a supplementary variable method we obtain a transient solution for both queueing and reliability measures of interest. These results provide insight into the effect of server breakdowns and repairs on system performance.

This note introduces reliability issues to the analysis of queueing systems. We consider an M/G/1 queue with Bernoulli vacations and server breakdowns. The server uptimes are assumed to be exponential, and the server repair times are arbitrarily distributed. Using a supplementary variable method we obtain a transient solution for both queueing and reliability measures of interest. These results provide insight into the effect of server breakdowns and repairs on system performance.

We could get the epidemic threshold from continuous-time SIS model in small-world networks, but the steady value of spreading process shows a large difference with the simulations. To explain this difference, by introducing discrete-time SIS model, the steady value fit well with the simulations. As the spreading rate and recovery rate close to 1, both models could not explain the periodicity in the spreading process.

A large number of real-world complex networks or their sub-networks possess excellent dynamical properties such as high dynamic synchronizability, optimal controllability, strong resistance to attacks, and fast information spreading capability, but existing network models are unable to well represent these intrinsic features and ubiquitous phenomena. This paper establishes an optimal homogeneous network model which can well describe at least one of such optimal dynamical behaviors — the best possible synchronizability.

The assortative/disassortative mixing is an important index to study the degree correlation among nodes in networks. This paper discussed Newman correlation coefficient r(g) for the assortative/disassortative mixing and pointed out that the metric was unstable about network's size and dense degree. Besides, a simple and effective assortative/disassortative metric was put forward for networks, and it was named as mixing coefficient I(g). The result showed that this metric had more advantages than r(g) or improved R(g).

作为一门新兴交叉科学，诞生于本世纪前夕的网络科学，冲破了随机图论的静态束缚，开启了动态复杂网络研究的新时代。网络科学与随机图论的一个关键不同之处，是(节点)度分布不再局限于像一条钟形曲线那样的泊松分布。这一拓扑结构的变化使得网络功能及其动力学特征涌现出前所未有的属性。无标度网络的发现，是网络科学产生过程中的一个里程碑，因此，正确了解无标度网络的度分布，对于网络科学的进一步发展至关重要。 本文抓住了无标度网络概念的共性，即度分布具有重尾特征，给出了严格的定义和分类。 幂律随机图是指度分布服从精确幂律的一类随机图。无标度网络则宽泛些，只要求度分布尾部按幂律衰减。因为幂律分布或幂律衰减在双对数坐标系上，图形都呈现为一条直线。所以网络文献都据此来判断是否为无标度网络，然而这种推理极易误导读者。如图中所示， 4套数据看似与直线拟合很好，并且尽管有2套数据是无标度网络 (黄色是阿波罗尼斯网络，度指数有争议；绿色来自Barabasi等人研究的节点一致适应度模型)，但没有一套数据有衰减的幂律尾部。可见在理解和判断无标度网络度分布问题上，网络科学共同体还未达成共识。 幂律随机图与无标度网络的相似处是度分布都具有重尾特征。区别在于幂律随机图的度分布服从精确幂律；而无标度网络的度分布可以是任意重尾分布。虽然幂律分布是最具代表性的重尾分布，但重尾分布却不只局限于精确幂律分布。由此会引发一系列问题，例如，基于无标度网络模拟得到的某些网络重要特性与根据精确幂律推导的结果会不一致。史定华教授研究发现幂律随机图属于无标度网络大家庭中最小的子集，而实际的复杂网络往往不在其中。 精确幂律分布有简洁的解析表达式，而任意重尾分布却没有。在研究无标度网络时，人们往往用精确幂律分布替代，从而演绎出许多有争议的命题。另一方面，在网络实证分析时，要么采用在双对数坐标系上画图，要么采用基于连续幂律分布的极大似然估计。这种实证分析结果的可信性值得商榷。为了应对这些挑战，人们需要引入新的计算和统计方法。 本文认为，为了使得网络科学发展成为一门成熟的现代科学，必须在基础理论研究上多费些功夫。

Currently, simulation is usually used to estimate network degree distribution P(k) and to examine if a network model predicts a scale-free network when an analytical formula does not exist. An alternative Markovian chain-based numerical method was proposed by Shi et al. [Phys. Rev. E 71, 036140 (2005)] to compute time-dependent degree distribution P(k, t). Although the numerical results demonstrate a quick convergence of P(k, t) to P(k) for the Barabasi-Albert model, the crucial issue on the rate of convergence has not been addressed formally. In this paper, we propose a simpler Markovian iterative method to compute P(k, t) for a class of growing network models. We also provide an upper bound estimation of the error of using P(k,t) to represent P(k) for sufficiently large t, and we show that with the iterative method, the rate of convergence of P(k, t) is root linear.

In this paper, we study the two-dimensional tri-diagonal quasi-birth-and-death (QBD) process with infinite blocks and the blocks are infinite double sides tri-diagonal matrices, which has an important application in queue theory such as joining the shortest queue problem. Our objective is to develop an accurate and easily implementable algorithmic approach to compute the stationary probabilities of the process. We also give the computational complexity for the algorithm and some numerical examples.

In this paper, we abstract a kind of stochastic processes from evolving processes of growing networks, this process is called growing network Markov chains. Thus the existence and the formulas of degree distribution are transformed to the corresponding problems of growing network Markov chains. First we investigate the growing network Markov chains, and obtain the condition in which the steady degree distribution exists and get its exact formulas. Then we apply it to various growing networks. With this method, we get a rigorous, exact and unified solution of the steady degree distribution for growing networks.

This paper discusses continuous fractal traffic queueing models by combining the density evolution method with fractal-chaos function theory. We use fractal-chaos functions to control the input process of queueing models. By setting up and carrying out the density evolution equations, we obtain the limiting probability of the number of packets in the system with invariant measures. Simulation results are obtained to show a heavy tailed property. We believe that this model will benefit engineering applications, where the engineer just needs to adjust the parameters of S/sub (x)/ to present the appropriate models in a mobile communication process.

The paper discusses continuous fractal M/M/1 traffic models by combining the density evolution method with fractal-chaos function theory. We use fractal-chaos functions to control the input process of queueing models. By setting up and carrying out density evolution equations, we obtain the limiting probability of the number of packets in the system with invariant measures. Simulation results are obtained showing a heavy tailed property.

In this paper we study an M/T-SPH/1 queue system, where T-SPH denotes the continuous time phase type distribution defined on a birth and death process with countably many states. The queue model can be described by a quasi-birth-and-death (QBD) process with countable phases. For the QBD process, we give the computation scheme of the joint stationary distribution. Furthermore, the obtained results enable us to give the stationary queue length distribution for the M/T-SPH/1 queue.

It is well-known that the key to calculating system reliability lies in finding disjoint S-O-P expression of the system structure functions. In this paper two general algorithms, direct sharp and recursive sharp, are developed for this purpose. They are suitable not only for coherent systems, but non-coherent systems as well. Especially, the recursive sharp algorithm has more advantages than the direct sharp algorithm. It not only has more rapid computation speed than existing methods have, but also simultaneously obtains disjoint covers of success and failure events of the system, which are useful in calculating the time-specific frequency of system failure. In addition, the recursive sharp algorithm can yield good approximations of the reliability when the system is so large that computation time becomes prohibitive.

Although the scale invariance is a main feature of growing networks, evidence from a few modelled networks show that the finite-size effect of network at a fixed time t cannot be ignored. We propose a concept of time-dependent scale-free networks, and prove the criteria for the stability and scale-free of growing networks by the degree-growing Markov chain. Our results show the importance of rigorous theoretical analysis for the network science.