Abstract-Analys av stora nätverk är en kritisk komponent i många av dagens tillämpningsmiljöer, inklusive online sociala nätverk, proteininteraktioner i biologiska nätverk, och Internet trafikanalys. Ankomsten av massiva nätverksgrafer med hundratals miljoner noder, t.ex. sociala grafer, utgör en unik utmaning för grafanalys applikationer. De flesta av dessa applikationer bygger på datoravstånd mellan nodpar, som för stora grafer kan ta minuter att beräkna med hjälp av traditionella algoritmer som bredd-första-sök (BFS). I detta dokument studerar vi sätt att möjliggöra skalbara grafprocesser för dagens massiva nätverk. Vi utforskar designutrymmet för grafkoordinatsystem, ett nytt tillvägagångssätt som exakt approximerar nodavstånd i konstant tid genom att inbädda grafer i koordinatutrymmen. Vi visar att en hyperbolisk inbäddning ger relativt låg distorsionsfel, och föreslår Rigel, ett hyperboliskt grafkoordinatsystem som lämpar sig för effektiv parallellisering över ett datorkluster. Rigel producerar betydligt mer exakta resultat än tidigare system, och är naturligt parallelliserbara över compute kluster, så att det kan ge exakta resultat för grafer upp till 43 miljoner noder. Slutligen visar vi att Rigels funktionalitet enkelt kan utökas för att lokalisera (nära) kortaste vägar mellan nodpar. Efter en gång förbehandling kostar, Rigel besvarar nod-distans frågor i 10-tals mikrosekunder, och producerar också kortaste vägen resultat upp till 18 gånger snabbare än tidigare kortaste-pat system med liknande nivåer av noggrannhet. Index Terms-Online Social Network, Graph Coordinate Sys tem. Snabb och skalbar analys av stora nätverk är en viktig komponent i många av dagens applikationsmiljöer, bland annat i sociala nätverk på nätet, nätverk för biologisk proteininteraktion och analys av internetrouterns ryggrad. Till exempel kan ett socialt spelnätverk söka efter "centrala" användare för att hjälpa till att distribuera nya spel, medan en social auktionsplats [1] vill berätta för en köpare om en viss vara auktioneras ut av någon i hennes sociala kretsar. Helst bör sådana frågor besvaras snabbt, oavsett storleken på grafen, eller även om graferna själva förändras över tiden. Tyvärr är dessa mål helt enkelt ouppnåeliga för dagens sociala nätverk online. Detta beror på att många grafanalys problem såsom centralitet beräkning, nod separanson, och gemenskap upptäckt alla förlitar sig på den enkla nodavstånd (längd kortaste vägen) primitiva, som skalar dåligt med graf (eller nätverk) storlek. För grafer som genereras från sociala nätverk som Facebook (700 miljoner noder), Linkedin (l00 miljoner) och Twitter (200 miljoner), kan det kortaste avståndet mellan ett enda par noder ta en minut eller 77 mer med traditionella algoritmer som bredd-första-sök (BFS) [2]. På samma sätt ska varianter som Dijkstra och Floyd War inte heller skalas till dessa nätverksstorlekar. Utan ett effektivt alternativ för kompilering av nodavstånd har det senaste arbetet inriktats på att utforska effektiva ap-proximeringsalgoritmer [2], [3], [4]. Vårt tidigare arbete [4] beskrev idén om grafkoordinatsystem, som inbäddar grafnoder i punkter på ett koordinatsystem. De resulterande koordinaterna kan användas för att snabbt approximera nodavståndsförfrågningar på den ursprungliga grafen. Vårt ursprungliga system, Orion, var ett centraliserat system som approximerade nodavstånd genom att kartlägga noder till det euklideiska koordinatsystemet [4]. Den har flera begränsningar i praktiken. Först, Orions inledande graf inbäddningsprocessen är centraliserad och beräknings dyrt, som presenterar en betydande prestanda flaskhals för större grafer. För det andra ger Orions resultat felfrekvenser mellan 15 % och 20 %, vilket begränsar de typer av tillämpningar som kan användas. Slutligen är det omöjligt att producera faktiska vägar som förbinder nodpar, vilket ofta är nödvändigt för ett antal grafapplikationer. I detta arbete strävar vi efter att utvidga arbetet med grafkoordinatsystem genom att utveckla ett praktiskt system som avsevärt förbättrar noggrannheten, skalbarheten och den utvidgade funcnaliteten. Vi undersöker systematiskt beslut i utformningen av ett grafkoordinatsystem och gör två viktiga observationer. För det första föreslår vi att vi utökar vårt arbete med grafkoordinatsystem genom att inbädda stora grafer i ett hyperboliskt utrymme för mindre distorsionsfel. Vår inbäddningsalgoritm parallelliserar naturligt den kostsamma inbäddningsprocessen över flera servrar, vilket gör det möjligt för vårt system att snabbt bädda in multi miljoner noddiagram. För det andra föreslår vi ett nytt sätt att använda grafkoordinater för att effektivt lokalisera kortaste vägar mellan nodpar. Resultatet av vårt arbete är Rigel, ett hyperboliskt grafkoordinatsystem som stöder frågor om både nodavstånd och kortaste vägar på dagens stora sociala grafer. Efter en engångs, lätt parallelliserbara, förbehandlingsfas, Rigel kan lösa frågor i tiotals mikrosekunder, även för massiva sociala grafer upp till 43 miljoner noder. I vårt dokument beskrivs fyra viktiga bidrag. • I avsnitten III och IV beskriver vi Rigels detaljerade design och visar hur vi kan minimera inbäddningstiden genom att effektivt parallellisera de dyraste delarna av grafens inbäddningsprocess. • Vi utvärderar en distribuerad prlW tt 17tfSilQrkJ6lYJl
Antalet landmärken bör vara lika med, eller till och med högre än dimensionen av inbäddat utrymme REF.
Efficient shortest paths on massive social graphs
{'venue': '7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)', 'journal': '7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)', 'mag_field_of_study': ['Computer Science']}