Tema 4 from jennypao39
guia word medidas de centralidada y dispercion
Doc medidas from jennypao39
en ingles
Degree centrality [ edit]
Main article: Degree ( graph theory)
The degree centrality (' degree centrality ') is the first and simplest measures centralidad.7 corresponds to the number of links a node has with others.
Formally , given a graph G : = ( V , E ), where V is the set of vertices and E the set of edges , then for every node v \ in V its degree centrality C { DEG } ( v ) is defined as 7
C { DEG } ( v ) = \ mbox { degree } ( v )
If it is the adjacency matrix of the graph , where a_ { ij } each position takes the value 1 if the edge (i, j ) and 0 , if not, then the degree centrality of each node j is can be defined as :
C { DEG } ( j ) = \ sum_i a_ { ij }
For directed graphs , we can define two different centrality measures , corresponding to the degree of input or output level . In the sense of interpersonal relationships, the first can be interpreted as a measure of popularity, while the second one of sociability.
Two criteria for normalizing this measure may be to divide the degree of each node obtained by the maximum network degree or dividing by the total number of nodes in the network .
Interpretations of this measure may be multiple. In a social network , can be the number of friends or connections held by each person , in which case quantifies the connectivity and network popularity . In a network of infection can measure the degree of risk of being caught or the exposure index . The spread of a rumor , you can measure the probability of obtaining information through a rumor.
In computational complexity of this calculation step takes \ Theta ( V ^ 2 ) in a dense adjacency matrix , and \ Theta ( E ) in a sparse array .
K - path centrality [ edit]
The degree of a node can be seen as the number of paths of length 1 connecting it to other nodes. A natural generalization to degree centrality , is the centrality of road -K (" K -path centrality ') for each node measures the number of paths of length at most k that connect other nodos.7
Katz and Bonacich centralities [ edit]
Another generalization of the degree centrality is the centrality of Katz, 9 which for a node counts the number of all other nodes that are connected to him through a path , while connections with more distant nodes are penalized by through a \ beta \ in (0,1) factor .
Formally, let A be the adjacency matrix of the graph , and n is the total number of nodes , the centrality of Katz KATZ { C } ( i ) of a node i is defined as 7
C_ { \ mathrm { Katz } } (i) = \ sum_ { k = 1 } ^ { \ infin } \ sum_ { j = 1 } ^ n \ alpha ^ k (A ^ k ) _ { ji }
where e_i ^ T is a row vector whose ith element is 1 and the rest are 0, and 1 is a vector of all ones . As seen below, this measure is related to the centrality of vector propio.7
A small variation of the Katz centrality is given by the Bonacich centrality of 10 which allows negative values for the factor \ beta :
C { BON } (i) = e_i ^ T ( \ frac { 1} { \ beta } \ sum_ { k = 1 } ^ { \ infty } ( \ beta A) ^ k ) { \ mathbf 1} = \ frac { 1} { \ beta } \ sum_ { k = 1 } ^ { \ infty } \ sum_ { j = 1 } ^ n \ beta ^ k (A ^ k ) _ { ij }
Thus subtracting the negative weight allows the paths of the even number odd number , which is interpretable intercambio.7 networks 6
Centrality of Hubbell [ edit]
A generalization that includes the Bonacich centralities Katz and Hubbell is the centrality of 11 formally defined as:
C { HUB } (i) = e_i ^ T ( \ sum_ { k = 0} ^ { \ infty } X ^ j ) { \ mathbf y}
where X is a matrix and { \ mathbf y} a vector. If X = \ beta A and { \ mathbf y} = \ beta A { \ mathbf 1} Katz centrality is obtained , and if X = \ beta A and { \ mathbf y} = A { \ mathbf 1} is obtained the centrality of Bonacich.7
Closeness [ edit]
The measure of closeness , defined by the mathematician Murray Beauchamp in 196512 and then popularized by Freeman in 1979.3 is the most known and used radial length measurements . Calculated based on the sum or the average of the shortest distances from one node to all demás.7
Formally, C_ { CLO } ( i) of a node i closeness is defined as :
C { CLO } (i) = { e_i ^ TS \ mathbf 1} = \ sum_ { j = 1 } ^ n ( S ) _ { ij }
where S is the matrix of network distances , ie , that array whose elements (i, j ) corresponds to the shortest distance from node i to node j . The smaller the value above, we can say that the node is more "close" to the center of the network. In this case defined and actually corresponds to a measure of distance. For the same reason , sometimes the proximity well defined as the reciprocal of the above, why not changing idea concepto.13
C { CLO } (i) = \ frac { 1} { e_i ^ TS { \ mathbf 1} } = \ frac { 1} { \ sum_ { j = 1 } ^ n ( S ) _ { ij } }
In a flow network this measure can be interpreted as the time of arrival at destination of something flowing through red.1 also be interpreted as the speed it will take the spread of information from one node to all demás.14 the proximity somehow measured the accessibility of a node in the network. This concept is also used similarly in topology ( which is defined as a metric space ) and in graph theory, which is applied from other fields and network analysis .
No hay comentarios.:
Publicar un comentario