Generating graphs that are similar to real ones is an open problem, while the similarity notion is quite elusive and hard to formalize. In this paper, we focus on sparse digraphs and propose SDG, an algorithm that aims at generating graphs similar to real ones. Since real graphs are evolving and this evolution is important to study in order to understand the underlying dynamical system, we tackle the problem of generating series of graphs. We propose SEDGE, an algorithm meant to generate series of graphs similar to a real series. SEDGE is an extension of SDG. We consider graphs that are representations of software programs and show experimentally that our approach outperforms other existing approaches. Experiments show the performance of both algorithms.
We have shown that the in-degree and the out-degree distributions of the graphs generated by exhibit a power law. This may come as a surprise to the reader, well aware of earlier works, such as @cite_8 . Indeed, our graph is not growing, keeping a set of @math nodes, connecting them along the iterations of the algorithm. However, the departure from a power law is expected when the number of iterations is approximately @math , that is when the graph gets dense. However, as we emphasized it earlier, we only consider sparse graphs, and the number of iterations, hence the number of edges, remains @math , hence much less than @math .
@cite_8
2008620264
Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.