Topic Web Mashups
Topic Web Mashups CS 249
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 22 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 249 at Wellesley College taught by Staff in Fall. Since its upload, it has received 37 views. For similar materials see /class/230936/cs-249-wellesley-college in ComputerScienence at Wellesley College.
Reviews for Topic Web Mashups
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
CS 249B Science of Networks Week 14 Monday 042808 Daniel Bilar Wellesley College Spring 2008 l 1 Goals today I How to search Small Worlds networks with only local information I Two Models Kleinberg s single criterion geography model Watts and Dodds s multiple criterion hierarchy model I Serves also as examples of two schools of sc1ent1 c 1nqu1ry Abstracted rationalist prooforiented Kleinberg Em irical experimental dataoriented Watts Do ds Some material and slides gratefully acknowledged from Kearns U Penn 2 Question I Milgram s experiment Columbia Small Worlds all emphasize existence of short paths between pairs But how do individuals nd short paths in an incremental nextstep fashion using purely local information about the network and location of target I This is not just a structural question about network topology but an algorithmicheuristic one l Local vs Global information I Common problem Need to find path search for nodes people a Have only local partial View of network not global total overview I How to we search and find globally with only local information I Two examples 39 Kleinberg s geography grid model Watts and Dodd s hierarchy model 1 Milgram s experiment revisited I What did Milgram s experiment show a There are short paths in large networks that connect individuals b People are able to find these short paths using a simple greedy decentralized algorithm I Small world models take care of a I Kleinberg what about b Kleinberg s thinking I WS with a twist distance I Milgram s senders doing a directed search in a very large social network with limited global information I WS models say uniformly random shortcuts allow for short paths Every node is equally likely to be chosen regardless of where it is located I But no notion of distance in WS Geography class income education interests race Kleinberg s model adds also random links but probability decreases with distance uses geography as distance J Kleinberg s model I Model parameters p q and a I Start with an n by n grid of vertices so N nquot2 u add local connections all vertices within grid distance p eg 2 1w 1i add distant connections q additional connections probability of connection at distance r 1rquot a O 0 O O 0 O 0 large a hea bias towards more local ongdlstance connections small a approach uniformly random Kleinberg s question I Assume parties know only grid address of target addresses of their own direct links I Algorithm pass message to neighbor closest to target I Fine tuning a what value of 1 permits effective search 0 large a heavy bias towards more local longd1stance connectlons small a approach uniformly random 1 Kleinberg s intuition I if a is too large strong local bias then long distance connections never help much short paths may not even exist I if a is too small no local bias we may quickly get close to the target but then we ll have to use local links to finish I Analogy Transport system with only long haul jets or donkey carts effective search requires a delicate balance of link distances I Kleinberg s results I a 2 is the only value that permits rapid navigation log2N steps I Any other value of a will result in time polynomial in n n5 Locality of information crucial to th1s argument Centralized algorithm may compute short paths V Can recognize when backwards steps are beneficial 000009 0 ladd local connections all vertlces w1th1n gr1d distance p here lt 2 steps away Iadd one distant connection q probab111ty of connectlon at 1stance r 1rquota 10 Searching in a small world I For 1 lt 2 the raph has gaths of logarithmic length small world ut a gree y algorithm cannot n them I For 1 gt 2 the graph does not have short paths no small world exists I For a 2 is the only case where there are short paths and the greedy algorithm is able to find them y axis is exponent t 3 of the delivery E g 12mm ebb04 g t1me T lower bound cnl3 2 02 o i i x ax1s IS exponent 0 1 2 3 4 Clustering exponent a 1 Of long range llnkS 11 Int erpretation of r l Each node u has link to the peer v with probability proportional to wh lOp l ruava ere ruv is the distance between u and v timal value a dim dimension of the space If a lt dim we tend to choose more far away nei hbors decentralized algorithm can quickly a proach t e neighborhood of target but then slows down till fina y reaches target itself i If a gt dim we tend to choose more close neighbors algorithm finds quickly target in its neighborhood but reaches it slowly if it is far away When a 0 long range contacts are chosen uniforml Random graph theo proves that there exist short pat s between every pair 0 vertices but there is no decentralized algorithm capable nding these paths 12 I V39 f th W ld Interpretatlon of r Eli 9th iwe9r l Given node if we can partition the remaining node into sets A1 A2 A3 AlogN where A consists oanll nodes whose d1stance from u 1s between 21 and 2H1 l0logN1 Then given r dim each long range contact of u is nearly equally likely to belong to any of the sets A Roughly same number of friends on each scale 13 39 Recap Searching in a small world Given a source s and a destination t define a greedy local search algorithm that 1 knows the positions of the nodes on the grid 2 knows the neighbors and shortcuts of the current node 3 knows the neighbors and shortcuts of all nodes seen so far 4 operates greedily each time moving as close to t as possible Kleinberg proved the following i a When 12 an algorithm that uses only local information at each node not 2 can reach the destination in expected time Olog2n l n When ult2 a local greedy algorithm 14 needs expected time 9012003 When rgt2 a local greedy algorithm 14 needs expected time Qna2a1 n Generalizes for a ddimensional lattice when ad query time is independent of the lattice dimension d 1 the Watts Strogatz model 14 39 1 Conclusions from Kleinberg I With respect to the WS model There is no decentralized algorithm capable performing effective search in the class of SW networks constructed according to Watts and Strogatz I Kleinberg presented the infinite family of Small World networks that generalizes the Watts and Strogatz model and shows that decentralized search algorithms can nd short paths with high probability I There exist only one unique model within that family for which decentralized algorithms are effective 15 l H Dim Searching I Follow up to on Columbia Small World investigation 7 http smallworldcolumbiaedu I With respect to how why social networks are searchable WampD say Kleinberg s model not a satisfactory model of society Based exclusively on geography We don t navigate social networks by purely geographic information Kleinberg s distance We don t use any single criterion Different criteria used a different points in the chain 16 1 Six contentions about social NW WampD model start with plausible assumptions observations about society and individuals 1 Individual don t just have ties but Hdimensional identities in groups 2 Hierarchical treelike cognitive partition of humanity into size wise manageable groups 3 Group membership primary basis for interaction 4 Cognitive partition is done along simultaneous H dimensions via attributes Attribute values have d1stances between them tree structured 5 Social Distance between individuals minimum distance in any attribute 6 Individuals use social distance and network ties to direct messages ef ciently Algorithm given attribute vector of target forward message to neighbor closest to target 17 Navigation via social distance I Model based on hierarchical groups I Represent individuals by a vector of attributes profession religion hobbies education background etc 7 attribute values have distances between them tree structured distance between individuals minimum distance in any attr1bute 7 only need one thing in common to be close I Algorithm given attribute vector of target forward message to neighbor closest to target Identity and search in social networks D J Watts P S Dodds and M E J Newman Science 296 13021305 2002 18 39 1 Navigation via social distance distance hijheightof least Hierarchical organization of groups common ance Individuals in the same dgroup are It an the mum separation of two individuals is x Individuals i and 39 belong to a cate my two leveis above that of their respective groups distance between them is xi 3 Individuals each have z friends are more likely to be connected with each other the closer their groups are see contention 3 in Permits fast decentralized navi ation under broader con tions multlple 1ndependent 39L39 Notdan sensitive as Kleinberg s hierarchies coexist U0 8 l N Main Results Fig 2 A Reg39nns in Hn Space A 39pfx here mrcha inerno s a I I I K c c H39d quot rim 5 Ni ll h F1g 2 1s a good bad example ncfdzslll grnhgbilltyontll mSage i x Wh Q failuren 025 branching ratio 1 y b 2 group see 9 100 J 3 x 39 39 d It 39 Q 39 l Slmulatlon model of H wgch s simpid n 2 I i a a t d1mens1onal h1erarch1cal i i Si 39 f x 39 39 leti St be 11 T quot 39F 39 decentrahzed search and emp1r1cal Ema g mt l a Q l 3 a small world experimental results won1 to boundaries of the Searthdble network regim for N 39 converge m miqgfig gamma r B a 2 I II D 1 an I 39 39 I Best performance for fast mew this L 1 r our Sullhdble networks shrinks w ith decentrahzed search algor1thm gwtisrgng agsaggi va gd m1 Lng D 39Wo u r when 2 or 3 d1mens10ns are use to 39pmim mmai 9 is r Hp 39 navigate nit strewn H HH cienttv large an hdrvidml39s l neighbors must il be contained ith thui 121 at a39 a I W ampD saif model 1s apphcable to a gmti img g 1 3 5 7 H g 11 13 5 decentra lzed searCh On any d39hj 392 circles for the it lEIZACIJ data Set ied in AJiThe horizontal he shwisthe position network has elements nfthe threshold r LrLIS upen Symbols nthsate that the natural is starthalal i qz r and cloned Ej39l39l39hlllli mean chemis For 1 a n Searchdzulitzql degaduswith each additional hierarchy For the quantlfiable hemophilous cm of or 2 with a single hierarchy Lass than 1 crf dl marches ind their target characteristics akin to ether hierard39g increases the success rate to q 39 0144 and q slcmlI identities People music files webpages H dimensions news research reports can be Judges along more than one or 2 measure of homophlly tendency d1mens1on can you name some to group with like 20 3911 Watts amp Dodd vs Kleinberg I WampD says 7 Kleinberg s model not a satisfactory model of society Based exclusively on geography I We don t navigate social networks by purely geographic information Kleinberg s distance i We don t use any single criterion Different criteria used a different points in the chain 21
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'