Penn CIS 112 - Collective Human Computation in Networks

Unformatted text preview:

News and Notes: Feb 9Collective Human Computation in Networks: Beyond Shortest PathsGraph ColoringsMatchings in GraphsCliques and Independent SetsThe ResultsSlide 7Slide 8Slide 9Slide 10Slide 11Just 40 More Times and You Can Buy a Share of GoogleSocial Network Theory“Natural” Networks and UniversalitySome Interesting QuantitiesA “Canonical” Natural Network has…Some Models of Network GenerationApproximate RoadmapProbabilistic Models of NetworksStatistics and Probability Theory: The Absolute, Bare Minimum EssentialsProbability and Random VariablesSome Basic Notions and LawsConvergence to ExpectationsThe Normal DistributionThe Binomial DistributionThe Poisson DistributionHeavy-tailed DistributionsDistributions vs. DataZipf’s LawModels of Network Generation and Their PropertiesThe Erdos-Renyi (ER) Model (Random Graphs)A Closely Related ModelAnother Closely Related ModelThe Evolution of a Random NetworkRecapCombining and Formalizing Familiar IdeasMonotone Network PropertiesFormalizing Tipping: Thresholds for Monotone PropertiesSo Which Properties Tip?Ever More Precise…Other Tipping Points?Erdos-Renyi SummaryThe Clustering Coefficient of a NetworkErdos-Renyi: Clustering CoefficientCaveman and SolariaMaking it (Somewhat) Precise: the a-modelSmall Worlds and Occam’s RazorMeanwhile, Back in the Real World…Case 1: Kevin Bacon GraphCase 2: Western States Power GridCase 3: C. Elegans Nervous SystemTwo More ExamplesOne More (Structural) Property…Preferential AttachmentTwo Out of Three Isn’t Bad…Slide 56The MidtermSearch and NavigationFinding Short PathsKleinberg’s ModelKleinberg’s ResultNavigation via IdentityNext Up: The Web as NetworkNews and Notes: Feb 9•Watts talk reminder: –tomorrow at noon, Annenberg School (3620 Walnut), Room 110–extra credit reports•Turn in revisions of NW Construction Project, Task 1–MK will review quickly–deadline for Task 2 set shortly; start working!•Description of Tuesday class experiments •Social Network Theory, continuedCollective Human Computation in Networks: Beyond Shortest Paths•Travers and Milgram, Dodds et al., Kleinberg,…:–human networks can efficiently route messages–using only local topology and info on target•What about other computations?–minimum coloring –maximum matching–maximum independent set•Participation on Tuesday is for course credit•Start at 12:05 sharp•You will be given a score for each experiment–but as long as you participate, you will receive full credit•$50 cash prize will be split between those with the highest total score•An experimental investigation of the Price of Anarchy:–comparison of centralized “social optimum” and decentralized “greedy” solutionsGraph Colorings•A coloring of an undirected graph is:–an assignment of a color (label) to each vertex–such that no pair connected by an edge have the same color–chromatic number of graph G: fewest colors needed•Example application: –classes and exam slots–chromatic number determines length of exam period•Here’s a coloring demo•Computation of chromatic numbers is hard–(poor) approximations are possible•Interesting fact: the four-color theorem for planar graphs•Here is a description of our Lifester Coloring ExperimentMatchings in Graphs•A matching of an undirected graph is:–a subset of the edges –such that no vertex is “touched” more than once–perfect matching: every vertex touched exactly once–perfect matchings may not always exist (e.g. N odd)–maximum matching: largest number of edges•Can be found efficiently; here is a perfect matching demo•Example applications:–pairing of compatible partners•perfect matching: nobody “left out”–jobs and qualified workers•perfect matching: full employment, and all jobs filled–clients and servers•perfect matching: all clients served, and no server idle•Here is a description of our Lifester Matching ExperimentCliques and Independent Sets•A clique in a graph G is a set of vertices:–informal: that are all directly connected to each other–formal: whose induced subgraph is complete–all vertices in direct communication, exchange, competition, etc.–the tightest possible “social structure”–an edge is a clique of just 2 vertices–generally interested in large cliques•Independent set:–set of vertices whose induced subgraph is empty (no edges)–vertices entirely isolated from each other without help of others•Maximum clique or independent set: largest in the graph•Maximal clique or independent set: can’t grow any larger•Here is a description of our Lifester Independent Set ExperimentThe ResultsThe chromatic number of the Lifester network is 4...…and the 43 class members present computed a legal 5-coloring.The Lifester network has a maximum independent set of size 16...… and the class computed a maximal independent set of size 13.(mean degree of winners: 4 mean degree of losers: 5.3)The Lifester network has a maximum matching of size 21… and the class found one.(mean degree of score 2: 5 mean degree of others: 3.8)Just 40 More Times and You Can Buy a Share of GoogleCHEN,CHARLENECHENG,ZAISHAOFAULKNER,ELIZABETHFRANK,WILLIAMGROFF,MAX JOHNNIDIS,CHRISTOPHERLAWEE,AARONLEIKER,MATTHEWMUTREJA,MOHITRYTERBAND,JASONSILENGO,MICHAELSWANSON,EDWARDPost-experiment analysis assignment due in class Tuesday!Social Network TheoryNetworked LifeCSE 112Spring 2005Prof. Michael Kearns“Natural” Networks and Universality•Consider the many kinds of networks we have examined:–social, technological, business, economic, content,…•These networks tend to share certain informal properties:–large scale; continual growth–distributed, organic growth: vertices “decide” who to link to–interaction restricted to links–mixture of local and long-distance connections–abstract notions of distance: geographical, content, social,…•Do natural networks share more quantitative universals?•What would these “universals” be?•How can we make them precise and measure them?•How can we explain their universality?•This is the domain of social network theory•Sometimes also referred to as link analysisSome Interesting Quantities •Connected components:–how many, and how large?•Network diameter:–maximum (worst-case) or average?–exclude infinite distances? (disconnected components)–the small-world phenomenon•Clustering:–to what extent to links tend to cluster “locally”?–what is


View Full Document

Penn CIS 112 - Collective Human Computation in Networks

Documents in this Course
Load more
Download Collective Human Computation in Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Collective Human Computation in Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Collective Human Computation in Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?