Vertex similarity in networks

2005/10/14 by E. A. Leicht, Petter Holme, M. E. J. Newman · 5 citations
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #cond-mat.dis-nn #physics.data-an #physics.soc-ph

paper · pdf · doi:10.1103/physreve.73.026120

published as Phys. Rev. E 73, 026120 (2006)

arxiv created 2005/10/14 · openalex publication_date 2006/02/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• Community structure in social and biological networks
• Emergence of scaling in random networks
• Structural equivalence of individuals in social networks
• A New Status Index Derived from Sociometric Analysis
• Similarity measures in scientometric research: The Jaccard index versus Salton's cosine formula
• Statistical mechanics of complex networks
• Birds of a Feather: Homophily in Social Networks
• Evolution of networks
• The structure and function of complex networks
• Two algorithms for computing regular equivalence

Cited by

• Transforming Graph Representations for Statistical Relational Learning
• Panther: Fast Top-k Similarity Search in Large Networks
• Privacy Attacks on Network Embeddings
• Link prediction based on local random walk
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces