期刊
INFORMATION SCIENCES
卷 417, 期 -, 页码 344-360出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2017.07.012
关键词
Community search; Weighted k-truss community; Weighted networks
资金
- NSFC [61402292, 61472338]
- National Key Research and Development Program [2016YFB1000101]
- NSF-Shenzhen [JCYJ20150324140036826]
- Startup Grant of Shenzhen Kongque Program [827/000065]
- Fundamental Research Funds for the Central Universities
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. (C) 2017 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据