Local community detection with hints

摘要

Local community detection is a widely used method for identifying groups of nodes starting from seeding nodes. The seed(s) are usually selected either randomly or based only on structural properties of the network. However, in many cases the choice of seed(s) incorporates external knowledge that attaches to these nodes an additional importance for their community. This knowledge, may be derived from an expert on the domain, or may arise from the network’s side information and it constitutes our motivation for the present work; this additional information about the importance of seed(s) can be exploited for detection of better and more relevant communities. We call such biased seed(s), hint(s). Our approach, is to reflect the importance of hints by changing appropriately the network in their vicinity. To the best of our knowledge, no such viewpoint of the seeding nodes in local community detection has been considered before. The aim of this study is to identify a single community which contains the hint(s). Our key contribution is the proposed Hint Enhancement Framework(HEF) that applies a two-step procedure to discover the community of the hint(s): 1) it changes the network by amplifying the hint(s) using re-weighting or re-wiring strategies so as to materialize the bias towards them and 2) it applies local community detection algorithms on the altered network of step 1. We experimentally evaluate HEF in synthetic and real datasets, and demonstrate the positive aspects of the framework in identifying better communities, in comparison with plain local community detection algorithms as well as a global one.