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

《签订房屋租赁合同的十大注意事项.pptx》由会员分享，可在线阅读，更多相关《签订房屋租赁合同的十大注意事项.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 centralityna p

8、aper 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?How

9、 much variation is there in the centrality scores among the nodes?maximum value in the network11degree centralization examplesCD CD CD 12degree centralization examplesexample financial trading networkshigh centralization: one node trading with many otherslow centralization: trades are more evenly di

10、stributed13when 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 nBetweenness centralitynCloseness

11、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 connecting j-k, and gjk

12、= 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-1)*(N-2)betweenness on

13、 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 credit18betweenness on toy netw

14、orksnnon-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? 21betweenness on toy netwo

15、rksnnon-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 computationsnSlight variations in ge

16、odesic 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 ranking similar to geodesic

17、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 modification: when normal

18、izing, 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 not necessarily lie on

19、 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 still wants to be in th

20、e “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: definition28depends on inverse dista

21、nce 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 t

22、o closeness?31Closeness centralitynValues tend to span a rather small dynamic rangentypical distance increases logarithmically with network sizenIn a typical network the closeness centrality C might span a factor of five or lessnIt is difficult to distinguish between central and less central vertice

23、sna small change in network might considerably affect the centrality ordernAlternative computations exist but they have their own problems32Influence rangenThe influence range of i is the set of vertices who are reachable from the node i33Extensions of undirected closeness centralityncloseness centrality usually impliesnall paths should lead to younpaths should lead from you to everywhere else nusually consider only vertices from which the node i in question can be reached34