With the proliferation of proximity based services/applications, Device-to-Device (D2D) communication has become an emerging technology in facilitating data transfer among proximal cellular User Equipments (UEs). However one of the most challenging issues in D2D communication is the need for a robust device discovery scheme that effectively discovers UEs without any performance bottlenecks. In a densely populated cellular network, the conventional device discovery schemes proposed in the literature suffer from one or more adversities. High signaling overhead, large number of collisions and inefficient use of resources are some of the major issues that severely limit the performance of a device discovery scheme. Based on the characteristics of the network-assisted and autonomous device discovery schemes, we propose a novel device discovery scheme that discovers proximal UEs without causing any significant performance degradation. The cellular UEs are first divided into clusters based on their social relationship status and common interests. Every cluster will then execute a device discovery algorithm which is composed of two stages. In the first stage, UEs discover their neighbors using the conventional beacon based discovery scheme. The second stage comprises of successful UEs reporting to BS by initiating the LTE random access procedure. In this way, we not only reduce the signaling overhead but also enable substantial number of device discoveries to happen simultaneously at any instant of time. Further, we present a stochastic geometry based framework to analyze the collision probability and link discovery probability of the proposed scheme. Through extensive simulations we find that our proposed device discovery scheme effectively results in higher discovery probability compared to a recently proposed discovery scheme, by reducing the amount of collisions.