An Efficient Shortest Path Approach For Social Networks Based On Community Structure

The rapid development of technology makes people enter the age of the internet. More and more people join the social network. The number of internet users has accounted for the proportion of a large population, and the application of social network more rich, people making friends on the social network, entertainment and consumption, working, etc. Social network size increases rapidly, the amount of information is growing rapidly, and structure is more and more complex. Attracted the researches of experts and scholars in the field of various subjects, such as understanding network topology structure, information dissemination, the personalized recommendation system and so on. The shortest path(SP) in these problems have played an important role. So the SP problem in social network has very important value and application significance in social network researching.But the traditional SP algorithm have been unable to be adapted to the social network because of the large scale, the complicated structure and the large amount of information in social network. In recent years, the proposed algorithm based on the characteristics of the specific network cannot transplanted to this problem. So, we need a new SP algorithm suitable to social network shortest path problem.The main works are built up community graph model based on community structure and utilize it to reduce the scope of searching the SP so as to improve the efficiency of the SP algorithm. In this thesis, the main innovation points are as follows:(1) A community graph model based on community information is proposed. Community is modeled to a point of community graph, and ignore the edges in community. The edges are the minimum edge between the corresponding communities. Community graph scale is far smaller than the original social network. Before the community detection, the longest edge added a positive integer minus the original network. If the length of the original network is zero, the edges is remained. Get the community information of new graph by community detection algorithm.(2) This thesis proposes an algorithm to solve the SP problem using community graph. The first step is calculating k shortest community path. Then make the intersection between the k shortest communities and make the reconstitution based on the intersection. The last step is find out the SP by SP algorithm. In this thesis, we selected five network datasets to test the algorithm proposed above. At the same time, approximation error(aper) and efficiency(eff) are represented as evaluation index. The experimental results show that the proposed algorithm can meet the requirements of aper is less than 0.05, the eff has hundreds or even thousands of ascension.(3) The influence of parameter k that the number of community path in community graph to experimental results is analyzed from theory and experiment. With the increase of k, the aper will be larger but the eff smaller and we draw a conclusion that it is a multi-objective optimization problem.