Abstract-Estimerande egenskaper hos stora grafer via provtagning är avgörande i studien av komplexa nätverk. I detta arbete studerar vi Mean Squared Error (MSE) i samband med olika provtagningsmetoder för examensfördelningen. Dessa provtagningsmetoder inkluderar oberoende slumpmässig vertex (RV) och slumpmässig (RE) provtagning, och krypande metoder såsom slumpmässiga promenader (RWs) och den allmänt använda MetropolisHastings algoritm för enhetlig provtagning hörn (MHRWu). Vi ser att RW MSE är övre begränsas av en kvantitet som är proportionell mot RE MSE och omvänt proportionell mot spektral gapet i RW övergång sannolikhetsmatrisen. Vi bestämmer också under vilka förhållanden RW är att föredra framför RV. Slutligen presenterar vi en approximation av MHRWu MSE. Vi utvärderar exaktheten i våra approximationer och gränser genom simuleringar på stora verkliga grafer.
Ribeiro m.fl. studerade det genomsnittliga kvadratfelet medan du datoriserade graden distribution av nätverket REF.
On the estimation accuracy of degree distributions from graph sampling
{'venue': '2012 IEEE 51st IEEE Conference on Decision and Control (CDC)', 'journal': '2012 IEEE 51st IEEE Conference on Decision and Control (CDC)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}