Networked and Social Systems Engineering (nets) 112 Fall 2014 Prof. Michael Kearns



Download 12,57 Kb.
Date conversion30.01.2017
Size12,57 Kb.

Course Introduction and Overview

  • Networked Life
  • Networked and Social Systems Engineering (NETS) 112
  • Fall 2014
  • Prof. Michael Kearns

A Little Experiment

An Artificial Social Network

  • Consider yourself “connected” to everyone in this room who:
    • Was born within a few hundred miles of the city or town you were born in
    • Or shares one of your favorite hobbies/interests/activities
    • Network is the aggregate of all these pairwise connections
  • Some observations
    • Network is artificial, yet not unrelated to reality --- you really might meet people due to proximity or shared interests
    • Network definition has “knobs” or “parameters” we can fiddle with
      • Radius around your birthplace, strength of interest
      • But might expect certain qualitative properties to remain invariant (NYC density)
  • Seems hard to guess at global structure
    • Might be quite complicated
    • None of us has a bird’s eye view
  • Let’s experiment with navigation or search in this network
    • Communal goal: route a “message” from one part of the network to another
    • Try to do it in as few “hops” as possible
    • The Catch: everyone has only local information about the network
  • Existence of short paths (structure) vs. finding them (algorithm)
  • What happens when we go from 100 to 100 million to 7 billion?

Networks (Social and Otherwise)

  • Internet, 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 riding
  • The 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, competition, free riding,…)
  • An Emerging Science:
    • Examining apparent similarities (and differences) between many social, economic, 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 contagion in networks
      • Dynamics of economic and strategic interaction
    • Quantitative and qualitative; experimental and theoretical
    • Enabled by the revolution of instrumentation and measurement

Who’s Doing All This?

  • Computer Scientists
    • Understand and design complex, distributed networks
    • View “competitive” decentralized systems as economies
  • Social Scientists, Behavioral Psychologists, Economists
  • 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 collaborating

Course 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 world

A Communal Experiment

  • Few similar undergraduate courses
    • (e.g. 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
  • Course was initial inspiration and basis for the new Networked and Social Systems Engineering (NETS) program

Course Outline

What is a Network?

  • Networks as a collection of pairwise relationships
  • Measures: degree, diameter, clustering, centrality, expansion…
  • Examples of (un)familiar and important types of networks
    • social networks
    • content networks
    • technological networks
    • biological networks
    • economic networks
  • What makes a network interesting?
  • The distinction between structure and dynamics

Contagion and Tipping in Networks

  • The dynamics of transmission
  • Viral spread and 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 Structure

  • “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 structure

Towards Rational Dynamics

  • Moving beyond the dynamics of contagion
  • 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

Behavioral Experiments in Social Networks

    • Analyses of recent years’ experiments…
    • … and hopefully some new ones of your own.

Strategic 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
  • Competitive landscape (GOOG vs. MSFT vs. YHOO vs…)
  • Equilibrium studies
  • The economics of sponsored search
  • SEO vs. SEM

Internet Economics

  • Internet basics
  • Selfish routing and The Price of Anarchy
  • Peer-to-peer as competitive economy
  • Paris Metro Pricing for QoS
  • Economic views of network security and spam

Course Mechanics

  • Will make heavy use of course web page:
    • www.cis.upenn.edu/~mkearns/teaching/NetworkedLife
    • You will need good Internet access!
  • No technical prerequisites!!!
  • Lectures:
    • slides provided; emphasis on concepts
    • frequent demos, visualizations, and in-class experiments
    • please be on time to lectures! (10:30)
  • No recitations
  • Readings: mixture of general audience writings and articles from the scientific literature
  • Three required texts:
    • “The Tipping Point”, Gladwell
    • “Six Degrees”, Watts
    • “Micromotives and Macrobehavior”, Schelling
  • Assignments (~1/3 of grade)
    • computer/web exercises, short essays, quantitative problems
    • collaboration is not permitted
  • Midterm (~1/3 of grade)
  • Final exam (~1/3 of grade)
  • Possible we’ll throw in a project/paper assignment

First Assignment

  • Due next lecture (Thursday 9/4)
    • Simple background questionnaire
    • Last-names exercise


The database is protected by copyright ©sckool.org 2016
send message

    Main page