A Hierarchical Random Tree Model To Uncover Hierarchical Structure In Road Networks

Hierarchical structure is one of the most significant features in complex networks.The road network has an intrinsic hierarchical structure based on the semantic information,such as trunk roads,motorways etc.To uncover the hierarchical structure of road networks can not only support the traffic management and city planning,but also help to improve the speed and safety of the network of transportation.Many solutions have been propos ed to uncover the hierarchical sturcture of road networks,but most are simply break based on the importance of road.Previous works lacks an overall description and presentation of the road network while considering the connection between different hierarchies.Furthermore,these approaches did not achieve the automatically constuction.Hierarchy was regarded as an intrinsic and effective self-organization pattern within the cosmic system.Discovering and automatically building the hierarchy of the network in its natural sense,essentially,is a kind of explicit,formalized and computable implicit knowledge,which is also a key issue to be solved urgently in many disciplines.It is hard but necessary to automatically find and build the intrinsic hierarchy for complex road network in the big picture.A method named "hieracihcial random tree model" to uncover the hierarchical structure of road network is proposed in this paper.Based on a sight of global scale embedded in the evolution view,the proposed method achieved automatically hieracihcial structure constuction for the first time in the world.Firstly,we propsoed a "hierarchical random tree model" based on the evolution view.This kind of hierarchical structure can be described as tree.The tree consisted of nodes,connections and layers.The nodes of the tree correspond to the nodes of the network;and the connections,the edges of the network.Connections divide into two parts: the branches,which body the tree;and the surplus connections,which are opposite to the branches.Layers are regarded as the stages,identified with level,of nodes.Each node belongs to one layer is distributed on the hierarchical structure.Then,we build the mathematical model of hierarchical structure based on the Bayes' law.In order to obtain a stable hierarchical structure,we suggest the generation of the layers follows a slow productive approach called as general process.The general process means the layers grow with nodes,except on top,filling one by one following the appearance of the branches,which are regarded as the ‘pillars' used to support the ‘ceilings',one layer by one layer from top to bottom.By involving the backbone description and the general process,the probability of hierarchical structure described as the probability of the the branches and the surplus connections.Then we solve this problem through the simulated annealing algorithm.Simulated annealing algorithm is derived from the simulation of solid annealing,it is considered as to coerce a solid with a high energy into a low energy state.In this paper,we consider the solid as a random hierarchical structure initialized from a network at the beginning.The adjustment of the structure analogies is to the coerced process.The highly ordered state represents the final result originated from the ‘coercion'.After the simulated annealing process,we obtain a hierarchical structure as a reasonable answer to the network.Thus this paper provides a method to avoid this problem by digging out the Consensus Layer.Consensus Layers provide both a way to assess the stability of hierarchical structure to the network,and a way to select a hierarchical result to avoid the excessively fixed problem.We apply this model to uncover the hierarchical structures of road networks of four cities: Chengdu,San Diego,Warren,and Birmingham.In some extent,the data represents four different patterns of road networks displayed in the world.With the same ‘spindle' appearance,the hierarchical results of road networks are classified into 4 or 5 layers.We simultaneously invite three structural measures of network,which are capable to qualify the status of each road to link with the nodes on the hierarchical results.The comparisons between the groups of nodes on different layers,provided by means of the three measures,perform a great sympathetic response between the hierarchical results and the structural measures,i.e.the roads on higher layers probably are more dominant than the others below.This paper carried out the experiment of the model in two aspects and verified the applicability in different applications.The two applications are road selection in map generalization and the hierarchical construction of airport networks.The experimental results show that the model can satisfy the need of multi-scale road map mapping.The model can effectively construct the reasonable hieracical structure ofairport network.Thus the hierarchical random tree model has a wide application prospect.Hierarchical random tree model is a general method to uncover the hieracical structure of networks which with no weigh or order.It translates a chaotic and disorderly network to an orderly,organized tree automatically.The model has verified the hieracical structure does exist,and the number of levels is limited,within the five levels.In the near future,the model can also be used to construct the hierarchy of other networks,and assist the prediction of networks.It is expected to help build the geographical system of "open giant complex system",to enrich the spatial data model of the big data era.