Course Introduction and OverviewSlide 2Slide 3Slide 4Slide 5Slide 6The Premise of Networked LifeWho’s Doing All This?Course MissionA Communal ExperimentCourse OutlineThe Networked Nature of Society (~2 lectures)Contagion, Tipping and Networks (~2 lectures)Introduction to Graph Theory (~1 lecture)Social Network Theory (~3 lectures)The Web as Network (~2 lectures)Towards Rationality: Emergence of Global from Local (~1 lecture)An Introduction to Game Theory (~2 lectures)Interdependent Security and Networks (~1 lecture)Network Economics (~2 lectures)Behavioral Economics (~1 lectures)Internet Basics (~1 lecture)Internet Economics (~2 lectures)Modern Financial Markets (~2 lectures)Course MechanicsFirst AssignmentCourse Introductionand OverviewNetworked LifeCSE 112Spring 2006Prof. Michael KearnsInternet, Router Level•A purely technological network?•“Points” are physical machines•“Links” are physical wires•Interaction is electronic•What more is there to say?North American Power Grid•Points: power stations•Operated by companies•Connections embody business relationships•Food for thought:–2003 Northeast blackoutGnutella Peers•Points are still machines… but are associated with people •Links are still physical… but may depend on preferences•Interaction: content exchange•Food for thought:“free riding”Foreign Exchange•Points: sovereign nations•Links: exchange volume•A purely virtual networkThe Human Brain•Purely biological network•Links are physical•Interaction is electrical•Food for thought:–Do neurons cooperate or compete?The Premise of Networked Life•It makes sense to study these diverse networks together.•The 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 and technological 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•Physicists and Mathematicians–Interest and methods in complex systems–Theories of macroscopic behavior (phase transitions)•All parties 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–psychology and sociology–mathematics–physics•Emphasize the common themes•Develop a new way of examining the worldA Communal Experiment•No similar undergraduate course•No formal technical prerequisites–greatly aided by recent books–publications in Science, Nature, etc.–preliminary class demographics:•~37% freshmen/sophomore•~52% College/Wharton•Extensive web visualizations and demos•Extensive participatory in-class and out-of-class social experiments•Exercises in data analysis•Note: Networked Life is now approved to fulfill the College’s Quantitative Data Analysis Requirement•Also counts as an SEAS engineering elective courseCourse OutlineThe Networked Nature of Society(~2 lectures)•Networks as a collection of pairwise relations•Examples of (un)familiar and important networks–social networks–content networks–technological networks–biological networks–economic networks•The distinction between structure and dynamicsA network-centric overview of modern society.Contagion, Tipping and Networks(~2 lectures)•Epidemic as metaphor•The three laws of Gladwell:–Law of the Few (connectors in a network)–Stickiness (power of the message)–Power of Context •The importance of psychology•Perceptions of others•Interdependence and tipping•Paul Revere, Sesame Street, Broken Windows, the Appeal of Smoking, and Suicide EpidemicsInformal case studies from social behavior and pop culture.Introduction to Graph Theory(~1 lecture)•Networks of vertices and edges•Graph properties:–cliques, independent sets, connected components, cuts, spanning trees,…–social interpretations and significance •Special graphs:–bipartite, planar, weighted, directed, regular,…•Computational issues at a high levelBeginning to quantify our ideas about networks.Social Network Theory(~3 lectures)•Metrics of social importance in a network:–degree, closeness, between-ness, clustering…•Local and long-distance connections•SNT “universals”–small diameter–clustering–heavy-tailed distributions•Models of network formation–random graph models–preferential attachment–affiliation networks•Examples from society, technology and fantasyA statistical application of graph theory to human organization.The Web as Network(~2 lectures)•Empirical web structure and components•Web and blog communities•Web search:–hubs and authorities–the PageRank algorithm•The Main Streets and “dark alleys” of the webThe algorithmic implications of network structure.Towards Rationality:Emergence of Global from Local(~1 lecture)•Beyond the dynamics of transmission •Context, motivation and influence•The madness/wisdom of crowds:–thresholds and cascades–mathematical models of tipping–the market for lemons–private preferences and global segregationBegin to connect to classical issues of human and societal behavior.An Introduction to Game Theory(~2 lectures)•Models of economic and strategic interaction•Notions of equilibrium–Nash, correlated, cooperative, market, bargaining•Multi-player games•Evolutionary game theory–mimicking vs. optimizing•Network effects•Social choice theoryPowerful mathematical models of what happensover links in competitive and cooperative settings.Interdependent Security and Networks(~1