  In many advanced network analysis applications, like social networks,
e-commerce, and network security, hotspots are generally considered as a group
of vertices that are tightly connected owing to the similar characteristics,
such as common habits and location proximity. In this paper, we investigate the
formation of hotspots from an alternative perspective that considers the routes
along the network paths as the auxiliary information, and attempt to find the
route hotspots in large labeled networks. A route hotspot is a cohesive
subgraph that is covered by a set of routes, and these routes correspond to the
same sequential pattern consisting of vertices' labels. To the best of our
knowledge, the problem of Finding Route Hotspots in Large Labeled Networks has
not been tackled in the literature. However, it is challenging as counting the
number of hotspots in a network is #P-hard. Inspired by the observation that
the sizes of hotspots decrease with the increasing lengths of patterns, we
prove several anti-monotonicity properties of hotspots, and then develop a
scalable algorithm called FastRH that can use these properties to effectively
prune the patterns that cannot form any hotspots. In addition, to avoid the
duplicate computation overhead, we judiciously design an effective index
structure called RH-Index for storing the hotspot and pattern information
collectively, which also enables incremental updating and efficient query
processing. Our experimental results on real-world datasets clearly demonstrate
the effectiveness and scalability of our proposed methods.
