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.

2 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?

3 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.

4 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(".)

5 /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.

6 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.

7 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).

8 The nodes with higher indegree is more prestigious (choicesreceived).LetA Rn nbe the adjacency matrix of a directed graph. 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)

9 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) 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(".)

10 /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)