Vertex similarity in networks.

By Elizabeth A. Leicht, Petter Holme, Mark Newman. Physical review. E, Statistical, nonlinear, and soft matter physics, 2005

865 citations recorded by the source corpus.

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.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1d0f007192db92d29b1cdf43aa9325ba0535b23a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

A Survey of Link Prediction in Complex Networks (2016, methodology): “This index is deﬁned as the ratio of actual paths of length two between two nodes and a value proportional to the expected number of paths of length two between them [Leicht et al. 2006].”
Graph-based term weighting for information retrieval (2012, background): “…Ferrer i and Solé 2001), syntactic (i Cancho et al. 2007; Ferrer i Cancho et al. 2004; Widdows and Dorow 2002), semantic (Kozareva et al. 2008; Leicht et al. 2006; Motter et al. 2011; Sigman and Cecchi 2002; Steyvers and Tenenbaum 2005), phonological (Vitevitch and Rodrguez 2005),…”
Recommender Systems (2012, methodology): “If instead of referring to nodes, the individuals refer to pairs of nodes, this approach can be used to quantify node similarity [144,309].”
struc2vec: Learning Node Representations from Structural Identity (2017, background): “CCS CONCEPTS •Computing methodologies→Unsupervised learning; Learning latent representations; •Arti cial Intelligence→ Learning; KEYWORDS feature learning; node embeddings; structural identity”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, background): “ng and graph pre-training. 2.1 Vertex Similarity Quantifying similarity of vertices in networks/graphs has been extensively studied in the past years. The goal of vertex similarity istoanswerquestions[26]like“Howsimilararethesetwovertices?” or “Which other vertices are most similar to these vertices”
Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review (2012, background): “All these greatly help drug design (Yu et al., 2004b; Sharan et al., 2005; Leicht et al., 2006; Sharan & Ideker, 2006; Zhang et al., 2008; McGary et al., 2010; Korcsmáros et al., 2011).”
Link prediction in social networks: the state-of-the-art (2014, background): “Leicht-Holme-Nerman (LHN): This metric assigns high similarity to node pairs that have many common neighbors compared not to the possible maximum, but to the expected number of such neighbors [93].”
Handwritten Optical Character Recognition (OCR): A Comprehensive Systematic Literature Review (SLR) (2020, neutral): “scoring [105] and vertex similarity method [106].”
The science of science: from the perspective of complex systems (2017, background): “Similar indices with the same purpose but with different forms are many, such as Cosine index [184], Sørensen index [257], Hub promoted index [265], and Leicht–Holme–Newman index [258], to name a few.”
Graph Representation Learning (2020, background): “To alleviate this, Leicht et al. [2006] propose an improved metric by considering the ratio between the actual number of observed paths and the number of expected paths between two nodes:”
A Review of Relational Machine Learning for Knowledge Graphs (2015, methodology): “Global similarity indices such as the Katz index [100] and the Leicht–Holme–Newman index [101] derive the similarity of entities from the ensemble of all paths between entities, while indices like Hitting Time, Commute Time, and PageRank [102] derive the similarity of entities from random walks on t”
Link Prediction in Complex Networks: A Survey (2010, background): “The former embodies a latent assumption that the link itself indicated a similarity between two endpoints (see, for example, the Leicht–Holme–Newman index [36] and transferring similarity [37]), while the latter assumes that two nodes are similar if their neighbors are similar.”