Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition

DOI10.1016/J.INS.2017.09.020MaRDI QIDQ781014zbMATH OpenOpenAlexFDO

Authors Andrew Gozzard, Max Ward, Amitava Datta

Publication date 16 July 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2017.09.020

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Communication networks in operations research (90B18)

Recommendations

• Network structure optimization for social networks by minimizing the average path length
• A low complexity method for the optimization of network path length in spatially embedded networks
• Optimization of the critical diameter and average path length of social networks
• Analyzing Kleinberg's (and other) small-world models
• Navigable small-world networks with few random bits

Cites work

• A zoom-in approach to design SDH mesh restorable networks
• Collective dynamics of `small-world' networks
• Deterministic scale-free small-world networks of arbitrary order
• Deterministic small-world networks
• Introduction to algorithms
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• The Structure and Function of Complex Networks

Cited in

(5)

• A multilevel simplification algorithm for computing the average shortest-path length of scale-free complex network
• A new coupled disease-awareness spreading model with mass media on multiplex networks
• Optimization of the critical diameter and average path length of social networks
• A low complexity method for the optimization of network path length in spatially embedded networks
• Network structure optimization for social networks by minimizing the average path length

This page was built for publication: Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q781014)