TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.4, April 201 4, pp. 3015 ~ 3 0 2 0   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i4.4774          3015     Re cei v ed Se ptem ber 10, 2013; Revi se d No vem ber  20, 2013; Accepted Decem ber 3, 201 3   Uncertain Attribute Graph Sub-Graph Isomorphism and  its Determination Algorithm      Yanjun Zhao * , Chun y i ng  Zhang   Coll eg e of Scie nce, Heb e i Unt i ed U n ivers i t y   46  Xin h u a  Roa d ,  T angsha n 0 630 09, He bei,  Chin a T e l: 031 5-25 924 80    *Corres p o ndi n g  author, e-ma i l : teacher_ j sj@ 126.com       A b st r a ct   T he exp e ctativ e sub- gra ph  is omor p h is m of  uncerta in  attrib ute gra p h  is b a sed  on t he  a nalysis  of   compl e x n e tw ork structure a n d  the  char acte ristic of  u n cert ain attribute   gr aph.  T h e ex pe ctative su b-gra p h   i s om o r ph i s m   o f  u n c e r ta i n  a ttrib u t e   g r a p h  i s  on l y  on e  th re sho l d  va lu e   a s  con s tra i n t  co n d i t io n s . Th e   me thod  is si mp le, b u t t he c o mputati o n is  larg e  a m o unt. T herefor e, this p a p e r br in gs in  the  defi n i t ion  of   sub- grap h is o m orp h is m of  unc ertain  attr ibute  gr aph,  an d ex pla i ns th e co nce p t.  T hen, this  p aper  des ig ns a n d   comes true th e alg o rith m of  sub-gr aph is o m or phis m . F i n a lly, throu gh t he exp e ri me nt s proves that    sub- grap h  iso m or phic  is  b e tter than  ex pec tative su b-gr ap h, an d  it a naly z e s  the  var i ati on  in t h e   different thresh old cas e s. T he research of   sub-gr aph is o m orph ism a l g o ri t h m l a id the fo u ndati on for   uncerta in attrib ute grap h sub- grap h qu ery an d commun i ty minin g .      Ke y w ords :  ex pectative su b-g r aph is o m orp h i s m,   sub-gr aph  isomorp h is m, uncerta in attrib ute grap h      Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  As a gen eri c  data structu r e, graph  ca n modelin g and  expre ss the  real worl d all kind s of   compl e x data  entity and th e relatio n ship  betwe en the  entities.  The whol e  social relation ship can  be ab stra cted  as a g r ap h i n  the field of so cial  relatio n  netwo rk [1-3]. Attribute graph [4 -5] is t he  grap h struct ure  con s ide r i ng the verti c e s  and e d ges attrib ute s  and  relati onship s  bet ween   attributes i n  the traditio nal  map ba se d on. It can be  better de scri bed vari ou s  node s an d th e  relation shi p  b e twee n attrib utes in the  so cial net work,  and ea sie r  to  analyze the  effects of the s e   prop ertie s . Howeve r, vertice s  and verti c e s  relatio n s  and their attri butes a r e p r o bability in a social   netwo rk  o r   ot her co mplex netwo rks. Un certai n  attr i b ute graph  is  pre s ente d   co nsid erin g to t h is  factor, an d it furthe r de scrib e s  the soci al netwo rk u n ce rtainty.  Sub-g r ap h i s omorphi sm i s  the  cl assifi cation  of  sub - graph  to n e twork  with t h e same  cha r a c teri stics, and  re se a r ch  the  sub - grap h  i s omo r phism  of dat a graph i s  a  more  profou nd  study on th e so cial net works.  No w, about the sub - g r ap h isom orphi sm rese arch work is  followin g . Do ng Ang uo [6]  given alg o rith ms fo r sub-graph i s om orp h i sm in  graph  pattern mi nin g .  The algo rithm s  are b a sed o n  algeb ra the o ry by  makin g  use of de gree se que nce  of a vertex and  eigenvalu e  of adjace n cy m a trix. Xie Chunxin [7 ] given OES: sub-g r aph iso m orph ism verification  algorith m . Which  find  a  sub-g r a ph i s o m orp h ism  g r aph  by  sea r ching  edg e by  edg e, a nd it  ca n   raise the verification effi cien cy by adjusti n g  the edge o r de r.L i u Bo [8] given desi gn  and  impleme n tation of su b-g r aph isomo r p h ism d e tectio n algo rithm b a se d on relat i onal mod e l. He  prop oses a   new sub-gra ph i s omo r p h i s m  algo rithm   nam ed Rel a tional Gra p h   Decompo s i t io n   Index (RG D I), and it ha s h i gher  dete c tio n  effici en cy. Fred  DePie r o  [9] given an  algorith m  u s i ng  lengthe r p a th s to  app roxim a te subg rap h  iso m or phi sm . The s e  su b-grap h i s om orphism  alg o rit h m  desi gn a r e ba sed o n  tra d itional g r ap h or uncertain  graph. But in the real  com p le x networks, it is  often use d  to  descri be by uncertain attri bute gr aph [1 0]. Howeve r, how to de sig n  the algo rith m  of unce r tain  attribute grap h for un certa i n attri bute sub-g r a ph iso m orp h ism, it is an imp o rta n t  issues.  Attributes fig u re  is the  ex pan sion  of traditional  gra p h ， an d it i s   con s id ere d  t he ve rtex  and edg e attribute s  and t he relatio n shi p  of attr ibute between the  structu r e of the grap h. And  without  con s i derin g the  a ttribute, attrib ute gr aph  d egen erate  int o  traditio nal  figure. So th e   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3015 – 3 020   3016 traditional fig u re is a  spe c ial case of tradition g r ap h. The re se arch on the  attribute gra ph  st ru ct ur e,   it s  v a riou s cha r a c t e ri st ic s and   ope rat i on  i s   the theo ry  co mpleme nt an d inn o vation  of  traditional g r aph. On un certain g r ap h sub - g r ap h isomorphi sm h a s some research. With t he  uncertain  att r ibute  graph  is put fo rward,  a nd  on u n certain  attribute  g r aph  su b-g r a ph  isomo r p h ism  proble m  is urgent. The  unce r tainty   in the data is everywh e re, so it is the  particula rly importa nt that research u n c ertai n  a ttrib ute gra ph. T h is pa per  prese n ts two  kinds  definition s  of  sub - g r ap h i s omo r p h ism   on un ce rtain t y attribute  grap h d a ta. In probabili ty,  uncertainty a ttribute graph  expectatio n s sub - g r ap h isomorphi sm is uncertain  graph  sub - g r ap h   isomo r p h ism  definition dire ct extension.  The pro babili stic si gnifica n c e of expecta tions sub-gra ph  isomo r p h ism  of unce r tain  attribute grap h is very  intui t ive, but it is  huge  comp utational cost a nd  matche s re su lts descri be complex. So, this pap er  put s forward u n certainty attribute   sub-gra p h   isomo r p h ism  definition and  judgment alg o rithm. Un ce rtain attribute grap h isom orphism i s  usin g  two thre shol d  values to re place un certa i nty a ttribute grap h expe ctativ e sub-gra ph isom orphi sm  the singl e limit thresh old value.   This pa pe r structure mainly  divided into five parts follo wing.       2. The Unc e r t ain Attribu t e Graph   DEFINITIO N   2.1. (Uncertai n  attri bute  g r aph) un ce rtai n attribute  g r aph  and  un certain  attribute graph  are   cal l ed  u n cert ain  attri but e grap h. It is denoted  as (( ( , ), ( , )), ) P GA V V A L V E EA L E P : (( , ) , ( , ) ) VV A L V E E A L E   is an attribute   graph ;  P  is the  prob ability function of ed ge, ve rtex and their attri bute. ( P incl ud es  :[ 0 , 1 ] E PE , :[ 0 , 1 ] V PV , :[ 0 , 1 ] EA PE A  and  :[ 0 , 1 ] VA PV A ).       3. Expecta t iv e Sub-gra ph Isomorphis m  of Unce rta i n Attribu t e  Graph   Becau s e  of t he u n ce rtain   attribute g r a p h  is  di vided  i n to two  aspe cts to  di scuss, we  still  discu ss the u n ce rtain attrib ute grap h exp e ctativ e su b-grap h iso m orphism follo wi ng two a s pe cts.    3.1. Expecta t iv e the Sub-graph Isomo r phism of Uncertain Attr ibute Gra ph    First, we di scuss the un certain attribute grap h :  NATURE 1.  Acco rdi ng to  wheth e r  P the  value is 1,  the un ce rtain  attribute g r a ph    divided into:     '' { , 0( ) 1 0( ) 1 ( 0 ( ) 1 0( ) 1 ) , , } UC ii i ii i GA GA G A GA P e o r P v o r P e and P v e E v V      and   } , , 1 ) ( , 1 ) ( , { " " V v E e v P e P GA GA GA GA i i i i C     C GA is the certai n  attribute gra ph set of  GA . UC GA  is the certain a ttribute grap h  set o f GA .Two set to meet  UC C GA GA  and  GA GA GA UC C .  )) , ( ), , ( ( 1 1 LE EA E LV VA V GA C is a  po ssible  wo rld  graph  the u n certai n attribute  g r aph  ) , )), , ( ), , ( (( V E P P LE EA E LV VA V GA ,and  ) , ( ) , ( LV VA V LV VA V , ) , ( ) , ( 1 LE EA E LE EA E .  GA  contai ns C GA ,a nd  s i gn C GA GA .So the probability  of “  GA  cont ains C GA ”  comp utationa l formula is:     )) ( 1 )( ) ( 1 ( ) ( ) ( ) ( i GA GA i i i GA C v P e P v P e P GA GA P C UC C                                        (1)    The probability of “ GA  sub-g r a ph isom orphi c to C GA ” is the fol l owin g formul a:  12 12 11 2 2 1 2 () () ( ) ( , ) GA GA PG A G A P GA G A P G A G A G A G A                                                                (2)  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Un certai n Attribute Gra ph  Sub-G r ap h Isom or phi sm  and its Dete rm ination… (Y a n jun Zha o )  3017 Functio n   ) , ( 2 1 GA GA  va lues in  {0,1} . If  1 GA  and  2 GA  sub - gra ph i s omo r p h i s m,  ) , ( 2 1 GA GA  value is 1,  or 0. Appare n tly,  ) ( 2 1 GA GA P  is the  probability expectation of  ) , ( 2 1 GA GA . Acco rdin g t o  the exp e ct ative value  we  ca n b e  defi ned fo r the  e x pectation  su b - grap h iso m orphism of un certain attrib ute grap h .  DEFINITIO N 3.1. Known  uncer tainty a ttribute g r ap h  1 GA  and 2 GA , and  expe ctative  threshold val u e ] 1 , 0 ( , if and only if  ) ( 2 1 GA GA P ,  1 GA  is sub-g r ap h isom orphi c to 2 GA . Sign 2 1 GA GA .    3.2 The exp e c ta tiv e  sub-graph isomo r phic of unc ertain a ttribu t e grap h   Similarly, we  can  define  the expe ctative su b-gra ph i s omo r p h ism   of uncertai n   attribute  grap h  .  NATURE 2.  Acco rdi ng to  the a val u e  wh ether P  is  1, the un ce rt ain attrib ute  grap h  divides into mutually disjoint  subsets of  '' { , 0( ) 1 0( ) 1 (0 ( ) 1 0 ( ) 1 ) , , } UC ii ii i i GA GA GA GA P e a o r P v a or P e a and P v a e a E A v a V A        and   } , , 1 ) ( , 1 ) ( , { " " VA va EA ea va P ea P GA GA GA GA i i i i C     . Where  C GA   is th e  certain   attribute grap h of   GA , and UC GA   is the uncertain  attribute gra ph of   GA ,and Two set to meet    UC C GA GA and     GA GA GA UC C .  )) , ( ), , ( ( 1 1 LE EA E LV VA V GA C  is a po ssible  worl d graph  o f  unce r tain att r ibute g r ap h  ,and ) , ( 1 LV VA V LV VA V ） ， （ ,  ) , ( ) , ( 1 LE EA E LE EA E .  GA  contai ns C GA  , and si gn s  C GA GA   .So the probability of “  GA  contains C GA  ” is the fo llowing fo rmul a:   () () () ( 1 () ) ( 1 ( ) ) UC CC C ii i i G A GA GA PG A G A P e a P va P e a P va                                                                       (3)  The probability of “  GA  sub-g r a ph isom orphi c to C GA  ” is the fol l owin g formul a:  ) , ( ) ( ) ( ) ( 2 1 2 2 1 1 2 1 2 1 GA GA GA GA P GA GA P GA GA P GA GA     .                              (4)  Functio n   ) , ( 2 1 GA GA  va lues in {0,1} . If  1 GA  and  2 GA  sub-graph isomo r p h ism,   ) , ( 2 1 GA GA  value is  1, o r  0. Appa rent ly,  ) ( 2 1   GA GA P  is the  probability exp e ctation  of  ) , ( 2 1 GA GA . Acco rdin g t o  the exp e ct ative value  we  ca n b e  defi ned fo r the  e x pectation  su b - grap h iso m orphism of un certain attrib ute grap h .  DEFINITIO N  3.2. Known u n ce rtainty attribute g r ap h  1  GA  and 2  GA , and expectative   threshold val u e ] 1 , 0 ( . If and only if    ) ( 2 1 GA GA P , 1  GA  is su b-g r aph isomo r ph ic to 2  GA . Sign 2 1   GA GA .    3.3. The Expecta t iv e Sub - grap h Isomorphic of Un certain Attri bute Gr aph   DEFINITIO N   3.3. (the exp e ctat ive sub-grap h isomo r phism  of  un certain attri but e gra p h )   1 P GA , 1 P GA and expe ct ation thre shold ) 1 , 0 ( are  kn own  qua ntity. If and only if    ) ( ) ( 2 1 2 1 GA GA P GA GA P , 1 P GA  is  su b - graph  iso m orp h ic to 2 P GA . Sign   2 1 P P GA GA .  The alg o rith m of expectat i ve sub - graph  isomo r phi sm  judging i s  co stly. Expectative sub - graph  i s om orphi sm still exist  the problem of  m a tching resul t s describe  difficulty in t h e   appli c ation. T hese pro b lem s  limit the applic atio n of expectative sub - graph i s omo r phi sm.         Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3015 – 3 020   3018 4. The  - Sub-g r aph Isomor phism of Un certain Attri bute   4.1. The  -  Sub-grap h Isomorphism of  Unce rtain Attribute  Grap h    DEFINITIO N  4.1. The u n ce rtain attri but es  set of  uncertain  a ttribute grap h  GA   is.Definition  ] 1 , 0 ( 2 UC GA ： is  er r o r  fu nc tio n .  F o r th e  an y s u b- gr a p h  ' GA  of  UC GA , error f u nction   value is the followin g :     0 )) ( 1 ))( ( 1 ( 1 ) ( ' ' GA GA i i v P e P GA ' ' GA GA                                                                  (5)    DEFINITIO N   4.2. The  un certain  attribut es set   of  u n c ertai n  attrib ute  g r ap h  UC GA  is  kno w .    GA  is any sub-graph of   GA . Definition  ] 1 , 0 ( 2 : I GA  is stre ngth fun c tion. For the  any  s u b- gr a p h    GA  of  GA , strength fun c tion is the fol l owin g:       GA GA GA i i e P v p GA ) ( ) ( ) (                                                                                                  (6)    DEFINITIO N   4.3. Un ce rtain attribut e  g r ap h 1 GA and 2 GA are  kno w n  qua ntity.  Hypothe si s t he u n certai n  attribute  of 1 GA is UC GA , if the p r e s en ce   UC GA GA '  and   mappin g   function f , while s a tis f ying the following:  (1)  ' 1 max ) ( GA GA I  sub - grap h isomo r p h ic  to ) ( 2 max GA I and  f is map p ing fun c tion;   (2)  max ' ) ( GA , Consta nt  max  called erro r thre shol d valu e,  ] 1 , 0 [ max ;  (3)  min 1 1 )) ( ) ( ( V f E f , Consta nt  min called  stren g t h threshold value,  ] 1 , 0 [   So unce r tain  attribute graph  1 GA -   sub-g r aph isomo r p h ic to un cert ain attribute   grap h  2 GA . Sign  2 , 1 GA GA .  THEO RERN 1. If the uncertain attribut e grap h 1 GA  is isomorphi sm to the unce r ta in  attribute gra p h   2 GA  in limiting  condition max and   min , then  ) , ( ) ( min max 2 1 GA GA P ,and  min max min max ) 1 ( ) , ( .  If the unce r tain attribute  grap h    1 GA  is  -  sub-g r a ph iso m orp h ism to  uncertai n   attribute grap h  2 GA , then the prob ability is  ) , ( ) ( min max 2 1 GA GA P  that the uncertai n   attribute g r ap h    1 GA  is  -  sub - gra ph isomo r phi sm to un ce rt ain attribute  grap h  2 GA  in the  real  wo rld. A s   sho w ing  in  definition  3.1, ex pectativ e   su b-gra ph isomo r p h ism   use s  a sing le  con s tant a s  t he limit thre shold valu e, a nd  -  sub-graph  isomo r p h ism  use s  two co nstant s  max and  min as the li mit thre shol d  value to  re place  . Sub-graph i s om orphi sm  has  probability  signifi can c e.  It can be expre s sed a s  followin g . If the un certai n  attribute gra p h 1 GA  is sub- grap h i s omo r phic to  a the   uncertain  attri bute g r ap h 2 GA and  ) , ( min max  is not le ss than the  desi r ed  threshold  , then, u n ce rtain  attrib ute graph   1 GA   is expectative sub-g r a ph  i s o m orp h ic  to unce r tain a ttribute gra p h   2 GA .    4.2. The  -  S ub-graph Isomo r phism of Uncertain Attr ibute Gra ph    DEFINITIO N   4.4. The un certain attri but es  set of un certai n attrib ute gra ph    GA  is  } 1 0 , 1 0 , {   EA VA UC P P GA GA GA GA .Definite  ] 1 , 0 ( 2  UC GA ： is e r ror fu nction.  For the  any sub - g r ap h   GA  of  UC GA  , error func tion valu e is  the following:     0 )) ( 1 ))( ( 1 ( 1 ) ( GA GA i i va P ea P GA （   GA GA                                              (7)  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Un certai n Attribute Gra ph  Sub-G r ap h Isom or phi sm  and its Dete rm ination… (Y a n jun Zha o )  3019 DEFINITIO N  4.5. The  un certai n attrib ut es  set of u n ce rtain  attribute g r ap h    GA  is  kno w .    GA  is an y sub - graph  of   GA . Definition  ] 1 , 0 ( 2 :  GA   is  s t rength func tion.  For the  any sub - g r ap h   GA  of  GA , s t rength func tion is  the following:        GA GA GA i i UC ea P va p GA ) ( ) ( ) (                                                                                    (8)    DEFINITIO N  4.6. Unce rtain attribut e grap h 1  GA and 2  GA are kno w n  quantity.  Hypothe si s t he u n certain  attribute  of 1  GA is UC GA  , if th e  pr es en c e   UC GA GA   '  and  ma pping   function f , while s a tis f ying the following:  (1)  ' 1 max ) (   GA GA I  sub - grap h isomo r p h ic  to ) ( 2 max  GA I and  f is map p ing fun c tion;   (2)  max ' ) (  GA , Consta nt  max  called erro r thre shol d valu e,  ] 1 , 0 [ max ;  (3)  min 1 1 )) ( ) ( ( VA f EA f , Consta nt  min called  stren g th threshold value,  ] 1 , 0 [   So un certai n  attribute g r aph  1  GA -  sub - g r aph i s om orp h ic to  un cert ain attrib ute  grap h  2  GA . Sign  2 , 1   GA GA .    4.3. The Semantics o f   -  Sub-gra ph Iso m orphism of Uncer tain Attribu t e Gr ap h  DEFINITIO N  4.7. Unce rtain attribute  graph  1 P GA  and  2 P GA are known quantity.  Hypothe si s t he u n certain  attribute  of 1 P GA is UC P GA 1 , if the presence  UC P P GA GA '  and   mappin g   function f , while s a tis f ying the following:  (1)  ' 1 max ) ( P P GA GA I  sub - grap h isomo r p h ic  to ) ( 2 max P GA I and  f is map p ing fun c tion;   (2)  max ' ' ) ( ) (  GA GA , Consta nt  max  called erro r thre shol d valu e,  ] 1 , 0 [ max ;  (3)   min 1 1 )) ( ) ( ) ( ) ( ( V f E f VA f EA f , Cons tant  min calle d  stren g th thre sh old  value,   ] 1 , 0 [   So un ce rtain  attribute  graph  1 P GA -   sub-graph i s om orp h ic to  un ce rtain attrib ute   grap h  2 P GA . Sign 2 , 1 P P GA GA .      5. Experimental An aly s is  5.1. The Experimental Da ta  and the Parameter Sett ing  Un certai n attribute gra ph d a ta inclu d e s  t he que ry gra ph and u n certain attribute grap h.  The expe rim ent uses  4 g r oup s q u e r y grap h  GA5,  GA8, GA11  and GA1 4 , a nd ea ch  gra ph  numbe r of vertice s  is n . the  sub - g r ap h iso m orp h ism of  uncertain attri bute gra ph d a ta use d   para m eters mainly  inclu d e s  ) , ( max maz , and set t ing up thre e  of paramet ers  are  ) 7 . 0 , 2 . 0 ( , ) 7 . 0 , 4 . 0 ( and  ) 3 . 0 , 4 . 0 ( .It main  observes  the error threshold a nd the time of  c a lc ulation how to  cha nge i n   th e sa me  stre n g th functio n    circum stan ce s, and  the  strength  th re sh old an d the ti me  of calculation   how to ch an ge in the sam e  error thresh old circu m sta n ce s.     5.2. Analy s is  of Experime ntal Re sults   Thro ugh  the  experim ent, it ca n be  seen  that  the  erro r threshold i s  small e r  and   sho r ter  cal c ulatio n time in the sa me stren g th thre shol d circumstan ce s from the  analytical Figure 1 ;  th e   intensity thre shol d incre a ses a nd the ti me of  com p u t ational imple m entation th e longe r in t he  same  error t h re shol d und er ci rcum stan ce s. Figur e 2  is avera ge e x ecution time  of before a n d  after optimiza t ion sub - g r ap h isom orp h ism judgme n t algorith m . Th e paramete r  of experime n t is  the second  grou ps b e ca use it is a repre s e n ta tive sample. Th e execution  time of decision   algorith m  sh o r tens in the  search o r de r o p timizing afte r.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3015 – 3 020   3020     Figure 1. The  Time of Com putational  Implementati on und er Th resh old  Circum stan ce s      Figure 2.   Average Exe c utio n Time of before  and after O p timization Su b-grap h  Isomo r phi sm Jud geme n t  Algorithm       6. Results a nd Prospec t s  Un certai n attribute gra ph e x pectation s sub-g r a ph iso m orp h ism i s  a kind of ide a l state.  But it is  often difficult to   achi eve in  th e prac ti cal  problem s. Thi s  pap er fo cu ses  on  define d  of  uncertain attri bute  graph  sub-g r a ph i s o m orp h ism  an d its dete r min a tion metho d . In setting   the two th re shold valu e,  sub-g r a ph i s o m orp h ism i s   more  clo s e to  the actu al isomorphi sm.  The dete r min i ng algo rithm  efficiency h a s  bee n great l y  improved i n  the pre m ise that thresh old   can b e  mod u l ated by.  Sub-graph i s om o r phi sm lay a  foundatio n for su b-g r a ph q uery an d  comm unity mining work in-depth devel o p ment in  co mplex network (So c ial  Net w ork). Ho we ver,  how to  set th e thre shol d to make su b-grap h isomo r phism i s  mo re rea s o nable  and the a c tual  situation mo re matchin g , it is  the further  resea r ch pro b lems.       Referen ces   [1]  Z hang Sh uo,  Gao Hon g , Li Jianz hon g. Efficient  Quer y Pr ocessi ng on U n certai n Graph  Databas es.   Chin ese Jo urn a l of Co mp uter s . 2009; 32( 10) : 2066-2 0 7 9 .  [2]  Z hang  Yin an,  Z ou Z h a oni an,  Li Ji anz hon g.  Algor ithm for   α - β  sub-gr ap h Isomorp h ism  Probl em o n   Uncerta i n Grap h.  Intellig ent C o mputer a nd A pplic atio ns . 20 11; 10: 1-3.   [3] Z hang,  Ch un yi ng,  Guo,   Jin g feng, Ch en, Xi a o .  Res earc h  o n  ra nd om w a lk  rou g h   matchi n g  a l gor ith m   o f   attribute s ub- grap h.  Interna t iona l Co nfere n ce o n  Adv a nced M a teri al s and  Com p uter Scie nce ,   ICAMCS. 2011 ; 5: 297-30 2.  [4]  JK Che ng, T S  Huan g. A sub g rap h  isom orp h ism al gorit hm using r e sol u ti on ori g i nal r e s earch  article .   Pattern Reco g n itio n . 198 1; 13(5): 371- 37 9.  [5]  Don g  An gu o,  Gao L i n, Z h a o   Jian ban g. Al go rithms  for su b- grap h is omorp h ism i n  gr ap h  pattern M i ni ng.   Mathe m atics i n  Practice and T heory . 20 11; 7:  105-1 11.   [6]  Xi e Ch un xi n, W ang W e i. OES: sub-gr ap h i s omorp h ism verificati on al go rithm.  Comput er Engi neer in g .  201 1; 3: 46-51.   [7]  Liu B o , F a n g   Bin, Z h a ng S h i y on g, Li  Z h il in . Desig n   and  i m pleme n tatio n  of sub g ra ph  i s omorp h ism   detectio n  al gori t hm based o n  r e lati ona l mod e l .   Comp uter En gin eeri n g . 20 1 1 ; 11: 39-4 3 .  [8]  F r ed DePi ero,  David Kr out. An alg o rithm us i ng  le ngth-r p a ths to appr o x im ate sub g rap h  i s omorp h ism.   Pattern Recognition Letters . 200 3; 24(1 –3): 33-4 6 .  [9]  Z hou Ao yi ng, J i n Ch eqi ng, W ang Gu oren. A  Su rve y   on th e  Manag eme n t of Uncertai n D a ta.  Chin es e   Journ a l of Co mputers . 200 9; 1 :  1-16.              0.00 0.50 1.00 1.50 2.00 2.50 5 8 11 14 查询 图规模 判定时间 （秒） 第 1组参数 第 2组参数 第 3组参数   0 .00 0 .50 1 .00 1 .50 5 8 11 14 查询 图规 模 判定时间（ 秒） 未改 进算 法 改进 算法 Evaluation Warning : The document was created with Spire.PDF for Python.