3

I have a graph with vertices that represent some entities and the edges are weighted as the correlation between two such entities.

I would like to break this graph into several subgraphs with high inner-correlation.

My problem is that I have a few 'hubs', with high correlation to a lot of different entities.

How can I detect such hubs in order to remove them?

scf
  • 185
  • 1
  • 5

1 Answers1

2

Depends on how you define "hubs". In Network Science, a hub is simply a node with high degree i.e. those node who contribute to the power-law nature of the degree distribution the most. But you can also find other definitions for instance according to the information flow in the network where hubs are defined as those node that are critical in the process information flow (also called central nodes).

My Suggestions

  1. Degree Distribution: The simplest approach would be to choose high degree nodes as hubs. To ensure your results a bit more I recommend to calculate the summation of all correlations correspond to each node and have a look at these numbers as well. In this case you are looking for nodes which have high degrees and contain a larger value of correlation.

  2. Centrality Measure: or Betweenness introduced by Linton Freeman which again somehow measures the influence of a node in the process of information flow over the network. Calculating the centrality for a vertex $v$ in a graph has basically 3 steps:

    • For each pair of vertices $(s,t)$, compute the shortest paths between them.
    • For each pair of vertices $(s,t)$, determine the fraction of shortest paths that pass through the vertex in question (here, vertex $v$).
    • Sum this fraction over all pairs of vertices $(s,t)$.

For more information read this carefully and in case you need any help (specially for implementation) just drop me a line in the comments :)

Good Luck!

Kasra Manshaei
  • 6,570
  • 1
  • 21
  • 45