106
个编辑
更改
跳到导航
跳到搜索
第51行：
第51行： + 第56行：
第57行： − + + + − + − 首先，FPF算法枚举并维护位于模式树根的子图的所有匹配项的信息。然后，它通过在目标图中添加匹配边缘支持的一条边缘，在模式树中一一建立前一节点的子节点，然后尝试将与匹配有关的所有先前信息扩展到新的子图中（子节点）。在下一步中，它确定当前模式的频率是否低于预定义的阈值。如果它较低并且保持向下闭合，则FPF可以放弃该路径，而不会在树的此部分进一步遍历；结果，避免了不必要的计算。继续此过程，直到没有剩余的遍历路径为止。 −
无编辑摘要
|-
|-
}
}
===FPF (Mavisto)算法===
===FPF (Mavisto)算法===
Schreiber and Schwöbbermeyer [12] proposed an algorithm named flexible pattern finder (FPF) for extracting frequent sub-graphs of an input network and implemented it in a system named Mavisto.[27] Their algorithm exploits the downward closure property which is applicable for frequency concepts F2 and F3. The downward closure property asserts that the frequency for sub-graphs decrease monotonically by increasing the size of sub-graphs; however, this property does not hold necessarily for frequency concept F1. FPF is based on a pattern tree (see figure) consisting of nodes that represents different graphs (or patterns), where the parent of each node is a sub-graph of its children nodes; in other words, the corresponding graph of each pattern tree's node is expanded by adding a new edge to the graph of its parent node.
Schreiber and Schwöbbermeyer [12] proposed an algorithm named flexible pattern finder (FPF) for extracting frequent sub-graphs of an input network and implemented it in a system named Mavisto.[27] Their algorithm exploits the downward closure property which is applicable for frequency concepts F2 and F3. The downward closure property asserts that the frequency for sub-graphs decrease monotonically by increasing the size of sub-graphs; however, this property does not hold necessarily for frequency concept F1. FPF is based on a pattern tree (see figure) consisting of nodes that represents different graphs (or patterns), where the parent of each node is a sub-graph of its children nodes; in other words, the corresponding graph of each pattern tree's node is expanded by adding a new edge to the graph of its parent node.
Schreiber和Schwöbbermeyer [12]提出了一种称为灵活模式查找器（FPF）的算法，用于提取输入网络的频繁子图，并将其在名为Mavisto的系统中加以实现。[27]他们的算法利用了向下闭包特性，该特性适用于频率概念<math>F_{2}</math>和<math>F_{3}</math>。向下闭包性质表明，子图的频率随着子图的大小而单调下降；但这一性质并不一定适用于频率概念 F1。FPF基于模式树（见图），由代表不同图形（或模式）的节点组成，其中每个节点的父级是其子节点的子图；换句话说，每个模式树节点的对应图通过向其父节点图添加新边来扩展。
Schreiber和Schwöbbermeyer [12]提出了一种称为灵活模式查找器（FPF）的算法，用于提取输入网络的频繁子图，并将其在名为Mavisto的系统中加以实现。[27]他们的算法利用了向下闭包特性，该特性适用于频率概念<math>F_{2}</math>和<math>F_{3}</math>。向下闭包性质表明，子图的频率随着子图的大小而单调下降；但这一性质并不一定适用于频率概念 F1。FPF算法基于模式树（见右图），由代表不同图形（或模式）的节点组成，其中每个节点的父节点是其子节点的子图；换句话说，每个模式树节点的对应图通过向其父节点图添加新边来扩展。
[[Image:The pattern tree in FPF algorithm.jpg|right|thumb|''Illustration of the pattern tree in FPF algorithm.''.]]
At first, the FPF algorithm enumerates and maintains the information of all matches of a sub-graph located at the root of the pattern tree. Then, one-by-one it builds child nodes of the previous node in the pattern tree by adding one edge supported by a matching edge in the target graph, and tries to expand all of the previous information about matches to the new sub-graph (child node). In next step, it decides whether the frequency of the current pattern is lower than a predefined threshold or not. If it is lower and if downward closure holds, FPF can abandon that path and not traverse further in this part of the tree; as a result, unnecessary computation is avoided. This procedure is continued until there is no remaining path to traverse.
At first, the FPF algorithm enumerates and maintains the information of all matches of a sub-graph located at the root of the pattern tree. Then, one-by-one it builds child nodes of the previous node in the pattern tree by adding one edge supported by a matching edge in the target graph, and tries to expand all of the previous information about matches to the new sub-graph (child node). In next step, it decides whether the frequency of the current pattern is lower than a predefined threshold or not. If it is lower and if downward closure holds, FPF can abandon that path and not traverse further in this part of the tree; as a result, unnecessary computation is avoided. This procedure is continued until there is no remaining path to traverse.
首先，FPF算法枚举并维护位于模式树根部的子图的所有匹配信息。然后，它通过在目标图中添加匹配边缘支持的一条边缘，在模式树中一一建立前一节点的子节点，然后通过在目标图中添加匹配边支持的一条边，逐个构建模式树中前一个节点的子节点，并尝试将以前关于匹配的所有信息拓展到新的子图(子节点)中。下一步，它判断当前模式的频率是否低于预定义的阈值。如果它低于阈值且保持向下闭包，则FPF算法会放弃该路径，而不会在树的此部分进一步遍历；这样就避免了不必要的计算。重复此过程，直到没有剩余可遍历的路径为止。
The advantage of the algorithm is that it does not consider infrequent sub-graphs and tries to finish the enumeration process as soon as possible; therefore, it only spends time for promising nodes in the pattern tree and discards all other nodes. As an added bonus, the pattern tree notion permits FPF to be implemented and executed in a parallel manner since it is possible to traverse each path of the pattern tree independently. However, FPF is most useful for frequency concepts F2 and F3, because downward closure is not applicable to F1. Nevertheless, the pattern tree is still practical for F1 if the algorithm runs in parallel. Another advantage of the algorithm is that the implementation of this algorithm has no limitation on motif size, which makes it more amenable to improvements. The pseudocode of FPF (Mavisto) is shown below:
The advantage of the algorithm is that it does not consider infrequent sub-graphs and tries to finish the enumeration process as soon as possible; therefore, it only spends time for promising nodes in the pattern tree and discards all other nodes. As an added bonus, the pattern tree notion permits FPF to be implemented and executed in a parallel manner since it is possible to traverse each path of the pattern tree independently. However, FPF is most useful for frequency concepts F2 and F3, because downward closure is not applicable to F1. Nevertheless, the pattern tree is still practical for F1 if the algorithm runs in parallel. Another advantage of the algorithm is that the implementation of this algorithm has no limitation on motif size, which makes it more amenable to improvements. The pseudocode of FPF (Mavisto) is shown below: