Home > Papers

 
 
A Novel Graph Isomorphism Algorithm Based on Feature Selection in Network Motif Discovery
HU Jialu 1,SUN Ling 2,YU Liang 3,GAO Lin 4 *
1.Freie Universitaet Berlin
2.Freie Universitaet Berlin, 14195
3.Computer Science Department, Xidian Univeristy, 710126
4.Computer Science Department, Xidian University, 710126
*Correspondence author
#Submitted by
Subject:
Funding: the Ph.D Programs Foundation of Ministry of Education of China （No.Grant No. 200807010013）, This work was supported by NSFC-Microsoft Research Asia Joint Research Fund（No.Grant No. 60933009）, NSFC（No.Grant No.60970065）
Opened online: 2 September 2011
Accepted by: none
Citation: HU Jialu,SUN Ling,YU Liang.A Novel Graph Isomorphism Algorithm Based on Feature Selection in Network Motif Discovery[OL]. [ 2 September 2011] http://en.paper.edu.cn/en_releasepaper/content/4441016
 
 
Motifs are small connected subnetworks that occur in significantly higher frequencies than in random networks. For finding motifs, we have to count the subnetwork frequencies, which conduct graph isomorphism. However, subgraph isomorphism remains a challenging problem. In this paper, we present a new heuristic algorithm based on feature selection to cluster huge amounts of graphs into isomorphic categories. Firstly, four rich-information features of graphs, MinB, πa, πp and SFeature, are constructed to reducing the searching space and complexity. Then , two feature combination approaches FCCG ( feature compression for clustering graphs ）and FVCG (feature vector for clustering graphs) are introduced to canonically label graphs using these features. Finally, we implement five kinds of feature combinations on a synthetically generated database to evaluate the performance of the algorithm. Experiment results show that our new algorithms can precisely and effectively solve the graph isomorphism problem for both the directed and undirected graphs. Furthermore, we test the algorithm for motif detection in Saccharomyces cerevisiae gene regulatory network. Network motifs which are theoretically and experimentally proved to be of great significance are successfully detected.
Keywords:Graph Isomorphism; Network Motif; Feture Selection
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 431
Bookmarked 0
Recommend 7
Comments Array
Submit your papers