One of the challenges in studying large-scale networks is the extent to which they become intertwined with one another and with their environments. Social and technological networks are becoming increasingly dependent on one another, and both types of networks are fundamentally embedded in time, space, and organizational structure.

I'll discuss how these issues arise in the context of search problems and 'small-world' effects in networks, focusing on some basic models that capture the notion of a network embedded in spatial and organizational structure, and the surprising extent to which these models are reflected in recent experimental data. I'll also discuss some recent studies of how large-scale networks evolve over time, including a few findings that suggest the limitations of our current models.

Bio:
Jon Kleinberg is a Professor in the Computer Science Department at Cornell.
His research focuses on the interactions between algorithms, information, and networks, with connections to Web information systems and computational social network analysis. He is the recipient of awards including an NSF Career Award,
an ONR Young Investigator Award, and research fellowships from the Sloan and Packard Foundations.

[handout]