Report

A Set of Measures of Centrality Based on Betweenness Linton C. Freeman, 1977 Advisor : Professor Frank Y. S. Lin Presented by: Tuan-Chun Chen Presentation date: Mar. 13, 2012 Agenda Introduction Measuring point centrality Measuring graph centrality Applications Agenda Introduction Measuring point centrality Measuring graph centrality Applications Introduction Betweenness : A point in a communication network is central to the extent that it falls on the shortest path between pairs of other points. (Bavelas, 1948) Another viewpoint by Shimbel (1953): If we count all of the minimum paths which pass through a site, then we have a measure of the ‘stress’ which the site must undergo during the activity of the network. Agenda Introduction Measuring point centrality Measuring graph centrality Applications Measuring Point Centrality Shaw (1954) Unordered pair of points {pi, pj} {pi, pj} are Unreachable or there are one or more paths between them. pk pi pj Measuring Point Centrality A point falling between two others can facilitate, block, distort or falsify communication between the two. But if it falls on some but not the shortest path connecting a pair of points , its potential for control is more limited. pk pi pj Measuring Point Centrality Define “partial betweenness” If pi and pj are not reachable from each other, pk is not between them. let bij ( p k ) 0 If pi and pj are reachable. bij ( p k ) ( 1 g ij )( g ij ( p k )) gij The number of geodesics linking pi and pj. gij(pk) The number of geodesics linking pi and pj that contain pk. Measuring Point Centrality p2 and p4 each have a probability of ½ of falling between p1 and p3. b13 ( p 2 ) ( 1 )(1) 1 2 2 p3 p2 p4 p1 Measuring Point Centrality Determine overall centrality of a point: n cB ( pk ) n b ij ( pk ) i j i j CB(pk) An index of the over all partial betweenness of point pk. n The number of points in the graph. Measuring Point Centrality Its magnitude depends upon two factors: 1) the arrangement of edges in the graph that define the location of pk with respect to geodesics linking pairs of points. 2) the number of points in the graph. Measuring Point Centrality Problem ! ? Example: A graph containing 5 points, CB(pi)=6. A graph containing 25 points, CB(pj)=6. They have the same potential for control in absolute terms, but differ markedly in their relative potential for control. Measuring Point Centrality Maximum Value: C m ax [ n ( n 1)] 2 pk n pi pj ph n 3n 2 2 [ n 1] 2 The number of points in the graph. Measuring Point Centrality The relative centrality of any point in a graph, expressed as a ratio : C 'B ( p k ) 2C B ( pk ) n 3n 2 2 , 0 C 'B ( p k ) 1 When C’B(pk)=1, the graph is a star or a wheel. Agenda Introduction Measuring point centrality Measuring graph centrality Applications Measuring Graph Centrality A network is central to the degree that a single point can control its communication.(Measures of graph centrality based upon the dominance of one point.) n C 'B [C B '( p k *) C B '( p i )] i 1 n 1 , 0 C 'B 1 C’B(pk*) The largest centrality value associated with any point in the graph. C’B(pi) The centrality value of pi n The number of points in the graph. Agenda Introduction Measuring point centrality Measuring graph centrality Applications Applications Original application was in the study of communication in small groups. Speed, activity and efficiency in solving problems and personal satisfaction and leadership in small group setting(Leavitt 1951). Study of the diffusion of a technological innovation in the steel industry(Czepiel 1974) Examined the impact of centrality on urban growth(Pitts 1965). Discussing the design of organization(Beauchamp 1965)(Mackenzie 1966) Applications Consider the relationship between point centrality and personal satisfaction in Leavitt’s(1951) study of small group problem solving. Each participant had a piece of information necessary for the solution of a problem. Each could communicate only with designated others. Leavitt measured point centrality as a function of the lengths of paths or the distance between points. Applications Thanks for your attention！