Community Structure Detection Of Complex Network And Urban Transit Network Research

With the arrival of the Internet era and the globalization of people exchanges and economic activities, people find that the nature and human society are filled with all kinds of complex systems, most of them can be expressed with the appropriate network. Complex network is a new subject in recent years, which has penetrated into many different fields. In-Depth exploration of complex networks is helpful for people to understand the function of the network, to explore the hidden rules in complex networks and to make the network serve human better.Firstly, this article presents an improved K-means algorithm based on optimized initial center points. Initializing cluster centers randomly, traditional K-means algorithm is prone to local optimal and instability of clustering results. To solve these problems, this paper presents a method to optimize the initial center. First, the two furthest mutual distance points in high-density region were selected as the initial clustering centers. Second, the point which was far away from the midpoint of the two points was selected as the third center. Then according to the maximum distance, the fourth initial center was selected until k points were found by this way. In the process of algorithm, the parameter value was adjusted automatically to enhance robustness of the algorithm. The experimental results demonstrate that the improved K-means algorithm have better accuracy, it can eliminate the dependence on the initial cluster center, and show a good adaptive ability, thus the clustering effect has been greatly improved.Secondly, Community structure is one of the obvious characteristics of complex network. In order to find the community structure, this paper proposes a new detecting method based on K-means cluster algorithm. The right initial center was selected by using the definition of node importance coefficient. Then the network was divided into k communities. Finally the community structure which has the highest modularity was chosen. This paper is mainly simulated based on classical networks. The analysis demonstrates that the community detecting accuracy is relatively high, and it shows that this method is reasonable.Finally, urban transportation network was constructed based on modeling and analyzing methodology. Node degree, average distance, clustering coefficient were introduced to analyze public transit sites network, public transit interchange network and public transit lines network. The result indicates that the three network models are scale-free networks, public transit interchange network and public transit lines network also have small world characteristic. In order to further study the interaction strength between the sites, this paper models a weighted complex network based on traffic volume. The weighted network still is a scale-free network, but its average distance and weighted clustering coefficient are relatively small, do not have small world characteristic. Finally, a new metric, namely importance degree D(i) is proposed to find the important nodes in the network. What we have done could provide some suggestions to optimize bus routes.This paper presents a method to optimize traditional K-means algorithm. The experimental results demonstrate that the improved K-means algorithm have better accuracy, and it improves the clustering quality. Then this paper proposes a new method of community structure detection based on K-means algorithm, the simulation experiment demonstrates that the community detecting accuracy is relatively high and it shows that the algorithm is reasonable. Using complex network theory, Qingdao public transportation network was researched and its topology characteristics were analyzed. What we have done could provide some suggestions to optimize bus routes.