Abstract-Graphs utgör en naturlig modell för relationer och interaktioner mellan enheter, till exempel mellan människor i sociala nätverk och samarbetsnätverk, servrar i datornätverk, eller taggar och ord i dokument och tweets. Men vilka av dessa relationer eller interaktioner är de mest bestående? I detta papper studerar vi följande problem: med tanke på en uppsättning graf ögonblicksbilder, som kan motsvara tillståndet för en föränderlig graf vid olika tidpunkter, identifiera den uppsättning noder som är de mest tätt anslutna i alla ögonblicksbilder. Vi kallar detta problem för "Best Friends For Ever" (BFF) problem. Vi ger definitioner för densitet över flera graf ögonblicksbilder, som fångar olika semantik av uppkoppling över tid, och vi studerar motsvarande varianter av BFF-problemet. Vi tittar sedan på On-Off BFF (O 2 BFF) problem som slappnar av kravet på noder som är anslutna i alla ögonblicksbilder, och ber om den tätaste uppsättningen noder i minst k av en given uppsättning graf ögonblicksbilder. Vi visar att detta problem är NP-komplett för alla definitioner av densitet, och vi föreslår en uppsättning effektiva algoritmer. Slutligen presenterar vi experiment med syntetiska och verkliga dataset som visar både effektiviteten i våra algoritmer och nyttan av BFF och O 2 BFF problem.
Semertzidis m.fl. REF introducerar problemet med att identifiera en uppsättning hörn som är tätt anslutna i alla eller åtminstone k tidstampar i ett tidsnät.
Best Friends Forever (BFF): Finding Lasting Dense Subgraphs
{'venue': 'Data Mining and Knowledge Discovery - Journal Track of ECML PKDD 2019', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}