TELKOM NIKA , Vol.11, No .1, Janua ry 2013, pp. 181 ~18 6   ISSN: 2302-4 046           181     Re cei v ed O c t  1, 2012; Re vised  No vem ber 28, 201 2; Acce pted De cem ber 4, 20 12   A Survey on Weighted Network Measurement and  Modeling      Xin Xia, Shu- xin Zhu  Coll eg e of Information Sci enc e and T e chno l o g y , Nan jin g A g ricult ural U n iv ersit y   W e iga ng 1, Na njin g,chi an, 21 009 5   *corres pon di ng  author, e-mai l : zzxia xin@ nj au .edu.cn       A b st r a ct  Real n e tw orks have co mpl e x  topolo g ica l  structure  char acteristics such a s  pares of nod es hav e   different stren g t h and ca pacit y connecti on.  T here are  ma ny instanc es i n   our rea l  life.  Every person  has   strong or w eak  relatio n shi p  w i th others in soc i al n e tw ork and  different reacti on paths  have  non- unifor m  flo w   in  metab o lic  n e tw ork. In the  food  ch ain  pr ed ator a n d  pr ey  have  div e rse  r e lati on  an in t he  ne ural  n e tw ork   electric al si gn a l  trans miss ion   paths  have  diff erent  c apac ity. All th ese syst ems  cou l be  descri bed  w e ll  by   the co ncept  of  w e ighte d  n e tw ork and  w e ig ht of e a ch   ed g e  in  w e ig hted  netw o rk stand   for the c onn ectio n   strength a m o n g  ind i vid u a l s. This pa per a i ms  to provid e an o v erview  of rece nt advanc es in  such study ar e a .   W e  first intro d u ce  a s e ries  of  w e ighte d   netw o rk statis tica l c haracter i stic p a ra meter  an conce p ts .T he n i n   particu lar, w e  also  discuss  some pr actical  netw o rk ap plic ation  exa m ples . Emp i rica l res u lts show  that  p u r e   topol ogic a mo del is  not suffi cient to ex pla i n the a bun da n t  and co mplex  characteristics  observ ed i n  r e a l   system s and it is necess a ry to im pr ov e suc h  m o del. So we finally focus  on some latest optimi z e d weight e d   netw o rk mo del s and giv e  co mparis ons.     Key w ords :   Weig hted net work; Statistical characte ri stic; Mod e l;    Copyrig h ©  2013  Univer sitas Ahmad  Dahlan. All rights res e rv ed.       1. Introduc tion  Many thing s   in re al  worl d  su ch  as vari ety of entities a nd  com p l e x relatio n betwe en  entities  coul d  be exp r e s se d by the fo rm of wei ghted network . From Internet [1] to WWW [1],   from la rge  po wer net work [ 2 ] to glob al transportatio n   netwo rk [3], from b r ai n in t he o r ga nism  to   variou s meta bolic  network [4], and fro m  Scientif ic  colla boration  netwo rk [5] to all kin d s of  eco nomi c , po litical and  so cial relation  n e twork [5,6], we  can  say  we h a ve alre ady have live d  in   the worl d filled with  vario u s we ight e d  net wo rk s.  I n  su ch sit u at io n, weighte d  netwo rk top o l ogy  stru cture stud y has beg un to be the hotspot.  The re st of pape r is o r g anized a s  follows. Section  2 introdu ce s some  statist i cs a nd  con c e p ts  of weig hted n e twork. Se ction  3 de scri be some  weight ed net wo rk m odelin g meth ods,   inclu d ing YJBT [7], ZTZ H [8] and AK [9]. Section 4 points o u t the defaul ts of above three   modelin g met hod s a nd giv e s th e imp r o v ements. In  se ction 5  we   co ncl ude an di scuss  fut u re   wor k .       2. Weighted  Net w o r k M e asureme nt  A weighted  netwo rk  could be ex pre s sed a s   W ,, GN l W whe r e no de  12 ,, , N Nn n n  and edg 12 , , , K ll l l  and  weight i n  different  edge s   12 ,, , K Ww w w . The  weig hted n e two r coul d b e   sh own  a s  Fig. 1 where thi c kne s s of  edge s expresse s the wei g ht. When in t he form of m a trix,  W G  is usua lly expressed  as wei ghted   matrix  W  with the si ze of  NN  and the ele m e n t value  ij w  sta nds fo r the  correspon ding   edge weight.  ij w =0 wh en no d e  i and j have no con n e c tion. In this paper we discu ss o n ly two  situation s . On e is  0 ij j i ww  and th other i s   0 ii w i . In certain  circu m stan ce the  weight  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  181 – 1 8 6   182 of edge may be negative  such as the  strang e deg ree amo ng p eople in soci al netwo rk.  One  prima r y cha r a c teri stic of we ighted  network is the weig h t  distribution  () Qw , which  stand s for the  prob ability that the edge weight is w         Figure 1. W e i ghted net work      2.1 Node Str e ngth a nd Intensi t y Dis t ri bution and c o rrelation   In weighte d   netwo rk, the  degree  i k  of node  i  is call ed nod e stre ngth whi c o fte n   expre s sed a s i s .The definitio n of  i s is [10-12]   ii j j sw  (1)     We  can  dra w  a  co ncl u si on from  form ula (1) th at node  strengt h incl ude s b o th nod e   degree a nd  e dge  weig ht conne cting th e  node.  Wh en  t he wei ght an d the top o logi cal  stru cture  of  the network i s  not  releva n t  and if the  node  deg ree  is k , the node  stre ngth i s   () sk w k   whe r w  is the averag e wei g ht. If we con s i der the  correl ation,  () sk A k Given a nod i  with degre e   i k  and stren g th i s , ij w  has the same o r de of / ii sk .The  discre pan cy in different ed ge wei ght of node  i  could b e  descri bed a s  [13-1 4 ]:    i ij i jN i w Y s     (2)     whe r i N  indicates the fi rst-orde r n e ighb or no de s set of node i . i Y   is well correl ated  with no de d e g ree. If all  ed ges  have  simi lar  weight,  () Yk is prop ortio nal  t o 1/ k .If one edge coul d   influen ce formula (2) th en () 1 Yk . In anothe word,  () Yk is irrel e vant to  k   in s u ch sit uat io [15]. Intensity distrib u tion  () Rs  stand s fo r th e pro bability  of sele cting  a  node  with in tensity s . () Rs  and   () Pk  ,which  i s  often  called  deg ree  di stri buti on ,d escri be the  struct ural  prope rtie s of  weig hted net work well.    2.2 Lowes t-weight pa th   Networks in  n-dim e n s iona l Euclid  Spa c e are often t w or th ree  d i mensi onal  a nd  so the   distan ce of n ode  i  and  j  cou l d be rep r e s e n ted by Euclidean di stan ce yardsti ck. Edge length in  weig hted n e twork  ca n be  defined  a s   a functio n  of  weig ht, for i n stan ce 1/ ij ij lw .In weighted   netwo rk, an  optimal path is usu a lly not the lo west -h op path for consi deri ng th e edge weig ht.  Cho o si ng of the lowest-wei ght path is co mple tely dep ende nt on the  definition of edge  weight.       Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Survey  on W e ighted Networ k Meas u re me nt and M odeling  ( Xin Xia 183 2.3 Weigh t  cluster c o effic i ent  In the literatu r e [16], Barra t  et al. define d  clu s te ring  coefficient o n   node  i  in  wei ghted  netwo rk a s :    W , 1 (1 ) 2 ij i m ii j j m m i jm ii ww ca a a sk  (3)     Weig ht clu s te ring  coeffici e n t con s id ers  not only the triangle  numb e r adja c ent to  node  i   but al so th e relative weigh t  of releva nt  node s i n ten s i t y or  stren g th (1 ) ii sk is a  no rmali z ation  fac t or to ensure W 01 i C  . W C  is th e av erag e valu of all n ode s’  weig ht cl uste ring  co efficie n and  W () Ck  is  the a v erage val ue  of node s’ wei ght clu s teri ng  coeffici ent wi th the deg ree  being k . In the ca se  of larg e-scal e ran dom  ne twork(not co nsid erin g de gree  rel e vant ) W CC  and   W () () Ck C k  whe r C  is th e avera ge val ue of cl uste ri ng coefficie n t of un-weig hted net work  with the  sam e  topolo g y a nd  () Ck  is the a v erage val u e  of su ch n e twork n ode s’  clu s terin g   coeffici ent wit h  degree bei n g   k In re al  weight ed n e two r we may m eet t w re cip r o c al  situatio ns.  O ne i s   W CC  and  then ed ge s formin g trian g l e  usually hav e larg er  weig ht. The othe is  W CC  and the s e  edge have small e weig ht.      3. Weighted  net w o r k mo deling  3.1 Yook–Je ong– Bara si–Tu (YJ B T)  The sim p le st way to co nstruct a weighte d  netwo rk is to build a rand om network  with the   degree di stri bution is  () Pk  a nd then try to make it submit to mutual and in depe ndent  distrib u tion , s uppo sin g  the  edge s’  weig ht are  inde pen d ent of ea ch  ot her. O ne int r e s ting  situation  is that the  n ode  deg ree   and  weig ht a r e often  co u p led. S.H. Y ook et al. p r opo sed th Yook– Jeo ng–Ba r a b á si–T u (YJBT )  free scale weighted  net work mo del. The topology o f  the model and  the edg e we ight distri buti on in the m odel a r e g e n e rated  ba sed  on prefere n t ial attachme nt  mech ani sm  d u ring  the  peri od of  network gro w th [7 ]. T he YJBT  Mo d e l con s tru c tio n  process i s   as  follows Starting fro m   o m  isol ated n o d e s, eve r y tim e  when i n tro d uce d  a  ne w n ode  j  we  ma k e   it con n e c tabl e to  m   existin g  node s wh ere   0 mm .The p r ob abili ty that nod j  is  c o nn ec te d to   the existin g   node   i  obeys BA Net w ork prefe r e n tial  con n e c tion  chara c te risti c We  ca n a s si g n   each edg e weight of node  j   () j ii j ww    ' ' i ji i i k w k  (4)     YJBT co uld g enerate a fre e  scale n e two r who s e d e g r ee di strib u tio n  is  () ~ Pk k  and  3 .The network’s po we r law intensity dist ribution i s   () ~ s R ss where th e valu s  of is  clo s ely relate d to the choi ce of  m   3.2 Zheng– T r imper–Zhe n g –Hui (Z TZH)   Zheng –Tri mp er–Z hen g– Hu i (ZTZH) is  the gene rali zed form of YJBT. It combine s   rand om  wei g ht allo cation   mech ani sm  b a se d o n  the   node  de gre e   distrib u tion  [8 ]. We  add  ne w   edge  j i l  on the probability of  p  and on the p r oba bility of  1 p  add ed ge  j i l  weight:    Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  181 – 1 8 6   184 ' ' i ji i i w  (5)     whe r i  is th e optimu m  p a ram e ter  an d is ra ndoml y  sele cted  o n  the  pro bab ility of     between 0 and 1  [17].When  1 p ,it is YJBT model.  Z TZH  also lea d s to  po we law  intensity di stribution’ s bei n g   () ~ s R ss . s  is  sensitiv e to  p  and if  p  i n cr ea se s f r o m  0 t h e n   s  falls down from 3 contin u ously.     3.3 Antal–Kr apiv sk y  (AK)  Antal–Krapiv sky (AK) p r op ose d  a stru ct ural g r owth  weighted net work m odel ba sed o n  edge  and  weig ht cou p ling [9]. The model ge ne ration pro c e s s is a s  follo ws: Every st ep a ne w n ode   con n e c ts to a n  existing no de  i  and the conne ction p r o bability is    i ji l l s s  (6)     This p r eferen tial conne ctio n rule is a strengt h-pri o r ru le. That is the new nod e is alway s   inclin ed to conne ct the n ode with hig her st re n g th. Many real  netwo rks nat urally use this  con n e c tion  m e ch ani sm.  Due to  the  co nsid eratio n o f  the b and wi dth an d flo w ,  in Inte rnet,  new  route r sho u l d  be co nne ct ed to central routers [1].  In the scientific rese arch net work, auth o rs a r e   more e a sily  to search  co operating wit h  ot hers. Fo r each edg e  adding the  weig ht whi c h  is   positive and  obedi en ce to distributio () w ,the final sha pe of the network is the tree form.  Whe n  the co nne cting process  last s a long time and with  s  ,the intensity distrib u tion  () Rs   of the network app roa c h e s a stable dist ribution  3 () ~ R ss  and is irrel e vant to  () w ,the edge   weig ht distrib u tion.      4. Model comparison an d impro v ement  Above YJBT  ZTZH and  AK model are  all ba se d  on g r o w th  mech ani sm.  Weig ht is  assign ed wh en edg e is fi rst e s tabli s he d and  kee p s unchang ed.  These mo del s all ign o re the  dynamic evol ution  cha r a c t e risti c s of th e  edg we ig ht  whe n  n e w no des an d e d g e are a dde d  to   the net work.  Not only th at, the wei ght  evolution a n d  edge  re co nn ection i s   common  natu r al  cha r a c teri stics of  network. For  examp l e in  th e avi a tion n e two r k, when  a  n e route  wa s   establi s h ed it would  affect  other route s  traffi c volum e . In such sit uation an im proved  wei g h t ed   netwo rk m o del appe are d . That is Barrat–B a rth é lemy–Ve s pi gnani  BBV  model which  con s tru c ted  b a se d on weig ht dynamic e v olution  ca used by the local netwo rk  growth an d ed ge  reconnec tion  [18-20]. It s t arts  from  0 m  nod es  and th e e dge  weig ht is  0 w .Then every   step a   new node co nne cts  exi s tin g   m  node s o n  the proba bility as  sho w n in  formula  (7 ), suppo sin g  the   origin al wei g h t  of  m edge s is 0 w   0 () 1 kK Nk K kK Pk N Kp Kp kK kK NN         (7)     Let  j i l  be a ne w edge a nd its  appe ara n ce make weig h t  of edges b e t ween n ode  i  and   its neigh bor n ode set cha n ge as follo ws:    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046       A Survey  on W e ighted Networ k Meas u re me nt and M odeling  ( Xin Xia 185 i l il il i ww w l N   (8)     w h er   il il i w w s   (9)     Whe n  a new edge with the weig ht of  0 w  is conne ct ed to node  i  it would ma ke  comm uni cati on traffic on  the othe r ed g e s of  i  incre a s e by  .Duri n g  the process  each si de’ s   increa sed  a m ount i s   p r opo rtion a l t o  the  edg e  wei ght a n d  p r odu ce s the  re sult  o f   0 ii ss w   in the end. Specifi c  evoluti on pro c e s s is sho w n in figu re 2.       0 ii ss w  i j 0 w     Figure 2. Edge weig ht evolution pro c e ss of BBV      Intensity and weight generated by BBV model  both obey exponential dist ribution. In   orde r n o t to  lose th e g e n e ral  we  ca make   0 1 w  and t hen the  mod e l is  determi ned by  para m eter  .After a few steps  we  coul d get th e weig ht distribution a s   () ~ w Qw w , 21 / w   and deg re e distrib u tion a s   () ~ Pk k  and inte nsity distributio n as  () ~ s R ss ,where 43 / 2 1 s   .This  res u lt s h ows that  BBV  c o uld generate  a free sc ale   netwo rk  who s e power la w expone nt  [2 , 3 ] .When  0  BBV is  t he s a me as  B A     5. Conclusio n  and Futu r e  Works   Weig hted n e twork  ha s be en an  active  and difficult re sea r ch to pic fo r re ce n t  years.   Some re sea r che r s o b tain fairly good results. Bu t there still exist so me unresolve d and sca r cel y   addresse d problem s su ch  as comm uni ty detecti on ,con se nsus p r oblem an d node impo rtan ce  evaluation  an d so o n . At the same tim e some  ki nd s o f  statistics  of  weig hted n e tworks h a ve n o a unified defi n ition and the i r physi cal  sig n ifican ce s ar e not very cle a r. To solve su ch qu estio n s,   we  need  to l ook for m o re  relia ble m e thod to  de scri be the  wei g h t ed net work.  More over,  we   should try to find  m o re effective methods to bu ild weighted  network end-to -end reli ability in the  con d ition of n ode failure.      Referen ces   [1]  Pastor-Satorra s R, Vespign ani A.  Evoluti on an d Structur e of the Internet: A Statistical Physic s   Appro a ch , Ca mbridg e Un iver sit y  Press, Ca mbridg e, 20 04.   [2]  Watts DJ. S m all Worlds:  T h e Dyna mics of  Netw orks betw een Order a nd Ra ndo mne s s , Princeton  Univers i t y  Pr es s, Princeton, N J , 1999.   [3]  Guimerà R, Mossa S,  T u rtschi A. T he w o rldw ide air tra n s portatio n  net w o rk: Anoma l o u s central i ty,  Evaluation Warning : The document was created with Spire.PDF for Python.
                          ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 1, Janua ry 2013 :  181 – 1 8 6   186 community stru cture, and citie s  g l o bal ro les , Proc. Natl. Acad. Sci. USA, 2005; 102( 22): 77 94-7 799.   [4]  Girvan M, New m an MEJ.  Community stru cture in soci al  and bi ol ogic a l  netw o rks , PNAS, 2002; 99:   782 1-78 26.   [5] Scott  J.  Social Netw ork Analy s is: A Handb oo k . Londo n: Sag e  Publ icatio ns, 2nd e d ., 2002.   [6]  Latora  V, Mar c hior M  V, Ma rchior M,  Ec o n o m ic s m all-w o rld  be havi our  in w e i ghte d  n e tw orks , Eur.   Ph y s . J. B, 200 3, 32: 249 –26 3 .   [7]  Song C, Hav lin  S, Makse HA.  Self-Si m il arity of Compl e x Ne tw orks , Nature, 2005; 4 33: 39 2-39 5.  [8]  Broder A, Ku mar R, Magh o u l F ,   Stata R,  T o mkins A, and W i en er J.  Graph structur e in the w e b Comp uter Net w o r ks, 200 0, 33: 309-3 14.   [9]  Klemm K, Eguíluz VM.  High l y clustere d scale -free netw o rks , Ph y s . Rev. E, 200 2; 65: 036 1 23.   [10]  Barrat A, Barthél em y  M, Pa stor S R,  T he architecture  o f  comp lex w e i ghted  netw o rks , Proc. Natl.   Acad. Sci. USA, 2004, 10 1: 3747- 380 0.   [11]  Yook SH, Jeo n g  H, Barabás i AL.  W e ighted Evolvi ng  Netw orks , Phy s . Rev. Lett., 2001; 86: 5835.   [12]  Onnel a J P,  Chakr aborti  A, Kaski K.  Dy na mics of ma rket  correl a ti on s: Ta xo nom y a n d  po rtfo l i analysis , Ph ys. Rev. E , 2003, 68: 056 110.   [13]  Barthél em y M,  G ondr an B, G u ich a rd E.  S p a t ial structur e of  the Inter net tr affic , Ph ysica   A, 200 3; 3 1 963 3-64 3.   [14]  Derrid a  B, F l yv bjer g H.  Statist i cal pro perties  of  ran d o m ly br ok en  ob jects a nd of  multiva l l e y structures  in dis o rder ed s ystems , J. Ph ys. A, 1987; 20: 527 3-52 88.   [15]  Barratan d  A, W e igt M. On th e prop erties of  sm all- w o rld n e t w o r ks, Eur. Phys. J. B, 2000; 13: 547 –5 60.   [16]  Molloy  M, Reed B.  A critical poi nt for rando m gr aphs  w i th  a give n de gre e  seque nce , Ra ndom Struct.   Algorit hm, 199 5; 6: 161-1 79.   [17]  Barab á si AL, J eon g H, Rav a s z  R.  Evolutio of the socia l  n e tw ork of scien tific colla bor ati ons , Phy s ica   A , 2002; 311:  590- 614.   [18]  Barrat A, Barthél em y  M, Ve spig nan i A.  Mode lin g the ev oluti on  of w e ig hted netw o rks , Phy s , Rev. E,  200 4; 70: 066 1 49.   [19]  Doro govtsev S N , Mend es JF F ,  Samukhin  AN.  Si z e -d ep e nde nt  de gree  distrib u tion of a  scal e -free   grow ing n e tw ork , Ph y s .Rev. E ,  2001, 63: 06 2 101.   [20]  Pand ya  RV R. A note  on “ W e ig hted Ev olvi ng N e tw orks: Cou p li ng T o po logy  an d W e i g ht Dyna mics ”,   200 4; 16: 644- 657   [21] Che n   W en,   Z hao Yon g ji u, Ju n Z hou xi ao. C o mpact an w i de up per-sto p ban d triple-m o de bro a d ban microstrip BPF,  Te lko m nika , 2 012,1 0 (2): 35 3 - 358   [22]  Ya n X ij un, Me ng  Xi ang w e i, Y an Ya n. A  w i re less sens or n e t w o rk  in pr ecisi on a g ricu lture,  Te lkom n i ka 201 2; 10(4): 78 8-79 7     Evaluation Warning : The document was created with Spire.PDF for Python.