The Networked Nature of SocietyWhat is a Network?Some DefinitionsExamples of Networks“Real World” Social NetworksOnline Social NetworksMK’s Friendster NW, 1/19/04Content NetworksBusiness and Economic NetworksPhysical NetworksAgenda: Thursday, Jan 20Biological NetworksNetwork StaticsNetwork DynamicsNetwork FormationStructure, Dynamics, Formation: Two Case StudiesCase Study 1: A (Brain-Dead) Model of Economic ExchangeCase Study 2: Grandmother Cells, Associative Memory, and Random NetworksA Back-of-the Envelope AnalysisRemarksRecapThe Networked Natureof SocietyNetworked LifeCSE 112Spring 2005Prof. Michael KearnsWhat 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 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 u: number of edgesExamples 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 Mansour  Alon  Erdos–how do we navigate in such networks?Online Social Networks•A very recent 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)–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 interdependenceAgenda: Thursday, Jan 20•Finish up “Networked Nature…” lectures•Detail and due date for first network construction project task•Introduction to Lifester and first assignmentBiological 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 statistics across many networks–will also use the term topology to refer to structure•Structure can reveal:–community–“important” vertices, centrality, etc.–robustness and vulnerabilities–can also impose constraints on dynamics•Less emphasis on what actually occurs on network–web pages are linked… but people surf the web–buyers and sellers exchange goods and cash–friends are connected… but have specific interactionsNetwork Dynamics•Emphasis on what happens on networks•Examples: –mapping spread of disease in a social network–mapping spread of a fad–computation in the brain•Statics and dynamics often closely linked–rate of disease spread (dynamic) depends critically on network connectivity (static)–distribution of wealth depends on network topology•Gladwell emphasizes dynamics–but often dynamics of transmission–what about dynamics involving deliberation, rationality, etc.?Network Formation•Why does a particular structure emerge?•Plausible processes for network formation?•Generally interested in processes that are–decentralized–distributed–limited to local communication and interaction–“organic” and growing–consistent with measurement•The Internet versus traditional telephonyStructure, Dynamics, Formation: Two Case StudiesCase Study 1: A (Brain-Dead) Model of Economic Exchange•Imagine an(y) undirected, connected network of