Target Oriented Network Intelligence Collection (TONIC) is a problem which deals with acquiring maximum number of profiles in the online social network so as to maximize the information about a given target through these profiles. The acquired profiles, also known as leads in this paper, are expected to contain information which is relevant to the target profile. TONIC problem has been solved by modeling it as search problem and using heuristics to direct the best-first search on the social graph. The problem with this approach is that in case of dense neighbors of the target profile the computation of the heuristic can be significantly expensive. In this paper, we have introduced a k-beam search Heuristic which significantly mitigates this overhead. © 2020, Springer Nature Singapore Pte Ltd.