Abstrakt. Vi föreslår en allmän ram och metoder för förenkling av stora nätverk. Metoderna kan användas för att förbättra ett visst näts begriplighet, för att komplettera användarcentrerade analysmetoder eller som ett förbearbetningssteg för beräkning av mer komplexa metoder. Tillvägagångssättet är väg-orienterad: kanterna är beskurna samtidigt som den ursprungliga kvaliteten på bästa vägar mellan alla par av noder (men inte nödvändigtvis alla bästa vägar). Ramverket är tillämpligt på olika typer av grafer (t.ex. flödesnät och slumpmässiga grafer) och anslutningar kan mätas på olika sätt (t.ex. med kortast möjliga väg, maximalt flöde eller maximal sannolikhet). Det har relativa grannskap grafer, spänner träd, och vissa Pathfinder grafer som sina specialfall. Vi ger fyra algoritmiska varianter och rapporterar om experiment med 60 riktiga biologiska nätverk. Förenklingsmetoderna är en del av pågående projekt för intelligent analys av nätverksbaserad information.
Den strategi som är närmast relaterad till vår är vägorienterad förenkling REF, som tar bort kanter som inte påverkar kvaliteten på bästa vägar mellan varje par av noder.
A Framework for Path-Oriented Network Simplification
{'venue': 'IDA', 'journal': None, 'mag_field_of_study': ['Computer Science']}