Community membership identification from small seed sets

摘要: In many applications we have a social network of people and would like to identify the members an interesting but unlabeled group or community. We start with small number exemplar -- they may be followers political ideology fans music genre need use those examples discover additional members. This problem gives rise seed expansion in community detection: given example members, how can graph used predict identities remaining, hidden members? contrast global detection (graph partitioning covering), is best suited for identifying communities locally concentrated around nodes interest. A growing body work has as scalable means detecting overlapping communities. Yet despite interest expansion, there are divergent approaches literature still isn't systematic understanding which different domains. Here evaluate several variants uncover subtle trade-offs between approaches. explore properties set improve performance, focusing on heuristics that one control practice. As consequence this found opportunities performance gains. also consider adaptive version requests made membership labels particular nodes, such finds field studies leads connections contrasts active learning exploration exploitation. Finally, topological sets correlate algorithm explain these empirical observations theoretical ones. our methods across multiple domains, using publicly available datasets labeled, ground-truth