377
个编辑
更改
→Definition
Let {{math|G {{=}} (V, E)}} and {{math|G′ {{=}} (V′, E′)}} be two graphs. Graph {{math|G′}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G′ ⊆ G}}) if {{math|V′ ⊆ V}} and {{math|E′ ⊆ E ∩ (V′ × V′)}}. If {{math|G′ ⊆ G}} and {{math|G′}} contains all of the edges {{math|⟨u, v⟩ ∈ E}} with {{math|u, v ∈ V′}}, then {{math|G′}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G′}} and {{math|G}} isomorphic (written as {{math|G′ ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V′ → V}} with {{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} for all {{math|u, v ∈ V′}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G′}}.<ref name="die1">{{cite journal |author=Diestel R |title=Graph Theory (Graduate Texts in Mathematics) |volume=173 |year=2005|publisher=New York: Springer-Verlag Heidelberg}}</ref>
Let {{math|G {{=}} (V, E)}} and {{math|G′ {{=}} (V′, E′)}} be two graphs. Graph {{math|G′}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G′ ⊆ G}}) if {{math|V′ ⊆ V}} and {{math|E′ ⊆ E ∩ (V′ × V′)}}. If {{math|G′ ⊆ G}} and {{math|G′}} contains all of the edges {{math|⟨u, v⟩ ∈ E}} with {{math|u, v ∈ V′}}, then {{math|G′}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G′}} and {{math|G}} isomorphic (written as {{math|G′ ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V′ → V}} with {{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} for all {{math|u, v ∈ V′}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G′}}.<ref name="die1">{{cite journal |author=Diestel R |title=Graph Theory (Graduate Texts in Mathematics) |volume=173 |year=2005|publisher=New York: Springer-Verlag Heidelberg}}</ref>
设{{math|G {{=}} (V, E)}} 和 {{math|G′ {{=}} (V′, E′)}} 是两个图。若{{math|V′ ⊆ V}}且满足{{math|E′ ⊆ E ∩ (V′ × V′)}}）（即图{{math|G′ ⊆ G}的所有边和点都属于图{{math|G}}）即{{math|G′}}则称图{{math|G′ ⊆ G}是图{{math|G}}的一个子图
设{{math|G {{=}} (V, E)}} 和 {{math|G′ {{=}} (V′, E′)}} 是两个图。若{{math|V′ ⊆ V}}且满足{{math|E′ ⊆ E ∩ (V′ × V′)}}）（即图{{math|G′ ⊆ G}的所有边和点都属于图{{math|G}}）则称图{{math|G′ ⊆ G}是图{{math|G}}的一个子图
若{{math|G′ ⊆ G}}，且对于顶点{{math|u}}、{{math|v}}及其连边，只要{{math|u}}和{{math|v}}存在于{{math|G&prime }}（即若{{math|U}}, {{math|V′ ⊆ V}}），那么{{math|G′ ⊆ G}}中就应该包含原图{{math|G}}中的所有{{math|u}}和{{math|V}}的对应连边（即{{math|⟨u, v⟩ ∈ E}}），则称此时图{{math|G&prime }}就是图{{math|G}}的导出子图。
如果存在一个双射（一对一）{{math|f:V′ → V}}，且对所有{{math|u, v ∈ V′}}都有{{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} ，则称{{math|G&prime }}是{{math|G}}的同构图（记作：{{math|G′ → G}}），映射f则称为{{math|G}}与{{math|G&prime }}之间的同构（isomorphism）。[2]
When {{math|G″ ⊂ G}} and there exists an isomorphism between the sub-graph {{math|G″}} and a graph {{math|G′}}, this mapping represents an ''appearance'' of {{math|G′}} in {{math|G}}. The number of appearances of graph {{math|G′}} in {{math|G}} is called the frequency {{math|F<sub>G</sub>}} of {{math|G′}} in {{math|G}}. A graph is called ''recurrent'' (or ''frequent'') in {{math|G}}, when its ''frequency'' {{math|F<sub>G</sub>(G′)}} is above a predefined threshold or cut-off value. We use terms ''pattern'' and ''frequent sub-graph'' in this review interchangeably. There is an [[Statistical ensemble (mathematical physics)|ensemble]] {{math|Ω(G)}} of random graphs corresponding to the [[Null model|null-model]] associated to {{math|G}}. We should choose {{math|N}} random graphs uniformly from {{math|Ω(G)}} and calculate the frequency for a particular frequent sub-graph {{math|G′}} in {{math|G}}. If the frequency of {{math|G′}} in {{math|G}} is higher than its arithmetic mean frequency in {{math|N}} random graphs {{math|R<sub>i</sub>}}, where {{math|1 ≤ i ≤ N}}, we call this recurrent pattern ''significant'' and hence treat {{math|G′}} as a ''network motif'' for {{math|G}}. For a small graph {{math|G′}}, the network {{math|G}} and a set of randomized networks {{math|R(G) ⊆ Ω(R)}}, where {{math|1=R(G) {{=}} N}}, the ''Z-Score'' that has been defined by the following formula:
When {{math|G″ ⊂ G}} and there exists an isomorphism between the sub-graph {{math|G″}} and a graph {{math|G′}}, this mapping represents an ''appearance'' of {{math|G′}} in {{math|G}}. The number of appearances of graph {{math|G′}} in {{math|G}} is called the frequency {{math|F<sub>G</sub>}} of {{math|G′}} in {{math|G}}. A graph is called ''recurrent'' (or ''frequent'') in {{math|G}}, when its ''frequency'' {{math|F<sub>G</sub>(G′)}} is above a predefined threshold or cut-off value. We use terms ''pattern'' and ''frequent sub-graph'' in this review interchangeably. There is an [[Statistical ensemble (mathematical physics)|ensemble]] {{math|Ω(G)}} of random graphs corresponding to the [[Null model|null-model]] associated to {{math|G}}. We should choose {{math|N}} random graphs uniformly from {{math|Ω(G)}} and calculate the frequency for a particular frequent sub-graph {{math|G′}} in {{math|G}}. If the frequency of {{math|G′}} in {{math|G}} is higher than its arithmetic mean frequency in {{math|N}} random graphs {{math|R<sub>i</sub>}}, where {{math|1 ≤ i ≤ N}}, we call this recurrent pattern ''significant'' and hence treat {{math|G′}} as a ''network motif'' for {{math|G}}. For a small graph {{math|G′}}, the network {{math|G}} and a set of randomized networks {{math|R(G) ⊆ Ω(R)}}, where {{math|1=R(G) {{=}} N}}, the ''Z-Score'' that has been defined by the following formula: