106
个编辑
更改
跳到导航
跳到搜索
第72行：
第72行： − + − + + − + − + − 2. Make a list L of all neighbor edges of Es. Omit from L all edges between members of Vs. <br>+ − 3. Pick a random edge e = {vk,vl} from L. Update Es = Es ⋃ {e}, Vs = Vs ⋃ {vk, vl}. <br>+ − 4. Repeat steps 2-3 until completing an n-node subgraph (until |Vs| = n). <br>+ − 5. Calculate the probability to sample the picked n-node subgraph. <br>+ + + + + + + + + + + + + + + + − + − + + − + − 1. 随机选择一条边<math> e_{1} = (v_{i}, v_{j}) </math>，更新 <math>E_{s} = \{e_{1}\}, V{s} = \{v_{i}, v_{j}\}</math><br>+ − 2. 列出<math>E{s}</math>的所有邻边列表<math> L </math>，从<math> L </math>中删除<math>V{s}</math>中所有元素组成的边。<br>+ − 3. 从<math> L </math>中随机选择一条边<math> e = \{v_{k},v_{l}\} </math>， 更新<math>E_{s} = E_{s} \cup \{e\} , V_{s} = V_{s} \cup \{v_{k}, v_{l}\}</math>。<br>+ − 4. 重复步骤2-3，直到完成包含n个节点的子图 (<math>\left | V_{s} \right | = n</math>)。<br>+ − 5. 计算对选取的n节点子图进行采样的概率。<br>+ + + + + + + + + + + + + + + +
无编辑摘要
{|class="wikitable"
{|class="wikitable"
|+ mfinder
|+ Mavisto
|-
|-
!rowspan="1"|Definitions: Esis the set of picked edges. Vs is the set of all nodes that are touched by the edges in E.
!rowspan="1"|Data: Graph G, target pattern size t, frequency concept F.<br>
Result: Set R of patterns of size t with maximum frequency.<br>
|-
|-
|rowspan="5"|Init Vs and Es to be empty sets.<br>
|rowspan="20"|R ← φ, fmax ← 0<br>
1. Pick a random edge e1 = (vi, vj). Update Es = {e1}, Vs = {vi, vj} <br>
P ←start pattern p1 of size 1<br>
Mp1 ←all matches of p1 in G<br>
While P ≠ φ do<br>
Pmax ←select all patterns from P with maximum size.<br>
P ← select pattern with maximum frequency from Pmax<br>
Ε = ExtensionLoop(G, p, Mp)<br>
Foreach pattern p ∈ E<br>
If F = F1 then f ← size(Mp)<br>
Else f ← Maximum Independent set(F, Mp)<br>
End<br>
If size(p) = t then<br>
If f = fmax then R ← R ⋃ {p}<br>
Else if f > fmax then R ← {p}; fmax ← f<br>
End<br>
Else<br>
If F = F1 or f ≥ fmax then P ← P ⋃ {p}<br>
End<br>
End<br>
End<br>
End<br>
|}
|}
{|class="wikitable"
{|class="wikitable"
|+ mfinder
|+ Mavisto
|-
|-
!rowspan="1"|定义：<math>E_{s}</math>是采集的边集合。<math>V_{s}</math>是<math>E</math>中所有边的顶点的集合。
!rowspan="1"|数据: 图 <math>G</math>, 目标模式规模 <math>t</math>, 频率概念 <math>F</math>。<br>
结果: 以最大频率设置大小为 <math>t</math>的模式 <math>R</math>.<br>
|-
|-
|rowspan="5"|初始化<math>V_{s}</math>和<math>E_{s}</math>为空集。<br>
|rowspan="20"| <math>R \leftarrow \Phi , f_{max}\leftarrow 0</math><br>
<math>P \leftarrow</math> 开始于大小为1的模式 <math>p_{1}</math><br>
<math>M_{p_{1}} \leftarrow </math> 图 <math>G</math> 中模式 <math>p_{1}</math> 的所有匹配<br>
当 <math>P \neq \Phi </math> 时，执行：<br>
<math>P_{max} \leftarrow</math> 从 <math>P</math> 中选择最大规模的所有模式。<br>
<math>P\leftarrow</math> 从 <math>P_{max}</math> 中选择最大频率的模式<br>
<math>E = ExtensionLoop(G, p, M_{p})</math><br>
对于 <math>p \in E </math> 的所有模式：<br>
如果 <math>F = F_{1}</math> ，那么 <math>f \leftarrow size(M_{p})</math><br>
其他<math>f \leftarrow</math> 最大独立集 <math>(F, M_{p})</math><br>
结束<br>
如果 <math>size(p) = t</math> ，那么<br>
如果 <math>f = f_{max}</math> ，那么 <math>R \leftarrow R \cup \{p\}</math><br>
其他 如果 <math>f > f_{max}</math> ，那么 <math>R \leftarrow \{p\}</math>； <math>f_{max} \leftarrow f</math><br>
结束<br>
其他<br>
如果 <math>F = F_{1} or f \geq f_{max}</math> ，那么 <math> P \leftarrow P \cup \{p\}</math><br>
结束<br>
结束<br>
结束<br>
结束<br>
|}
|}