Extended Lorenz majorization and frequencies of distances in an undirected network

2023/11/24 by Leo Egghe, Egghe, Leo
Computer Science · Engineering · Physics and Astronomy · #05C12 #Complex Network Analysis Techniques #FOS: Mathematics #General Mathematics (math.GM) #Slime Mold and Myxomycetes Research #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2312.11472

openalex publication_date 2023/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Findings: We show that the distance distribution in an undirected network Lorenz majorizes the one of a chain. As a consequence, the average and median distances in any such network are smaller than or equal to those of a chain. Research limitations: We restricted our investigations to undirected, unweighted networks. Practical implications: We are convinced that these results are useful in the study of small worlds and the so-called six degrees of separation property.

Related

• Networks and their degree distribution, leading to a new concept of small worlds
• The small-world phenomenon: a model, explanations, characterizations and examples
• Simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks
• Dependence of the average to-node distance on the node degree for random graphs and growing networks
• Discrete small world networks