Abstract-Networks från olika genrer är inte statiska enheter, men uppvisar dynamiskt beteende. Trafikstockningarna i transportnäten varierar i tid beroende på trafiken. På samma sätt används sociala förbindelser och kommunikationsförbindelser i varierande takt allteftersom informationskaskaderna utvecklas. Under de senaste åren har intresset för modellering och gruvdrift ökat. Begränsad uppmärksamhet har dock ägnats åt upptäckt av högskärande subgrafer i tidevolverande nätverk. Vi definierar problemet med att hitta den högst scoring temporal subgraph i ett dynamiskt nätverk, kallas Heaviest Dynamic Subgraph (HDS). Vi visar att HDS är NP-hård även med kantvikter i {−1, 1}, och utforma en effektiv strategi för stora graf instanser som utvecklas under långa tidsperioder. Medan en naiv strategi skulle räkna upp alla O(t 2 ) sub-intervals, vår lösning utför en effektiv beskärning av sub-interval utrymme genom att överväga O(t · log(t)) grupper av sub-intervals och beräkna ett aggregat av varje grupp i logaritmisk tid. Vi definierar också en snabb heuristic och en tight övre gräns för approximering av den statiska versionen av HDS, och använder dem för ytterligare beskärning av sub-interval utrymme och snabbt verifiera kandidat sub-intervals. Vi utför en omfattande experimentell utvärdering av vår algoritm på transport-, kommunikations- och sociala medienätverk för att upptäcka subgrafer som motsvarar trafikstockningar, kommunikationsspill och lokala sociala diskussioner. Vår metod är två storleksordningar snabbare än en naiv strategi och skalar väl med nätverksstorlek och tidslängd.
I REF undersökte författarna subgraffyndigheten i dynamiska nätverk.
Mining Heavy Subgraphs in Time-Evolving Networks
{'venue': '2011 IEEE 11th International Conference on Data Mining', 'journal': '2011 IEEE 11th International Conference on Data Mining', 'mag_field_of_study': ['Computer Science']}