Graphs, the Internet, and EverythingIs there a Science of Networks?Jon KleinbergVocabularyTraversalsDepth-first search on GraphsBFS compared to DFSGraph implementationsGraph implementations (continued)Six Degrees of BaconHow does the Oracle work?How does the Oracle Work?Slide 13Center of the Hollywood Universe?CompSci 100e11.1Graphs, the Internet, and Everythinghttp://www.caida.org/CompSci 100e11.2Is there a Science of Networks?What kinds of networks are there?From Bacon numbers to random graphs to InternetFrom FOAF to Selfish Routing: apparent similarities between many human and technological systems & organizationModeling, simulation, and hypothesesCompelling concepts•Metaphor of viral spread•Properties of connectivity has qualitative and quantitative effectsComputer Science?From the facebook to tomogravityHow do we model networks, measure them, and reason about them?What mathematics is necessary?Will the real-world intrude?CompSci 100e11.3Jon Kleinberg2005 MacArthur Fellow, 2008 Infosys Award, 2008 Discover “20 Best Brains under 40”Networks course and bookCompSci 96 Spring 2010"....Try to keep an open mind about topics and areas going on....It's much easier to make progress on a problem when you are enjoying what you are doing. In addition to finding work that is important, find work that has some personal interest for you....I've benefited from a lot of mentoring throughout my career. I think it's important to pass it on to the next generation and work in a mentoring capacity or a teaching capacity with people entering the field....”ACM Infosys InterviewCompSci 100e11.4VocabularyGraphs are collections of vertices and edges (vertex also called node)Edge connects two vertices•Direction can be important, directed edge, directed graph•Edge may have associated weight/costA vertex sequence v0, v1, …, vn-1 is a path where vk and vk+1 are connected by an edge.If some vertex is repeated, the path is a cycleA graph is connected if there is a path between any pair of verticesWhat vertices are reachable from a given vertex?Traverse the graph…NYCPhilBostonWash DC20478190268394LGALAXORDDCA$186$186$412$1701$441CompSci 100e11.5TraversalsWhat vertices are reachable from a given vertex?Connected components?Degree: # edges incident a vertexStarting at Bacon where can we get?Random search, choose a neighboring vertex at random •Can we move in circles?Depth-first search, envision each vertex as a room, with doors leading out•Go into a room, mark the room, choose an unused door, exit–Don’t go into a room you’ve already been in (see mark)•Backtrack if all doors used (to room with unused door)•Used in Percolation assignmentRooms are stacked up, backtracking is really recursionOne alternative uses a queue: breadth-first searchCompSci 100e11.6Depth-first search on Graphspublic Set<Graph.Vertex> dfs(Graph.Vertex start){ Set<Graph.Vertex> visited = new TreeSet<Graph.Vertex>(); Stack<Graph.Vertex> qu = new Stack<Graph.Vertex>(); visited.add(start); qu.push(start); while (qu.size() > 0){ Graph.Vertex v = qu.pop(); for(Graph.Vertex adj : myGraph.getAdjacent(v)){ if (! visited.contains(adj)) { visited.add(adj); qu.push(adj); } } } return visited;}CompSci 100e11.7BFS compared to DFSpublic Set<Graph.Vertex> bfs(Graph.Vertex start){ Set<Graph.Vertex> visited = new TreeSet<Graph.Vertex>(); Queue<Graph.Vertex> qu = new LinkedList<Graph.Vertex>(); visited.add(start); qu.add(start); while (qu.size() > 0){ Graph.Vertex v = qu.remove(); for(Graph.Vertex adj : myGraph.getAdjacent(v)){ if (! visited.contains(adj)) { visited.add(adj); qu.add(adj); } } } return visited;}CompSci 100e11.8Graph implementationsTypical operations on graph:Add vertexAdd edge (parameters?)getAdjacent(vertex)getVertices(..)String->Vertex (vice versa)Different kinds of graphsLots of vertices, few edges, sparse graph•Use adjacency listLots of edges (max # ?) dense graph•Use adjacency matrixAdjacency listCompSci 100e11.9Graph implementations (continued)Adjacency matrixEvery possible edge represented, how many?Adjacency list uses O(V+E) spaceWhat about matrix?Which is better?What do we do to get adjacent vertices for given vertex?What is complexity?Compared to adjacency list?What about weighted edges?T F…CompSci 100e11.10Six Degrees of BaconBackgroundStanley Milgram’s Six Degrees of Separation?Craig Fass, Mike Ginelli, and Brian Turtle invented it as a drinking game at Albright CollegeBrett Tjaden, Glenn Wasson, Patrick Reynolds have run t online website from UVa and beyondInstance of Small-World phenomenonhttp://oracleofbacon.org handles 2 kinds of requests1. Find the links from Actor A to Actor B. 2. How good a center is a given actor?How does it answer these requests?CompSci 100e11.11How does the Oracle work?Not using Oracle™Queries require traversal of the graphBN = 0Mystic RiverApollo 13FootlooseJohn LithgowSarah Jessica ParkerBill PaxtonTom HanksSean PennTim RobbinsBN = 1Kevin BaconCompSci 100e11.12How does the Oracle Work?Kevin BaconMystic RiverApollo 13FootlooseJohn LithgowSarah Jessica ParkerBill PaxtonTom HanksSean PennTim RobbinsBN = 0BN = 1Sweet and LowdownFast Times at Ridgemont HighWar of the WorldsThe Shawshank RedemptionCast AwayForrest GumpTombstoneA Simple PlanMorgan FreemanSally FieldHelen HuntVal KilmerMiranda OttoJudge ReinholdWoody AllenBilly Bob ThorntonBN = 2BN = Bacon NumberQueries require traversal of the graphCompSci 100e11.13How does the Oracle work?Mystic RiverFootlooseJohn LithgowSarah Jessica ParkerTom HanksSean PennTim RobbinsBN = 0BN = 1Sweet and LowdownFast Times at Ridgemont HighWar of the WorldsThe Shawshank RedemptionCast AwayForrest GumpA Simple PlanMorgan FreemanSally FieldHelen HuntMiranda OttoJudge ReinholdWoody AllenBilly Bob ThorntonBN = 2Bill PaxtonTombstoneVal KilmerApollo 13Kevin BaconHow do we choose which movie or actor to explore next?Queries require traversal of the graphCompSci 100e11.14Center of the Hollywood Universe?1,018,678 people can be connected to BaconIs he the center of the Hollywood Universe?Who is?Who are other good centers?What makes them good centers?CentralityCloseness: the inverse
View Full Document
Unlocking...