K-trusten är en typ av sammanhållna subgrafer som nyligen föreslagits för studier av nätverk. Medan problemet med att beräkna mest sammanhängande subgrafer är NP-hård, det finns en polynom tid algoritm för att beräkna k-truss. Jämfört med k-core som också är effektivt att beräkna representerar k-truss "kärnan" i en k-core som håller nyckelinformationen om, samtidigt som den filtrerar bort mindre viktig information från, k-core. Befintliga algoritmer för beräkning av k-truster är dock ineffektiva för hantering av dagens massiva nätverk. Vi förbättrar först den befintliga in-minne algoritmen för att beräkna k-truss i nätverk av måttlig storlek. Sedan föreslår vi två I/O-effektiva algoritmer för att hantera massiva nätverk som inte får plats i huvudminnet. Våra experiment på verkliga datauppsättningar verifierar effektiviteten hos våra algoritmer och värdet av k-truss.
Den I/O-effektiva algoritmen för k-truss-problemet undersöks i REF.
Truss Decomposition in Massive Networks
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}