Fake news propagation has a significant negative effect on society, especially in the current era - where online social networks accelerates the information propagation. Therefore, identifying fake news when they begin to spread is an important task. Past studies have focused mainly on the theoretical modeling of fake news propagation, and on utilizing the feature of their text and users for identification. However, the propagation network features of fake news collected from social networks have rarely been studied. Here, we study and compare the structural features of propagation networks inferred from fake and real news collected from Weibo in China and Twitter in Japan between the years 2012-2016. We compare various structural measures of the propagation networks and we find that fake and real news networks have distinct topological characteristics. For example, the degree heterogeneity of fake news is significantly smaller than that of real news. We find that these distinct structural features emerge within few hours from the first repost in most networks, which allows an early detection of fake news. Our results help to understand the mechanism of fake news spread and propose new structural considerations for detecting and preventing the spread of fake news in their early stage.