签订房屋租赁合同的十大注意事项

1、Lecture 5:Network centralitySlides are modified from Lada AdamicMeasures and MetricsnKnowing the structure of a network, we can calculate various useful quantities or measures that capture particular features of the network topology.nbasis of most of such measures are from social network analysisnSo

2、 far,nDegree distribution, Average path length, DensitynCentralitynDegree, Eigenvector, Katz, PageRank, Hubs, Closeness, Betweenness, .nSeveral other graph metricsnClustering coefficient, Assortativity, Modularity, 2Characterizing networks:Who is most central?3network centralitynWhich nodes are most

3、 central?nDefinition of central varies by context/purposenLocal measure:ndegreenRelative to rest of network:ncloseness, betweenness, eigenvector (Bonacich power centrality), Katz, PageRank, nHow evenly is centrality distributed among nodes?nCentralization, hubs and autthorities, 4centrality: whos im

4、portant based on their network positionindegreeIn each of the following networks, X has higher centrality than Y according toa particular measureoutdegreebetweennesscloseness5OutlinenDegree centralitynCentralization nBetweenness centralitynCloseness centralitynEigenvector centralitynBonacich power c

5、entralitynKatz centralitynPageRanknHubs and Authorities6He who has many friends is most important.degree centrality (undirected)When is the number of connections the best centrality measure?o people who will do favors for youo people you can talk to (influence set, information access, )o influence o

6、f an article in terms of citations (using in-degree)7degree: normalized degree centralitydivide by the max. possible, i.e. (N-1)8Prestige in directed social networksnwhen prestige may be the right wordnadmirationninfluencengift-givingntrustndirectionality especially important in instances where ties

7、 may not be reciprocated (e.g. dining partners choice network)nwhen prestige may not be the right wordngives advice to (can reverse direction)ngives orders to (- ” -)nlends money to (- ” -)ndislikesndistrusts9Extensions of undirected degree centrality - prestigendegree centralitynindegree centrality

8、na paper that is cited by many others has high prestigena person nominated by many others for a reward has high prestige10Freemans general formula for centralization: (can use other metrics, e.g. gini coefficient or standard deviation)CDCD(n*)CD(i)i1g(N 1)(N 2)centralization: how equal are the nodes

9、?How much variation is there in the centrality scores among the nodes?maximum value in the network11degree centralization examplesCD = 0.167CD = 0.167CD = 1.012degree centralization examplesexample financial trading networkshigh centralization: one node trading with many otherslow centralization: tr

10、ades are more evenly distributed13when degree isnt everythingIn what ways does degree fail to capture centrality in the following graphs?nability to broker between groupsnlikelihood that information originating anywhere in the network reaches you14OutlinenDegree centralitynCentralization nBetweennes

11、s centralitynCloseness centrality15betweenness: another centrality measurenintuition: how many pairs of individuals would have to go through you in order to reach one another in the minimum number of hops?nwho has higher betweenness, X or Y?XY16CB(i) gjk(i)/gjkjkWhere gjk = the number of geodesics c

12、onnecting j-k, and gjk = the number that actor i is on.Usually normalized by:CB(i) CB(i )/(n 1)(n 2)/2number of pairs of vertices excluding the vertex itselfbetweenness centrality: definition17betweenness of vertex ipaths between j and k that pass through iall paths between j and kdirected graph: (N

13、-1)*(N-2)betweenness on toy networksnnon-normalized version:ABCEDnA lies between no two other verticesnB lies between A and 3 other vertices: C, D, and EnC lies between 4 pairs of vertices (A,D),(A,E),(B,D),(B,E)nnote that there are no alternate paths for these pairs to take, so C gets full credit18

14、betweenness on toy networksnnon-normalized version:19betweenness on toy networksnnon-normalized version:20brokerNodes are sized by degree, and colored by betweenness. exampleCan you spot nodes with high betweenness but relatively low degree? What about high degree but relatively low betweenness? 21b

15、etweenness on toy networksnnon-normalized version:ABCEDnwhy do C and D each have betweenness 1?nThey are both on shortest paths for pairs (A,E), and (B,E), and so must share credit:n+ = 1nCan you figure out why B has betweenness 3.5 while E has betweenness 0.5?22Alternative betweenness computationsn

16、Slight variations in geodesic path computationsninclusion of self in the computationsnFlow betweenness nBased on the idea of maximum flownedge-independent path selection effects the resultsnMay not include geodesic pathsnRandom-walk betweennessnBased on the idea of random walks nUsually yields ranki

17、ng similar to geodesic betweennessnMany other alternative definitions exist based on diffusion, transmission or flow along network edges23Extending betweenness centrality to directed networksnWe now consider the fraction of all directed paths between any two vertices that pass through a nodenOnly mo

18、dification: when normalizing, we have (N-1)*(N-2) instead of (N-1)*(N-2)/2, because we have twice as many ordered pairs as unordered pairsCB(i) gjkj,k(i)/gjkbetweenness of vertex ipaths between j and k that pass through iall paths between j and kCB(i) CB(i)/(N 1)(N 2)24Directed geodesicsnA node does

19、 not necessarily lie on a geodesic from j to k if it lies on a geodesic from k to jkj25OutlinenDegree centralitynCentralization nBetweenness centralitynCloseness centrality26closeness: another centrality measurenWhat if its not so important to have many direct friends?nOr be “between” othersnBut one

20、 still wants to be in the “middle” of things, not too far from the center27Closeness is based on the length of the average shortest path between a vertex and all vertices in the graphCc(i) d(i, j)j1N1) 1).()(NiCiCCCCloseness Centrality:Normalized Closeness Centralitycloseness centrality: definition2

21、8depends on inverse distance to other verticesCc(A) d(A, j)j1NN 111 2 3 4411041 0.4closeness centrality: toy exampleABCED29closeness centrality: more toy examples30ndegree nnumber of connectionsndenoted by sizenclosenessnlength of shortest path to all othersndenoted by colorhow closely do degree and betweenness correspond to closeness?31Closeness centralitynValues tend to span a rather small