Approval of emergency use of the Novel Coronavirus Disease 2019 (COVID-19) vaccines in many countries has brought hope to ending the COVID-19 pandemic sooner. Considering the limited vaccine supply in the early stage of COVID-19 vaccination programs in most countries, a highly relevant question to ask is: who should get vaccinated first? In this article we propose a network information- driven vaccination strategy where a small number of people in a network (population) are categorized, according to a few key network properties, into priority groups. Using a network-based SEIR model for simulating the pandemic progression, the network information-driven vaccination strategy is compared with a random vaccination strategy. Results for both large-scale synthesized networks and real social networks have demonstrated that the network information-driven vaccination strategy can significantly reduce the cumulative number of infected individuals and lead to a more rapid containment of the pandemic. The results provide insight for policymakers in designing an effective early-stage vaccination plan.