Barabási kutatócsoportja 1999-2000-ben két nagyon fontos tanulmányt publikált a világ egyik legfontosabbnak tartott tudományos magazinjában, a Nature-ben. Ezekben a cikkekben egy réges-régi hiedelmet sikerült szertefoszlatniuk. Hosszú évtizedeken keresztül a tudósok azon a véleményen voltak, hogy az összes természetben és mesterséges úton létrejövő hálózat véletlenszerű. Bármelyik hálózatról volt szó, alkosson akár olyan összetett rendszert, mint a társadalom, vagy a sejtek kémiai anyagai, esetleg a honlapokat összekötő URL-ek, mindegyikről azt feltételezték, hogy véletlenszerűen rendeződnek el. (A véletlenszerű hálózat gondolatát, amelyben a csomópontokat véletlenszerűen kötjük egymáshoz, két magyar matematikus, Erdős Pál és Rényi Alfréd vetette fel a hatvanas években.) Többek között Barabási kutatócsoportjának érdeme, hogy a 90-es évek legvégén fokozatosan rájöttek: nem minden hálózat engedelmeskedik a "véletlenszerűség törvényeinek".
Barabásiék rámutattak arra, hogy ha az Erdős-Rényi-féle elvet alkalmaznánk az internetre, akkor "a legtöbb embernek nagyjából ugyanannyi barátja lenne, nagyon kevésnek lenne csak sokkal több vagy sokkal kevesebb. A világhálón ez nem így van: a legtöbb oldalra csak nagyon kevés más oldal mutat, ezek tehát majdnem láthatatlanok a világhálón, néhány oldalra pedig majdnem mindenki rámutat." Ezt a fajta hálózatot következő cikkükben elnevezték skálafüggetlen hálózatnak. Barabási hamarosan programot íratott egyik ifjú kollegájával, amellyel nemsokára megvalósulhatott az internet feltérképezése.