publication . Preprint . Conference object . 2016

Growing Graphs from Hyperedge Replacement Graph Grammars

Salvador Aguiñaga; Rodrigo Palacios; David Chiang; Tim Weninger;
Open Access English
  • Published: 10 Aug 2016
Abstract
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 additio...
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Computer Science - Social and Information Networks, Computer Science - Computation and Language
Related Organizations
25 references, page 1 of 2

[1] S. Aguinaga and T. Weninger. The infinity mirror test for analyzing the robustness of graph generators. In ACM SIGKDD Workshop on Mining and Learning with Graphs, MLG '16, New York, NY, USA, 2016. ACM. [OpenAIRE]

[2] S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987.

[3] L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In SIGKDD, pages 44-54. ACM, 2006.

[4] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. science, 286(5439):509- 512, 1999.

[5] C. Canestro, H. Yokoi, and J. H. Postlethwait. Evolutionary developmental biology and genomics. Nat Rev Genet, 8(12):932-942, Dec 2007. [OpenAIRE]

[6] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of combinatorics, 6(2):125-145, 2002.

[7] F. Drewes, B. Hoffmann, and D. Plump. Hierarchical graph transformation. Journal of Computer and System Sciences, 64(2):249 - 283, 2002. [OpenAIRE]

[8] S. Geman and M. Johnson. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In ACL, pages 279-286. Association for Computational Linguistics, 2002. [OpenAIRE]

[9] H. S. Heaps. Information retrieval: Computational and theoretical aspects. Academic Press, Inc., 1978.

[10] D. R. Hunter, M. S. Handcock, C. T. Butts, S. M. Goodreau, and M. Morris. ergm: A package to fit, simulate and diagnose exponential-family models for networks. J Stat Softw, 24(3), May 2008. 19756229[pmid]. [OpenAIRE]

[11] C. Kemp and J. B. Tenenbaum. The discovery of structural form. PNAS, 105(31):10687-10692, 2008.

[12] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.

[13] J. P. Kukluk, L. B. Holder, and D. J. Cook. Inference of node replacement recursive graph grammars. In SDM, pages 544-548. SIAM, 2006. [OpenAIRE]

[14] J. P. Kukluk, L. B. Holder, and D. J. Cook. Inference of edge replacement graph grammars. International Journal on Artificial Intelligence Tools, 17(03):539-554, 2008.

[15] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11:985-1042, feb 2010.

25 references, page 1 of 2
Related research
Abstract
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 additio...
Subjects
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Computer Science - Social and Information Networks, Computer Science - Computation and Language
Related Organizations
25 references, page 1 of 2

[1] S. Aguinaga and T. Weninger. The infinity mirror test for analyzing the robustness of graph generators. In ACM SIGKDD Workshop on Mining and Learning with Graphs, MLG '16, New York, NY, USA, 2016. ACM. [OpenAIRE]

[2] S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987.

[3] L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In SIGKDD, pages 44-54. ACM, 2006.

[4] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. science, 286(5439):509- 512, 1999.

[5] C. Canestro, H. Yokoi, and J. H. Postlethwait. Evolutionary developmental biology and genomics. Nat Rev Genet, 8(12):932-942, Dec 2007. [OpenAIRE]

[6] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of combinatorics, 6(2):125-145, 2002.

[7] F. Drewes, B. Hoffmann, and D. Plump. Hierarchical graph transformation. Journal of Computer and System Sciences, 64(2):249 - 283, 2002. [OpenAIRE]

[8] S. Geman and M. Johnson. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In ACL, pages 279-286. Association for Computational Linguistics, 2002. [OpenAIRE]

[9] H. S. Heaps. Information retrieval: Computational and theoretical aspects. Academic Press, Inc., 1978.

[10] D. R. Hunter, M. S. Handcock, C. T. Butts, S. M. Goodreau, and M. Morris. ergm: A package to fit, simulate and diagnose exponential-family models for networks. J Stat Softw, 24(3), May 2008. 19756229[pmid]. [OpenAIRE]

[11] C. Kemp and J. B. Tenenbaum. The discovery of structural form. PNAS, 105(31):10687-10692, 2008.

[12] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.

[13] J. P. Kukluk, L. B. Holder, and D. J. Cook. Inference of node replacement recursive graph grammars. In SDM, pages 544-548. SIAM, 2006. [OpenAIRE]

[14] J. P. Kukluk, L. B. Holder, and D. J. Cook. Inference of edge replacement graph grammars. International Journal on Artificial Intelligence Tools, 17(03):539-554, 2008.

[15] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11:985-1042, feb 2010.

25 references, page 1 of 2
Related research
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue