Online sociala nätverk har blivit mycket populära under de senaste åren och deras antal användare mäts redan i många hundratals miljoner. För olika kommersiella och sociologiska ändamål är det viktigt med en oberoende uppskattning av deras storlek. I detta arbete, algoritmer för att uppskatta antalet användare i sådana nätverk beaktas. De föreslagna systemen är också tillämpliga för att uppskatta storleken på nätverkens delpopulationer. De föreslagna algoritmerna interagerar med de sociala nätverken endast via sina offentliga API:er och förlitar sig inte på någon annan extern information. På grund av uppenbara trafik- och integritetsproblem är antalet sådana interaktioner kraftigt begränsat. Vi fokuserar därför på att minimera antalet API-interaktioner som behövs för att producera uppskattningar av god storlek. Vi använder abstraktionen av sociala nätverk som oriktade grafer och använder slumpmässig nodprovtagning. Genom att räkna antalet kollisioner eller icke-unika noder i provet, producerar vi en storleksbedömning. Sedan visar vi analytiskt att uppskattningsfelet försvinner med stor sannolikhet för mindre antal prover än de som krävs av tidigare konstalgoritmer. Dessutom, även om våra algoritmer är bevisligen korrekta för alla grafer, utmärker de sig när de tillämpas på sociala nätverksliknande grafer. De föreslagna algoritmerna utvärderades på syntetiska och verkliga sociala nätverk som Facebook, IMDB och DBLP. Våra experiment bekräftade de teoretiska resultaten och visade algoritmernas effektivitet.
Som Katzir et al REF fokuserade sin uppmärksamhet på att bedöma storleken på online-communityn.
Estimating Sizes of Social Networks via Biased Sampling
{'venue': 'Internet Mathematics', 'journal': 'Internet Mathematics', 'mag_field_of_study': ['Mathematics', 'Computer Science']}