News and Notes, 1/12News and Notes, 1/17News and Notes, 1/19The Networked Nature of SocietyWhat is a Network?Some DefinitionsTypes of Networks“Real World” Social NetworksOnline Social NetworksMK’s Friendster NW, 1/19/04Content NetworksBusiness and Economic NetworksPhysical NetworksBiological NetworksNetwork StaticsNetwork DynamicsNetwork FormationStructure, Dynamics, Formation: Two Brief Case StudiesCase Study 1: A “Contagion” Model of Economic ExchangeCase Study 2: Grandmother Cells, Associative Memory, and Random NetworksA Back-of-the Envelope AnalysisRemarksRecapNews and Notes, 1/12•Please give your completed handout from Tue to Jenn now•Reminder: Mandatory out-of-class experiments 1/24 and 1/25–likely time: either 5-7PM or 6-8 PM–both sessions are required–if you are registered and cannot make one or both sessions, send Prof Kearns email ASAP (including time constraints)•please use “Experiments” as subject lineNews and Notes, 1/17•You should be reading “The Tipping Point”•Reminder: Mandatory out-of-class experiments 1/24 and 1/25–likely time: either 5-7PM or 6-8 PM–both sessions (Tuesday and Wednesday) are required–if you are registered and cannot make one or both sessions, send Prof Kearns email ASAP (including time constraints)•please use “Experiments” as subject line–confirmation of your attendance will be sent out later this weekNews and Notes, 1/19•You should be reading “The Tipping Point”•Two new assigned articles on the web page•UPDATE ON EXPERIMENTS:–Tue 1/24, Wed 1/25–Both sessions 6 – 8 PM; end time is approximate only–Location: 207 Moore–Need to arrive promptly and be present for entire session–Confirmation of your expected attendance(s) will be emailed to you–LAST CALL FOR CONFLICTS!–You must be present at Tuesday’s class to participate in either sessionThe Networked Natureof SocietyNetworked LifeCSE 112Spring 2006Prof. Michael KearnsWhat is a Network?•A collection of individual or atomic entities•Referred to as nodes or vertices (the “dots” or “points”)•Collection of links or edges between vertices (the “lines”)•Links can represent any pairwise relationship•Links can be directed or undirected•Network: entire collection of nodes and links•For us, a network is an abstract object (list of pairs) and is separate from its visual layout–that is, we will be interested in properties that are layout-invariant•Extremely general, but not everything:–e.g. menage a trois–may lose information by pairwise representation•We will be interested in properties of networks–often structural properties–often statistical properties of families of networksSome Definitions•Network size: total number of vertices (denoted N)•Maximum number of edges: N(N-1)/2 ~ N^2/2•Distance between vertices u and v:–number of edges on the shortest path from u to v–can consider directed or undirected cases–infinite if there is no path from u to v•Diameter of a network:–worst-case diameter: largest distance between a pair–average-case diameter: average distance•If the distance between all pairs is finite, we say the network is connected; else it has multiple components•Degree of vertex v: number of edges connected to vTypes 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 examine the results of our own last-names exercise•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 Kearns  Mansour  Alon  Erdos–how do we navigate in such networks?Online Social Networks•Now outdated and discredited example: Friendster–vertices: subscribers to www.friendster.com–links: created via deliberate invitation–Here’s an interesting visualization by one user•More recent and interesting: thefacebook•Older example: social interaction in LambdaMOO–LambdaMOO: chat environment with “emotes” or verbs–vertices: LambdaMOO users–links: defined by chat and verb exchange–could also examine “friend” and “foe” sub-networksMK’s Friendster NW, 1/19/04•Number of friends (direct links): 8•NW size (<= 4 hops): 29,901•13^4 ~ 29,000•But let’s look at the degree distribution•So a random connectivity pattern is not a good fit•What is???•Another interesting online social NW:–AOL IM BuddyzooContent Networks•Example: document similarity–vertices: documents on the web–links: defined by document similarity (e.g. Google’s related search)–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–a thesaurus defines a network–so do the interactions in a mailing listBusiness and Economic Networks•Example: eBay bidding–vertices: eBay users–links: represent bidder-seller or buyer-seller–fraud detection: bidding rings•Example: corporate boards–vertices: corporations–links: between companies that share a board member•Example: corporate partnerships–vertices: corporations–links: represent formal joint ventures•Example: goods exchange networks–vertices: buyers and sellers of commodities–links: represent “permissible” transactionsPhysical Networks•Example: the Internet–vertices: Internet routers–links: physical connections–vertices: Autonomous Systems (e.g. ISPs)–links: represent peering agreements–latter example is both physical and business network•Compare to more traditional data networks•Example: the U.S. power grid–vertices: control stations on the power grid–links: high-voltage transmission lines–August 2003 blackout: classic example of interdependenceBiological Networks•Example: the human brain–vertices: neuronal cells–links: axons connecting cells–links carry action potentials–computation: threshold behavior–N ~ 100 billion–typical degree ~ sqrt(N)–we’ll return to this in a moment…Network Statics•Emphasize purely structural properties–size, diameter, connectivity, degree distribution, etc.–may examine