Similarity and centrality of vertices in graphs/networks

  • Ernesto Estrada (Campus Universitat de les Illes Balears, Spain)
A3 02 (Seminar room)


I consider the problem of detecting the group of vertices more similar to a given one in a graph/network. Starting from measures defined in the literature I analyze their main drawbacks. Then, I propose a metric based on the communicability cosine angle between pairs of vertices in a network. I then define a similarity measure based on it and illustrate that it solves the problems existing with previous measures. I then define a measure based on this similarity measure, which quantifies the communicability closeness centrality (CCC) of a vertex to the rest in a network. Using it I approach the problem of distinguishing all pairs of vertices which are not automorphically equivalent in a network. Finally, I illustrate the use of the CCC in ranking vertices in real-world networks, and illustrate its main differences with existing centrality measures like the degree, closeness, betweenness and eigenvector centrality.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail