Graph Theory

A social network is represented as a graph G = (V,E), where the set of vertices V is the set of actors and the set E of edges is the set of connections between those actors.

Define a path from two vertices s and t in the set V as an alternating sequence of vertices and edges, beginning with s and ending with t, such that each edge connects its preceding vertex with the succeeding vertex.

Define the length of a path as the sum of the weights on its edges; in the case on an unweighted graph, take this as the sum total number of edges instead.

Define a shortest path between two vertices s and t in the set V as a path between s and t which minimizes the value of length of the path beginning with s and ending in t. (Note: There may be multiple equally-optimal shortest paths between a given pair of vertices.)

Define d(x,y) for some pair of vertices x and y as the length of the shortest path(s) from x to y in G.

Define q(x,y) for some pair of vertices x and y as the number of shortest paths from x to y in G. Let q(x,x) = 1 for every x in V.

Define f(x,y,z) for some set of vertices x, y and z as the number of shortest paths from x to y in G which also contain the "focal vertex" z.



Consider the following measures of centrality of a vertex in a social network:

Define stress centrality s(z) = sum [ f(x,y,z) ] for all vertices x != y != z in V. In other words, the stress centrality of a "focal vertex" z is the total number of shortest paths in G which include z.

Define betweenness centrality b(z) = sum [ f(x,y,z) / q(x,y) ] for all vertices x != y != z in V. In other words, the betweenness centrality of a "focal vertex" z measures the proportion of shortest paths which pass through z.

Define closeness centrality c(z) = 1 / sum [ d(z,v) ] for all vertices v in V. In other words, closeness centrality measures how close a "focal vertex" z is to each other vertex in the graph. Note that, because we are computing the inverse, c(z) increases as this total distance decreases.

Define graph centrality g(z) = 1 / max [ d(z,v) ] for all vertices v in V. In other words, graph centrality measures how close a "focal vertex" z is to the most distant vertex in the graph. Note that, because we are computing the inverse, g(z) increases as this maximum distance decrease.

For at least two of the centrality measures described (stress, betweenness, closeness, and graph centrality), explain the definition of the measure and provide an example of a real-world-type problem where this measure would be useful. This would mean at least 2 examples total--one each for at least 2 centrality measures. Come up with your own visual aids and descriptions. Use these examples to help teach the concepts of the centrality measures.

Provide pseudocode for computing any one of these four centrality measures.