Limits...
Identifying emerging motif in growing networks.

Shi H, Shi L - PLoS ONE (2014)

Bottom Line: Upper and lower boundaries of the range were obtained in analytical form according to a chosen risk level.Then, the statistical metric Z-score was extended to a new one, Z(continuous), which effectively reveals the statistical significance of subgraph in a continuous period of time.In this paper, a novel research framework of motif identification was proposed, defining critical boundaries for the evolutionary process of networks and a significance metric of time scale.

View Article: PubMed Central - PubMed

Affiliation: State Key Joint-Laboratory of Environmental Simulation and Pollution Control, School of Environment, Tsinghua University, Beijing, China.

ABSTRACT
As function units, network motifs have been detected to reveal evolutionary mechanisms of complex systems, such as biological networks, food webs, engineering networks and social networks. However, emergence of motifs in growing networks may be problematic due to large fluctuation of subgraph frequency in the initial stage. This paper contributes to present a method which can identify the emergence of motif in growing networks. Based on the Erdös-Rényi(E-R) random model, the variation rate of expected frequency of subgraph at adjacent time points was used to define the suitable detection range for motif identification. Upper and lower boundaries of the range were obtained in analytical form according to a chosen risk level. Then, the statistical metric Z-score was extended to a new one, Z(continuous), which effectively reveals the statistical significance of subgraph in a continuous period of time. In this paper, a novel research framework of motif identification was proposed, defining critical boundaries for the evolutionary process of networks and a significance metric of time scale. Finally, an industrial ecosystem at Kalundborg was adopted as a case study to illustrate the effectiveness and convenience of the proposed methodology.

Show MeSH

Related in: MedlinePlus

Variation of  in the evolutionary process of the industrial network at Kalundborg.(A) The relationship between the switching times n and  at E = 14, 16, 18, 20, 22, 24. (B) The relationship between the rewiring ratio r (n/E) and  at E = 14, 16, 18, 20, 22, 24, 30, 35. The exponential function  is used to approximate the curve of randomized process of the network  at each time point. And the curves at E = 14, 16 are marked in gray.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4061033&req=5

pone-0099634-g007: Variation of in the evolutionary process of the industrial network at Kalundborg.(A) The relationship between the switching times n and at E = 14, 16, 18, 20, 22, 24. (B) The relationship between the rewiring ratio r (n/E) and at E = 14, 16, 18, 20, 22, 24, 30, 35. The exponential function is used to approximate the curve of randomized process of the network at each time point. And the curves at E = 14, 16 are marked in gray.

Mentions: With the increase of n, at the time points (E = 14, 16, 18, 20, 22, 24) are compared and shown in Figure 7(A), (B). It is concluded that the curvature of each curve decreases gradually and converges to a constant. This constant represents the maximum value of . The most distinct difference among these curves is how many switching times it costs to reach to the extreme value . It seems a little hard to distinguish when the network is adequately randomized. In our research the exponential function is adopted to approximate these curves. Stipulate that if , the network is thought to be adequately randomized. Then the critical switching times and rewiring ratio (dividing n by E) of each curve can be calculated and marked in Figure 7(A), (B). When E = 14, the network is adequately randomized just by executing the switching times twice, but later, increases to over twenty. From the rewiring ratio point of view, when E = 14, approaches to its maximum value rapidly only by rewiring 13% of the edges, and for E = 16, a little better, 42%. For the time interval , exceeds 100% rapidly. These changes indicate that the result of motif identification before E = 18 is quite easily influenced by tiny disturbances and it is not trustworthy. However, with the increase of and , the reliability of results improve significantly. Therefore, it is concluded that the threshold of the detection range proposed in the method of motif identification is reasonable and necessary, especially for those small scale networks, such as food webs, social networks and industrial networks.


Identifying emerging motif in growing networks.

Shi H, Shi L - PLoS ONE (2014)

Variation of  in the evolutionary process of the industrial network at Kalundborg.(A) The relationship between the switching times n and  at E = 14, 16, 18, 20, 22, 24. (B) The relationship between the rewiring ratio r (n/E) and  at E = 14, 16, 18, 20, 22, 24, 30, 35. The exponential function  is used to approximate the curve of randomized process of the network  at each time point. And the curves at E = 14, 16 are marked in gray.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4061033&req=5

pone-0099634-g007: Variation of in the evolutionary process of the industrial network at Kalundborg.(A) The relationship between the switching times n and at E = 14, 16, 18, 20, 22, 24. (B) The relationship between the rewiring ratio r (n/E) and at E = 14, 16, 18, 20, 22, 24, 30, 35. The exponential function is used to approximate the curve of randomized process of the network at each time point. And the curves at E = 14, 16 are marked in gray.
Mentions: With the increase of n, at the time points (E = 14, 16, 18, 20, 22, 24) are compared and shown in Figure 7(A), (B). It is concluded that the curvature of each curve decreases gradually and converges to a constant. This constant represents the maximum value of . The most distinct difference among these curves is how many switching times it costs to reach to the extreme value . It seems a little hard to distinguish when the network is adequately randomized. In our research the exponential function is adopted to approximate these curves. Stipulate that if , the network is thought to be adequately randomized. Then the critical switching times and rewiring ratio (dividing n by E) of each curve can be calculated and marked in Figure 7(A), (B). When E = 14, the network is adequately randomized just by executing the switching times twice, but later, increases to over twenty. From the rewiring ratio point of view, when E = 14, approaches to its maximum value rapidly only by rewiring 13% of the edges, and for E = 16, a little better, 42%. For the time interval , exceeds 100% rapidly. These changes indicate that the result of motif identification before E = 18 is quite easily influenced by tiny disturbances and it is not trustworthy. However, with the increase of and , the reliability of results improve significantly. Therefore, it is concluded that the threshold of the detection range proposed in the method of motif identification is reasonable and necessary, especially for those small scale networks, such as food webs, social networks and industrial networks.

Bottom Line: Upper and lower boundaries of the range were obtained in analytical form according to a chosen risk level.Then, the statistical metric Z-score was extended to a new one, Z(continuous), which effectively reveals the statistical significance of subgraph in a continuous period of time.In this paper, a novel research framework of motif identification was proposed, defining critical boundaries for the evolutionary process of networks and a significance metric of time scale.

View Article: PubMed Central - PubMed

Affiliation: State Key Joint-Laboratory of Environmental Simulation and Pollution Control, School of Environment, Tsinghua University, Beijing, China.

ABSTRACT
As function units, network motifs have been detected to reveal evolutionary mechanisms of complex systems, such as biological networks, food webs, engineering networks and social networks. However, emergence of motifs in growing networks may be problematic due to large fluctuation of subgraph frequency in the initial stage. This paper contributes to present a method which can identify the emergence of motif in growing networks. Based on the Erdös-Rényi(E-R) random model, the variation rate of expected frequency of subgraph at adjacent time points was used to define the suitable detection range for motif identification. Upper and lower boundaries of the range were obtained in analytical form according to a chosen risk level. Then, the statistical metric Z-score was extended to a new one, Z(continuous), which effectively reveals the statistical significance of subgraph in a continuous period of time. In this paper, a novel research framework of motif identification was proposed, defining critical boundaries for the evolutionary process of networks and a significance metric of time scale. Finally, an industrial ecosystem at Kalundborg was adopted as a case study to illustrate the effectiveness and convenience of the proposed methodology.

Show MeSH
Related in: MedlinePlus