Source author record

Milena Mihail

Milena Mihail appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics

Catalog footprint

What is connected

2works

2topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Graphic Realizations of Joint-Degree Matrices

In this paper we introduce extensions and modifications of the classical degree sequence graphic realization problem studied by Erdős-Gallai and Havel-Hakimi, as well as of the corresponding connected graphic realization version. We define the joint-degree matrix graphic (resp. connected graphic) realization problem, where in addition to the degree sequence, the exact number of desired edges between vertices of different degree classes is also specified. We give necessary and sufficient conditions, and polynomial time decision and construction algorithms for the graphic and connected graphic realization problems. These problems arise naturally in the current topic of graph modeling for complex networks. From the technical point of view, the joint-degree matrix realization algorithm is straightforward. However, the connected joint-degree matrix realization algorithm involves a novel recursive search of suitable local graph modifications. Also, we outline directions for further work of both theoretical and practical interest. In particular, we give a Markov chain which converges to the uniform distribution over all realizations. We show that the underline state space is connected, and we leave the question of the mixing rate open.

preprint2012arXiv

Efficient Generation ε-close to G(n,p) and Generalizations

We give an efficient algorithm to generate a graph from a distribution $ε$-close to $G(n,p)$, in the sense of total variation distance. In particular, if $p$ is represented with $O(\log n)$-bit accuracy, then, with high probability, the running time is linear in the expected number of edges of the output graph (up to poly-logarithmic factors). All our running times include the complexity of the arithmetic involved in the corresponding algorithms. Previous standard methods for exact $G(n,p)$ sampling (see e.g. Batagelj and Brandes, 2005) achieve similar running times, however, under the assumption that performing real number arithmetic with arbitrary accuracy takes constant time. We note that the actual accuracy required by these methods is O(n)-bit per step, which results in quadratic running times. The main idea of our $G(n,p)$ generation algorithm is a Metropolis Markov chain to sample $ε$-close from the binomial distribution. This is a new method for sampling from the binomial distribution: it is of separate interest and may find other useful applications. Our analysis accounts for all necessary bit-accuracy and arithmetic, and our running times are comparable to known methods for exact binomial sampling. We further obtain efficient generation algorithms for random graphs with given arbitrary degree distributions, Inhomogeneous Random Graphs when the kernel function is the inner product, and Stochastic Kronecker Graphs. To the best our knowledge, our work can be viewed as the first effort to simulate efficient generation of graphs from classical random graph models, while taking into account implementational considerations as fundamental computational aspects, and quantifying the tradeoff between accuracy and running time in a way that can be useful in practice.