Vertex similarity in networks

(

We consider methods for quantifying the similarity of vertices in networks.
We propose a measure of similarity based on the concept that two vertices are
similar if their immediate neighbors in the network are themselves similar.
This leads to a self-consistent matrix formulation of similarity that can be
evaluated iteratively using only a knowledge of the adjacency matrix of the
network. We test our similarity measure on computer-generated networks for
which the expected results are known, and on a number of real-world networks.

rating distribution

average user rating4.0 out of 5.0 based on 1 review

- @folke 4 years agoThis is a very interesting approach to vertex similarity in undirected networks. The main idea is to consider vertices as similar, if there is a direct neighbor of one node, which is similar to the other. This leads to a recursive formulation, considering the number of paths of all lengths relative to the expected such number in the corresponding configuration model. The authors derive their approach in theory and also give some practical examples for evaluation. The main drawback of the presented approach is, that the derived similarity score is only "expected to be approxximately correct" according to the modelled approach and that it incorporates a free constant whos value is determined experimentally. It is worth noting, that the presented approach also yields a notion of structural equivalence (i.e. considering only direct links) which measures similarity relative to a randomly connected network.