News and NotesCourse ReviewAn Emerging ScienceCourse Vision and MissionCourse OutlineThe Networked Nature of SocietyWhat is a Network?“Real World” Social NetworksContent NetworksContagion, Tipping and NetworksKey Characteristics of TippingThree Sources of TippingThe Strength of Weak TiesIntroduction to Graph TheorySocial Network TheoryA “Canonical” Natural Network has…Some Models of Network GenerationHeavy-tailed DistributionsRecapFormalizing Tipping: Thresholds for Monotone PropertiesSo Which Properties Tip?The Clustering Coefficient of a NetworkCaveman and SolariaMeanwhile, Back in the Real World…Preferential AttachmentFinding Short PathsThe Web as NetworkFive Easy PiecesThe HITS System (Hyperlink-Induced Topic Search)The PageRank AlgorithmEmergence of Global from LocalGlobal Conflict from Local PreferencesVolleyball, Critical Mass and TippingLocal Preferences and SegregationAn Introduction to Game TheoryThe World According to NashBoard Games and Game TheoryRepeated GamesCorrelated EquilibriumA More Complex Setting: BargainingSocial Games on Networks: Interdependent SecurityThe Airline Security ProblemThe IDS Model [Kunreuther and Heal]Results of SimulationThe Tipping PointBehavioral EconomicsHow People Ultimatum-BargainTwo Problems with Game TheoryA New Theory of UtilitySubjective RandomizationMarket Economies and NetworksMathematical EconomicsMarket EquilibriumA Network Model of Market EconomiesNetwork EquilibriumA Sample Network and EquilibriumEvolutionary Game TheoryEvolution Without BiologyEvolutionary Stable StrategiesThe EGT AppletInternet EconomicsCompetition in the InternetCase Study: Selfish RoutingClosing RemarksNews and Notes•HW4 due now for all those not present•HW4 due Tuesday for those present–please sign attendance sheet–place HW in Prof. Kearns’ mailbox in CIS dept office, 3rd floor•No MK office hours today–will hold some extended OHs next week, announce by email•Today:–course review–course evaluationCourse ReviewNetworked LifeCSE 112Spring 2004Prof. Michael KearnsAn 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•Structure, asymmetry and heterogeneity•Details of interaction matter greatly•The metaphor of viral spread•Qualitative and quantitative; can be very subtle•A revolution of–measurement–theory–breadth of visionCourse Vision and Mission•A network-centric examination of a wide range of social, technological, 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 worldCourse OutlineThe Networked Nature of Society•Networks as a collection of pairwise relations•Examples of familiar and important networks–Social networks–Content networks–Technological networks–Economic networks•The distinction between structure and dynamics•Network formationA network-centric overview of modern society.What is a Network?•A collection of individual or atomic entities•Referred to as nodes or vertices•Collection of links or edges between vertices•Links represent pairwise relationships•Links can be directed or undirected•Network: entire collection of nodes and links•Extremely general, but not everything:–actors appearing in the same film–lose information by pairwise representation•We will be interested in properties of networks–often statistical properties of families of networks“Real World” Social Networks•Example: Acquaintanceship networks–vertices: people in the world–links: have met in person and know last names–hard to measure–let’s do our own Gladwell estimate•Example: scientific collaboration–vertices: math and computer science researchers–links: between coauthors on a published paper–Erdos numbers : distance to Paul Erdos–Erdos was definitely a hub or connector; had 507 coauthors–MK’s Erdos number is 3, via Mansour  Alon  Erdos–how do we navigate in such networks?Content Networks•Example: document similarity–vertices: documents on the web–links: defined by document similarity (e.g. Google)–here’s a very nice visualization–not the web graph, but an overlay content network•Of course, every good scandal needs a network–vertices: CEOs, spies, stock brokers, other shifty characters–links: co-occurrence in the same article•Then there are conceptual networks–vertices: concepts to be discussed in NW Life–links: arbitrarily determined by Prof. Kearns•Update: here are two more examples [thanks Hanna Wallach!]–a thesaurus defines a network–so do the interactions in a mailing listContagion, Tipping and Networks•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.Key Characteristics of Tipping•Contagion:–“viral” spread of disease, ideas, knowledge, etc.–spread is determined by network structure–network topology will influence outcomes•who gets “infected”, infection rate, number infected•Amplification of the incremental:–small changes can have large, dramatic effects•network topology, infectiousness, individual behavior•Sudden, not gradual change:–phase transitions and non-linear phenomenaThree Sources of Tipping•The Law of the Few (Messengers):–Connectors, Mavens and Salesman–Hubs and Authorities•The Stickiness Factor (Message):–The “infectiousness” of the “message” itself•The Power of Context:–global influences affecting messenger behaviorThe Strength of Weak Ties•Not all links are of equal importance•Granovetter 1974: study of job searches–56% found current job via a personal connection–of these, 16.7% saw their contact “often”–the rest saw their contact “occasionally” or “rarely”•Your “closest” contacts might not be the most useful–similar backgrounds and experience–they may not know much more than you do–connectors derive power from a large fraction of weak ties•Further evidence in Dodds et al.