Centrality

From Wikipedia, the free encyclopedia

(Redirected from Closeness (graph theory))
Jump to: navigation, search

Within graph theory and network analysis, there are various measures of the centrality of a vertex within a graph that determine the relative importance of a vertex within the graph (for example, how important a person is within a social network, or, in the theory of space syntax, how important a room is within a building or how well-used a road is within an urban network).

There are four measures of centrality that are widely used in network analysis: degree centrality, betweenness, closeness, and eigenvector centrality.

Contents

The first, and simplest, is degree centrality. Degree centrality is defined as the number of links incident upon a node (i.e., the number of ties that a node has). Degree is often interpreted in terms of the immediate risk of node for catching whatever is flowing through the network (such as a virus, or some information). If the network is directed (meaning that ties have direction), then we usually define two separate measures of degree centrality, namely indegree and outdegree. Indegree is a count of the number of ties directed to the node, and outdegree is the number of ties that the node directs to others. For positive relations such as friendship or advice, we normally interpret indegree as a form of popularity, and outdegree as gregariousness.

Hue (from red=0 to blue=max) shows the node betweenness.
Hue (from red=0 to blue=max) shows the node betweenness.

Betweenness is a centrality measure of a vertex within a graph. Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.

For a graph G: = (V,E) with n vertices, the betweenness CB(v) for vertex v is:

C_B(v)= \sum_{s \neq v \neq t \in V \atop s \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}

where σst is the number of shortest geodesic paths from s to t, and σst(v) is the number of shortest geodesic paths from s to t that pass through a vertex v. This may be normalised by dividing through by the number of pairs of vertices not including v, which is (n − 1)(n − 2).

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.

In the network theory, closeness is a sophisticated measure of centrality. It is defined as the mean geodesic distance (i.e the shortest path) between a vertex v and all other vertices reachable from it:

\frac{\displaystyle \sum_{t \in V\setminus v}d_G(v,t)}{n-1}

where n\ge 2 is the size of the network's 'connectivity component' V reachable from v. Closeness can be regarded as a measure of how long it will take information to spread from a given vertex to other reachable vertices in the network[1].

Some define closeness to be the reciprocal of this quantity, but either ways the information communicated is the same (this time estimating the speed instead of the timespan). The closeness CC(v) for a vertex v is the reciprocal of the sum of geodesic distances to all other vertices of V[2]:

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

Different methods and algorithms can be introduced to measure closeness, like the random-walk centrality introduced by Noh and Rieger (2003) that 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[3].

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[4].

Dangalchev (2006), in order to measure the network vulnerability, modifies the definition for closeness so it can be used for disconnected graphs and the total closeness is easier to calculate [5]:

C_C(v)=\sum_{t \in V\setminus v}2^{-d_G(v,t)}.

Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.

Let xi denote the score of the ith node. Let Ai,j be the adjacency matrix of the network. Hence Ai,j = 1 if the ith node is adjacent to the jth node, and Ai,j = 0 otherwise. More generally, the entries in A can be real numbers representing connection strengths.

For the ith node, let the centrality score be proportional to the sum of the scores of all nodes which are connected to it. Hence

x_i = \frac{1}{\lambda} \sum_{j \in M(i)}x_j

(where M(i) is the set of nodes that are connected to the ith node, N is the total number of nodes and λ is a constant),

or equivalently using the adjacency matrix,

x_i = \frac{1}{\lambda} \sum_{j = 1}^N A_{i,j}x_j

in vector notation this can be rewritten as

\mathbf{x} = \frac{1}{\lambda}A\mathbf{x}

or,

A\mathbf{x} = {\lambda}\mathbf{x}

which is the eigenvector equation.

In general, there will be many different eigenvalues λ for which an eigenvector solution exists. However, the additional requirement that all the entries in the eigenvector be positive implies (by the Perron–Frobenius theorem) that only the greatest eigenvalue results in the desired centrality measure.[6] The ith component of this eigenvector then gives the centrality score of the ith node in the network.

Google's PageRank is a variant of the Eigenvector centrality measure.

  1. ^ Newman, MEJ, 2003, Arxiv preprint cond-mat/0309045.
  2. ^ Sabidussi, G. (1966) The centrality index of a graph. Psychometrika 31, 581--603.
  3. ^ J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004).
  4. ^ Stephenson, K. A. and Zelen, M., 1989. Rethinking centrality: Methods and examples. Social Networks 11, 1–37.
  5. ^ Dangalchev Ch., Residual Closeness in Networks, Phisica A 365, 556 (2006).
  6. ^ M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved on 2006-11-09.

  • Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.
  • Sabidussi, G. (1966). The centrality index of a graph. Psychometrika, 31, 581-603.
  • Freeman, L. C. (1977) A set of measures of centrality based on betweenness. Sociometry 40, 35--41.
  • Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16-61, LNCS 3418, Springer-Verlag.

Retrieved from "http://en.wikipedia.org/wiki/Centrality#closeness"
Advanced Search
Included Web Search Engines


Safe Search

close

Top Matching Results

Occasionally Search.com will highlight specialized results that are based on the context of your query. Examples of specialized results include specific links to news, images, or video.

Top Matching Results may highlight information from other Search.com pages, content from the CNET Network of sites, or third party content. The listings are based purely on relevance. Search.com does not receive payment for listings in this section but our partners that provide this data may get paid for listing these products.

Sponsored Links

This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Search.com sends your search query to several search engines at one time and integrates the results into one list which has been sorted by relevance using Search.com's proprietary algorithm. You can customize the list of search engines included in your metasearch from the preferences.

The search engines that are used in your metasearch may allow companies to pay to have their Web sites included within the results. To view the Paid Inclusion policy for a specific search engine, please visit their Web site. Search.com does not accept payment or share revenue with any search engine partner for listings in this section.