Course Introduction and OverviewSlide 2Slide 3Slide 4Slide 5The Premise of Networked LifeWho’s Doing All This?Course MissionA Communal Experiment (Literally.)Course OutlineWhat is a Network?Contagion and Tipping in NetworksNetwork ScienceThe Web as NetworkTowards Rational DynamicsGame Theory and NetworksEconomic Models of Network FormationSponsored Web SearchPeer ProductionInternet EconomicsBehavioral Experiments in Network ScienceCourse MechanicsFirst AssignmentCourse Introductionand OverviewNetworked LifeCIS 112Spring 2009Prof. Michael KearnsInternet, Router Level•“Points” are physical machines•“Links” are physical wires•Interaction is electronic•A purely technological network?•Points are people •Links are social•Interactions: relationships, professional, virtual…•How and why does structure form?Gnutella Peers•Points are machines… but are associated with people •Links are physical… but may depend on human preferences•Interaction: content exchange•Food for thought: free ridingThe Human Brain•Points are neurons•Links are axons•Interaction is electrical, but…•New field: “Connectomics”•Food for thought:–Do neurons cooperate or compete?The Premise of Networked Life•It makes sense to study these diverse networks together.•Commonalities:–Formation (distributed, bottom-up, “organic”,…)–Structure (individuals, groups, overall connectivity, robustness…)–Decentralization (control, administration, protection,…)–Strategic Behavior (economic, free riding, Tragedies of the Common)•An Emerging Science:–Examining apparent similarities between many human, social, biological and technological networked systems & organizations–Importance of network effects in such systems•How things are connected matters greatly•Details of interaction matter greatly•The metaphor of viral spread•Dynamics of economic and strategic interaction–Qualitative and quantitative; can be very subtle–A revolution of measurement, theory, and breadth of visionWho’s Doing All This?•Computer Scientists–Understand and design complex, distributed networks–View “competitive” decentralized systems as economies•Social Scientists, Behavioral Psychologists, Economists–Understand human behavior in “simple” settings–Revised views of economic rationality in humans–Theories and measurement of social networks•Biologists–Neural networks, gene regulatory networks,…•Physicists and Mathematicians–Interest and methods in complex systems–Theories of macroscopic behavior (phase transitions)•Communities are interacting and collaboratingCourse Mission•A network-centric examination of a wide range of social, technological, biological, financial and political systems•Examined via the tools and metaphors of:–computer science–economics and finance–psychology and sociology–biology–mathematics and physics•Emphasize the common themes•Develop a new way of examining the worldA Communal Experiment(Literally.)•No similar undergraduate course –(except maybe now at Cornell)•No formal technical prerequisites–greatly aided by recent books–publications in Science, Nature, popular press etc.–class demographics:•majors: cog sci, communications, linguistics, history, econ, finance, psych,…•freshmen through graduate students•Extensive web visualizations and demos•Participatory in-class and out-of-class social experiments•MK’s self-serving motivation/agendaCourse OutlineWhat is a Network?•Networks as a collection of pairwise relationships•Degrees, diameters, cliques, expansion…•Examples of (un)familiar and important networks–social networks–content networks–technological networks–biological networks–economic networks•What makes a network interesting?•The distinction between structure and dynamicsContagion and Tipping in Networks•The dynamics of transmission•Viral spread and the epidemic as metaphor•Amplification of the incremental•Connectors, hubs, and small worlds •Travers and Milgram’s famous experiment•Loosely based on Gladwell’s “The Tipping Point”Network Science• “Universal” structural properties of networks–small diameter–clustering–mixtures of local and long-distance connectivity–heavy-tailed distributions•Models of network formation–random graph models–preferential attachment–small-world models–affiliation networks–all will be stochastic or randomized… for now•Loosely based on Watts’ “Six Degrees”The Web as Network•Empirical structure of the web–connected components and directionality–diameter–robustness measures•Web and blog communities•Web search:–hubs and authorities–the PageRank algorithm and organic search–gaming Google and the SEO industry–later: sponsored search•Web trust and network structureTowards Rational Dynamics•Beyond the dynamics of transmission •Dynamics of self-interest and optimization•Introduction to equilibrium concepts•Emergence of the global from the local•The wisdom/madness of crowds:–thresholds and cascades–mathematical models of tipping–the market for lemons–private preferences and global segregation•Loosely based on Schelling’s “Micromotives and Macrobehavior”Game Theory and Networks•The mathematical language of strategic and economic behavior•Notions of equilibrium–Nash, correlated, cooperative, market, bargaining•Multi-player games and markets•Evolutionary game theory–mimicking vs. optimizing•Games and markets on networks•How does network structure influence strategic behavior?•Behavioral game theory and human subject studies–classic example: the Ultimatum gameEconomic Models of Network Formation•Network Science: stochastic models of formation•But networks form for a reason…•Examine game-theoretic formation:–players must purchase the edges…–…but accrue “participation benefits”Sponsored Web Search•Web as Network: PageRank and “organic” search•Sponsored search: formal markets in search phrases•Mechanism design and auctions•Google vs. Yahoo!•Equilibrium studies•The economics of sponsored search•SEO vs. SEMPeer Production•Aka “Web 2.0”•Why do millions of users provide free labor?•When will they do so?•How can we harness or engineer peer production?•The Web, Wikipedia, ESP Game, Prediction Markets, Crowdsourcing, Digg, Facebook, del.icio.us,…Internet