377
个编辑
更改
无编辑摘要
All networks, including [[biological network]]s, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as [[complex network|graphs]], which include a wide variety of subgraphs. One important local property of networks are so-called '''network motifs''', which are defined as recurrent and [[statistically significant]] sub-graphs or patterns.
All networks, including [[biological network]]s, social networks, technological networks (e.g., computer networks and electrical circuits) and more, can be represented as [[complex network|graphs]], which include a wide variety of subgraphs. One important local property of networks are so-called '''network motifs''', which are defined as recurrent and [[statistically significant]] sub-graphs or patterns.
所有网络，包括生物网络(biological networks)、社会网络(social networks)、技术网络（例如计算机网络和电路）等，都可以用图的形式来表示，这些图中会包括各种各样的子图(subgraphs)。网络的一个重要的局部性质是所谓的网络基序，即重复且具有统计意义的子图或模式(patterns)。
Network motifs are sub-graphs that repeat themselves in a specific network or even among various networks. Each of these sub-graphs, defined by a particular pattern of interactions between vertices, may reflect a framework in which particular functions are achieved efficiently. Indeed, motifs are of notable importance largely because they may reflect functional properties. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks.<ref name="mas1">{{cite journal |vauthors=Masoudi-Nejad A, Schreiber F, Razaghi MK Z |title=Building Blocks of Biological Networks: A Review on Major Network Motif Discovery Algorithms |journal=IET Systems Biology |volume=6 |issue=5 |pages=164–74 |year=2012|doi=10.1049/iet-syb.2011.0011 |pmid=23101871 }}</ref> Although network motifs may provide a deep insight into the network's functional abilities, their detection is computationally challenging.
Network motifs are sub-graphs that repeat themselves in a specific network or even among various networks. Each of these sub-graphs, defined by a particular pattern of interactions between vertices, may reflect a framework in which particular functions are achieved efficiently. Indeed, motifs are of notable importance largely because they may reflect functional properties. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks.<ref name="mas1">{{cite journal |vauthors=Masoudi-Nejad A, Schreiber F, Razaghi MK Z |title=Building Blocks of Biological Networks: A Review on Major Network Motif Discovery Algorithms |journal=IET Systems Biology |volume=6 |issue=5 |pages=164–74 |year=2012|doi=10.1049/iet-syb.2011.0011 |pmid=23101871 }}</ref> Although network motifs may provide a deep insight into the network's functional abilities, their detection is computationally challenging.
网络模体(Network motifs)是指在特定网络或各种网络中重复出现的相同的子图。这些子图由顶点之间特定的交互模式定义，一个子图便可以反映一个框架，这个框架可以有效地实现某个特定的功能。事实上，之所以说模体是一个重要的特性，正是因为它们可能反映出对应网络功能的这一性质。近年来这一概念作为揭示复杂网络结构设计原理的一个有用概念而受到了广泛的关注。<ref name="mas1">{{cite journal |vauthors=Masoudi-Nejad A, Schreiber F, Razaghi MK Z |title=Building Blocks of Biological Networks: A Review on Major Network Motif Discovery Algorithms |journal=IET Systems Biology |volume=6 |issue=5 |pages=164–74 |year=2012|doi=10.1049/iet-syb.2011.0011 |pmid=23101871 }}</ref> 但是，虽然通过研究网络模体可以深入了解网络的功能，但是对于模体的检测在计算上是具有挑战性的。
==Definition==
==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}}的一个子图
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: