Många online sociala nätverk har restriktiva webbgränssnitt som bara tillåter frågan om en användares lokala grannskap. För att möjliggöra analys över ett sådant socialt nätverk online genom sitt webbgränssnitt, många senaste ansträngningar använder Markov Chain Monte Carlo (MCMC) metoder som slumpmässiga promenader för att prova användare i det sociala nätverket och därmed stödja analys baserad på proverna. Problemet med ett sådant tillvägagångssätt är dock den stora mängd frågor som ofta krävs för en slumpmässig promenad för att konvergera till en önskad (stationär) provtagningsdistribution. I denna artikel, vi anser ett nytt problem med att möjliggöra en snabbare slumpmässig promenad över online sociala nätverk genom att "omkoppla" det sociala nätverket i farten. Specifikt utvecklar vi en modifierad Topology Sampling (MTO-Sampling) schema som, genom att använda endast information som exponeras av det restriktiva webbgränssnittet, konstruerar en "virtuell" slumpmässig-walk-vänlig overlay topologi av det sociala nätverket samtidigt utföra en slumpmässig promenad och ser till att den slumpmässiga promenaden följer den modifierade overlay topologin snarare än den ursprungliga. Vi beskriver i denna artikel ögonblick av MTO-Sampling för olika typer av slumpmässiga promenader, såsom Simple Random Walk (MTO-SRW), Metropolis-Hastings Random Walk (MTO-MHRW), och General Random Walk (MTO-GRW). Vi bevisar inte bara styvt att MTO-Sampling förbättrar effektiviteten i provtagning, utan vi visar också betydelsen av en sådan förbättring genom experiment på verkliga online sociala nätverk som Google Plus, Epinion, Facebook, etc. Ett socialt nätverk online tillhandahåller inte bara en plattform för användare att dela information med sina bekanta, utan utgör också en rik resurs för ett brett spektrum av tredjepartsanalyser, såsom analys av rykte/nyheter spridning över ett socialt nätverk, utvinning av känslor av sociala nätverk användare på vissa ämnen, och, mer allmänt, social-nätverk-baserad marknadsforskning. Även om vissa tredje parter (t.ex. annonsörer) kan förhandla om avtal med ägaren av det sociala nätverket för att få tillgång till hela den underliggande databasen, saknar många tredje parter resurser för att göra det. För att möjliggöra analysprogram från tredje part utan full tillgång till databasen, måste man kunna uppskatta stora bilder (t.ex. genomsnittsåldern för användare, COUNT för användarposter som innehåller ett givet nyckelord) på ett socialt nätverk online genom att ge ut ett litet antal individuella användarfrågor via det sociala nätverkets webbgränssnitt. Vi tar itu med detta problem av tredje part aggregerad uppskattning i denna artikel. En viktig utmaning som tredje part står inför är bristen på samarbete från leverantörer av sociala nätverk på nätet. I synnerhet, den information som returneras av varje enskild användare fråga är extremt begränsad, endast innehåller information om grannskapet av en användare. Dessutom, nästan alla storskaliga online sociala nätverk genomdriva gränser för det antal webbförfrågningar man kan utfärda (t.ex. 600 öppna graf frågor per 600 sekunder för Facebook, 2 och 350 förfrågningar per timme för Twitter 3 ). Som ett resultat är det praktiskt taget omöjligt att få hela topologin av ett socialt nätverk och / eller krypa alla användardata innan generera aggregerade uppskattningar. Befintliga tekniker: För att ta itu med denna utmaning har ett antal provtagningsmetoder föreslagits för att utföra analyser över ett socialt nätverk online utan förutsättningen att krypa [Leskovec och Faloutsos 2006; Jin et al. 2011; Katzir m.fl. Europaparlamentets och rådets förordning (EU) nr 182/2011 av den 16 februari 2011 om fastställande av allmänna regler och principer för medlemsstaternas kontroll av kommissionens utövande av sina genomförandebefogenheter (EUT L 55, 28.2.2011, s. År 2010 )........................................................................................................... Syftet med provtagningen är att slumpmässigt välja ut element (t.ex. noder/användare eller kanter/relationer) från det sociala nätet på nätet enligt en förutbestämd sannolikhetsfördelning och sedan generera aggregerade skattningar baserade på de återvunna proven. Eftersom endast enskilda lokala stadsdelar (dvs. en användare och uppsättningen av sina grannar), snarare än hela graf topologi, kan hämtas från det sociala nätverkets webbgränssnitt, de flesta befintliga samplorer bygger på idén att utföra slumpmässiga promenader över grafen som bara utfärdar ett litet antal individuella användare frågor som motsvarar de lokala stadsdelar som besöks av en slumpmässig promenad. I litteraturen finns det flera populära slumpmässiga gångalgoritmer: Simple Random Walk (SRW) [Lovász 1993] börjar från en godtycklig användare, upprepade gånger hoppar från en användare till en annan genom att välja jämnt slumpmässigt från den tidigare användarens grannskap, och stannar efter ett antal steg för att hämta prover. När SRW är tillräckligt lång tenderar sannolikheten för att varje användare ska provtas att nå en stationär (sannolikhet) fördelning som är proportionell mot varje användares grad (dvs. antalet användare som är anslutna till användaren). Det som motiverar oss att hämta prover från sociala nätverk online är att vi kan generera aggregerad information såsom medelålder, antal YouTube-abonnenter och antal tweets som läggs ut dagligen, vilket vi hänvisar till som exempel på AVG-aggregat, COUNT-aggregat och SUM-aggregat. En formell definition av dessa
Zhou m.fl. REF modifierar den vanliga RW genom att "rewiring" nätverket av intresse på flygningen för att minska blandningstiden för promenaden.
Faster Random Walks by Rewiring Online Social Networks On-the-Fly
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}