Promatra li se mreža prijatelja kao neusmjereni graf u kojem vrhovi predstavljaju osobe, a bridovi dvosmjernu relaciju prijateljstva, pokazano je da prosječan stupanj vrha grafa nije veći od prosječnog stupnja njegovih susjednih vrhova. Ovaj rezultat naziva se paradoksom o prijateljstvu, zbog interpretacije u obliku: ”Vaši prijatelji imaju više prijatelja nego Vi”. Navedeni paradoks se može interpretirati na još nekoliko načina. Primjerice, odaberimo li uniformno slučajno jednu osobu u mreži, a zatim uniformno slučajno nekog njezinog prijatelja, tada će on u prosjeku imati više prijatelja nego prvobitno izabrana osoba. Uz pomoć slučajnih šetnji u grafu, navedeni paradoks može se generalizirati na ”prijatelja prijateljevog prijatelja” za kojeg će vrijediti isti rezultat ako pazimo na parnost duljine promatrane šetnje. Navedena generalizacija možeme se proširiti ako se uvede definicija k - udaljenih prijatelja. Paradoks o prijateljstvu tada kaže da očekivani broj prijatelja 1 - udaljenih prijatelja nekog pojedinca nije manji od broja 0 - udaljenih prijatelja istog tog pojedinca. Uz pomoć slučajnih šetnji u grafu, navedeni paradoks može se generalizirati na ”prijatelja prijateljevog prijatelja” za kojeg će vrijediti isti rezultat ako pazimo na parnost duljine promatrane šetnje. Navedena generalizacija možeme se proširiti ako se uvede definicija k - udaljenih prijatelja. Paradoks o prijateljstvu tada kaže da očekivani broj prijatelja 1 - udaljenih prijatelja nekog pojedinca nije manji od broja 0 - udaljenih prijatelja istog tog pojedinca.