Limits...
Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

Bottom Line: The considerable computational and spacial complexity also presents a significant challenge.According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs.Experimental results show that this algorithm has higher speed and better stability than its alternatives.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, (Dalian university), Ministry of Education, Dalian, 116622 China.

ABSTRACT
A network motif is a recurring subnetwork within a network, and it takes on certain functions in practical biological macromolecule applications. Previous algorithms have focused on the computational efficiency of network motif detection, but some problems in storage space and searching time manifested during earlier studies. The considerable computational and spacial complexity also presents a significant challenge. In this paper, we provide a new approach for motif mining based on compressing the searching space. According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs. We obtain a new network with smaller size after removing parity nodes and the "repeated edges" connected with the parity nodes. Random graph structure and sub-graph searching are based on the Back Tracking Method; all sub-graphs can be searched for by adding edges progressively. Experimental results show that this algorithm has higher speed and better stability than its alternatives.

No MeSH data available.


An illustration of isomorphic graphs.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4269098&req=5

Fig2: An illustration of isomorphic graphs.

Mentions: Figure 1 is an example of parity nodes and Figure 2 shows the isomorphism visually.Figure 1


Motif mining based on network space compression.

Zhang Q, Xu Y - BioData Min (2014)

An illustration of isomorphic graphs.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4269098&req=5

Fig2: An illustration of isomorphic graphs.
Mentions: Figure 1 is an example of parity nodes and Figure 2 shows the isomorphism visually.Figure 1

Bottom Line: The considerable computational and spacial complexity also presents a significant challenge.According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs.Experimental results show that this algorithm has higher speed and better stability than its alternatives.

View Article: PubMed Central - PubMed

Affiliation: Key Laboratory of Advanced Design and Intelligent Computing, (Dalian university), Ministry of Education, Dalian, 116622 China.

ABSTRACT
A network motif is a recurring subnetwork within a network, and it takes on certain functions in practical biological macromolecule applications. Previous algorithms have focused on the computational efficiency of network motif detection, but some problems in storage space and searching time manifested during earlier studies. The considerable computational and spacial complexity also presents a significant challenge. In this paper, we provide a new approach for motif mining based on compressing the searching space. According to the characteristic of the parity nodes, we cut down the searching space and storage space in real graphs and random graphs, thereby reducing the computational cost of verifying the isomorphism of sub-graphs. We obtain a new network with smaller size after removing parity nodes and the "repeated edges" connected with the parity nodes. Random graph structure and sub-graph searching are based on the Back Tracking Method; all sub-graphs can be searched for by adding edges progressively. Experimental results show that this algorithm has higher speed and better stability than its alternatives.

No MeSH data available.