August 16, 2005 | David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins
This paper explores geographic routing in social networks, focusing on the LiveJournal social network. It introduces a model called rank-based friendship, where the probability of befriending someone is inversely proportional to the number of closer people. The study shows that in a large social network, about one-third of friendships are independent of geography, while the rest exhibit this relationship. The authors also prove that short paths can be discovered in networks with this relationship.
The paper discusses the "small world" phenomenon, where people are connected through short chains of friends. Experimental studies have shown that messages can be passed through short chains of friends, even with limited information about the target. The study also highlights the importance of geography in routing, as it is the most valuable dimension for routing, and the presence of rank-based friendship can explain the navigability of large-scale social networks.
The LiveJournal social network is analyzed, with 1.3 million bloggers. The study shows that geographic information alone allows people to discover short paths to a destination city. The paper also discusses the relationship between friendship and geographic distance, showing that the probability of friendship decreases with distance. However, for distances larger than about 1,000 km, the background friendship probability becomes dominant.
The paper introduces a model of friendship formation called rank-based friendship, which is shown to be present in the LiveJournal network. This model explains the navigability of the network, as it allows for the discovery of short paths. The study also shows that rank-based friendship is a core mechanism for geographically biased friendship formation and that it provides two desirable properties: it matches experimental observations and admits a mathematical proof that networks with this property will contain discoverable short paths.
The paper concludes that rank-based friendship is a mechanism that has been empirically observed in real networks and theoretically guarantees small-world properties. It also highlights the importance of understanding the relationship between geography and friendship in social networks.This paper explores geographic routing in social networks, focusing on the LiveJournal social network. It introduces a model called rank-based friendship, where the probability of befriending someone is inversely proportional to the number of closer people. The study shows that in a large social network, about one-third of friendships are independent of geography, while the rest exhibit this relationship. The authors also prove that short paths can be discovered in networks with this relationship.
The paper discusses the "small world" phenomenon, where people are connected through short chains of friends. Experimental studies have shown that messages can be passed through short chains of friends, even with limited information about the target. The study also highlights the importance of geography in routing, as it is the most valuable dimension for routing, and the presence of rank-based friendship can explain the navigability of large-scale social networks.
The LiveJournal social network is analyzed, with 1.3 million bloggers. The study shows that geographic information alone allows people to discover short paths to a destination city. The paper also discusses the relationship between friendship and geographic distance, showing that the probability of friendship decreases with distance. However, for distances larger than about 1,000 km, the background friendship probability becomes dominant.
The paper introduces a model of friendship formation called rank-based friendship, which is shown to be present in the LiveJournal network. This model explains the navigability of the network, as it allows for the discovery of short paths. The study also shows that rank-based friendship is a core mechanism for geographically biased friendship formation and that it provides two desirable properties: it matches experimental observations and admits a mathematical proof that networks with this property will contain discoverable short paths.
The paper concludes that rank-based friendship is a mechanism that has been empirically observed in real networks and theoretically guarantees small-world properties. It also highlights the importance of understanding the relationship between geography and friendship in social networks.