TEMPORAL NETWORKS ANALYSIS

Social and Technological Network Analysis Lecture 10: Temporal Social Network Metrics and Applica>ons Dr. Cecilia Mascolo

In This Lecture •  We will show metric extensions for complex networks which keep >me into account. •  We will also show how these can be applied to applica>ons.

Why Temporal Social Network •  Most of the analysis we have seen has been done on aggregated network graphs •  Time has not been kept into account by the metrics •  Why does this maHer?

Empirical Networks J. Phys. A: Math. Theor. 41 (2008) 224014

F De Vico Fallani et al

Figure 2. (a) Realistic head model for the representative subject. On the right hemisphere of the scalp, the positions of the electrodes are depicted as white little spheres. On the left hemisphere of the cortex, all the cortical regions of interest are displayed and opportunely labelled. The trial-averaged waveforms for a particular subset of areas (7 L, MF L, SM L, CM L, 9 L) are illustrated. (b) Functional networks of the subject in the Beta frequency band during three representative instants (−1 s, onset, +1 s) of the task performance. Dark arrows represent the functional links that persist in all the three instants, while the light arrows represent those flows that changed direction in at least one instant.

Libya on the Internet 11 Aug 2011 22 Aug 2011 aybiL

aybiL

srosneS llA

rosneS morF

923

sedoN latoT

16

htlaetS noN latoT

862

htlaetS latoT

2

srosneS latoT

srosneS llA

rosneS morF

963

sedoN latoT

311

htlaetS noN latoT

652

htlaetS latoT

2

srosneS latoT

41.7.452.01 )stsoH 1(

)221(htlaetS )sedoN 2( )321(htlaetS )sedoN 2(

)202(htlaetS (h2tl(aetS )s)e2d3o1N )sedoN 2(

)61(htlaetS )sedoN 2(






)281(htlaetS

371.71.36.251 )sedoN 9(



)431(htlaetS )331(htlae)tS sedoN 2( )sedoN 2(

121.74.86.26 )sedoN 9(

)817(3h1tl.a6e9t1S.22.591 )sedoN )se2d( oN 41(



)222(htlaetS )sedoN 2( )551(htlaetS )031(htlaetS )sedoN 2( )sedoN 2(


011.291.22.591 )sedoN 9( )571(htlaetS )sedoN 2( )671(htlaetS )sedoN 2( )38(htlaetS )sedoN 2(



)181(htlaetS


751.71.36.251 )sedoN 21(

)921(htlae)t6S32(htlaetS )sedoN 2()sedoN 2(

05.812.22.591 )sedoN 2(




522.812.22.591 )sedoN 72(





)65(htlaetS )sedoN 2( )881(htlaetS )711()hsteladeotN S 2( )462(htlaetS )sedoN 2( )sedoN 2(









6.5.452.01 )stsoH 1(

)852(htlaetS )sed)o7N 522((htlaetS )sedoN 2(


)232(htlaetS




)98(htlaetS

421.74.86.26 )sedoN 51(



311.901.802.14 )sedoN 6( )stsoH 1(

4.0.11.01


432.84.86.26 )sedoN 2(

391.811.802.14 )sedoN 8(

621.38.802.14

66.74.86.26 )stsoH 1(

522.23.86.26

222.16.042.26

)08(htlaetS )stsoH 31(

)432(htlaetS)54(htlaetS )sedoN 2( )sedoN 2(

091.611.802.14


81.611.802.14

)931(htlaetS


)761(htlaetS )s e d o N 2(


)771(htlaetS 66.421.802.14 )stsoH 1(

37.95.86.26

37.101.802.14 )sedoN 8( )stsoH 2(

24.611.802.14

31.611.802.14

222.791.22.591 )s e d o N 7(

712.95.86.26

602.421.802.14 )sedoN 2(



1.06.86.26 )sedoN 01(


39.801.802.14 )sedoN 9(

131.53.86.26

02.06.042.26 )sedoN 4(

)38(htlaetS

)622(htlaetS


681.421.802.14 )sedoN 2(

102.611.802.14 )sedoN 4( )stsoH 2(


)912(htlaetS

)232(htlaetS




)052(htlaetS )stsoH 01( )7(htlaetS )sedoN 2(

)032(htlaetS )stsoH 41()902(htlaetS )sedoN 2( )801(htlaetS )sedoN 2(

)812(htlaetS )sedoN)026((htlaetS )sedoN 2(

921.201.802.14 )sedoN 5( 4.421.802.14 )sedoN 5(

642.84.86.26 )sedoN 2(



37.95.86.26



)212(htlaetS )sedoN 2( 521.71.36.251 )sedoN 21(



1.06.86.26 )0)9s(ehdtloaN et3 S1( )sedoN 2(


)18(htlaetS )101(htlaetS )sedoN 2( )sedoN 2(

56.85.86.26

)581(htlaetS

)851(htlaetS )sedoN 2( )05(htlaetS 942(h )sedo)N ( tlaetS )sedoN 2( 66.421.802.14 )stsoH 1(



)681(htlaetS )sedoN 2( 212.042.642.56 )96(htlaetS )sedoN 21( )sedoN 2( )2(htlae)t9 S81(htlaetS )83(htlaetS 371.71.36.251 161.71.36.251 )sedoN 2( )sedoN 2( )s)e2d5o1N(h2tl(aetS )sedoN 8( )sedoN 8( )57(htlaetS )46(htlaetS )sedoN 2( )sedoN 2( )s e d o N 2( )442(htlaetS )402(htlaetS )16(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )731(htlaetS )081(htlaetS )791(htlaetS )sedoN 2( )sedoN 2( 28.791.22.591 )58(htlaetS )6(htlaetS )sedoN 2)(322(htlaetS )sedoN)552( 2(htlaetS )sedoN 2( )28(htlaetS )sedoN 2( )sedoN 2( 452.791.22.591 )1(htlaetS )sedoN 2( )sedoN 2( 45.891.22.5911.86.891.56 )73(htlaetS )sedoN 5( )sedoN 2( )44(htlaetS )932(htlaetS )sedoN 3( )sedoN 21( )sedoN 2( 73.06.042.26 )231(htlaetS )501(htlae)tsSedoN 2( )sedoN 2( )701(htlaetS )sedoN 2( )122(h)tsla ee dtoSN 2( 07.101.802.14 )01(htlaetS )35(htlaetS )45(htlaetS 452.85.86.26 )sedoN 2( )sedoN 2( )sedoN 2( )36(htlaetS )sedoN 2( )sedoN 2( )sedoN 5( )971(htlaetS )712(htlaetS )802(htlaetS )sedoN)20(11(htlaetS )sedoN 2( )sedoN 2( )se)d4o3N 2t(laetS 1(h )2s4 e2 d(ohNtla2e( tS )68(htlaetS )591(htlaetS )781(htlaetS )202(htlaetS )601(htlaetS )s e d o N 2( )sedoN 2( )sedoN 2( )sedoN 2( )s)5e1d1o(N )8(htlaetS )47(htlaetS )sedoN 2( htl2a(etS )sedoN 2( )691(htlaetS )9(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )302(htlaetS )132(htlaetS 902.2.36.251 65.812.22.591 121.811.971.251 6).7 )sedoN 2( )422(htlaetS )98(htlaetS 94 5.(8h6 tl.a2e6tS )sedoN 2( )sedoN 81( )sedoN 71( )sedoN 31( )s)esdeodN )sedoN 2( )sedoN 2( oN7(2( )531(htlaetS 1.421.802.14 1.181.441.312 )881(htlaetS )sedoN 2( 181.71.36.251 )sedoN 31( )sedoN 91( )222(htlaetS )sedoN 2( )412(htlaetS )sedoN 01( )sedoN 2( )832(htlaetS )89(htlaetS )sedoN 2( 16.812.22.591 2.421.802.14 )sedoN 2( )s e d o N 2( )sedoN 02( )661(htlaetS )sedoN)133( 1(htlaetS )sedoN 2( )sedoN 2( )21(htlaetS )401(htlaetS36.812.22.591 )07(htlaetS )sedoN 2( )281(htlaetS )sedoN 2( )sedoN 02( )871(htlaetS )sedoN 2( )92(htlaetS 941.71.36.251 )031(htlaetS )29(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 21( )sedoN 2( )sedoN 2( )17(htlaetS )941(htlaetS 351.71.36.251 871.76.031.751 01.421.802.14 )sedoN 2( )sedoN 11( )86(htlaetS )sedoN 2( )sedoN 32( )34(htlaetS )sedoN 3( 39.421.80)226.1(h 4tlaetS 642.791.22.591)sedoN 2( )71(htla)e7t7S1(htla7 e5 tS1.71.36.251 )sedoN 2( 602).s7e9d1o.2N2.85(91 )51(htlaetS )901(htlaetS )sedoN)s7e1d( oN 2( 221.7)4s.e8d6o.2 68( )19(htla)seetSdoN 2)(sedoN 2()sedoN 21( )03(htlaetS N ) s e d o N 2 ( ) s e d o N 2 ( 45.611.802.14 )sedoN 8( )85(htlaetS )56(htlaetS )sedoN 2( )08(htlaetS )31(htlaetS )sedoN 2)(261(htlaetS )441(htlaetS )12(htlaetS )sedoN 2( )331(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )62(htlaetS )sedoN 2( )sedoN)3 23 ( (htlaetS )75(htlaetS )79(htlaetS )sedoN 2( )151(htlaetS )sedoN 2( )sedoN 2( )181(htlaetS )sedoN 2( )99(htlaetS )sedoN 2( 2.74.86.26 )sedoN 2( )sedoN 2( )sedoN 2( )52(htlaetS 35.611.802.14 )sedoN 02( 50)2s.e2d.3o6N.225(1 )97(htlaetS )sedoN 21( )5(htlaetS )341(htlaetS )sedoN 71( )sedoN 2( )69(htlaetS lae2t(S )s6e3d(hotN )sedoN 2( )252(htlaetS )64(htlaetS )sedoN 2( )sedoN 2( )912(htlaetS 522.812.22.591 )sedoN 2( )sedoN 2( )sedoN 2( )361(htlaetS )sedoN72013.(812.22.591)53(htlaetS )4(htlaetS )352(htlaetS )612(htlaetS )sedoN 62( )652(htlaetS )66(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )81(htlaetS 931.691.22.591 )022(htlaetS )332(htl1 a2 e1 tS.71.36.251 )sedoN 2( )sedoN 2( )831(htla)e0t2S(htlaetS )sedoN 2( )sedoN 2( )461)6 (h7t1la(e 1(htlaetS htS laetS )sedoN 91( )641(htlaetS )sedoN 2( )sedoN 2( )sedoN 2()sedo)6 N 8d ( oN 2( )sedoN)2 ( doN 2( )55(htlaetS se )sed)o Nd2o(N 2( )se se )sedoN 2( )512(htlaetS )051(htlaetS )152(htlaetS 831.181.441.312 )22(htlaetS 521.812.22.591 )sedoN 2( )sedoN 2( )sedoN 2( )sedoN )722(2(htlaetS )sedoN 61( )sedoN 2( )sedoN 72( )59(htlaetS )sedoN 2( 4.791.22.591 )11(htlaetS )sedoN 2( )43(htlaetS )sedoN 13( )sedoN 2( )561(htlaetS )481(htlaetS )sedoN 2( )552(htlaetS )sedoN 2( la9e1tS )sedoN 2( )122(1(htlaetS 731.6)9211.12(2h.t5 )sedoN 561.71.36.251 )611(htlaetS )951(htlaetS )42(htlaetS do9N1(2( )54(htlaetS )sedoN 2( )se)dsoeN )452(htlaetS )sedoN 21( )142(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )84(htlaetS ) 4 9 ( h t l a e t S 7 7 1 . 7 1 . 3 6 . 2 5 1 )742(htlaetS )942(htlaetS ) s e d o N 2 ( otNla2 )3)s8e1d(h e(tS )sedoN 2( )sedoN 2( )32(htlaetS )sedoN 21( )3(htlaetS )41(htlaetS )sedoN 2( )sedoN 2( )451(htlaetS)071(h)tslaeedto SN 2( )sedoN 2( )291(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( 521.74.86.26 )sedoN 2( )191(htlaetS )541(htlaetS )111(htlaetS )642(htlaetS )s e d o N 3 2( )491)(shetd laoeNtS2( )061(htlaetS )021(htlae)t)0 Ss1e2d(ohN )sedoN 2( )sedoN 2( )822(htlaetS tla2e(tS )sedoN 2( )sedoN 2( )76(htlaetS )74(htlaetS )sedoN 2( )sedoN 2( )042(htlaetS )sedoN 2( )65(htlaetS )sedoN 2( )sedoN 2( )741(htlaetS )sedoN 2( )sedoN 2( )112(htlaetS )sedoN 2( 321.74.86.26 )891(htlaetS )sedoN 2( )sedoN 91( )sedoN 2( )991(htlaetS )571(htlaetS ) 8 4 1 ( h t l a e t S ) s e d o N 2 ( )471(htlaetS )sedoN 2( )sedoN 2( )102(htlaetS )sedoN 2( )15(htlaetS )sedoN 2( )721(htlaetS )sedoN 2( )002(htlaetS )542(htlaetS )602(htlaetS )sedoN 2( )sedoN 2( )sedoN 2)7 ( 2(htlaetS )702(htlaetS )sedoN 2( )sedoN 2( )25(htlaetS )sedoN 2( )82(htlaetS )521(htlaetS )sedoN 2( )732(htlaetS )sedoN 2( )sedoN 2( )161(htlaetS )421(htlaetS )sedoN 2( )711(htlaetS )sedoN 2( )23(htlaetS )13(htlaetS )621(htlaetS )321(htlaetS )651(htlaetS )78(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )041(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )221(htlaetS )911(htlaetS )sedoN 2( )sedoN 2( )88(htlaetS )67(htlaetS )171(htlaetS )sedoN 2( e d o N 2( )sedoN 2( ))3s7 (htlaetS )77(htlaetS )632(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )04(htlaetS )sedoN 2( )27(htlaetS )551(htlaetS )93(htlaetS )922(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )301(htlaetS )sedoN 2( )201(htlaetS )sedoN 2( )931(htlaetS )811(htlaetS )sedoN 2( )sedoN 2( )241(htlaetS )532(htla)e4t3 S2(htlaetS )sedoN 2( )sedoN 2)(sedoN 2( 731.421.802.14 )sedoN 5(

541.201.802.14

121.111.802.14 )sedoN 4( )stsoH 7(



96.101.802.14

2.84.042.26

)271(htlaetS )sedoN )29(61(htlaetS

321.74.86.26 )sedoN 31(




1.46.802.14 )sedoN 01( 6.421.802.14 )sedoN 01(

12.421.802.14 )sedoN 2( 942.501.802.14 )sedoN 3( )stsoH 1(

)652(htlaetS



)15(htlaetS 202.791.22.591 )sedoN 2( 28.791.22.591 0.(22.27.9519.122.591 )6 se 4d 2o .7N9614 )sedoN 5( )se 452.791.22.591 )sedoN 4d ( o N 4( )sedoN 5(


622.63.042.26

532.84.86.26 )sedoN 2(

9.23.042.26 )sedoN 3( )stsoH 1(

201.421.802.14 )sedoN 8(


36.812.22.591 )sedoN 51( 3.181.441.312 )531(htla)esteSdoN 91( )sedoN12 .1(81.41461..831122.22.591 )sedoN)s7e1d( oN 51(



98.95.86.26 )stsoH 1(


)48(htlaetS

452.85.86.26 )sedoN 6(



1.23.86.26 )sedoN 3(

77.511.802.14 )sedoN 2(


)741(htlaetS )sedo)9N52 2((htlaetS )sedoN 2(



522.011.802.14

3.65.86.26

79.23.86.26

)25(htlaetS )412(htlae8 tS12.791.22.591 )sedoN 2( )271(htlaetS)sedoN 2( )sedoN 51( 261.891.22.591 )891(htlae)tsSedoN 2( )sedoN 2( )sedoN 2(

)471(htlaetS )sedoN 2( 181.71.3)6 4.2225(1htlaetS )sedoN)0 1d ( oN 2( se

961.95.86.26

01.23.86.26

1.31.452.01 )sedoN 2(

9.721.802.14 )sedoN 5(

391.111.802.14



771.95.86.26

56.24.86.26 )sedoN 3(

6.31.452.01 )sedoN 2(

1.721.802.14 )sedoN 11(

6.23.042.26 )sedoN 2(



281.891.22.591 )sedoN 51(


032.312.252.14 )602(htlaetS )sedoN 2(

1.41.452.01 )sedoN 2(

1.9.452.01 )sedoN 2(

6.2.452.01 )stsoH 1(

)402(htlaetS

121.811.971.251 )sedoN 41( )591(htlaetS )842(htlaetS )sedoN 2( )sedoN 2( )86(htlaetS )801(htlaetS )171(htlaetS )sedoN 2( )74(htlae)2tS6(htlaetS )69(htlaetS )sedoN 2( )sedoN 2( )s(edoN 2( )sedoN 2 )s e d o N 2( )391(htlaetS )99(htlaetS )151(htlaetS )37(htlaetS )sedoN 2( )621(htlaetS )sedoN 2( )162(htlaetS )sedoN 2( )sedoN 2( 922.812.22.591 )sedoN 2( )sedoN 2( )66(htlae)t3 S2(htlaetS )361(htlaetS )sedoN 42( )sedoN 2)(sedoN 2( )sedoN 2( )77(htlaetS )461(htlaetS )352(htlaetS )332(htlaetS )sedoN 2( )961(htlae)stSedoN 2( )sedoN 2( )41(htlaetS )sedoN 2( )642(htlaetS )sedoN 2( 941.71.36.251 )sedoN 2( 721.812.22.591 e(dhotN )381(htlaetS )96(htlaetS )sedoN 01( ))0s3 lae2t(S )sedoN 32( )18(htlaetS )02(htlaetS )911(htlaetS )91(htlae)stSedoN 2( )sedoN 2( 502.2.36.251 )sedoN 2( )05(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )542(htlaetS )sedoN 91( )36(htlaetS 871.76.031.751 )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 82( )21(htlaetS )2(htlaetS )491(htlaetS 931.691.22.591 902.2.36.251 )sedoN 2( )721(htlaetS )73(htlaetS )s e d o N 2 ( )sedoN 2( )29(htlaetS )sedoN 31( 561.71.36.251 )sedoN 91( )sedoN 2( )sedoN 2( )sedoN )25(62(htlaetS )261(htlaetS )27(htlaetS )sedoN 9( )071(htlaetS )47(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sed)o5N 2(h ( tlaetS 6 1 521.71.36.251 )sedoN 2( )93(ht)la )sedoN 2( )251(htlaetS )sedoN 01( 0e 9t(S htlaetS )87(htlaetS )sedoN )041(htlaetS )sedoN 2( )se2d( oN 2( )sedoN 2( 121.71.36.251 )sedoN 2( )822(htlaetS )sedoN 21( )39(htlaetS )sedoN 2( 45.181.441.312 )311(htlaetS 54.791.22.591 )122(htlaetS )sedoN 2( ) s e d o N 2 ( ) s e d o N 2 ( )sedoN 4( )sedoN 2( )04(htlaetS 74.791.22.591 45.891.22.591 )662(htlaetS 902.812.22.591 )sedoN 2( )021(htlaetS )s e d o N 3( )sedoN 3( htl2 1a1(e2tS .812.22.591 )002(htlaetS )sedoN 2( ))s3e7d1o(N )sedoN 2( )89(htlaetS )sedoN 2( )sedoN 3( )sedoN 2( )76(htlaetS )241(h)t2la2e(thStlaetS )sedoN 2( )102(htlaetS 242.891.22).856921(htlaetS se2d(oN 2( )sedoN 2( )sedo)N )sedoN 2( )sedoN )2s(edoN 2( 831.181.441.312 )262(htlaetS 521.74.86.26 )31 )212(htlaetS)841(htlaetS )sedoN )sedoN 2( 42 ( (htlaetS )sedoN 2( )811(htlaetS )sedoN 2( )sedoN 2( )522(htlaetS )s e d o N 2( )97(htlaetS )622(htlaetS )sedoN 2( )062(htlaetS )362(htlaetS )sedoN 2( )17)s(hetdlaoeNtS2( )sedoN 2( )sedoN 2( )581(htlaetS )341(htlaetS )sedoN 2( )441(htlaetS )63(htlaetS )sedoN 2( )732(htlaetS )53(htlaetS )sedoN 2)(001(htlaetS )sedoN 2( )sedoN )620(1(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )101(htlaetS )16(htlaetS )661(htlaetS )sedoN 2( )5(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )sedoN 2( )411(htlaetS )sedoN 2( )631(htlaetS )07(htlaetS )sedoN 2( )451(htlaetS )762(htlaetS )sedoN 2( )sedoN 2( )sedoN 2( )28(htlaetS )481(htlaetS )sedoN 2( )sedoN 2(

6.41.452.01 )sedoN 2(

6.9.452.01 )sedoN 2(

6.3.452.01

8.23.042.26

2.74.86.26 )33(htlaetS )sedoN 61( )sedoN 2( )112(htlaetS )081(htlaetS )sedoN 2( )sedoN 2(

2.891.22.591 )sedoN 3(


6.8.452.01


)121(htlaetS )sedoN 2()061(htlaetS)991(htlaetS )sedoN 2( )sedoN 2( )94(htlaetS )sedoN)022( 2(htlaetS )sedoN 2(



1.86.891.56 )sedoN 21( )502(htlaetS )79(htlaetS )sedoN 2( )sedoN 2(


521.812.22.591 )sedoN 72( )541(htlaetS )sedoN 2(

902.111.803 23 .1.8 411.802.14





771.71.36.251 351.71.36.251 )sedoN 7( )sedoN 01)(401(htlaetS )s e d o N 2(




201.291.22.591221.74.86.26 )sedoN 2( )sedoN 2(



)sedoN 2(





)722(htlaetS )681(htlaetS .71 )se1d6o1N 2.(36.251 )sedoN )9s(edoN 2( )59(htlaetS )sedoN 2( )44(htlaetS

212.042.64 )724.526(htlaetS )sedoN 2 )s1e(doN 2(



)01(htlaetS)052(htlaetS )sedoN 2( )sedoN 2( )34(htlaetS )sedoN 2(

)11(htlaetS )191(htlaetS )sedoN 2( )19(htlaet)S s e d o N 2( )sedoN 2(


)46(htlaetS )sedoN 2( )932(htlaetS )sedoN 2( )152(htlaetS )sedoN 2(





202.812.22.591


)091(htlaetS )3(htlaetS )sedoN 2)(sedoN 2(




2.7.452.01 )sedoN 2(


the representative Beta frequency band. The overall presence of mutual links in the cortical networks is always higher with respect to random (ρ > 0). However, a different behaviour can be found between the preparation and the execution of the movement. In particular, during the movement preparation the reciprocity of the cortical networks moves from a relative high reciprocal state (ρ > 0.25) to a lower (ρ < 0.17) level as revealed by the negative slope of ρ(t) for −1 < t < 0 s. Instead, during the movement execution the average trend of ρ(t) for 0 < t < 1 s constantly remains in the low reciprocal state reached in proximity of the onset (0.15 < ρ < 0.2). In figure 3(b), the level of reciprocity of all the possible connections within the cortical network is illustrated for the same band and during the entire period of interest. The level of grey codes the number of subjects that actually hold a particular reciprocal link identified by the values at the ordinates. In table 1, the correspondence between the y-values and the bilateral link can be deduced by inspecting the values of the symmetric adjacency matrix. The presence of continuous horizontal lines indicates a sort of ‘persistence’ of particular reciprocal connections which can also remain active during the entire task performance, as for the cingulate motor areas (CM L and CM R) with the ipsi-lateral supplementary motor areas (SM L and SM R), respectively. In such a case, at least three subjects present these persistent )342(htlaetS )sedoN 2(



37880 JN ,tesremoS ,evirD muirtA 003 ,noitaroproC atemuL 1102 thgirypoC

6

4

37880 JN ,tesremoS ,evirD muirtA 003 ,noitaroproC atemuL 1102 thgirypoC

slebaL tegraT 11

)EPIR( ertneC noitanidrooC krowteN EPIR

2

)CINIRFA( retneC noitamrofnI krowteN nacirfA

slebaL tegraT

:detnirP ...02 0040-TMG 30:93:31 42 guA deW

83

)CINIRFA( retneC noitamrofnI krowteN nacirfA

03

)EPIR( ertneC noitanidrooC krowteN EPIR

:detnirP ...02 0040-TMG 65:63:31 42 guA deW

Time in networks •  Timestamps

–  e.g. Facebook: friends added and removed over >me

•  Dura>on

–  e.g. Spending >me with friends

•  Frequency

–  e.g. Friends, colleagues, strangers

•  Time-‐order

–  e.g. Timetables in public transport systems 5

Temporal Graph

t=1

t=2

t=3

Temporal Graph

t=1

t=2

t=3

Temporal Graph

t=1

t=2

• Sta>c • Shortest path (A,G) = [A,B,D,E,G] • Shortest path length (A,G) = 4 hops

t=3

Temporal Graph

t=1

t=2

• Sta>c • Shortest path (A,G) = [A,B,D,E,G] • Shortest path length (A,G) = 4 hops • Temporal • Shortest path (A,G) = [A,C,B,D,E,F,G] • Shortest path length (A,G) = 6 hops • Time=3 seconds

t=3

Temporal Measures •  d ij = Shortest Temporal Path Dura>on •  d ∗ = Number of Hops in shortest temporal path ij

•  1 Temporal Efficiency of communica>on Eij =

dij

Temporal Measures •  Average Temporal Path Dura>on

L=

1 N (N −1)

�

1 N (N −1)

�

•  Average Temporal Path Hops

L = ∗

•  Average Temporal Efficiency Eglob =

1 N (N −1)

ij

dij

∗ d ij ij

�

ij

Eij

Does it really maHer? •  •  •  • 

Infocom 2005 conference environment Bluetooth coloca>on scans 5 Minute Windows Measure 24 hours star>ng 12am Sta$c

Temporal

Day

N

Ac$vity

Contacts

L

1

37

25.73

6pm-‐12pm

3668

1.291

0.856

4.090

19h 39m

0.003

2

39

28.31

12am-‐12pm 8357

1.269

0.870

4.556

9h 6m

0.024

3

38

22.32 12am-‐12pm 4217

1.420

0.798

4.003

10h 32m

0.018

4

39

21.44

1.444

0.781

4.705

9h 55m

0.013

12am-‐5pm

3024

Eglob

L*

L

Eglob

Temporal Centrality Measures •  Sta>c Closeness and Betweenness based on sta$c shortest paths •  Reformalise closeness and betweenness with temporal paths: –  Dura>on –  Time Order –  Frequency

Temporal Closeness W is the number of temporal windows

� 1 Cih = dhi,j W (N − 1) j�=i∈V

(2 + 2) + (3 + 3 + 3) CA = = 0.867 (3 ∗ (6 − 1)) B A

C

E F D

1

2 Time

3

Temporal Betweenness •  Using temporal path length

A

B

1

2

C 3 Time

4

5

Number of temporal shortest paths through B for which at >me 4 B was carrying a message

6

Evalua>ng Centrality •  Two perspec>ves:

–  Seman>c: known roles of nodes –  Dynamic Processes: mobile malware containment

Enron in the News

$

Public Inves>ga>on •  •  •  • 

Telephone logs Documents Financials Emails -‐ 151 user mailboxes -‐ May 1999 to Jun 2002 -‐ 250,000 emails -‐ NOT anonymised

Seman>cs ID 009 013 017 048 053 054 067 073 075 107 122 127 139 147 150

Role (Unknown) Legal Manager Executive Trader President Vice President Trader Director of Trading Trader Managing Director Manager Director Trader Secretary

Seman>cs ID 9 13 17 48 53 54 67 73 75 107 122 127 139 147 150

Name Stephanie Panus Marie Heard Mike Grigsby Tana Jones John Lavorato Greg Whalley Sara Shackleton Jeff Dasovich Gerald Nemec Louise Kitchen Sally Beck Kenneth Lay Mary Hain Carol Clair Liz Taylor

Role (Unknown) Legal Manager Executive Trader President Vice President Trader Director of Trading Trader Managing Director Manager Director Trader Secretary

•  Big bonuses linked with informa>on mediators

Mobile Phone Malware

Mobile Malware Propaga>on •  Long Range

–  Sms, mms, email –  Can be filtered by central service provider

•  Short Range

–  Bluetooth, wifi –  Evades central service provider

Limita>ons •  Devices

–  Resource constrained

•  Infrastructure

–  Limited bandwidth

•  Priori>se Devices using SNA

–  Patch individual devices via nodes with high Betweenness –  Flood patch via nodes with high Closeness

Priority Patching Schemes 1.  Tradi>onal Patching

➔ Can we block path of malware? ➔ Betweenness

2.  Opportunis>c Patching

➔ Can we compete with malware? ➔ Closeness

Patching Nodes

Flood Network with Patch

Flood Network with Patch Area under Curve (AUC)

Peak Infected Nodes

Imax

Complete patch >me

τ

Opportunis>c Patching

Malware Start Time

Patch Delay

1. Finite Time

Opportunis>c Patching 2. Sta>c is Poor

Malware Start Time

3. Temporal is Best

Patch Delay

Sta>c Small World •  Graphs which both are locally clustered but with small average path length

–  High local clustering but long paths => Lahce –  Small average paths but low clustering => Random

Temporal Small World •  Does this hold in >me-‐varying graphs •  Temporal small world:

–  quick paths from one node to another and –  have some temporal local persistence of links

32

Tes>ng for Temporally Small World •  Measure

–  communica>on efficiency

•  Temporal shortest path length

–  speed of change

•  Temporal correla>on coefficient •  Measure persistence of links

•  Model

–  Recreate a slowly changing and quickly changing temporal graph –  Brownian mo>on with prob(jump) 33

Gt if it was already present in graph Gt−1 . To quantify this effect, following Ref. [19] we compute C, the average Coefficient o f topological overlap of the neighbor set of a node between Temporal lustering two successive graphs in theCsequence: C=

!

Ci 1 Ci = N T −1 i

CA = 1/2

T −1 " t=1

!

aij (t)aij (t + 1) #! ! [ j aij (t)][ j aij (t + 1)] j

(1) We name this metric the temporal-clustering coefficient of G. Node i Node i A B A fundamental concept in graph A theory B is that of geodesic, or shortest path. In a static graph, a shortest path nodes i F and j is defined D C E between D of minC as a path E F imal length between the two nodes. This is a sequence of adjacent nodes starting at i, ending at j, and visiting t1 t2 the minimum number of nodes. Finally, the distance between node i and node j is set equal to the length of the

te di no of an Fi

th tim gr A (b ita gr wo G, gr es

Temporal SW Model •  N Random Walkers with Prob Jumping Pj Pj=0.0!

Pj=0.5!

Pj=1.0!


Pj=0.5!

Pj=1.0!


Pj=0.5!

Pj=1.0!

Temporal Small World •  Graphs which evolve slowly over >me can s>ll exhibit high communica>on efficiency

–  Highly temporal-‐clustering => non-‐jumping model –  Low temporal-‐delay => fully-‐jumping model

movement. Each time-varying graph has N = 16 nodes, representing cortical regions of interest, and consists in a time sequence of T = 100 directed unweighted graphs, where the directed links represent causal influences between cortical regions (see Ref. [13] for details). We have

Small-‐world Behaviour in Real Data 0.1

1

Brain network length and temporalraphs produced by the of the probability pj of s we have set N =contacts 100, Bluetooth produced (INFOCOM’06) sequences of mporal path length of dashed line.

C

C rand

L

α β γ δ

0.44 0.40 0.48 0.44

0.18 0.17 0.13 0.17

3.9 (100%) 6.0 (94%) 12.2 (86%) 2.2 (100%)

d1 d2 d3 d4

0.80 0.78 0.81 0.83

0.44 8.84 (61%) 0.35 5.04 (87%) 0.38 9.06 (57%) 0.39 21.42 (15%)

Mar Jun Sep Dec

0.044 0.046 0.046 0.049

0.007 0.006 0.006 0.006

456 380 414 403

Lrand

E

E rand

0.50 0.41 0.39 0.57

0.48 0.45 0.37 0.56

6.00 (65%) 4.01 (88%) 6.76 (59%) 15.55(22%)

0.192 0.293 0.134 0.019

0.209 0.298 0.141 0.028

451 361 415 395

0.000183 0.000047 0.000058 0.000047

0.000210 0.000057 0.000074 0.000059

4.2 3.6 8.7 2.4

(98%) (92%) (89%) (92%)

- We first illustrate (London network) in a network model ple motion rules. We lkers which move in TABLE I: Temporal-clustering, characteristic temporal path size D with a fixed length and efficiency for brain cortical networks (subject 1, long-distance jumps and four band frequencies) [13], for the social interaction

Summary •  We have introduced metrics for >me varying social networks •  We have shown examples of use on real networks

References •  •  •  •  •  •  • 

Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo and Vito Latora. Graph Metrics for Temporal Networks. Book Chapter in PeHer Home and Jari Saramaki (Editors). Temporal Networks. Springer. 2013. John Tang, Ilias Leon>adis, Salvatore Scellato, Vincenzo Nicosia, Cecilia Mascolo, Mirco Musolesi and Vito Latora. Applica$ons of Temporal Graph Metrics to Real-‐World Networks. Book Chapter in PeHer Holme and Jari Saramaki (Editors). Temporal Networks. Springer. 2013. J. Tang, S. Scellato, M. Musolesi, C. Mascolo and V. Latora. Small-‐world behavior in $me-‐varying graph In Physical Review E. Vol. 81 (5), 055101. May 2010. J. Tang, M. Musolesi, C. Mascolo, V. Latora, V. Nicosia. Analysing Informa$on Flows and Key Mediators through Temporal Centrality Metrics. In Proc. of the 3rd Workshop on Social Network Systems (SNS 2010). Apr 2010. J. Tang, M. Musolesi, C. Mascolo and V. Latora. Temporal Distance Metrics for Social Network Analysis. In Proc, of the 2nd ACM SIGCOMM Workshop on Online Social Networks (WOSN09). Aug 2009. J. Tang, C. Mascolo, M. Musolesi, V. Latora. Exploi$ng Temporal Complex Network Metrics in Mobile Malware Containment. In Proc. of the IEEE 12th Interna>onal Symposium on a World of Wireless, Mobile and Mul>media Networks (WoWMoM2011). Jun 2011. V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, V. Latora. Components in $me-‐varying graphs. In AIP Chaos. Vol.22 Issue 2. 2012.

TEMPORAL NETWORKS ANALYSIS

Recommend Documents