Network Observational Methods and�Quantitative Metrics: II�• Whitney topics�– Community structure (some done already in Constraints -I) – The Zachary Karate club story�– Degree correlation – Calculating degree correlation for simple regular structures like trees and grids 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 1Clustering or Grouping Metrics�•� Community structure – Seek to find tightly connected subgroups within a larger network •� Clustering coefficient –�Measure the extent to which nodes link to each other in triangles –�Are your friends friends? –�Clusters are often called “modules” by network researchers and are also associated by them with function •� Assortativity and disassortativity (AKA degree correlation) –�Do highly linked nodes (“hubs”) link to each other (assortative) or do they link with weakly linked nodes (disassortative) •� Average (shortest) path length (AKA geodesic) –�How far apart are nodes –�Max geodesic is called network diameter 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006�2Community-finding and Pearson�Coefficient r�•�Technological networks seem to have r < 0�•�Social networks seem to have r > 0 •�Newman and Park sought an explanation in community structure and clustering •�Their algorithm for finding communities looks like a flow algorithm •�Zachary used a flow algorithm to find the communities in the Karate Club 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006�3Summary Properties of Several Big�Networks (Newman) SOCIALFilm actorsCompany directorsMath coauthorshipPhysics coauthorshipBiology coauthorshipTelephone call graphE-mail messagesE-mail address booksStudent relationshipsSexual contactsNetwork Type n m z l C(1)C(2)rαINFORMATIONWWW nd.eduWWW AltavistaCitation networkRoget's ThesaurusWord co-occurrenceTECHNOLOGICALInternetPower gridTrain routesSoftware packagesSoftware classesElectronic circuitsPeer-to-peer networkBIOLOGICALMetabolic networkProtein interactionsMarine food webFreshwater food webNeural networkundirectedundirectedundirectedundirectedundirectedundirecteddirecteddirectedundirectedundirecteddirecteddirecteddirecteddirectedundirectedundirectedundirectedundirecteddirecteddirectedundirectedundirectedundirectedundirecteddirecteddirecteddirectedBasic statistics for a number of published networks. The properties measured are: type of graph, directed or undirected; total number of vertices n; total number of edges m; mean degree z; mean vertex-vertex distance l; exponent α of degree distribution if the distribution follows a power law (or "-" if not; in/out-degree exponents are given for directed graphs); clustering coefficient C(1); clustering coefficient C(2); and degree correlation coefficient r. Blank entries indicate unavailable data.44991376732533395290915202514700000059912168815732810269504203549046783339102246090210697494158714391377240978807652115135923072551648255392496489245300118030648000000086300570294771497135213000000067161985103170000003199265941960317232213532481296368622405989972359113.4314.443.929.2715.533.161.443.381.665.5510.468.574.9970.135.982.6766.791.201.614.341.479.642.124.4310.847.683.484.607.576.194.924.955.2216.0111.2716.184.873.3118.992.162.421.5111.054.282.566.802.051.903.972.3----2.11.5/2.0--3.22.1/2.42.1/2.73.0/--2.72.5--1.6/1.4-3.02.12.22.4---0.200.590.150.450.0880.170.0050.110.130.0350.100.0700.0330.0100.0120.0900.0720.160.200.180.780.880.340.560.600.160.130.0010.290.150.440.390.0800.690.0820.0120.0300.0110.670.0710.230.0870.280.2080.2760.1200.3630.1270.092-0.029-0.0670.157-0.189-0.003-0.033-0.016-0.119-0.154-0.366-0.240-0.156-0.263-0.326-0.226Figure by MIT OCW.Calculating r�12345# x y1 2 31 2 22 3 12 3 22 3 23 1 34 2 34 2 35 2 25 2 2! r =x " x ( )y " y ( )#x " x ( )2#y " y ( )2#! x = 2y = 2r = -0.676752968 using Pearson function in Excel Note: if all nodes have the same k then r = 0/0�3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 5�n=1�binary tree with n=52 32 33 23 33 33 23 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 13 13 33 13 13 33 13 13 33 13 13 33 13 13 33 13 13 33 13 13 33 13 11 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 rows like this - ignoren=2 6 rows like this - ignore All other rows like this12345n=3 except last two sets 2n-2 rows of 3-3n=4 2*2n-2 rows of 3-1 3-3 means 3-1 = 1-3 and means ! 3 " x ( )2n=5 2n-1 rows of 3-1 Census of Pairs for�Pure Binary Tree�! 3 " x ( )1" x ( )3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 6Result of Census�Sum of row entries = �Total number of rows = = ksum�! ki= 2n +1+ 4"! ki2= 10 * 2n"1"14#! " x =k2#k#= 2.5 in the limit of large n<k>=2 Total 2n rows of 3-1Approx (ksum - 2n) rows of 3-3r = - 0.4122 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 7�Closed Form Results�Property Pure Binary Tree Binary Tree with Cross-linking ksum ! 2n +1" 4 ! 3*2n"10 ksqsum ! 10 * 2n"1"14 ! 13* 2n" 64 ! x ! # 2.5 as n becomes large (>~ 6) ! #133 as n becomes large (>~ 6) Pearson numerator ! ~ 2n(3 " x )(1" x ) + (ksum " 2n)(3 " x )2 ! ~ 2n(5 " x )(1" x ) + (ksum " 2n)(5 " x )2 Pearson denominator ! ~ 2n"1(1" x )2+ (ksum " 2n"1)(3 " x )2 ! ~ 2n"1(1" x )2+ (ksum " 2n"1)(5 " x )2 ! r ! # "13 as n becomes large ! # "15 as n becomes large l ! r =16(2 " x )(3 " x ) + 8(l " 3)(3 " x )22(2 " x )2+ 12(l " 2)(3 " x )2#231234512345Note: Western Power Grid r = 0.0035 Bounded grid 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 8�Nested Self-Similar Networks�nestedr = - 0.25, c = 0.625nested2r = - 0.0925, c = 0.5500Probably, r = 0 in the limit as the network grows 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 9Tree with Diminishing Branching Ratio�16 times8 times4 times1 node with k = 1616 nodes with k = 98*16 = 128 nodes with k = 54*8*16 = 512 nodes with k = 32*4 *8*16 = 1024 nodes with k = 12 timesr = 0.38166 3/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 10�Toy Networks with Positive and�Negative r�12345789101112136r = 0.43301516171819202114r = - 0.443412345789101112 136151617181920 21143/20/06 Quantitative Metrics II © Daniel E Whitney 1997-2006 11�Toward Matlab for Pearson (symmetric)�! r =x " x ( )y " y ( )#x " x ( )2#y " y ( )2#Look at numerator, ignore xbar for the moment�! xiyj( )= xi'"ijyj= x'Ax#! "ij= 1 if i links to j"ij= 0 if i does not link to jEssentially the
View Full Document
Unlocking...