Social Networks as a Foundation for Computer ScienceA Future for Computer Science?Is there a Science of Networks?Physical NetworksWhat does the Internet look like?US Power GridBusiness & Economic NetworksContent NetworksEnronSocial networksPowerPoint PresentationAcquaintanceship & moreNetwork Models (Barabasi)Web-based social networksGolbeck’s CriteriaCSE 112, Networked Life (UPenn)CompSci 1: Overview CS0What can we do with real data?My recommendations at AmazonAnd again…How do search engines work?Google’s PageRankSlide 23Google’s PageRank (Brin & Page, http://www-db.stanford.edu/~backrub/google.html)Collaborative FilteringMemory-based methodsComputing weights - Cosine CorrelationComputing weights - Pearson & Spearman correlationModel-based methodsSocial Networks, CompSci 49s, 11/16/2006 1Social Networksas a Foundationfor Computer ScienceJeffrey Forbeshttp://www.cs.duke.edu/csed/socialnetSocial Networks, CompSci 49s, 11/16/2006 2A Future for Computer Science?Social Networks, CompSci 49s, 11/16/2006 3Is there a Science of Networks?From Erdos numbers to random graphs to InternetFrom FOAF to Selfish Routing: apparent similarities between many human and technological systems & organizationModeling, simulation, and hypothesesCompelling concepts•Metaphor of viral spread•Properties of connectivity has qualitative and quantitative effectsComputer Science?From the facebook to tomogravityHow do we model networks, measure them, and reason about them?What mathematics is necessary?Will the real-world intrude?Social Networks, CompSci 49s, 11/16/2006 4Physical NetworksThe InternetVertices: Routers Edges: Physical connectionsAnother layer of abstractionVertices: Autonomous systemsEdges: peering agreementsBoth a physical and business networkOther examplesUS Power GridInterdependence and August 2003 blackoutSocial Networks, CompSci 49s, 11/16/2006 5What does the Internet look like?Social Networks, CompSci 49s, 11/16/2006 6US Power GridSocial Networks, CompSci 49s, 11/16/2006 7Business & 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” transactionsSocial Networks, CompSci 49s, 11/16/2006 8Content NetworksExample: Document similarityVertices: documents on webEdges: Weights defined by similaritySee TouchGraph GoogleBrowserConceptual network: thesaurusVertices: wordsEdges: synonym relationshipsSocial Networks, CompSci 49s, 11/16/2006 9EnronSocial Networks, CompSci 49s, 11/16/2006 10Social networksExample: Acquaintanceship networksvertices: people in the worldlinks: have met in person and know last nameshard to measure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How do we navigate in such networks?Social Networks, CompSci 49s, 11/16/2006 11Social Networks, CompSci 49s, 11/16/2006 12Acquaintanceship & moreSocial Networks, CompSci 49s, 11/16/2006 13Network Models (Barabasi)Differences between Internet, Kazaa, ChordBuilding, modeling, predictingStatic networks, Dynamic networksModeling and simulationRandom and Scale-freeImplications?Structure and Evolution Modeling via TouchgraphSocial Networks, CompSci 49s, 11/16/2006 14Web-based social networkshttp://trust.mindswap.orgMyspace 73,000,000Passion.com 23,000,000Friendster 21,000,000Black Planet 17,000,000Facebook 8,000,000Who’s using these, what are they doing, how often are they doing it, why are they doing it?Social Networks, CompSci 49s, 11/16/2006 15Golbeck’s CriteriaAccessible over the web via a browserUsers explicitly state relationshipsNot mined or inferredRelationships visible and browsable by othersReasons?Support for users to make connectionsSimple HTML pages don’t sufficeSocial Networks, CompSci 49s, 11/16/2006 16CSE 112, Networked Life (UPenn)Find the person in Facebook with the most friendsDocument your processFind the person with the fewest friendsWhat does this mean?Search for profiles with some phrase that yields 30-100 matchesGraph degrees/friends, what is distribution?Social Networks, CompSci 49s, 11/16/2006 17CompSci 1: Overview CS0Audioscrobbler and last.fmCollaborative filteringWhat is a neighbor?What is the network?Social Networks, CompSci 49s, 11/16/2006 18What can we do with real data?How do we find a graph’s diameter?This is the maximal shortest path between any pair of verticesCan we do this in big graphs?What is the center of a graph?From rumor mills to DDOS attacksHow is this related to diameter?Demo GUESS (as augmented at Duke)IM data, Audioscrobbler dataSocial Networks, CompSci 49s, 11/16/2006 19My recommendations at AmazonSocial Networks, CompSci 49s, 11/16/2006 20And again…Social Networks, CompSci 49s, 11/16/2006 21How do search engines work?Hotbot, Yahoo, Alta Vista, Excite, …Inverted index with buckets of wordsInsight: use matrix to represent how many times a term appears in one pageColumns: pages & Rows: termsProblems?Return pages that have the keyword - in what order?Early solution: return those pages with most occurrences of term first Problems?Solution?•Use structure of the web to do the work for us•What did Google do?Social Networks, CompSci 49s, 11/16/2006 22Google’s PageRankweb site xxxweb site yyyyweb site a b c d e f gweb site pdq pdq ..web site yyyyweb site a b c d e f gweb site xxxInlinks are “good” (recommendations)Inlinks from a “good” site are better than inlinks from a “bad” sitebut inlinks from sites with many outlinks are not as “good”...“Good” and “bad” are relative.web site xxxSocial Networks, CompSci 49s, 11/16/2006 23Google’s PageRankweb site xxxweb site yyyyweb site a b c d e f gweb site pdq pdq ..web site yyyyweb site a b c d e f gweb site xxxImagine a “pagehopper” that always either• follows a random