Phase-type models for cellular networks supporting voice, video and data traffic

This paper presents an analytical model for cellular networks supporting voice, video and data traffic. Self-similar and bursty nature of the incoming traffic causes correlation in inter-arrival times of the incoming traffic. Therefore, arrival of calls is modeled with Markovian arrival process as it allows for the correlation. Call holding times, cell residence times and retrial times are modeled as phase-type distributions. We consider that the cells in a cellular network are statistically homogeneous, so it is enough to investigate a single cell for the performance analysis of the entire networks. With appropriate assumptions, the stochastic process that describes the state of a cell is a Quasi-birth–death (QBD) process. We derive explicit expressions for the infinitesimal generator matrix of this QBD process. Also, expressions for performance measures are obtained. Further, complexity involved in computing the steady-state probabilities is discussed. Finally, queueing examples are provided that can be obtained as particular cases of the proposed analytical model.     

Centered graphs and the structure of ego networks

A way of comparing ego networks through examining patterns among their ties is introduced. It is derived from graph-theoretic ideas about centered graphs. An illustration using data from a computer conference is provided.     

Fractal and smoothness properties of space-time Gaussian models

Spatio-temporal models are widely used for inference in statistics and many applied areas. In such contexts, interests are often in the fractal nature of the sample surfaces and in the rate of change of the spatial surface at a given location in a given direction. In this paper, we apply the theory of Yaglom (1957) to construct a large class of space-time Gaussian models with stationary increments, establish bounds on the prediction errors, and determine the smoothness properties and fractal properties of this class of Gaussian models. Our results can be applied directly to analyze the stationary spacetime models introduced by Cressie and Huang (1999), Gneiting (2002), and Stein (2005), respectively.     

On the possible values of the entropy of undirected graphs

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.     

Intersection models of weakly chordal graphs

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.     

Divisors on graphs,binomial and monomial ideals,and cellular resolutions

We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show that the resolutions of all these ideals are closely related and that their \({\mathbb {Z}}\)-graded Betti tables coincide. As corollaries, we give conceptual proofs of conjectures and questions posed by Postnikov and Shapiro, by Manjunath and Sturmfels, and by Perkinson, Perlman, and Wilmes. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.     

Spectra of generalized compositions of graphs and hierarchical networks

We compute the Laplacian spectra and eigenfunctions of generalized compositions of graphs, as explicit functions of the spectra and eigenfunctions of their components. Applications to two-level hierarchical graphs are given. We introduce the tree composition of graphs and study its spectral decomposition, with applications to some hierarchical networks.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.     

Strongly regular graphs and spin models for the Kauffman polynomial

We study spin models for invariants of links as defined by Jones [22]. We consider the two algebras generated by the weight matrices of such models under ordinary or Hadamard product and establish an isomorphism between them. When these algebras coincide they form the Bose-Mesner algebra of a formally self-dual association scheme. We study the special case of strongly regular graphs, which is associated to a particularly interesting link invariant, the Kauffman polynomial [27]. This leads to a classification of spin models for the Kauffman polynomial in terms of formally self-dual strongly regular graphs with strongly regular subconstituents [7]. In particular we obtain a new model based on the Higman-Sims graph [17].     

The weak limit of Ising models on locally tree-like graphs

We consider the Ising model with inverse temperature β and without external field on sequences of graphs G _n which converge locally to the k-regular tree. We show that for such graphs the Ising measure locally weakly converges to the symmetric mixture of the Ising model with + boundary conditions and the ? boundary conditions on the k-regular tree with inverse temperature β. In the case where the graphs G _n are expanders we derive a more detailed understanding by showing convergence of the Ising measure conditional on positive magnetization (sum of spins) to the + measure on the tree.     

Enumeration of 2-regular circulant graphs and directed double networks

We present a formula to enumerate non-isomorphic circulant digraphs of order n with connection sets of cardinality 2. This formula simplifies to C(n,2)=3×2^a−1−4 in the case when n=2^a(a≥3), and when n=p^a(where p is an odd prime and a≥1). The number of non-isomorphic directed double networks are also enumerated.     

Random walks and flights over connected graphs and complex networks

Markov chains provide us with a powerful probabilistic tool that allows to study the structure of connected graphs in details. The statistics of events for Markov chains defined on connected graphs can be effectively studied by the method of generalized inverses which we review. The approach is also applicable for directed graphs and interacting networks which share the set of nodes. We discuss a generalization of Lévy flight random walks for large complex networks and study the interplay between the nonlinearity of diffusion process and the topological structure of the network.     

New concepts of regular and (highly) irregular vague graphs with applications

In this paper, some types of vague graphs are introdaced such as $d_m$-regular, $t{d}_m$-regular, $m$-highly irregular and $m$-highly totally irregular vague graphs are introduced and some properties of them are discussed. Comparative study between $d_m$-regular ($m$-highly irregular) vague graph and $t{d}_m$-regular ($m$-highly totally irregular) vague graph are done. In addition, $d_m$-regularity and $m$-highly irregularity on some vague graphs, which underlying crisp graphs are a cycle or a path is also studied. Finally, some applications of regular vague graphs are given for demonstration of fullerene molecules, road transport network and wireless multihop networks.     

Complex dynamics of epidemic models on adaptive networks

There has been a substantial amount of well mixing epidemic models devoted to characterizing the observed complex phenomena (such as bistability, hysteresis, oscillations, etc.) during the transmission of many infectious diseases. A comprehensive explanation of these phenomena by epidemic models on complex networks is still lacking. In this paper we study epidemic dynamics in an adaptive network proposed by Gross et al., where the susceptibles are able to avoid contact with the infectious by rewiring their network connections. Such rewiring of the local connections changes the topology of the network, and inevitably has a profound effect on the transmission of the disease, which in turn influences the rewiring process. We rigorously prove that the adaptive epidemic model investigated in this paper exhibits degenerate Hopf bifurcation, homoclinic bifurcation and Bogdanov–Takens bifurcation. Our study shows that adaptive behaviors during an epidemic may induce complex dynamics of disease transmission, including bistability, transient and sustained oscillations, which contrast sharply to the dynamics of classical network models. Our results yield deeper insights into the interplay between topology of networks and the dynamics of disease transmission on networks.