Research On Resolution Limit Of Community Detection In Location-based Social Networks

The widespread use of mobile Internet and location technology has greatly facilitated people's production and life.It also promoted the development of location-based social networks(LBSN).Unlike traditional social networks that only contain user topology information,LBSN is a complex heterogeneous network that contains user information and location information.Community structure is of great significance for analysis of LBSN deeply.Modularity optimization is a traditional social network community detection method.Because of its excellent time performance and effectiveness,it is considered to be extended to LBSN.However,resolution limit is an inherent problem in the definition of modularity.Therefore,solving resolution limit and combining modularity optimization method with location information are the basis of community detection in LBSN.To solve above problems,this paper analyzes the characteristics of LBSN and the causes of resolution limit,after that a network weight preprocessing scheme is proposed.The preprocessed network not only can avoid the resolution limit but also applicable to LBSN when using modularity optimization method for community detection.The research work in this paper can be divided into two parts.Due to the excellent performance of network embedding in vertex feature learning,this paper analyzes a network embedding method for LBSN that named walk2 friends.The work of vertex similarity generation in walk2 friends is combined with a method for mining network structure by random walk.After that the preprocessing scheme of this paper is proposed.The preprocessing scheme transforms an undirected unweighted graph into an undirected weighted graph for community detection.The learned similarity obtained by walk2 friends that considering characteristics of LBSN can make the vertices more cohesive.The structural similarity obtained by random walk method can detect the network structure and distinguish the vertices of different communities.The application of K-nearest neighbor algorithm makes the edge weights between vertices with a low correlation close to zero,thus destroying the arise of resolution limit.Compared with existing community detection methods for LBSN which only take the check-in data as input,the preprocessing scheme also considers the social relationship.The experimental results show that the preprocessing scheme can effectively solve the resolution limit problem of modularity optimization method used for LBSN.The introduction of walk2 friends makes the scheme is suitable for LBSN.In view of the lack of social relationship in walk2 friends,this paper proposes a collaborative filtering method based on social relationship to improve it.This method not only can introduce social relationship to walk2 friends,but also avoid data sparsity in collaborative filtering.Then,the improved walk2 friends is used for the optimization of network preprocessing scheme.The experimental results show that the improved walk2 friends improves the link prediction performance greatly when compared with the previous one.When compared with the previous preprocessing scheme,the improved scheme not only can solve the resolution limit problem effectively but also the evaluation metrics are more reasonable.Meanwhile,it's more suitable for LBSN than other typical community detection methods.