Talk:Centrality

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Low Priority
 Field: Discrete mathematics

Betweenness centrality: authorship[edit]

I changed one of the not so relevant references from a thesis (which might be very nice but is not the most authoritative reference for betweenness centrality) to Brandes' article. I also added the first real publication on betweenness centrality by Freeman, but technically it was first introduced by Anthonisse in a technical report. In case anyone thinks that was relevant, here is the full reference: [1]. Note, however, that it is only published as a technical report, and that it is only introduced as some possible measures on networks, without any sociological background or introduction of an application. Netzwerkerin (talk) 20:24, 10 November 2011 (UTC)


Self-citation issues[edit]

It appears (perhaps from a naive perspective) as though this page is littered with individuals keen on citing their own work, when there are clearly more appropriate citations that are missing. I suggest that anyone with some free time on their hands go through and clean up that mess. —Preceding unsigned comment added by 149.171.105.105 (talk) 05:49, 21 January 2011 (UTC)

Agreed and guilty on that issue, but the article is underdeveloped currently. In my opinion, it is better to increase the size of the page, even if this done by including self-cites as this is easy and not very timeconsuming. Specifically, the deletion of my work on centrality in weighted networks by the anonymous user 130.223.101.78 on the grounds that it is "not relevant according to the size of the article, shouldn't appear in the preambule; according to the revision history, it is even a self-citation" is not helping. If it is agreed by the community that it shouldn't be in the preamble but in a section for weighted networks, fair enough. I have reverted the deletion and suggest that, if the anonymous user doesn't like this, that person could spend some time on extending the article instead of deleting relevant information. Let's have an open discussion about this instead of hiding behind IP addresses. Tore Opsahl 16:55, 27 July 2011 (UTC) — Preceding unsigned comment added by Tore.opsahl (talkcontribs)

Broken Links[edit]

Neither of the external links seem to work. Apparently, the server is either completely gone or its name changed (austria.phys.nd.edu is authoritatively unresolvable). --195.56.53.118 (talk) 17:23, 11 August 2008 (UTC)


Mathematical Definitions[edit]

I am no expert on this topic---I'm just looking for mathematical definitions of these measures, and it seems Wikipedia is one of the few sources that has defined them---but, I have a couple of comments and questions.

Are we sure about the definition of "degree centrality"? I'm staring at page 126 of Nooy et al. [1] and they say "The degree centrality of a vertex is its degree." Currently, the definition we have is one that is normalised by dividing by (n-1). If we went with Nooy's definition then that would impact the definitions of H and CD(G), but not their effect. Other authors have also used just degree [2, page 219], but it appears there has been quite some debate. Have people settled on the normalised version as presented in this article? If so, is there some standard text that could be referenced?

Nooy et al. also distinguish between a vertex's centrality and a graph's centralisation (rather than using the term centrality for both vertices and graphs as is currently being done in the article). Is this worth replicating, or at least mentioning?

[1] de Nooy, Wouter, Mrvar, Andrej, and Batagelj, Vladimir (2005), Exploratory Social Network Analysis with Pajek, Cambridge University Press.

[2] Freeman, L. C. (1979). Centrality in social networks: Conceptual clarification. Social Networks, 1(3), 215-239.

-- Mgwalker (talk) 17:52, 10 March 2009 (UTC)


Partly answering my own question... The 2005 review of the field by Koschützki et al., referenced as "further reading" at the bottom of the Wikipedia article, defines "degree centrality" without normalisation. --132.203.32.7 (talk) 21:58, 10 March 2009 (UTC)

Centrality[edit]

There is a problem in the phrasing of the definition of graph's centrality: "the" node that has highest degree does not define a unique node, so one should say "a" node instead. VIncentDanos (talk) 07:04, 13 October 2009 (UTC)

Eigenvector Centrality[edit]

  • I agree about the lack of definitions of these measures. EVC is ill-defined. References I've found say that the adjacency matrix for a directed graph used to compute EVC should be defined as follows:
A(i,j) = 1 if there is an edge from j to i, which is the reverse of a traditional adjacency matrix. This stipulation is not noted anywhere in this passage. In other words, EVC should be computed off of the transpose of the adjacency matrix, according to the implementation described in wikipedia (Adjacency Matrix)—Preceding unsigned comment added by 199.46.154.96 (talk) 20:03, 21 July 2009 (UTC)
  • "...A can be real numbers representing connection strengths, as in a stochastic matrix." Is this statement technically true? The entries in a stochastic matrix represent probabilities, not connection strength.

Identifying connected components?[edit]

It seems like at least eigenvalue centrality may identify connected components. For example:

> M=[0 1 1 0 0; 0 0 1 0 0; 0 0 0 0 0; 0 0 0 0 1; 0 0 0 0 0]; M=M+M'; 
M =
 
   0   1   1   0   0
   1   0   1   0   0
   1   1   0   0   0
   0   0   0   0   1
   0   0   0   1   0
 
> [v,d]=eig(M)
v =
 
   0.40825   0.00000   0.70711   0.00000   0.57735
   0.40825   0.00000  -0.70711   0.00000   0.57735
  -0.81650   0.00000   0.00000   0.00000   0.57735
  -0.00000  -0.70711   0.00000   0.70711   0.00000
  -0.00000   0.70711   0.00000   0.70711   0.00000
 
d =
 
  -1.00000   0.00000   0.00000   0.00000   0.00000
   0.00000  -1.00000   0.00000   0.00000   0.00000
   0.00000   0.00000  -1.00000   0.00000   0.00000
   0.00000   0.00000   0.00000   1.00000   0.00000
   0.00000   0.00000   0.00000   0.00000   2.00000

Clearly the two components are identified by the nonzero entries in each of the eigenvectors corresponding to positive eigenvalues. Is this true in general?

I have an application in which I have a graph with weighted edges and am trying to come up with a metric to find "more-connected" components. Eigenvalue centrality seems like it gets me part way there, but if I weekly connect two subgraphs (e.g., a weight of 0.1), the two eigenvectors seem to get mixed together so that I can't trivially identify weekly-connected components:

octave:52> M
M =
 
   0.00000   1.00000   1.00000   0.00000   0.00000
   1.00000   0.00000   1.00000   0.00000   0.00000
   1.00000   1.00000   0.00000   0.10000   0.00000
   0.00000   0.00000   0.10000   0.00000   1.00000
   0.00000   0.00000   0.00000   1.00000   0.00000
 
octave:53> [v,d]=eig(M)
v =
 
  -0.28437   0.70711   0.29268  -0.03531   0.57639
  -0.28437  -0.70711   0.29268  -0.03531   0.57639
   0.58546   0.00000  -0.56880  -0.00000   0.57767
  -0.51176   0.00000  -0.48772   0.70622   0.03844
   0.48333   0.00000   0.51698   0.70622   0.01920
 
d =
 
  -1.05884   0.00000   0.00000   0.00000   0.00000
   0.00000  -1.00000   0.00000   0.00000   0.00000
   0.00000   0.00000  -0.94339   0.00000   0.00000
   0.00000   0.00000   0.00000   1.00000   0.00000
   0.00000   0.00000   0.00000   0.00000   2.00222

Any thoughts? —Ben FrantzDale (talk) 12:13, 25 July 2009 (UTC)

Definition before use[edit]

This article's first line "...there are various measures of the centrality of a vertex within a graph that determine the relative importance of a vertex within the graph..." describes the use of centrality (and the various measures it has) in graph theory before defining centrality itself. It is easier for anyone not familiarized with the concept to read it's deffinition before any property. Vloody (talk) 18:13, 21 April 2011 (UTC)Vloody

Should normailization denominator have an extra division by two for undirected graphs?[edit]

I am not good at math or graphs and unfamiliar with contributing to Wikipedia. I was wondering, though, if the normalization part needs to be different for undirected graphs. In the Betweenness Centrality the denominator is adjusted: "for directed graphs and (N − 1)(N − 2) / 2 for undirected graphs.) Where N is the number of nodes in the giant component."

--PeterVermont (talk) 14:37, 4 September 2011 (UTC)

  1. ^ Anthonisse, Jac.M. (1971). "The rush in a directed network". Technical Report of the Stichting Mathematisch Centrum. BN 9/71, October.