Hide and seek in a complex world

HIDE AND SEEK

IN A

COMPLEX WORLD

Martin Rosvall

Licentiate Thesis

Department of Physics

Umeå University

January 2005

Department of Physics

C

omplex networks have become the key to uncover the patterns of inter-

actions in man-made and complex systems in nature. The Internet, the

proteins in our cells, our bonds of friendship and the web-pages we daily

browse form networks. Despite their widely different origins the networks have

many interesting features in common. We endeavor to a better understanding

of both man-made structures, like the Internet, and networks in nature, like the

protein-protein interactions in our cells. The ultimate goal is to avoid system break-

downs, hopefully to prevent major deceases and to benefit from undiscovered pos-

sibilities.

lution process in networks, probably an important component to understand the

formation dynamics of the Internet. Further, we present a social model with agents

that everyone tries to optimize their relative position in the network, based on local

limited information. This model opens for investigation of the interplay between

individual behavior and global organization. This in turn raises the question about

the inevitable connection to the network function from the point of view of com-

munication and navigability. In this context we have analyzed city navigation and

thereby been able to understand why it is more difficult to find the way in some

cities than in others. Perhaps you have wondered: What is the best strategy to find

the hotel — to go by chance or to ask a citizen in every corner? We found that the

2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Network topology . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Shortest path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Network models 8

3.1 Simple networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.2 Random networks . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.3 Small-world networks . . . . . . . . . . . . . . . . . . . . . . . . 10

3.4 Scale-free networks . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.2 Modeling social communication . . . . . . . . . . . . . . . . . . 19

Paper III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.3 Hide and seek on complex networks . . . . . . . . . . . . . . . . 21

Paper IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.4 An application: Navigation in cities . . . . . . . . . . . . . . . . 23

Paper V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24