Title: | Complex networks and decentralized search algorithms |

Author: | Jon Kleinberg |

Book Tittle: | Proceedings of the International Congress of Mathematicians |

Year: | 2006 |

Abstract: | The study of complex networks has emerged over the past several years as a theme spanning many disciplines, ranging from mathematics and computer science to the social and biological sciences. A significant amount of recent work in this area has focused on the development of random graph models that capture some of the qualitative properties observed in large-scale network data; such models have the potential to help us reason, at a general level, about the ways in which real-world networks are organized. We survey one particular line of network research, concerned with small-world phenomena and decentralized search algorithms, that illustrates this style of analysis. We begin by describing awell-known experiment that provided the first empirical basis for the “six degrees of separation” phenomenon in social networks; wethen discuss some probabilistic network models motivated by this work, illustrating how these models lead to novel algorithmic and graph-theoretic questions, and how they are supported by recent empirical studies of large social networks. |

Cited by 69

@InProceedings{kleinberg06a, author = {Jon Kleinberg}, title = {Complex networks and decentralized search algorithms}, booktitle = {Proceedings of the International Congress of Mathematicians}, year = 2006, abstract = {The study of complex networks has emerged over the past several years as a theme spanning many disciplines, ranging from mathematics and computer science to the social and biological sciences. A significant amount of recent work in this area has focused on the development of random graph models that capture some of the qualitative properties observed in large-scale network data; such models have the potential to help us reason, at a general level, about the ways in which real-world networks are organized. We survey one particular line of network research, concerned with small-world phenomena and decentralized search algorithms, that illustrates this style of analysis. We begin by describing awell-known experiment that provided the first empirical basis for the ``six degrees of separation'' phenomenon in social networks; wethen discuss some probabilistic network models motivated by this work, illustrating how these models lead to novel algorithmic and graph-theoretic questions, and how they are supported by recent empirical studies of large social networks.}, cluster = {5316437966672474115}, url = {http://jmvidal.cse.sc.edu/library/kleinberg06a.pdf} }Last modified: Wed Mar 9 10:16:45 EST 2011