Ranking Vertices or Edges of a Network by Loops: A New Approach

2008/04/11 by Valery Van Kerrebroeck, Enzo Marinari
Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Combinatorics #Complex Network Analysis Techniques #Computer science #Data Management and Algorithms #Data mining #Graph theory and applications #Loop (graph theory) #Mathematics #Measure (data warehouse) #Ranking (information retrieval) #cond-mat.dis-nn #physics.soc-ph

paper · pdf · doi:10.1103/physrevlett.101.098701

published as Phys. Rev. Lett. 101, 098701 (2008) · 4 pages, 2 figures, 1 table, corrected misprint

arxiv created 2008/04/11 · openalex publication_date 2008/08/26 · arxiv updated 2013/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We introduce loop ranking, a new ranking measure based on the detection of closed paths, which can be computed in an efficient way. We analyze it with respect to several ranking measures which have been proposed in the past, and are widely used to capture the relative importance of the vertices in complex networks. We argue that loop ranking is a very appropriate measure to quantify the role of both vertices and edges in the network traffic.

Citations

• Finding long cycles in graphs
• Local Structure of Directed Networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Error and attack tolerance of complex networks
• Subgraph centrality in complex networks
• Authoritative sources in a hyperlinked environment
• A faster algorithm for betweenness centrality*