Abstract-Vi föreslår ett nytt problem för att förenkla viktade grafer genom att beskära minst viktiga kanter från dem. Förenklade grafer kan användas för att förbättra visualiseringen av ett nätverk, för att extrahera dess huvudsakliga struktur, eller som ett förbearbetningssteg för andra data mining algoritmer. Vi definierar en graf konnektivitet funktion baserat på de bästa vägarna mellan alla par av noder. Med tanke på antalet kanter som ska beskäras, problemet är då att välja en delmängd av kanter som bäst upprätthåller den totala grafen anslutning. Vår modell är tillämplig på ett brett spektrum av inställningar, inklusive probabilistiska grafer, flödesgrafer och avståndsgrafer, eftersom den sökväg kvalitet funktion som används för att hitta bästa vägar kan definieras av användaren. Vi analyserar problemet, och ger lägre gränser för effekten av individuell kant avlägsnande i fallet där banan kvalitet funktion har en naturlig rekursiv egenskap. Vi föreslår sedan en rad algoritmer och rapporterar om experimentella resultat på verkliga nätverk som härrör från offentliga biologiska databaser. Resultaten visar att en stor del av kanterna kan tas bort ganska snabbt och med minimal effekt på den totala grafanslutningen. En grov semantisk analys av de borttagna kanterna visar att få viktiga kanter togs bort, och att den föreslagna metoden skulle kunna vara ett värdefullt verktyg för att hjälpa användare att se eller utforska viktade grafer.
I REF infördes idén om att förenkla viktade nät genom att beskära de minst viktiga kanterna från dem.
Network Simplification with Minimal Loss of Connectivity
{'venue': '2010 IEEE International Conference on Data Mining', 'journal': '2010 IEEE International Conference on Data Mining', 'mag_field_of_study': ['Computer Science']}