Lecture 6: Quantitative Aspects Of Networks III: OutlineNetwork Analysis Terminology -notatedNetwork Metrics (from lectures 2 and 4)ConnectivitySocial Network AnalysisTransitivity or Clustering coefficient, CExample calculation of transitivity coefficientsTransitivity or Clustering coefficient, IICentralityDegree CentralityPadgett’s Florentine Families:15th Century Marriage RelationsFlorentine Families Centrality Metrics I: DegreeCloseness CentralityFlorentine Families Centrality Metrics II ClosenessBetweeness Centrality IDefinition of HierarchyFlorentine Families Centrality Metrics:BetweenessPadgett’s Florentine Families:15th Century Marriage RelationsBetweeness Centrality IIInformation CentralityFlorentine Families Centrality MetricsEigenvector Centrality-UCINETEigenvector Centrality (from Newman and Brin and Page)Florentine Families Centrality Metrics (with Eigenvector Centrality)Centrality IIRelated newer Centrality-like metricsPrestige and Acquaintance CalculationLecture 6: Quantitative Aspects Of Networks III: OutlineDegree DistributionsTwo nearly normal distributionsA heavily skewed distributionDegree Distributions IIComparison of Models with Structural Metrics : Degree distributionCentral Limit TheoremMarginal and Markov process definedPower laws are ubiquitousComparison of Models with Structural Metrics : Degree distributionDegree Distributions IIIDegree Distributions IVNetwork Metrics (from lectures 2, 4 and now lecture 6)Networks structural characteristics: Preliminary summary of resultsReferences for Lecture 6Professor C. Magee, 2006Page 1Lecture 6: Quantitative Aspects Of Networks III: Outline• Network Analysis Terminology notated• Connectivity• Some Social Network Concepts-intuition and calculation• transitivity (clustering)• centrality• degree, closeness, betweenness, information, eigenvector• prestige and acquaintance• degree distributions• skew (and non-skew) distributions• fitting power laws to observed data• the normality of power laws• truncation• Structural implications and growth assumptions• Examples of some metrics from broad Assign. # 3 “systems”• Project DiscussionProfessor C. Magee, 2006Page 2Network Analysis Terminology -notated• node (vertex), link (edge) CM2, • size, sparseness, metrics CM2• degree, average degree, degree sequence DW4• directed, simple DW4• geodesic, path length, graph diameter DW4• transitivity (clustering),connectivity, reciprocity CM6• centrality (degree, closeness, betweenness, information, eigenvector) CM6• prestige, acquaintance CM6• ideal graphs (star, line, circle, team) CM6• degree distribution, power laws, exponents, truncation, CM6• Models (random, “small world”, poisson, preferential attachment)• constraints, hierarchy, rewiring• community structure, cliques, homophily, assortative mixing, degree correlation coefficient• motifs, coarse- graining• navigation, search, epidemics and cascades• self-similarity, scale-free, scale-rich• dendograms, cladograms and relationship strengthProfessor C. Magee, 2006Page 3Network Metrics (from lectures 2 and 4)• n, the number of nodes • m, the number of links • 2m/n is the average degree <k> as the number of links on a givennode, k, is the degree. • m/[(n)(n-1)] or <k>/2(n-1)is the “sparseness” or normalized interconnection “density”• Path length, l∑≥−=jiijdnnl)1(211Professor C. Magee, 2006Page 4Connectivity• Fraction of nodes connected in a network• Of interest in resilience/robustness which we will cover in a later lecture and then an inverse path length definition is useful• Can also be of interest during network formation or as links areadded to a set of nodes• Is also of interest in community determination (or decomposition) as one tries to arrive at a disconnected set of groups by (for example) cutting as few links as possible• Statistical “percolation” models are often used in network formation and destruction studies and then a specific network model (for example, random) is applied to calculate connectivity.Professor C. Magee, 2006Page 5Connectivity:(For the Poisson random graph)See Newman, M. E. J. "The Structure and Function of Complex Networks." SIAM Review 45, no. 2 (2003): 167–256. Society for Industrial and Applied Mathematics.00 1Mean Degree zGiant Component Size SMean Component Size s<<2 3 4 50246810.510Mean component size (solid line), excluding the giant component if there is oneGiant componentsize (dotted line)Figure by MIT OCW.Professor C. Magee, 2006Page 6Social Network Analysis • Many structural metrics have been invented and used by Social Scientists studying social networks over the past 70+ years.• These are well-covered in Wasserman and Faust –Social Network Analysis (1994) The following slides cover a fewselected examples in one area from that book. The purpose is to give some feel for the application of such metrics which attempt to measure structural properties of direct interest for analysis• We should also note that transitivity (clustering) and almost all other metrics discussed in this lecture were familiar to and used by social network scientists before the recent upsurge in activity over the past 7 years.Professor C. Magee, 2006Page 7Transitivity or Clustering coefficient, C• Measures quantitatively the degree to which nodes which each have relationships with a common node are likely to have a direct relationship.nodesoftriplesconnectedofnumbernetworkintrianglesofnumberxC31=;12∑=iiCnCioncenteredtriplesofnumberinodetoconnectedtrianglesofnumberCi=Professor C. Magee, 2006Page 8Example calculation of transitivity coefficients This network has one triangle and eight connected triples, and therefore has a clustering coefficient, , of 3 x 1/8 = 3/8 The individual vertices have local clustering coefficients, of 1, 1, 1/6, 0 and 0, for a mean value, = 13/30.1C2CFigure by MIT OCW.See Newman, M. E. J. "The Structure and Function of Complex Networks." SIAM Review 45, no. 2 (2003): 167–256. Society for Industrial and Applied Mathematics.Professor C. Magee, 2006Page 9Transitivity or Clustering coefficient, II• (Almost) always > than expected from random networks thus offering some support for earlier assertions that real networks have some non-random “structure” (more later)• Thus, assessing transitivity is a quick check whether you have a random graph where C = <k>/n. Indeed the size dependence of transitivity
View Full Document
Unlocking...