Abstract. We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Solé et al. [ Adv. Complex Syst., 5 (2002), pp. 43–54] in which the graph grows according to a duplication-divergence mechanism, i.e., by iteratively creating a copy of some node and then randomly alternating the neighborhood of a new node with probability [Formula: see text]. This model captures the growth of some real-world processes, e.g., biological or social networks. In this paper, we prove that for some [Formula: see text], the maximum degree and the average degree of a duplication-divergence graph on [Formula: see text] vertices are asymptotically concentrated with high probability around [Formula: see text] and [Formula: see text], respectively, i.e., they are within at most a polylogarithmic factor from these values with probability at least [Formula: see text] for any constant [Formula: see text].

Recently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph ( G , σ ) it holds that Δ ( G ) ≤ χ ′ ( G , σ ) ≤ Δ ( G ) + 1 , where Δ ( G ) is the maximum degree of G and χ ′ denotes its chromatic index. In general, the chromatic index of ( G , σ ) depends on both the underlying graph G and the signature σ . In the paper we study graphs G for which χ ′ ( G , σ ) does not depend on σ . To this aim we introduce two new classes of graphs, namely 1 ± and 2 ± , such that graph G is of class 1 ± (respectively, 2 ± ) if and only if χ ′ ( G , σ ) = Δ ( G ) (respectively, χ ′ ( G , σ ) = Δ ( G ) + 1 ) for all possible signatures σ . We prove that all wheels, necklaces, complete bipartite graphs K r , t with r ≠ t and almost all cacti graphs are of class 1 ± . Moreover, we give sufficient and necessary conditions for a graph to be of class 2 ± , i.e. we show that these graphs must have odd maximum degree and give examples of such graphs with arbitrary odd maximum degree bigger than 1.

In the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic one, are related: our new parameter is an upper bound for the game chromatic number.

Graph models often give us a deeper understanding of real-world networks. In the case of biological networks they help in predicting the evolution and history of biomolecule interactions, provided we map properly real networks into the corresponding graph models. In this paper, we show that for biological graph models many of the existing parameter estimation techniques overlook the critical property of graph symmetry (also known formally as graph automorphisms), thus the estimated parameters give statistically insignificant results concerning the observed network. To demonstrate it and to develop accurate estimation procedures, we focus on the biologically inspired duplication-divergence model, and the up-to-date data of protein-protein interactions of seven species including human and yeast. Using exact recurrence relations of some prominent graph statistics, we devise a parameter estimation technique that provides the right order of symmetries and uses phylogenetically old proteins as the choice of seed graph nodes. We also find that our results are consistent with the ones obtained from maximum likelihood estimation (MLE). However, the MLE approach is significantly slower than our methods in practice.

We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis.

Given a single snapshot of a dynamic network in which nodes arrived at distinct time instants along with edges, we aim at inferring a partial order σ between the node pairs such that uσv indicates node u arrived earlier than node v in the graph. The inferred partial order can be deduced to a natural clustering of the nodes into K ordered clusters C1Ksuch that for iijoined the network before nodes in cluster Cj, with K being a data-driven parameter and not known upfront. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal partial order, achieving the best precision (i.e., fraction of successfully ordered node pairs) for a fixed density (i.e., fraction of comparable node pairs). We then design algorithms to find temporal ordered clusters that efficiently approximate the optimal solution. To illustrate our techniques, we apply our methods to the vertex copying model (also known as the duplication-divergence model).

Abstract We continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs $$\Theta (n)$$ Θ(n) bits while its unlabeled version (structure) can be described by $$\Theta (\log n)$$ Θ(logn) bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).

Dirichlet distribution and multinomial distribution play important role in information theory and statistics. They find applications in estimation, average minimax redundancy in source coding, Pólya urn model, and graph compression. Dirichlet-multinomial distribution is a multinomial distribution in which parameters are distributed according to the Dirichlet distribution. In this paper, we present some characteristics of the Dirichlet-multinomial distribution, including a precise asymptotic for the entropy. It should be point out that such a characterization turns out to be technically quite challenging requiring analytic tools including analytic continuation of hypergeometric series.

Compression schemes for advanced data structures have become a central modern challenge. Information theory has traditionally dealt with conventional data such as text, images, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [8]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version (where order of subtrees doesn't matter). Furthermore, we assume that each name is generated by a known memoryless source (horizontal independence), but a symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name (vertical Markovian dependency). Such a model is closely connected to models of phylogenetic trees. While in general the problem of multimodal compression and associated analysis can be extremely complicated, we find that in this natural setting, both the entropy analysis and optimal compression are analytically tractable. We evaluate the entropy for both types of trees. For the plane case, with or without vertex names, we find that a simple two-stage compression scheme is both efficient and optimal. We then present efficient and optimal compression algorithms for the more complicated non-plane case.

Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multi-type and context dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version. Furthermore, we assume that each symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name. We first evaluate the entropy for both types of trees. Then we propose for known sources two compression schemes COMPRESSPTREE for plane trees with correlated names, and COMPRESSNPTREE for non-plane trees. We show that these schemes achieve the lower bound within two bits.