论文标题
定向图哈希
Directed Graph Hashing
论文作者
论文摘要
本文介绍了一些用于哈希定向图的算法。给出的算法能够放哈整个图，并将哈希值分配给给定图中的特定节点。通过计算顶点轨道和图自动形态组以及对称相同的节点相同的哈希，可以精确地进行节点对称性的概念。我们还提出了一种新颖的默克尔风格的哈希算法，该算法旨在实现递归原则，即节点的哈希只能取决于其邻居的哈希。即使在存在周期的情况下，这种算法也起作用，这是不可能的。结构上的哈希树已经在区块链，源代码版本控制和Web应用程序中广泛使用。尽管有树的流行，但在文献中仍未研究散列图。我们的算法为有向图和更复杂的数据结构提供了新的可能性，可以简化为有向图，例如HyperGraphs。
This paper presents several algorithms for hashing directed graphs. The algorithms given are capable of hashing entire graphs as well as assigning hash values to specific nodes in a given graph. The notion of node symmetry is made precise via computation of vertex orbits and the graph automorphism group, and nodes that are symmetrically identical are assigned equal hashes. We also present a novel Merkle-style hashing algorithm that seeks to fulfill the recursive principle that a hash of a node should depend only on the hash of its neighbors. This algorithm works even in the presence of cycles, which would not be possible with a naive approach. Structurally hashing trees has seen widespread use in blockchain, source code version control, and web applications. Despite the popularity of tree hashing, directed graph hashing remains unstudied in the literature. Our algorithms open new possibilities to hashing both directed graphs and more complex data structures that can be reduced to directed graphs such as hypergraphs.
