Abstract: In this paper, three new algorithms, a greedy algorithm, a KL-like algorithm, and an add-all algorithm, are proposed to find local optimal community structures in large networks starting from a given source vertex. The time complexity for finding a local community of all these algorithms is O(K2d), where K is the number of vertices to be explored in the sub-graph and d is the average degree of the vertices in the sub-graph. A JAVA tool is developed based on these algorithms to identify local community structures in large networks. The results of using this tool to analyze a co-purchase network from Amazon.com show that local community structures exist in this large-scale co-purchase network. Further analyses of the identified local communities show that purchases of media items form more compact local communities than purchases of book items do, indicating that recommending digital media items to customers based on co-purchasing information in the online store is more efficient than recommending books.
Keywords: community, network, local search, Kernighan-Lin
