Finding weighted k-truss communities in large networks

Community search is a fundamental problem in social network mining, which has attracted much attention in recent years. However, most previous community models only consider the link structure and ignore the link weights of the community, which may miss some useful properties of the community. In this paper, we propose a novel community model, called weighted k-truss community, based on the concept of k-truss. The proposed model takes the edge weight into consideration, thus can better characterize the properties of a community. Based on the new community model, we design a BFS-based online search algorithm to find the top-r weighted k-truss communities in O(m^1.5) time, where m denotes the number of edges in a network. To speed up the online search algorithm, we devise a space-efficient index structure, namely KEP-Index, to support efficient community search. We propose two algorithms to construct the index structure in an offline manner. Based on KEP-Index, the time complexity for finding the top-r weighted k-truss communities is linear to the size of these communities, thus it is optimal. We conduct extensive experiments on six large real-world networks, as well as a case study over a co-authorship network. The results demonstrate the efficiency and effectiveness of the proposed community model and algorithms.