Vårt mål är att prova noden uppsättningen av en stor okänd graf via krypning, att korrekt uppskatta ett givet mått av intresse. Vi designar en slumpmässig promenad på en lämpligt definierad viktad graf som uppnår hög effektivitet genom att företrädesvis krypa dessa noder och kanter som förmedlar mer information om målet metrisk. Vår strategi börjar med att använda teorin om stratifiering för att hitta optimala nodvikter, för en given uppskattning problem, under en oberoende provtagare. Medan optimal under oberoende provtagning, dessa vikter kan vara opraktiska under graf krypande på grund av begränsningar som uppstår från strukturen av grafen. Därför bör kantvikterna för vår slumpmässiga gång väljas för att leda till en jämviktsfördelning som skapar en balans mellan att approximera de optimala vikterna under en oberoende provtagare och att uppnå snabb konvergens. Vi föreslår en heuristisk metod (stratifierad viktad slumpmässig gång, eller S-WRW) som uppnår detta mål, samtidigt som endast begränsad information om grafstrukturen och nodegenskaperna används. Vi utvärderar vår teknik i simulering, och experimentellt, genom att samla ett urval av Facebook college användare. Vi visar att S-WRW kräver 13-15 gånger färre prover än den enkla omviktade randomgången (RW) för att uppnå samma uppskattningsnoggrannhet för ett intervall av mätvärden.
En slumpmässig gång har utformats på en lämpligt definierad viktad graf REF, som uppnår hög effektivitet genom att företrädesvis krypande noder och kanter som förmedlar rik information.
Walking on a graph with a magnifying glass: stratified sampling via weighted random walks
{'venue': 'PERV', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}