Abstrakt. Dense subgraph upptäckt är en nyckelfråga i graf mining, på grund av dess betydelse i flera tillämpningar, såsom korrelationsanalys, gemenskap upptäckt i webben, gen co-uttryck och protein-protein interaktioner i bioinformatik. I detta arbete studerar vi upptäckten av topp-k täta subgrafer i en uppsättning grafer. Efter utredningen av problemet i dess statiska fall utökar vi metoden till att arbeta med dynamiska grafsamlingar, där grafsamlingen förändras över tid. Vår metod är baserad på lägre och övre gränser för densiteten, vilket resulterar i en minskning av antalet exakta densitetsberäkningar. Våra algoritmer förlitar sig inte på användardefinierade tröskelvärden och den enda inmatning som krävs är antalet täta subgrafer i resultatet (k). Utöver de exakta algoritmerna tillhandahålls en approximationsalgoritm för toppk täta subgraffynd, som handlar om resultatnoggrannhet för hastighet. Vi visar att ett betydande antal exakta densitetsberäkningar undviks, vilket resulterar i effektiv övervakning av toppk täta subgrafer.
Dessutom har Valari m.fl. REF upptäckte toppk täta subgrafer i dynamiska grafsamlingar med hjälp av både exakta och ungefärliga algoritmer.
Discovery of Top-k Dense Subgraphs in Dynamic Graph Collections
{'venue': 'SSDBM', 'journal': None, 'mag_field_of_study': ['Computer Science']}