De flesta verkliga komplexa nätverk - såsom proteininteraktioner, sociala kontakter, internet - är bara delvis kända och tillgängliga för oss. Medan processen att utforska sådana nätverk i många fall liknar en slumpmässig promenad, blir det en nyckelfråga att undersöka och karakterisera hur effektivt noderna och kanterna av sådana nätverk kan täckas av olika strategier. Samtidigt är det ytterst viktigt att dra en slutsats om hur väl topologiska mätningar såsom den genomsnittliga nodgraden och den genomsnittliga klusterkoefficienten kan beräknas under sådana nätutforskningar. Den här artikeln tar upp dessa problem genom att överväga slumpmässiga och Barabási-Albert (BA) nätverksmodeller med varierande anslutning som utforskas av tre typer av slumpmässiga promenader: traditionella, företräde till ospårade kanter, och företräde till obesökta noder. En serie relevanta resultat erhålls, bland annat det faktum att slumpmässiga modeller och BA-modeller med samma storlek och genomsnittliga nodgrad tillåter liknande nod- och kanttäckningseffektivitet, identifiering av linjär skalning med storleken på nätverket av det slumpmässiga fotsteg där en viss procentandel av noderna/kanterna omfattas, och det kritiska resultatet att uppskattningen av den genomsnittliga nodgraden och klusterkoefficienten genom slumpmässiga promenader på BA-nätverk ofta leder till kraftigt snedvridna resultat. Många är de teoretiska och praktiska konsekvenserna av sådana resultat.
Da Fontoura Costa och Travieso REF studerar nätverkstäckningen av tre typer av slumpmässiga promenader: traditionella, preferenser till ospårade kanter, och preferens till obesökta noder.
Exploring complex networks through random walks.
{'venue': 'Physical review. E, Statistical, nonlinear, and soft matter physics', 'journal': 'Physical review. E, Statistical, nonlinear, and soft matter physics', 'mag_field_of_study': ['Medicine', 'Mathematics', 'Physics']}