A Study On Complex Network Based On Cliques And Its Application In Bus Transport Network

Complex network is a new interdisciplinary science which sprang up with the swift and violent development of the computer technology in recent ten years. It colligates many subjects including information science, mathematics, physics, biology, management science and so on. The study on complex network theory and application can help us to recognize networks, identify the different kinds of practical networks in nature and society; realize networks, open out the internal characteristics and evolving rules; improve networks, make the practical networks service for human better.Form the practical networks in this dissertation, a novel scale-free network model and a weighted network model are proposed respectively. The statistic characteristics of the real bus transport networks are analyzed. An optimal bus transport transfer algorithm based on weighted complex network is designed. The community structure and spread behavior of the real bus transport networks are analyzed. The main contributions are as follows:Firstly, a novel scale-free network model based on clique (complete subgraph of random size) growth and preferential attachment is proposed. Every time step of the evolving procedure, a new clique is added into the network, and this new clique attaches preferentially to the old ones that are already well connected. This novel model evolves on the basis of cliques, not vertices. Simulation results show that the degree of vertices of the generating network follows a scale-free power-law distribution. Besides, the cliques also constitute a network, with the connections of the cliques being their links. The degree distribution of this clique network also has the scale-free power-law properties. And based on the Mean-field theory, the analytical results of this model are given.Secondly, a weighted evolving network model on the basis of clique overlapping growth is proposed. The model shows different characteristics under two different attachment mechanisms which are preferential attachment and random attachment respectively. By Mean-field theory, we analyze the distributions of so-called "the number of cliques a vertex joins" and "the vertex strength" of this model under different attachment mechanisms. We verify that both of the distributions follow the scale-free power-law distribution in preferential attachment mechanism while both of them follow the exponential distribution in random attachment mechanism. Simulation results are in agreement with the analytical results well. Besides, we present the empirical investigation results on the practical bus transport networks of three major cities in China. The results show that this kind of collaboration networks can be modeled by our model very well.Thirdly, the statistic characteristics of the practical bus transport networks described by space L are studied, including the average path length, clustering coefficient, degree distribution and so on. We consider that the bus transport network described by space L is similar to the regular network, which do not have the obvious small-world phenomenon, and whose degree distribution follows the power-law distribution. Then the statistic characteristics of the practical bus transport networks described by space P are studied, including the degree distribution, multiple edges' overlapping times distribution, distribution of the overlap size between any two overlapping cliques, distribution of the number of cliques that a node belong to. Naturally, the cliques also constitute a network, with the overlapping nodes being their multiple links. We also research its network properties such as degree distribution, clustering coefficient, average path length and so on. We propose that the bus transport network described by space P has the properties of random clique increment and random overlapping clique, at the same time, it is a small-world network with highly clique clustered and highly clique overlapped. Finally, we introduce an evolution model whose simulation results agree well the statistical laws which emerge in real bus transport networks described by space P.Fourthly, we use the method of space P to model the bus transport network, by which an unweighted complex network model is obtained. Then by using the breadth-first search algorithm, we get all the least transfer routes between two inquired stations. We introduce the vertex weight, namely every station's longitudes and latitudes. The edge weight——straight-line distance between every two stations——will be got by computing the vertex weight. Further we model the BTN to a weighted complex network. A final transfer route which has the shortest total straight-line distance on the basis of the least transfer is obtained by this weighted complex network model and all the least transfer routes are got in prior. The practical data of Hangzhou is used to testify the new algorithm's efficiency. Fifthly, by improved community dividing algorithm (PKM agglomerative algorithm), we did the community property analysis on the BTN which is described in space L and space P respectively. The results show that BTN which is described in space L has obvious community property, but the one described in space P hasn't. The reason is that the BTN described in space P has the intense overlapping property, which makes the algorithm used above noneffective. So, a new community definition called N-depth community is proposed. And the method of finding this kind of communities in networks is represented. We obtained very good effect by using this community definition and dividing method on a BTN model.Finally, based on the SIS spread model, the spread behavior on the practical bus transport networks described by space P of Beijing, Shanghai and Hangzhou is simulated. The variations of the infected vertices' density with the time and the infected vertices' steady density with the infection rate are obtained. And the spread behavior on a bus transport network model is simulated. By the Mean-field theory, we analyze the epidemic threshold of this model which agrees with the simulation result well.