We exploit the core-periphery structure and the strong homophilic properties of online social networks to develop faster and more accurate algorithms for user interest prediction. The core of modern social networks consists of relatively few influential users, whose interest profiles are publicly available, while the majority of peripheral users follow enough of them based on common interests. Our approach is to predict the interests of the peripheral nodes starting from the interests of their influential connections. To this end, we need a formal model that explains how common interests lead to network connections. Thus, we propose a stochastic interest formation model, the Nearest Neighbor Influence Model (NNIM), which is inspired by the Hegselmann-Krause opinion formation model and aims to explain how homophily shapes the network. Based on NNIM, we develop an efficient approach for predicting the interests of the peripheral users. At the technical level, we use Variational Expectation-Maximization to optimize the instantaneous likelihood function using a mean-field approximation of NNIM. We prove that our algorithm converges fast and is capable of scaling smoothly to networks with millions of nodes. Our experiments on standard network benchmarks demonstrate that our algorithm runs up to two orders of magnitude faster than the best known node embedding methods and achieves similar accuracy.