I detta dokument studerar vi problemet med den förankrade k-kärnan. Med tanke på en graf G, ett heltal k och en budget b, syftar vi till att identifiera b hörn i G så att vi kan bestämma den största inducerade subgraf J där varje vertex, utom b hörn, har minst k grannar i J. Detta problem infördes av Bhawalkar och Kleinberg et al. i samband med användarengagemang i sociala nätverk, där en användare kan lämna ett samhälle om han/hon har färre än k-vänner engagerade. Problemet har visat sig vara NP-hårdt och ouppnåeligt. En polynom-tidsalgoritm för grafer med avgränsad trädbredd har föreslagits. Detta antagande håller dock vanligtvis inte i verkliga grafer, och deras tekniker kan inte utvidgas för att hantera allmänna grafer. Motiverade av detta föreslår vi en effektiv algoritm, nämligen onion-layer baserad förankrad k-core (OLAK), för det förankrade k-core problemet på storskaliga grafer. För att underlätta beräkning av den förankrade k-kärnan designar vi en lökskiktsstruktur, som genereras av en enkel lökpeelingliknande algoritm mot en liten uppsättning hörn i grafen. Vi visar att beräkning av det bästa ankaret helt enkelt kan utföras på hörnen på löklagren, vilket avsevärt minskar sökytan. Baserat på den välorganiserade lagerstrukturen, utvecklar vi effektiva kandidater prospektering, tidig terminering och beskärning tekniker för att ytterligare påskynda beräkningen. Omfattande experiment på 10 verkliga grafer visar effektiviteten och effektiviteten i våra föreslagna metoder.
Det finns en effektiv heuristisk algoritm för den förankrade kcore problem REF, medan det inte bara kan tillämpas för att lösa kant k-core problem.
OLAK: An Efficient Algorithm to Prevent Unraveling in Social Networks
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}