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

1、Lecture 5:Network centralitySlides are modified from Lada Adamic太原房产网 52youju.Measures and MetricsKnowing the structure of a network, we can calculate various useful quantities or measures that capture particular features of the network topology.basis of most of such measures are from social network

2、 analysisSo far,Degree distribution, Average path length, DensityCentralityDegree, Eigenvector, Katz, PageRank, Hubs, Closeness, Betweenness, .Several other graph metricsClustering coefficient, Assortativity, Modularity, 2.Characterizing networks:Who is most central?work centralityWhich nodes are mo

3、st central?Definition of central varies by context/purposeLocal measure:degreeRelative to rest of network:closeness, betweenness, eigenvector (Bonacich power centrality), Katz, PageRank, How evenly is centrality distributed among nodes?Centralization, hubs and autthorities, 4.centrality: whos import

4、ant based on their network positionindegreeIn each of the following networks, X has higher centrality than Y according toa particular measureoutdegreebetweennesscloseness5.OutlineDegree centralityCentralization Betweenness centralityCloseness centralityEigenvector centralityBonacich power centrality

5、Katz centralityPageRankHubs and Authorities6.He who has many friends is most important.degree centrality (undirected)When is the number of connections the best centrality measure? people who will do favors for you people you can talk to (influence set, information access, ) influence of an article i

6、n terms of citations (using in-degree)7.degree: normalized degree centralitydivide by the max. possible, i.e. (N-1)8.Prestige in directed social networkswhen prestige may be the right wordadmirationinfluencegift-givingtrustdirectionality especially important in instances where ties may not be recipr

7、ocated (e.g. dining partners choice network)when prestige may not be the right wordgives advice to (can reverse direction)gives orders to (- -)lends money to (- -)dislikesdistrusts9.Extensions of undirected degree centrality - prestigedegree centralityindegree centralitya paper that is cited by many

8、 others has high prestigea person nominated by many others for a reward has high prestige10.Freemans general formula for centralization: (can use other metrics, e.g. gini coefficient or standard deviation)centralization: how equal are the nodes?How much variation is there in the centrality scores am

9、ong the nodes?maximum value in the network11.degree centralization examplesCD = 0.167CD = 0.167CD = 1.012.degree centralization examplesexample financial trading networkshigh centralization: one node trading with many otherslow centralization: trades are more evenly distributed13.when degree isnt ev

10、erythingIn what ways does degree fail to capture centrality in the following graphs?ability to broker between groupslikelihood that information originating anywhere in the network reaches you14.OutlineDegree centralityCentralization Betweenness centralityCloseness centrality15.betweenness: another c

11、entrality measureintuition: how many pairs of individuals would have to go through you in order to reach one another in the minimum number of hops?who has higher betweenness, X or Y?XY16.Where gjk = the number of geodesics connecting j-k, and gjk = the number that actor i is on.Usually normalized by

12、:number 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-1)*(N-2).betweenness on toy networksnon-normalized version:ABCEDA lies between no two other vertices

13、B lies between A and 3 other vertices: C, D, and EC lies between 4 pairs of vertices (A,D),(A,E),(B,D),(B,E)note that there are no alternate paths for these pairs to take, so C gets full credit18.betweenness on toy networksnon-normalized version:19.betweenness on toy networksnon-normalized version:2

14、0broker.Nodes 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? 21.betweenness on toy networksnon-normalized version:ABCEDwhy do C and D each have betweenness 1?They are b

15、oth on shortest paths for pairs (A,E), and (B,E), and so must share credit:+ = 1Can you figure out why B has betweenness 3.5 while E has betweenness 0.5?22.Alternative betweenness computationsSlight variations in geodesic path computationsinclusion of self in the computationsFlow betweenness Based o

16、n the idea of maximum flowedge-independent path selection effects the resultsMay not include geodesic pathsRandom-walk betweennessBased on the idea of random walks Usually yields ranking similar to geodesic betweennessMany other alternative definitions exist based on diffusion, transmission or flow

17、along network edges23.Extending betweenness centrality to directed networksWe now consider the fraction of all directed paths between any two vertices that pass through a nodeOnly modification: when normalizing, we have (N-1)*(N-2) instead of (N-1)*(N-2)/2, because we have twice as many ordered pair

18、s as unordered pairsbetweenness of vertex ipaths between j and k that pass through iall paths between j and k24.Directed geodesicsA node does not necessarily lie on a geodesic from j to k if it lies on a geodesic from k to jkj25.OutlineDegree centralityCentralization Betweenness centralityCloseness

19、centrality26.closeness: another centrality measureWhat if its not so important to have many direct friends?Or be “between othersBut one still wants to be in the “middle of things, not too far from the center27.Closeness is based on the length of the average shortest path between a vertex and all ver

20、tices in the graphCloseness Centrality:Normalized Closeness Centralitycloseness centrality: definition28depends on inverse distance to other vertices.closeness centrality: toy exampleABCED29.closeness centrality: more toy examples30.degree number of connectionsdenoted by sizeclosenesslength of shortest path to all othersdenoted by colorhow closely do degree and betweenness correspond to closeness?31.Closeness centralityValues tend to span a rather small dynamic rangetyp