Presentation
Scalable Motif Counting on Large-Scale Dynamic Graphs
DescriptionMotifs, small subgraphs of k vertices, such as triangles and cliques, are well studied for static networks. They are used to characterize different biological networks and align different networks. Counting motifs reveal insights into the topological structure of a network such as MPI event graphs. However, for large networks and motifs, computing these frequencies is computationally expensive. Recent advances into sized-k or less motifs show promise but have difficulty scaling. Moreover, counting the frequency of all sized-k or less motifs on dynamic networks is still lacking.
We present a scalable method to compute the global edge-based frequencies of motifs of size 4 vertices or less on a fully dynamic network. Instead of recomputing the counts from scratch, we update the frequencies based on only the changed edges. Our results show that our method is scalable and outperforms the benchmark results by 10 times.
We present a scalable method to compute the global edge-based frequencies of motifs of size 4 vertices or less on a fully dynamic network. Instead of recomputing the counts from scratch, we update the frequencies based on only the changed edges. Our results show that our method is scalable and outperforms the benchmark results by 10 times.
Event Type
ACM Student Research Competition: Graduate Poster
ACM Student Research Competition: Undergraduate Poster
Doctoral Showcase
Posters
TimeTuesday, 19 November 202412pm - 5pm EST
LocationB302-B305
TP
XO/EX