Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks

Abstract

Testing or benchmarking network algorithms in bioinformatics requires a diverse set of networks with realistic properties. Real networks are often supplemented by randomly generated synthetic ones, but most graph generative models do not take into account the distribution of subgraph patterns, i.e. motifs or graphlets. Moreover, in many cases, biological interactions are uncertain events and must be modeled by probabilistic graph edges. The uncertainty is often ignored in practice, which can lead to incorrect conclusions about the properties of biological networks. In this work, we instead derive bounds on the graphlet counts and degree distribution of a probabilistic target network and use this information as input to a novel random graph generation algorithm. The algorithm grows graphs incrementally by making small modifications in every step, which allows for an efficient graphlet counting method. Using this method, we can update graphlet counts after each iteration in a time independent of the total node number on sparse graphs. We evaluate our model on synthetic and real networks of different sizes and with different degrees of uncertainty. Although computation times strongly depend on the size of graphlets taken into account, our experiments demonstrate that graphs with over 10 000 edges and well-controlled frequencies of all three- and four-node graphlets can be generated in under an hour.