AB - © 2018 Association for Computing Machinery. Given a scientific collaboration network, how can we find a group of collaborators with high research indicator (e.g., hindex) and diverse research interests? Given a social network, how can we identify the communities that have high influence (e.g., PageRank) and also have similar interests to a specified user? In such settings, the network can be modeled as a multi-valued network where each node has d (d = 1) numerical attributes (i.e., h-index, diversity, PageRank, similarity score, etc.). In the multi-valued network, we want to find communities that are not dominated by the other communities in terms of d numerical attributes. Most existing community search algorithms either completely ignore the numerical attributes or only consider one numerical attribute of the nodes. To capture d numerical attributes, we propose a novel community model, called skyline community, based on the concepts of k-core and skyline. A skyline community is a maximal connected k-core that cannot be dominated by the other connected k-cores in the d-dimensional attribute space. We develop an elegant space-partition algorithm to efficiently compute the skyline communities. Two striking advantages of our algorithm are that (1) its time complexity relies mainly on the size of the answer s (i.e., the number of skyline communities), thus it is very efficient if s is small; and (2) it can progressively output the skyline communities, which is very useful for applications that only require part of the skyline communities. Extensive experiments on both synthetic and real-world networks demonstrate the efficiency, scalability, and effectiveness of the proposed algorithm.
AU - Li, RH
AU - Qin, L
AU - Ye, F
AU - Yu, JX
AU - Xiaokui, X
AU - Xiao, N
AU - Zheng, Z
DA - 2018/05/27
DO - 10.1145/3183713.3183736
EP - 472
JO - Proceedings of the ACM SIGMOD International Conference on Management of Data
PY - 2018/05/27
SP - 457
TI - Skyline community search in multi-valued networks
Y1 - 2018/05/27
Y2 - 2019/11/20
ER -