Closeness (graph theory)

From Wikipedia, the free encyclopedia

You have new messages (last change).

In topology and related areas in mathematics, closeness is one of the basic concepts in a topological space. Intuitively we say two sets are close if they are arbitrarily near to each other. The concept can be defined naturally in a metric space where a notion of distance between elements of the space is defined, but it can be generalized to topological spaces where we have no concrete way to measure distances.

In Graph Theory Closeness is a centrality measure of a vertex within a graph. Vertices that are 'shallow' to other vertices (that is, those that tend to have short geodesic distances to other vertices with in the graph) have higher closeness. Closeness is preferred in network analysis to mean shortest-path length, as it gives higher values to more central vertices, and so is usually positively associated with other measures such as degree.


Contents


[edit] Definition of Closeness

In the network thoery, closeness is a sofisticated measure of centrality. It is defined as the mean geodesic(i.e the shortest path) between a vertex and all other vertices reachable from it. Closeness can be regarded as a measure of how long it will take information to spread from a given vertes to others in the network[1].

Some define closeness to be the reciprocal of this quantitiy, but either ways the information communicated is the same.

The closeness CC(v) for a vertex v is the reciprocal of the sum of geodesic distances to all other vertices in the graph[2]:

C_C(v)=\frac{1}{\sum_{t \in V}d_G(v,t)}.

[edit] Defining geodesics and an algorithm to measure it[3]

Fig.1 Geodesics, or shortest paths, in a network between the two nodes labeled A and B.
Enlarge
Fig.1 Geodesics, or shortest paths, in a network between the two nodes labeled A and B[3].

A fundamental concept in graph theory is the "geodesic," or shortest path of vertices and edges that links two given vertices. There may not be a unique geodesic between two vertices: there may be two or more shortest paths, which may or may not share some vertices (Fig.1). The geodesic(s) between two vertices i and j can be calculated using the following algorithm, which is a modified form of the standard breadth-first search[4].

  1. Assign vertex j distance zero, to indicate that it is zero steps away from itself, and set d ← 0.
  2. For each vertex k whose assigned distance is d, follow each attached edge to the vertex l at its other end and, if l has not already been assigned a distance, assign it distance d + 1. Declare k to be a predecessor of l.
  3. If l has already been assigned distance d + 1, then there is no need to do this again, but k is still declared a predecessor of l.
  4. Set d ← d + 1.
  5. Repeat from step 2 until there are no unassigned vertices left.


Now the shortest path (if there is one) from i to j is the path you get by stepping from i to its predecessor, and then to the predecessor of each successive vertex until j is reached. If a vertex has two or more predecessors, then there are two or more shortest paths, each of which must be followed separately if we wish to know all shortest paths from i to j.


Fig.1 shows the shortest paths of collaborations in the Los Alamos Archive, calculated through the algorithm above, between two of the author’s colleagues the vertices A and B). Even though the two scientists work on social networks of various kinds, the shortest path between them does not run entirely through ther collaborations in the field. For example, the vertex C represents the present author, and my connections to D and E derive from papers on topics unconnected with networks. It indicates that workers in the field come from different scientific ‘‘camps,’’ rather than from a single group or institution. This may increase the chance that those workers will express independent opinions on the open questions of the field.


Different methods and algorithms can be introduced to measure closeness like the random-walk centrality introduced by Noh and Rieger (2003) is a measure of the speed with which randomly walking messages reach a vertex from elsewhere in the network—a sort of random-walk version of closeness centrality[5].

The information centrality of Stephenson and Zelen (1989) is another closeness measure, which bears some similarity to that of Noh and Rieger. In essence it measures the harmonic mean length of paths ending at a vertex i, which is smaller if i has many short paths connecting it to other vertices[6].

[edit] See also

[edit] References

  1. ^ Newman, MEJ, 2003, Arxiv preprint cond-mat/0309045.
  2. ^ Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581--603.
  3. ^ a b Newman, M. E. J. (2001) Phys. Rev. E 64, 016132.
  4. ^ R. Sedgewick, Algorithms (Addison-Wesley, Reading, MA,1988).
  5. ^ J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
  6. ^ Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.

[edit] What mathematicians think of it

The closure operator closes a given set by mapping it to a closed set which contains the original set and all points close to it. The concept of closeness is related to limit point.

Retrieved from "http://en.wikipedia.org../../../c/l/o/Closeness_%28graph_theory%29.html"