Network Observational Methods and Quantitative Metrics: II •Topics – Degree correlation – Exploring whether the sign of degree correlation can be predicted from network type or similarity to regular structures, or details about the network itself, or maybe nothing – Calculating degree correlation for simple regular structures like trees and grids 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 1/24Summary Properties of Several Big Networks Degree Correlation2/16/2011 © Daniel E Whitney 1997-2010 2/24 Courtesy of Society for Industrial and Applied Mathematics. Used with permission. Table 2 in Mark E. J. Newman’s. “The Structure and Function of Complex Networks.” SIAM Review 45, no. 2 (2003): 167-256. (Newman)NetworkFilm actorsSocialInformationTechnologicalBiologicalCompany directorsMath coauthorshipPhysics coauthorshipBiology coauthorshipTelephone call graphEmail messagesEmail address booksStudent relationshipsSexual contactsWWW.nd.eduWWW.AltavistaCitation networkRoget's thesaurusWord co-occurrenceInternetPower gridTrain routesSoftware packagesSoftware classesElectronic circuitsPeer-to-peer networkMetabolic networkProtein interactionsMarine food webFreshwater food webneural networkDirectedDirectedDirectedDirectedDirectedDirectedDirectedDirectedDirectedDirectedDirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirectedUndirected 449, 913253, 33952, 9091, 520, 25147, 000, 00059, 91216, 8815732, 810269, 504203, 549, 046783, 339460, 90210, 6974, 9415871, 4391, 3772, 11513592307 2, 3599975982, 2403, 6861, 29653, 2482, 2131, 72319, 6036, 59431, 99217, 000, 0005, 1036, 716, 1982 ,130, 000, 0001, 497, 13547757, 02986, 30080, 000, 00011, 803, 064245, 300496, 48955, 39225, 516, 482 113.4314.443.929.2715.533.161.443.381.665.5510.468.574.9970.135.982.6766.791.201.614.341.472.564.2811.051.512.422.1618.993.314.8711.2716.1816.015.224.924.956.197.574.603.48 2.3 0.200.590.150.450.170.0050.110.130.0350.100.0700.0330.0100.0120.0900.0720.160.200.18 0.280.0870.230.0710.670.0110.0300.0120.0820.690.390.440.150.290.0010.130.160.600.560.340.880.78 0.2080.2760.1200.3630.1270.092-0.029-0.067-0.189-0.003-0.033-0.016-0.119-0.154-0.366-0.240-0.156-0.263-0.326-0.226 416, 4216, 35415539531836641686, 148119, 1572443517414, 34265, 26645321136311, 313311, 313107, 182105, 32320, 416Ref(s).8, 92722042122140.1570.0800.0883.22.11.5/2.02.1/2.42.1/2.72.72.51.6/1.43.02.12.22.43.0/______________6.802.051.903.972.129.644.4310.847.6824, 0978807651, 0227, 673Type n m z rl C(1)C(2)αUndirectedBasic statistics for a number of published networks. The properties measured are: type of graph, directed or undirected; total number of vertices n; total number ofedges 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) from Eq. (3); clustering coefficient C(2) from Eq. (6); and degree correlation coefficient r,Sec. III.F. The last column gives the citation(s) for the network in the bibliography. Blank entries indicate unavailable data.Image by MIT OpenCourseWare.Community-finding and Pearson Coefficient r • Newman says technological networks seem to have r < 0 while social networks seem to have r > 0 • Newman and Park sought an explanation in community structure and clustering: “Why Social Networks are Different From Other Kinds of Networks” Phys Rev E, 68, 036122 (2003) • Social networks can arise by people joining multiple groups and generating multiple connections • Networks derived from these multiple connections have positive r • Networks coauthconn and coauthwhole are from this paper – coauthconn is the connected portion with 147 nodes – coauthwhole has 42 clusters, smallest has 2 nodes, biggest has 5 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 3/24“Why Social Networks are Different” • “Left to their own devices, we conjecture, networks normally have negative values of r. In order to show a positive value of r, a network must have some specific additional structure that favors assortative mixing.” • Special structure that explains networks with r > 0: – Large clustering coeff compared to random network with same degree sequence – Community structure • (No special structure needed to explain r < 0) 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 4/24Degree Correlation © Daniel E Whitney 1997-2010Physics Coauthors Network 2/16/2011 5/24 coauthconn: r = 0.0159 coauthwhole: r = 0.1538 41 separate clustersWork with David Alderson • “Are Social Networks Really Different?” • ICCS 2006 paper, published in NECSI journal 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 6/24Our Observations • Data show a mixture of r > 0 and r < 0 for all kinds of networks (38 simple connected networks) • Many with r < 0 have community structure • There is a structural explanation for this, based on a structural property that all networks have: the variability of the degree sequence, but not related to category: social -technological • Can use it to show that certain networks cannot possibly have r > 0 • Also, some canonical structures have r < 0 or r > 0 and real networks share properties with these canonical structures: trees have r < 0 and grids have r > 0 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 7/24Degree Correlation2/16/2011 © Daniel E Whitney 1997-2010 8/24Full Range of rDegree Correlation © Daniel E Whitney 1997-2010Negative r 2/16/2011 9/24Positive r 2/16/2011 Degree Correlation © Daniel E Whitney 1997-2010 10/24More Data on r vs Network Type Network n m <k > fraction of nodes : k >x r C Random clustering coeff <k > /n Generalized random clustering coeff < k > n < k2 >−<k > < k >2 ⎡ ⎣⎢ ⎤ ⎦⎥ 2 Karate Club 34 78 4.5882 0.1471 -0.4756 0.5879 0.1349 0.2937 J. Tirole ŅErdos NetworkÓ 2 93 149 3.204 0.0645 -0.4412 0.5124 0.0345 0.2097 J. Stiglitz ŅErdos NetworkÓ 2 68 85 2.50 0.0882 -0.4366 0.7019 0.0368 0.1768 Scheduled Air Routes, US 249 3389 27.22 -0.39 0.64 0.109 Littlerock Lake food web* 92 997 10.837 0.337 -0.3264 0.256 0.117 0.1909 Grand Piano Action 1 key 71 92 2.59 0.197 -0.3208 0.1189 0.0365 0.0275 Santa Fe coauthors 118 198 3.3559 0.0593 -0.2916
View Full Document
Unlocking...