Report

Chapter 8 Embedding Introduction Density Reciprocity Transitivity Clustering Group-external and group-internal ties Krackhardt's graph theoretical dimensions of hierarchy Unit of analysis Micro Actor: People Dyad 环境 Triad Subgroups Organizations Collectives/aggregat es Communities Nation-states Macro/aggregates 组织 团体 个体 个体是镶嵌在网络中，而个体 所镶嵌的网络是镶嵌在更高层 3 及的网络中。 Dyad 两人组 Binary ties-present, or absent Directed relations 有无关系？是否是双向关系？(reciprocal) 还是单向(asymmetrical)？ Density The more actors are connected to one another, the more dense the network will be. Binary data: the number of present ties/the number of all possible ties Undirected network: n(n-1)/2 = 2n-1 possible pairs of actors. L Δ = n ( n 1) / 2 Directed network: n(n-1)*2/2 = 2n-2possible lines. ΔD = L n ( n 1) Valued data: the average strength of ties across all possible ties Density 1 3 5 1 1 3 1 5 1 1 Density=4/(3*2) Reciprocity Directed data, four possible dyadic relations • Actor: reciprocity pair (AB)/ all possible pairs (AB, BC, AC) • Dyad method: the number of pairs with a reciprocity tie/the number of pairs with any tie. (AB)/(AB, BC) Relations: reciprocal tie(AB, BA)/all possible pairs (AB, BA, BC, CB, AC, CA) • Arc method: The number of reciprocal ties/ total number of actual ties (AB,BA)/(AB, BA, BC) Reciprocity Dyad method Triad 三人组 Un-directed data, four possible types of triadic relations Directed-data, 16 possible types of triadic relations Tu = the number of triads that belong to isomorphism class u 9 Cg3 T=(T003, T012, ...,T300)‟ =(003, 012, 102, 021D, 021U, 021C, 111D, 111U, 030T, 030C, 201, 120D, 120U, 120C, 210, 300) Transtivity Clustering “6-degrees” phenomenon, How close actors are together “Clique-like” local neighborhood, the tendency towards dense local neighborhoods. Clustering: the density in neighborhood Weight, possible number of pairs Group-external and group-internal ties Measure of group based on comparing the numbers of ties within groups and between groups. E-I Index This value can range from 1 to -1, but for a given network density and group sizes its range may be restricted and so it can be rescaled. The index is also calculated for each group and for each individual actor. =36/(14+50) =42/(66+24) Krackhardt's graph theoretical dimensions of hierarchy Krackhardt argues that an ‘Outree” is the archetype of hierarchy. Krackhardt focuses on 4 dimensions: 1) Connectedness 2) Digraph hierarchic 3) digraph efficiency 4) least upper bound (what are the allowed triad types for an out-tree?) Connectedness: The digraph is connected if the underlying graph is a component. We can measure the extent of connectedness through reachability. V Connectedn ess 1 N ( N 1) / 2 Where V is the number of pairs that are not reachable, and N is the number of people in the network. How to calculate Connectedness: 1 4 2 3 5 1 2 3 4 5 Digraph: 1 2 3 4 5 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 Graph: 1 2 3 4 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 5 0 0 0 0 0 1 2 3 4 5 Reach: 1 2 3 4 0 1 2 1 1 0 1 2 2 1 0 3 1 2 3 0 0 0 0 0 V = # of zeros in the upper diagonal of Reach: V = 4. C = 1 - [4/((5*4)/2)] = 1 - 4/1 = .6 5 0 0 0 0 0 How to calculate Connectedness: 1 4 2 3 5 1 2 3 4 5 Reach: 1 2 3 4 0 1 2 1 1 0 1 2 2 1 0 3 1 2 3 0 0 0 0 0 This is equivalent to the density of the reachability matrix. 5 0 0 0 0 0 Reachable: 1 2 3 4 5 1 0 1 1 1 0 2 1 0 1 1 0 3 1 1 0 1 0 4 1 1 1 0 0 5 0 0 0 0 0 D = SR/(N(N-1)) = 12 /(5*4) = .6 Graph Hierarchy: The extent to which people are asymmetrically reachable. Graph Hierarchy V 1 max( V ) Where V is the number of symmetrically reachable pairs in the network. Max(V) is the number of pairs where i can reach j or j can reach i. Graph Hierarchy: An example 1 4 2 3 5 1 2 3 4 5 Digraph: 1 2 3 4 5 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 1 0 0 0 0 0 V=1 Max(V) = 4 H = 1/4 = .25 Dreach 2 3 4 1 2 1 0 1 0 1 0 0 0 0 0 0 0 0 5 0 0 0 0 0 1 2 3 4 5 Dreachable 1 2 3 4 5 0 1 2 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 Graph Efficiency: The extent to which there are extra lines in the graph, given the number of components. V Graph effi ciency 1 max( V ) Where v is the number of excess links and max(v) is the maximum possible number of excess links The minimum number of lines in a connected component is N-1 (assuming symmetry, only use the upper half of the adjacency matrix). Graph Efficiency: In this example, the first component contains 4 nodes and thus the minimum required lines is 3. There are 4 lines, and thus V1= 4-3 = 1. 1 4 2 1 6 3 5 7 2 The second component contains 3 nodes and thus minimum connectivity is = 2, there are 3 so V2 = 1. Summed over all components V=2. The maximum number of lines would occur if every node was connected to every other, and equals N(N-1)/2. For the first component Max(V1) = (6-3)=3. For the second, Max(V2) = (3-2)=1, so Max(V) = 4. Efficiency = (1- 2/4 ) = .5 Graph Efficiency: Steps to calculate efficiency: a) identify all components in the graph b) for each component (i) do: i) calculate Vi = S(Gi)/2 - Ni-1; ii) calculate Max(Vi) = Ni(Ni-1) - (Ni-1) c) V = S(Vi), Max(V)= S(Max(Vi) d) efficiency = 1 - V/Max(V) Substantively, this must be a function of the average density of the components in the graph. Least Upper Boundedness: This condition looks at how many ‘roots’ there are in the tree. The LUB for any pair of actors is the closest person who can reach both of them. In a formal hierarchy, every pair should have at least one LUB. E H B F A G C D In this case, E is the LUB for (A,D), B is the LUB for (F,G), H is the LUB for (D,C), etc. Graph Theoretic Dimensions of Informal Organizations Least Upper Boundedness: You get a violation of LUB if two people in the organization do not have an (eventual) common boss. Here, persons 4 and 7 do not have an LUB. Least Upper Boundedness: Calculate LUB by looking at reachability. 1 2 3 4 5 6 7 8 9 Distance matrix 1 2 3 4 5 6 7 8 9 1 1 1 2 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 3 4 5 6 7 8 9 Reachable matrix 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (Note that I set the diagonal = 1) A violation occurs whenever a pair is not reachable by at least one common node. We can get common reachability through matrix multiplication Graph Theoretic Dimensions of Informal Organizations Least Upper Boundedness: Calculate LUB by looking at reachability. 1 2 3 4 5 6 7 8 9 Reachable Trans 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 X 1 2 3 4 5 6 7 8 9 Reachable matrix 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (R by S) (S by R) R`*R = CR = 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 0 0 0 1 Common Reach 2 3 4 5 6 7 8 1 1 1 1 0 0 0 2 1 2 2 0 0 0 1 2 1 1 0 0 0 2 1 3 2 0 0 0 2 1 2 3 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 2 1 0 0 0 0 1 1 2 1 2 1 1 1 2 1 9 1 1 2 1 1 1 2 1 5 (R by R) Any place with a zero indicates a pair that does not have a LUB. Least Upper Boundedness: Calculate LUB by looking at reachability. V LUB 1 max( V ) Where V = number of pairs that have no LUB, summed over all components, and: Max (V n ) ( N n 1)( N n 2 ) 2 Bearman, Peter S., James Moody, and Katherine Stovel. "Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks1." American Journal of Sociology 110.1 (2004): 44-91.