Sampling properties of random graphs: the degree distribution

The need to produce accurate estimates of vertex degree in a large network, based on observation of a subnetwork, arises in a number of practical settings. We study a formalized version of this problem, wherein the goal is, given a randomly sampled subnetwork from a large parent network, to estimate the actual degree of the sampled nodes. Depending on the sampling scheme, trivial method of moments estimators (MMEs) can be used. However, the MME is not expected, in general, to...

Random graph null models have found widespread application in diverse research communities analyzing network datasets, including social, information, and economic networks, as well as food webs, protein-protein interactions, and neuronal networks. The most popular family of random graph null models, called configuration models, are defined as uniform distributions over a space of graphs with a fixed degree sequence. Commonly, properties of an empirical network are compared to...

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and online social networks (OSNs). Nowadays the massive size of some critical networks -- often stored in already overloaded relational databases -- effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propo...

We study the following problem: given an integer $k \ge 3$ and a simple graph $G$, sample a connected induced $k$-node subgraph of $G$ uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling; the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or ...

In random graph models, the degree distribution of an individual node should be distinguished from the (empirical) degree distribution of the graph that records the fractions of nodes with given degree. We introduce a general framework to explore when these two degree distributions coincide asymptotically in large homogeneous random networks. The discussion is carried under three basic statistical assumptions on the degree sequences: (i) a weak form of distributional homogene...

The simplest null models for networks, used to distinguish significant features of a particular network from {\it a priori} expected features, are random ensembles with the degree sequence fixed by the specific network of interest. These "fixed degree sequence" (FDS) ensembles are, however, famously resistant to analytic attack. In this paper we introduce ensembles with partially-fixed degree sequences (PFDS) and compare analytic results obtained for them with Monte Carlo res...

Sampling random nodes is a fundamental algorithmic primitive in the analysis of massive networks, with many modern graph mining algorithms critically relying on it. We consider the task of generating a large collection of random nodes in the network assuming limited query access (where querying a node reveals its set of neighbors). In current approaches, based on long random walks, the number of queries per sample scales linearly with the mixing time of the network, which can...

Understanding the mathematical properties of graphs underling biological systems could give hints on the evolutionary mechanisms behind these structures. In this article we perform a complete statistical analysis over thousands of graphs representing metabolic and protein-protein interaction (PPI) networks. First, we investigate the quality of fits obtained for the nodes degree distributions to power-law functions. This analysis suggests that a power-law distribution poorly d...

We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a d...

We present a simple model for the underlying structure of protein-protein pairwise interaction graphs that is based on the way in which proteins attach to each other in experiments such as yeast two-hybrid assays. We show that data on the interactions of human proteins lend support to this model. The frequency of the number of connections per protein under this model does not follow a power law, in contrast to the reported behaviour of data from large scale yeast two-hybrid s...