CompSci 100e 12.1 Is there a Science of Networks? !! What kinds of networks are there? !! From Bacon 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? CompSci 100e 12.2 From subsets to graphs with bits !! We’ll consider SequenceSync APT !! What is a “vertex” in the graph? Where are arcs? !! For state-0, we have {1,5,4,2} for transitions !! We’ll consider a graph in which vertices are sets of states !! Start with every possible state in our initial vertex 0 1 4 5 0 2 1 0 2 3 CompSci 100e 12.3 Six Degrees of Kevin Bacon !! Background !! Stanley Milgram’s Six Degrees of Separation? !! Craig Fass, Mike Ginelli, and Brian Turtle invented it as a drinking game at Albright College !! Brett Tjaden and Glenn Wasson put it on the web at UVA in 1995 !! Patrick Reynolds (Duke CS PhD) ran it since 1999 !! Link people to Kevin Bacon based on movies they have been in together !! Morgan Freeman was in Se7en with Brad Pitt !! Brad Pitt was in Sleepers with Kevin Bacon !! Morgan Freeman has a Bacon number of 2 !! Who has a Bacon number of 4 or more? The Oracle of Bacon Internet Movie Database Linking Engine Web server oracleofbacon.org •! Linking Engine: –!Is written in C –!Stores all movie data in memory –!Answers link, number, and center queries –!Doesn’t actually use Oracle™Inside the Linking Engine •! All three types of queries use breadth-first search Kevin Bacon BN = 0 Mystic River Apollo 13 Footloose John Lithgow Sarah Jessica Parker Bill Paxton Tom Hanks Sean Penn Tim Robbins BN = 1 Inside the Linking Engine •! All three types of queries use breadth-first search Kevin Bacon Mystic River Apollo 13 Footloose John Lithgow Sarah Jessica Parker Bill Paxton Tom Hanks Sean Penn Tim Robbins BN = 0 BN = 1 Sweet and Lowdown Fast Times at Ridgemont High War of the Worlds The Shawshank Redemption Cast Away Forrest Gump Tombstone A Simple Plan Morgan Freeman Sally Field Helen Hunt Val Kilmer Miranda Otto Judge Reinhold Woody Allen Billy Bob Thornton BN = 2 Inside the Linking Engine •! Link Val Kilmer to Kevin Bacon Mystic River Footloose John Lithgow Sarah Jessica Parker Tom Hanks Sean Penn Tim Robbins BN = 0 BN = 1 Sweet and Lowdown Fast Times at Ridgemont High War of the Worlds The Shawshank Redemption Cast Away Forrest Gump A Simple Plan Morgan Freeman Sally Field Helen Hunt Miranda Otto Judge Reinhold Woody Allen Billy Bob Thornton BN = 2 Bill Paxton Tombstone Val Kilmer Apollo 13 Kevin Bacon •! How good a center is Kevin Bacon? –!Average everyone’s Bacon number –!Currently 2.963, ranked 1222nd •! Who is exactly 2 hops away from Kevin Bacon? –!This whole column –!Currently 163,002 people Inside the Linking Engine Mystic River Footloose John Lithgow Sarah Jessica Parker Tom Hanks Sean Penn Tim Robbins Sweet and Lowdown Fast Times at Ridgemont High War of the Worlds The Shawshank Redemption Cast Away Forrest Gump A Simple Plan Morgan Freeman Sally Field Helen Hunt Miranda Otto Judge Reinhold Woody Allen Billy Bob Thornton Bill Paxton Tombstone Val Kilmer Apollo 13 Kevin BaconCaching •! Keep whole BFS trees for common queries –!Takes about 4MB of memory each •! Perform 75-85% fewer BFS calculations –!Faster website response time CompSci 100e 12.10 Center of the Hollywood Universe !! 739,979 people can be connected to Bacon !! Is he the center of the Hollywood Universe? !! Who is? !! Who are other good centers? !! What makes them good centers? !! Centrality !! Closeness: the inverse average distance of a node to all other nodes •! Geodesic: shortest path between two vertices •! Closeness centrality: number of other vertices divided by the sum of all distances between the vertex and all others. !! Degree: the degree of a node !! Betweenness: a measure of how much a vertex is between other nodes CompSci 100e 12.11 Word ladder CompSci 100e 12.12 Vocabulary !! Graphs 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/cost !! A 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 cycle !! A graph is connected if there is a path between any pair of vertices NYC Phil Boston Wash DC 204 78 190 268 394 LGA LAX ORD DCA $186 $186 $412 $1701 $441CompSci 100e 12.13 Graph questions/algorithms !! What vertices are reachable from a given vertex? !! Two standard traversals: depth-first, breadth-first !! Find connected components, groups of connected vertices !! Shortest path between any two vertices (weighted graphs?) !! Breadth first search is storage expensive !! Dijkstra’s algorithm is efficient, uses a priority queue too! !! Longest path in a graph !! No known efficient algorithm !! Visit all vertices without repeating? Visit all edges? !! With minimal cost? Hard! CompSci 100e 12.14 Vocabulary/Traversals !! Connected? !! Connected components? •! Weakly connected (directionless) !! Degree: # edges incident a vertex •! indegree (enter), outdegree (exit) !! Starting at 7 where can we get? !! 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) !! Rooms are stacked up, backtracking is really recursion !! One alternative uses a queue: breadth-first search CompSci 100e 12.15 Breadth first search !! In an unweighted graph this finds the shortest path between a start vertex and every vertex !! Visit every node one away from start !! Visit every node two away from start •! This is every node one away from a node one away !! Visit every node three away from start, … !! Put vertex on queue to start (initially just one) !! Repeat: take vertex off queue, put all adjacent vertices on !! Don’t put a vertex on that’s already been visited (why?) !! When are 1-away vertices enqueued?
View Full Document
Unlocking...