Passengers in city buses are possibly one of the main contributors to the increase in mobile traffic in cellular networks. Instead of each passenger accessing the cellular base station, we may deploy a small cell on the bus to serve these passengers. To reap the benefits of this deployment in the cellular network, resource allocation of the network needs to be addressed carefully. We call the small cells deployed in city buses as moving small cells. In this paper, we propose a probabilistic graph based resource allocation (PGRA) algorithm in a cellular network with moving small cells. We exploit the headway characteristics of city buses to study the interference relationship between different moving small cells. Our performance metric is the number of resource blocks used. Our performance evaluation shows an average decrease of 19.84% in the number of RBs used with moving small cells in the network as compared to a scenario without moving small cells, requiring each passenger to access the base station.