Online Social Networks (OSNs) have provided an infrastructure for a number of emerging applications in recent years, e.g., for the recommendation of service providers, where trust is one of the most important factors for the decision-making of service consumers. In order to evaluate the trustworthiness of a service provider (i.e., the target) without any prior interaction with a service consumer (i.e., the source), the trust network from the source to the target need to be extracted firstly before performing any trust evaluation, as it contains some important intermediate participants, the trust relations between the participants, and the social context, each of which has an important influence on trust evaluation. However, the network extraction has been proved to be NP-Complete. Towards solving this challenging problem, we first propose a complex contextual social network structure which considers some social contexts, having significant influences on both social interactions and trust evaluation between participants. Then, we propose a new concept called QoTN (Quality of Trust Network) and a social context-aware trust network discovery model. Finally, we propose a Heuristic Social Context-Aware trust Network discovery algorithm (H-SCAN) by adopting the K-Best-First Search (KBFS) method and our optimization strategies. The experimental results illustrate that our proposed model and algorithm outperform the existing methods in both algorithm efficiency and the quality of the extracted trust networks.