资源描述
Measures 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 far,nDegree distribution,Average path length,DensitynCentralitynDegree,Eigenvector,Katz,PageRank,Hubs,Closeness,Betweenness,.nSeveral other graph metricsnClustering coefficient,Assortativity,Modularity,1Characterizing networks:Who is most central?2network centralitynWhich nodes are most 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,3centrality:whos important based on their network positionindegreeIn each of the following networks,X has higher centrality than Y according toa particular measureoutdegreebetweennesscloseness4OutlinenDegree centralitynCentralization nBetweenness centralitynCloseness centralitynEigenvector centralitynBonacich power centralitynKatz centralitynPageRanknHubs and Authorities5He 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 of an article in terms of citations(using in-degree)6degree:normalized degree centralitydivide by the max.possible,i.e.(N-1)7Prestige in directed social networksnwhen prestige may be the right wordnadmirationninfluencengift-givingntrustndirectionality especially important in instances where ties 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(-”-)ndislikesndistrusts8Extensions of undirected degree centrality-prestigendegree centralitynindegree centralityna paper that is cited by many others has high prestigena person nominated by many others for a reward has high prestige9Freemans 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 among the nodes?maximum value in the network10degree centralization examplesCD=0.167CD=0.167CD=1.011degree centralization examplesexample financial trading networkshigh centralization:one node trading with many otherslow centralization:trades are more evenly distributed12when 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 you13OutlinenDegree centralitynCentralization nBetweenness centralitynCloseness centrality14betweenness: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?XY15Where gjk=the number of geodesics connecting j-k,and gjk=the number that actor i is on.Usually normalized by:number of pairs of vertices excluding the vertex itselfbetweenness centrality:definitionbetweenness of vertex ipaths between j and k that pass through iall paths between j and kdirected graph:(N-1)*(N-2)16betweenness 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 credit17betweenness on toy networksnnon-normalized version:18betweenness on toy networksnnon-normalized version:broker19Nodes 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?20betweenness 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?21Alternative betweenness computationsnSlight 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 ranking similar to geodesic betweennessnMany other alternative definitions exist based on diffusion,transmission or flow along network edges22Extending betweenness centrality to directed networksnWe now consider the fraction of all directed paths between any two vertices that pass through a nodenOnly modification: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 pairsbetweenness of vertex ipaths between j and k that pass through iall paths between j and k23Directed geodesicsnA node does not necessarily lie on a geodesic from j to k if it lies on a geodesic from k to jkj24OutlinenDegree centralitynCentralization nBetweenness centralitynCloseness centrality25closeness:another centrality measurenWhat if its not so important to have many direct friends?nOr be“between”othersnBut one still wants to be in the“middle”of things,not too far from the center26Closeness is based on the length of the average shortest path between a vertex and all vertices in the graphCloseness Centrality:Normalized Closeness Centralitycloseness centrality:definitiondepends on inverse distance to other vertices27closeness centrality:toy exampleABCED28closeness centrality:more toy examples29ndegree nnumber of connectionsndenoted by sizenclosenessnlength of shortest path to all othersndenoted by colorhow closely do degree and betweenness correspond to closeness?30Closeness 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 verticesna small change in network might considerably affect the centrality ordernAlternative computations exist but they have their own problems31Influence rangenThe influence range of i is the set of vertices who are reachable from the node i32Extensions 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 reached33谢谢你的阅读v知识就是财富v丰富你的人生
展开阅读全文