Testar ou avaliar algoritmos de rede em bioinformática requer um conjunto diversificado de redes com propriedades realistas. Redes reais são frequentemente complementadas por redes sintéticas geradas aleatoriamente, mas a maioria dos modelos geradores de gráficos não leva em conta a distribuição de padrões de subgrafos, ou seja, motivos ou grafos. Além disso, em muitos casos, interações biológicas são eventos incertos e devem ser modeladas por arestas de gráfico probabilísticas. A incerteza geralmente é ignorada na prática, o que pode levar a conclusões incorretas sobre as propriedades de redes biológicas. Neste trabalho, derivamos limites sobre as contagens de grafos e a distribuição de grau de uma rede-alvo probabilística e usamos essas informações como entrada para um novo algoritmo de geração de gráficos aleatórios. O algoritmo cresce gráficos incrementalmente fazendo pequenas modificações em cada etapa, o que permite um método eficiente de contagem de grafos. Usando esse método, podemos atualizar as contagens de grafos após cada iteração em um tempo independente do número total de nós em gráficos esparsos. Avaliamos nosso modelo em redes sintéticas e reais de diferentes tamanhos e com diferentes graus de incerteza. Embora os tempos de computação dependam fortemente do tamanho dos grafos considerados, nossos experimentos demonstram que gráficos com mais de 10.000 arestas e frequências bem controladas de todos os grafos de três e quatro nós podem ser gerados em menos de uma hora.
Mornie et al. (Ter,) estudaram essa questão.