Jon Kleinberg is visiting UIUC today and giving a talk “Decentralized Search, Cascading Behavior, and the Structure of On-Line Communities” in the Age of Networks seminar series. The abstract of his talk today:
The rise of large-scale information networks has provided us with systems that are simultaneously social and technological in nature, and in which the human interactions that unfold can be recorded and studied in extraordinary detail. Against this backdrop, a significant amount of recent work has focused on the development of mathematical 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 large networks are organized, and about the ways in which abstract models can capture the processes we observe.
We discuss two lines of research that illustrate this theme, concerned with two network processes that can be viewed as complementary: search, which narrows toward a specific target; and cascading behavior, which spreads outward from a small seed. We relate the search problem to issues that underpin the well-known “six degrees of separation” phenomenon in social networks, and describe how recent data from on-line communities aligns surprisingly well with some of the basic mathematical models for the underlying process. We identify cascading behavior in many social network processes that can be thought of as unfolding with the dynamics of an epidemic: as individuals become aware of new ideas, technologies, fads, rumors, or gossip, they have the potential to pass them on to their friends and colleagues, causing the resulting behavior to spread rapidly through the network. Here too, we find that the processes taking place within on-line communities provide new insights into models for cascading behavior that have been extensively studied in the social sciences.
He covered some results on algorithmic network analysis. He started with the “six degree of separation result” and continued rolling over different models. One of the interesting stop, models of innovation diffusion over inventions. Yes, he went over Everret Rogers “Diffusion of innovations” work. Also presented the NP problem involved on finding the key diffusors and diminishing returns presenting some heuristics about it.