SocialNetworkAnalysis: CentralityMeasures - UNB

1 Social Network Analysis: Centrality MeasuresDonglei of Business Administration, University of New Brunswick, NB Canada FrederictonE3B 9Y2 Donglei Du (UNB)Social Network Analysis1 / 85 Table of contents1 Centrality measuresDegree centralityCloseness centralityBetweenness centralityEigenvectorPageRank2 Comparison among centrality measures3 ExtensionsExtensions to weighted networkExtensions to bipartitie networkExtensions to dynamic networkExtensions to hypergraph4 AppendixTheory of non-negative, irreducible, and primitive matrices:Perron-Frobenius theorem (Luenberger, 1979)-Chapter 6 Donglei Du (UNB)Social Network Analysis2 / 85 What is centrality? ICentrality measures address the question:"Who is the most important or central person in thisnetwork?"There are many answers to this question, depending on what wemean by to Scott Adams, the power a person holds in theorganization is inversely proportional to the number of keys onhis janitor has keys to every office, and no CEO does not need a key: people always open the door are a vast number of different centrality measures thathave been proposed over the Du (UNB)Social Network Analysis4 / 85 What is centrality?

2 IIAccording to Freeman in 1979, and evidently still true today:"There is certainly no unanimity on exactly what centrality is oron its conceptual foundations, and there is little agreement onthe proper procedure for its measurement."We will look at some popular Du (UNB)Social Network Analysis5 / 85 Centrality measuresDegree centralityCloseness centralityBetweeness centralityEigenvector centralityPageRank centrality..Donglei Du (UNB)Social Network Analysis6 / 85 Degree centrality for undirected graph IThe nodes with higher degree is more Rn nbe the adjacency matrix of a undirected Rnbe the degree vector. Lete Rnbe the all-onevector. Thenk=AeFor comparison purpose, we can standardize the degree bydividing by the maximum possible valuen is simply the number of nodes at distance simple, degree is often a highly effective measure of theinfluence or importance of a node:In many social settings people with more connections tend tohave more power and more Du (UNB)Social Network Analysis7 / 85 Degree centrality for undirected graph IIGroup-level centralization: degree, as an individual-levelcentrality measure, has a distribution which can be summarizedby its mean and variance as is commonly practiced in Du (UNB)Social Network Analysis8 / 85An example: The Padgett Florentine families:Business networkrm(list =ls())# clear memorylibrary(igraph)# load packagesload(".)

3 /R ")# load dataplot(padgett$PADGB)# plot the business graphACCIAIUOLALBIZZIBARBADORIBISCHERICA STELLANGINORIGUADAGNILAMBERTESMEDICIPAZZ IPERUZZIPUCCIRIDOLFISALVIATISTROZZITORNA BUOND onglei Du (UNB)Social Network Analysis9 / 85An example: the Padgett Florentinefamilies:Marriage networkplot(padgett$PADGM)# plot the marriage graphACCIAIUOLALBIZZIBARBADORIBISCHERICA STELLANGINORIGUADAGNILAMBERTESMEDICIPAZZ IPERUZZIPUCCIRIDOLFISALVIATISTROZZITORNA BUOND onglei Du (UNB)Social Network Analysis10 / 85An example: Degree centrality for the PadgettFlorentine families: business netowrk# calculate the degree centrality for business networkdeg_B <-degree(padgett$PADGB, loops = FALSE)sort(deg_B, decreasing = TRUE)## MEDICI GUADAGNI STROZZI ALBIZZI BISCHERI CASTELLAN PERUZZI##6443333## RIDOLFI TORNABUON BARBADORI SALVIATI ACCIAIUOL GINORI LAMBERTES##3322111##PAZZIPUCCI##10# calculate the standardized degree centralitydeg_B_S <-degree(padgett$PADGB, loops = FALSE)/(vcount(padgett$PADGM) - 1)sort(deg_B_S, decreasing = TRUE)## MEDICI GUADAGNI STROZZI ALBIZZI BISCHERI CASTELLAN PERUZZI## ## RIDOLFI TORNABUON BARBADORI SALVIATI ACCIAIUOL GINORI LAMBERTES## ##PAZZIPUCCI## Du (UNB)Social Network Analysis11 / 85An example: Degree centrality for the PadgettFlorentine families.

4 Marriage network# calculate the degree centrality for business networkdeg_M <-degree(padgett$PADGM, loops = FALSE)sort(deg_M, decreasing = TRUE)## MEDICI BARBADORI LAMBERTES PERUZZI BISCHERI CASTELLAN GINORI##5444332## GUADAGNIPAZZI SALVIATI TORNABUON ACCIAIUOL ALBIZZIPUCCI##2111000## RIDOLFI STROZZI##00# calculate the standardized degree centralitydeg_M_S <-degree(padgett$PADGM, loops = FALSE)/(vcount(padgett$PADGB) - 1)sort(deg_M_S, decreasing = TRUE)## MEDICI BARBADORI LAMBERTES PERUZZI BISCHERI CASTELLAN GINORI## ## GUADAGNIPAZZI SALVIATI TORNABUON ACCIAIUOL ALBIZZIPUCCI## ## RIDOLFI STROZZI## Du (UNB)Social Network Analysis12 / 85 Outdegree centrality and indegree prestige fordigraph IThe nodes with higher outdegree is more central (choices made).The nodes with higher indegree is more prestigious (choicesreceived).LetA Rn nbe the adjacency matrix of a directed graph.

5 Letkin,kout Rnbe the indegree and outdegree vectorsrespectively. Lete Rnbe the all-one vector. Thenkout=ATe(column sum ofA);kin=Ae(row sum ofA).Note: The adjacency matrix in directed graph has thecounter-intuitive convention whereAij=1iff there is a Du (UNB)Social Network Analysis13 / 85An examplerm(list=ls())#remove ALL objectslibrary(igraph)#Generate graph object from adjacency matrix: igraph has the regular meaningadj<-matrix(c(0, 1, 0, 1,0, 0, 0, 1,1, 1, 0, 0,0, 0, 1, 0),# the data elementsnrow=4,# number of rowsncol=4,# number of columnsbyrow = TRUE)# fill matrix by rowsg < (t(adj), mode="directed")# create igrpah object from adjacency matrixdegree(g, mode='in')## [1] 2 1 2 1degree(g, mode='out')## [1] 1 2 1 2plot(g)# plot the graph1234 Donglei Du (UNB)Social Network Analysis14 / 85 Closeness centrality for undirected graphThe farness/peripherality of a nodevis defined as the sum of itsdistances to all other nodesThe closeness is defined as the inverse of the (v) =1 i6=vdviFor comparison purpose, we can standardize the closeness by dividing bythe maximum possible value1/(n 1)If there is no (directed)

6 Path between vertexvandithen the totalnumber of vertices is used in the formula instead of the path more central a node is, the lower its total distance to all can be regarded as a measure of how long it will take tospread information fromvto all other nodes Du (UNB)Social Network Analysis15 / 85 Example: Closeness centrality for the PadgettFlorentine familiesrm(list =ls())# clear memorylibrary(igraph)# load packagesload("./R ")# load data# calculate the closeness centralitysort(closeness(padgett$PADGB), decreasing = TRUE)## MEDICI RIDOLFI ALBIZZI TORNABUON GUADAGNI BARBADORI STROZZI## ## BISCHERI CASTELLAN SALVIATI ACCIAIUOL PERUZZI GINORI LAMBERTES## ##PAZZIPUCCI## # calculate the standardized closeness centralityclose_B_S <-closeness(padgett$PADGB) * (vcount(padgett$PADGB) - 1)sort(close_B_S, decreasing = TRUE)## MEDICI RIDOLFI ALBIZZI TORNABUON GUADAGNI BARBADORI STROZZI## ## BISCHERI CASTELLAN SALVIATI ACCIAIUOL PERUZZI GINORI LAMBERTES## ##PAZZIPUCCI## Du (UNB)

7 Social Network Analysis16 / 85 Betweenness centralityBetweenness centrality quantifies the number of times a nodeacts as a bridge along the shortest path between two was introduced as a measure for quantifying the control of ahuman on the communication between other humans in a socialnetwork by Linton this conception, vertices that have a high probability to occuron a randomly chosen shortest path between two randomlychosen vertices have a high Du (UNB)Social Network Analysis17 / 85 Betweenness centrality IThe betweenness of a vertexvin a graphG:= (V,E)withVvertices is computed as follows:For each pair of vertices(s,t), compute the shortest pathsbetween each pair of vertices(s,t), determine the fraction of shortestpaths that pass through the vertex in question (here, vertexv).Sum this fraction over all pairs of vertices(s,t).More compactly the betweenness can be represented as:Betwenness(v) = s6=v6=t V st(v) stwhere stis total number of shortest paths from nodesto nodetand st(v)is the number of those paths that pass Du (UNB)Social Network Analysis18 / 85 Betweenness centrality IIThe betweenness may be normalized by dividing through thenumber of pairs of vertices not includingv, which for directedgraphs is(n 1)(n 2)and for undirected graphs is(n 1)(n 2) Du (UNB)Social Network Analysis19 / 85An example I123456 The node betweenness for thegraph on the Du (UNB)Social Network Analysis20 / 85 How to find the betweeness in the example?

8 For example: for node 2, the(n 1)(n 2)/2=5(5 1)/2=10terms in the summation in the order of 13, 14, 15, 16, 34, 35, 36, 45,46, 56 are11+01+01+01+01+12+01+01+01+01= the denominators are the number of shortest paths between pair ofedges in the above order and the numerators are the number of shortestpaths passing through edge 2 between pair of edges in the above Du (UNB)Social Network Analysis21 / 85 Betweenness centrality for the Padgett Florentinefamiliesrm(list =ls())# clear memorylibrary(igraph)# load packagesload("./R ")# load data# calculate the betweenness centralitysort(betweenness(padgett$PADGB ), decreasing = TRUE)## MEDICI GUADAGNI ALBIZZI SALVIATI RIDOLFI BISCHERI STROZZI## ## BARBADORI TORNABUON CASTELLAN PERUZZI ACCIAIUOLGINORI LAMBERTES## ##PAZZIPUCCI## # calculate the standardized Betweenness centralitybetw_B_S <- 2*betweenness(padgett$PADGB)/((vcount(pa dgett$PADGB) - 1)*(vcount(padgett$PADGB)-2))sort(betw_B _S, decreasing = TRUE)## MEDICI GUADAGNI ALBIZZI SALVIATI RIDOLFI BISCHERI STROZZI## ## BARBADORI TORNABUON CASTELLAN PERUZZI ACCIAIUOLGINORI LAMBERTES## ##PAZZIPUCCI## Du (UNB)Social Network Analysis22 / 85 Eigenvector centrality for undirected graph ILetxbe eigenvector of the largest eigenvalue of thenon-negative adjacency matrixAof the undirected graphG= (V,E).

9 The eigenvector centrality of nodeiis equal to the leadingeigenvectorxiof (column) stochastic matrixN:=AD 1(whose leading eigenvalue is 1):Nx=xConsider a particular nodeiwith its neighboring nodesN(i):xi= j N(i)xj= jAijxjDonglei Du (UNB)Social Network Analysis23 / 85 Eigenvector centrality for undirected graph IIThe eigenvector centrality defined in this way depends both onthe number of neighbors|N(i)|and the quality of itsconnectionsxj,j N(i).Donglei Du (UNB)Social Network Analysis24 / 85 Why the leading eigenvector?Suppose we want to choose an eigenvectorxto define acentrality measure, then a necessary condition isx R+ non-negative matrix, the leading eigenvector is non-negative(seeAppendix A (Slide 68)for background information on non-negative,irreducible and primitive matrices).Donglei Du (UNB)Social Network Analysis25 / 85A toy examplerm(list=ls())#remove ALL objectslibrary(igraph)#Generate graph object from adjacency matrix: igraph has the regular meaningadj<-matrix(c(0, 1, 0, 1,1, 0, 1, 1,0, 1, 0, 1,1, 1, 1, 0),# the data elementsnrow=4,# number of rowsncol=4,# number of columnsbyrow = TRUE)# fill matrix by rowsg < (adj, mode="undirected")# create igrpah object from adjacency matrixplot(g)# plot the graph1234 Donglei Du (UNB)Social Network Analysis26 / 85A toy exampleD <-diag(1/degree(g), 4)#degree diagonal matrixD##[,1] [,2] [,3] [,4]## [1,] ## [2,] ## [3,] ## [4,] <- adj %*% D# PageRank matrixN##[,1] [,2] [,3] [,4]## [1,] ## [2,] ## [3,] ## [4,] <-eigen(N)# find the eigenvalues and eigenvectorsy$val# the eigenvalues## [1] +00 $vec# the eigenvectors##[,1] [,2][,3][,4]## [1,] ## [2,] ## [3,] +00 ## [4,] Du (UNB)Social Network Analysis27 / 85 Eigenvector centrality for the Padgett Florentinefamiliesrm(list =ls())# clear memorylibrary(igraph)

10 # load packagesload("./R ")# load data# calculate the degree centralitysort(evcent(padgett$PADGB)[[1] ], decreasing = TRUE)## MEDICI STROZZI RIDOLFI TORNABUON GUADAGNI BISCHERI PERUZZI## +00 ## CASTELLAN ALBIZZI BARBADORI SALVIATI ACCIAIUOL LAMBERTESGINORI## ##PAZZIPUCCI## (evcent(padgett$PADGM)[[1]], decreasing = TRUE)## PERUZZI LAMBERTES CASTELLAN BARBADORI BISCHERI MEDICI GUADAGNI## +00 ## GINORI TORNABUONPAZZI SALVIATI ACCIAIUOL ALBIZZIPUCCI## ## RIDOLFI STROZZI## Du (UNB)Social Network Analysis28 / 85 PageRank centrality IGoogle s PageRank is a variant of the Eigenvector centralitymeasure for directed a nodeihas no outgoing link, we addd a self loop toisuch thatkini=kouti=1. ThereforeAii=1for such nodes inthe adjacency the diagonal matrix of outdegrees where each elementDii=kiDefine a column stochastic matrixN=AD 1 The PageRank centrality of nodeiis equal to the leadingeigenvectorxiof matrixN(The leading eigenvalue is 1):x=NxDonglei Du (UNB)Social Network Analysis29 / 85 PageRank centrality IINote: The adjacency matrix in directed graph has thecounter-intuitive convention whereAij=1iff there is a Du (UNB)Social Network Analysis30 / 85A toy example for the basic PageRankrm(list=ls())#remove ALL objectslibrary(igraph)#Generate graph object from adjacency matrix.