Growing Graphs with Hyperedge Replacement Graph Grammars
This provides a method for generating realistic synthetic graphs that mimic complex real-world networks, which is useful for researchers and practitioners in network science and machine learning, though it is incremental as it builds on existing graph grammar techniques.
The paper tackles the problem of discovering underlying structures in large real-world graphs by extracting hyperedge replacement grammars from clique trees, which can generate isomorphic copies or random graphs with similar properties. Experiments show that random graphs from these grammars preserve both global properties like degree centrality and local substructures, performing well on robustness tests.
Discovering the underlying structures present in large real world graphs is a fundamental scientific problem. In this paper we show that a graph's clique tree can be used to extract a hyperedge replacement grammar. If we store an ordering from the extraction process, the extracted graph grammar is guaranteed to generate an isomorphic copy of the original graph. Or, a stochastic application of the graph grammar rules can be used to quickly create random graphs. In experiments on large real world networks, we show that random graphs, generated from extracted graph grammars, exhibit a wide range of properties that are very similar to the original graphs. In addition to graph properties like degree or eigenvector centrality, what a graph "looks like" ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that our generative graph model is able to preserve these local substructures when generating new graphs and performs well on new and difficult tests of model robustness.