MIT ESD 342 - Search and Navigation on Social and other Networks (50 pages)

Previewing pages 1, 2, 3, 24, 25, 26, 27, 48, 49, 50 of 50 page document View the full content.
View Full Document

Search and Navigation on Social and other Networks



Previewing pages 1, 2, 3, 24, 25, 26, 27, 48, 49, 50 of actual document.

View the full content.
View Full Document
View Full Document

Search and Navigation on Social and other Networks

65 views


Pages:
50
School:
Massachusetts Institute of Technology
Course:
Esd 342 - Network Representations of Complex Engineering Systems
Network Representations of Complex Engineering Systems Documents
Unformatted text preview:

Lecture 14 Search and Navigation on Social and other Networks Affiliation Hierarchies Christopher L Magee April 4 2006 Professor C Magee 2006 Page 1 Lecture 14 Outline Introductory Remarks Search and Navigation search briefly Navigation Milgram s experiment and critiques Kleinberg s first model The influence of structure and Kleinberg s second model and the Watts Dodds and Newman model Modeling Overview Search navigation as case study of model evolution Modeling limitations and benefits The fundamental modeling tradeoff Systems and applications of most interest Professor C Magee 2006 Page 2 Search and Navigation Search To look over carefully in order to find something to explore to make an effort to find something seek hunt quest Navigate To plan record and control the position of to follow a planned Course or to make one s way Use of maps is not explicitly mentioned but their usage relative to navigation seems more normal than for search Professor C Magee 2006 Page 3 Search and Navigation Search To look over carefully in order to find something to explore to make an effort to find something seek hunt quest Network literature to find the node containing information that is desired Navigate To plan record and control the position of to follow a planned Course or to make one s way Network literature to get from one to another specific node by a the short est path using only local information Professor C Magee 2006 Page 4 Network Search I Exhaustive WWW Search Catalog while crawling the network and create a map local index of the entire network Use information in nodes to select relevant web pages Rank nodes for significance using the link information Eigenvector Centrality Brin and Page Each node has a weight i that is defined to be proportional to the weights of all nodes that point to i And xi 1 j Aij x j x And then Ax x Thus the weights are an eigenvector of the adjacency matrix A with eigenvalue Kleinberg has considered a more sophisticated version with weights for pointing hubs and receiving hubs Professor C Magee 2006 Page 5 Network Search II Guided Search databases or the web for unmapped elements Web spiders Queries passed if not answered to highest k node of neighbors If some nearest neighbor information is also stored this is a valuable approach for peer to peer systems This last approach takes advantage of structure with knowledge of high k nodes being present Professor C Magee 2006 Page 6 Network Navigation Milgram s experiment The unpublished but widely circulated paper of Kochen and Pool using simple random graph models indicated the possibility of short paths through social networks This instigated the famous social scientist Stanley Milgram to try an experiment route letter to person XXX who is a stockbroker living in Sharon MA who works in Boston The letters can only be sent to someone who the recipient knows on a first name basis but in a way to get closer to person XXX Participants also were asked to record and send along the routing information Professor C Magee 2006 Page 7 Social networks Milgram s experiment Figure removed for copyright reasons Source Milgram Psych Today 2 60 1967 Professor C Magee 2006 Page 8 Milgram s experiment route letter to person XXX who is a stockbroker living in Sharon MA who works in Boston The letters can only be sent to someone who the recipient knows on a first name basis but in a way to get closer to person XXX Some guesses that it would take hundreds of steps were refuted by results that showed it took actually can take much less Professor C Magee 2006 Page 9 Six degrees of separation Distance Figure removed for copyright reasons Source Milgram Psych Today 2 60 1967 Professor C Magee 2006 Page 10 Milgram s experiment II route letter to person XXX who is a stockbroker living in Sharon MA who works in Boston The letters can only be sent to someone who the recipient knows on a first name basis but in a way to get closer to person XXX Some guesses that it would take hundreds of steps were refuted by results that showed it took actually can take much less A play was written and coined the phrase six degrees of separation as its Title and Milgram s result became something everyone knows Everyone is separated by only six removes from everyone else on the planet But What did Milgram really show Professor C Magee 2006 Page 11 What did Milgram really show Of 300 letters in original experiment only 96 random Nebraska sampled tested the everyone part of what everyone knows Only 18 of these were ever returned the preceding graph contained very non random Nebraska letters Other trials that were random and tested the everyone basis had even smaller return rates than Milgram s initial experiment Issues Is everyone really 6 or less steps from everyone Professor C Magee 2006 Page 12 Small world networks Regular Figure by MIT OCW After Watts Strogatz 1998 Random Small world Increasing Randomness p 0 p 1 Figure by MIT OCW After Watts Strogatz 1998 1 N 1000 0 8 Large clustering coeff C p C 0 0 6 Short typical path 0 4 0 2 Watts Strogatz Nature 393 440 1998 0 0 0001 L p L 0 0 001 p 0 01 0 1 Professor C Magee 2006 Page 13 1 Ubiquity of small world networks N L p N N F N Figure by MIT OCW After Barrat Weigt 2000 1 0 8 N 100 0 6 L p Figure by MIT OCW After Watts Strogatz 1998 Bertelemy and Amaral Phys Rev Lett 83 3180 1999 Newman Watts Phys Lett A 263 341 1999 Barrat Weigt Eur Phys J B 13 547 2000 0 4 N 20000 0 2 0 N 10 5 1 p 10 4 p Professor C Magee 2006 Page 14 10 2 1 Potential short paths There are almost surely relatively short paths between any two individuals The path length is apparently about that calculated for random networks ln n l ln k For n representative of the whole world this would give path lengths as large as 10 20 Even though 10 degrees of separation does not sound as impressive it is still small As a model the Small World Model is obviously primitive as a Systems Formation Model For this phenomena purpose explaining Milgram s experiment is this its most serious shortfall Professor C Magee 2006 Page 15 Schematic of Engineering System Model Types within a Framework Architecture structure Observation Models System Structure Quantified by a Rich set of metrics System Formation Models predict Structure System formation mechanisms and constraints Properties Modelsmodels to predict properties from structure System Properties understood quantitatively in terms of desirability Professor C Magee 2006 Page 16 What did Milgram really show Of


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Search and Navigation on Social and other 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 Search and Navigation on Social and other Networks 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?