Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https://github.com/lyuheng/T-FSM.

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (γ 1 , γ 2 ) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (γ 1 ,γ 2 )-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Micromobility refers to small, lightweight vehicles such as shared bicycles and electric scooters (e-scooters). Recently, shared micromobility services see increasing deployment in urban areas to solve the "last mile´ problem, where the travel distance is considered long when walking on foot, but not worth driving a car (e.g., to avoid parking). A key question to ask when deciding whether to deploy a shared micromobility service in an area is: how much car traffic can be reduced during peak hours if this service is deployed? This work answers this question by agent-based transportation simulation. The key challenge here is to generate a realistic synthetic population of the target area along with their travel day-plans. We propose to use an area-specific travel survey plus openly available data sources for this purpose, and demonstrate our approach through a case study that studied the traffic impacts of deploying dockless e-scooters in Birmingham, AL. A demo of our simulation is available at https://youtu.be/zh_mHQ6ck4U.