  Community search is a personalized community discovery problem aimed at
finding densely-connected subgraphs containing the query vertex. In particular,
the search for communities with high-importance vertices has recently received
a great deal of attention. However, existing works mainly focus on conventional
homogeneous networks where vertices are of the same type, but are not
applicable to heterogeneous information networks (HINs) composed of multi-typed
vertices and different semantic relations, such as bibliographic networks. In
this paper, we study the problem of high-importance community search in HINs. A
novel community model is introduced, named heterogeneous significant community
(HSC), to unravel the closely connected vertices of the same type with high
attribute values through multiple semantic relationships. An HSC not only
maximizes the exploration of indirect relationships across entities of the
anchor-type but incorporates their significance. To search the HSCs, we first
develop online algorithms by exploiting both segmented-based meta-path
expansion and significance increment. Specially, a solution space reuse
strategy based on structural nesting is designed to boost the efficiency. In
addition, we further devise a two-level index to support searching HSCs in
optimal time, based on which a space-efficient compact index is proposed.
Extensive experiments on real-world large-scale HINs demonstrate that our
solutions are effective and efficient for searching HSCs, and the index-based
algorithms are 2-4 orders of magnitude faster than online algorithms.
