Exploratory Equivalence in Graphs: Definition and Algorithms

• Autorzy: Jurij Mihelič , Luka Fürst , Uroš Čibej
• Języki publikacji: EN

Abstrakty

EN

Motivated by improving the efficiency of pattern matching on graphs, we define a new kind of equivalence on graph vertices. Since it can be used in various graph algorithms that explore graphs, we call it exploratory equivalence. The equivalence is based on graph automorphisms. Because many similar equivalences exist (some also based on automorphisms), we argue that this one is novel. For each graph, there are many possible exploratory equivalences, but for improving the efficiency of the exploration, some are better than others. To this end, we define a goal function that models the reduction of the search space in such algorithms. We describe two greedy algorithms for the underlying optimization problem. One is based directly on the definition using a straightforward greedy criterion, whereas the second one uses several practical speedups and a different greedy criterion. Finally, we demonstrate the huge impact of exploratory equivalence on a real application, i.e, graph grammar parsing.(original abstract)

Słowa kluczowe

EN

Graphs; Algorithms; Mathematical analysis

PL

Grafy; Algorytmy; Analiza matematyczna

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 447--456

Twórcy

autor

Jurij Mihelič

• University of Ljubljana, Slovenia

autor

Luka Fürst

• University of Ljubljana, Slovenia

autor

Uroš Čibej

• University of Ljubljana, Slovenia

Bibliografia

• Agrafiotis D. K., Lobanov V. S., Shemanarev M., Rassokhin D. N., Izrailev S., Jaeger E. P., Alex S., and Farnum M., "Efficient Substructure Searching of Large Chemical Libraries: The ABCD Chemical Cartridge," J. Chem. Inf. Model., 2011. doi: 10.1021/ci200413e
• Barnard J. M., "Substructure searching methods: Old and new," J. Chemical Information and Computer Sciences, vol. 33, no. 4, pp. 532-538, 1993. doi: 10.1021/ci00014a001
• Cordella L. P., Foggia P., Sansone C., and Vento M., "A (sub)graph isomorphism algorithm for matching large graphs." IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-72, Oct. 2004. doi: 10.1109/TPAMI.2004.75
• Ehrig H., Engels G., Kreowski H. -J., Rozenberg G., and Montanari U., Eds., Handbook of graph grammars and computing by graph transformation (Vols. 1.-3.). World Scientific, 1997-1999.
• Everett M. G. and Borgatti S. P., "Regular equivalence: General theory," Journal of mathematical sociology, vol. 19, no. 1, pp. 29-52, 1994. doi: 10.1080/0022250X.1994.9990134
• Fomin F. V. and Kratsch D., Exact Exponential Algorithms. Springer, 2011.
• Fuurst L., Mernik M., and Mahniˇc V., "Improving the graph grammar parser of Rekers and Sch¨urr," IET Software, vol. 5, no. 2, pp. 246-261, 2011. doi: 10.1049/iet-sen.2010.0081
• Hopkins B., "Kevin Bacon and graph theory," PRIMUS, vol. 14, no. 1, pp. 5-11, 2004. doi: 10.1080/10511970408984072
• Jackson M. O., Social and Economic Networks. Princeton, NJ, USA: Princeton University Press, 2008. ISBN 0691134405, 9780691134406
• Knoke D., Political Networks: The Structural Perspective, ser. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. ISBN 9780521477628
• Liberti L., "Automatic generation of symmetry-breaking constraints," in COCOA, ser. Lecture Notes in Computer Science, B. Yang, D.-Z. Du, and C. Wang, Eds., vol. 5165. Springer, 2008. doi: 10.1007/978-3-540-85097-7 31 pp. 328-338.
• McKay B. D. and Piperno A., "Practical graph isomorphism, ii," J. Symbolic Computation, vol. 60, pp. 94-112, 2013. doi: 10.1016/j.jsc.2013.09.003
• Mucherino A., Lavor C., and Liberti L., "Exploiting symmetry properties of the discretizable molecular distance geometry problem," J. Bioinformatics and Computational Biology, vol. 10, no. 3, 2012. doi: 10.1142/S0219720012420097
• Rekers J. and Schurr A., "Defining and parsing visual languages with Layered Graph Grammars," Journal of Visual Languages and Computing, vol. 8, no. 1, pp. 27-55, 1997. doi: 10.1006/jvlc.1996.0027
• Rozenberg G. and Welzl E., "Boundary NLC graph grammars - basic definitions, normal forms, and complexity," Information and Control, vol. 69, no. 1-3, pp. 136-167, 1986. doi: 10.1016/S0019-9958(86)80045-6
• Ullmann J. R., "An Algorithm for Subgraph Isomorphism," J. Assoc. for Computing Machinery, vol. 23, pp. 31-42, 1976. doi: 10.1145/321921.321925