AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (1.2 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Fast Skyline Community Search in Multi-Valued Networks

School of Computer Science and Technology, Shandong University, Qingdao 266237, China.
School of Computer Science and Technology, Qilu University of Technology, Jinan 250353, China.
Department of Computing Science, Georgia State University, Atlanta, GA 30303, USA.
Show Author Information

Abstract

Community search has been extensively studied in large networks, such as Protein-Protein Interaction (PPI) networks, citation graphs, and collaboration networks. However, in terms of widely existing multi-valued networks, where each node has d ( d1) numerical attributes, almost all existing algorithms either completely ignore the attributes of node at all or only consider one attribute. To solve this problem, the concept of skyline community was presented, based on the concepts of k-core and skyline recently. The skyline community is defined as a maximal k-core that satisfies some influence constraints, which is very useful in depicting the communities that are not dominated by other communities in multi-valued networks. However, the algorithms proposed on skyline community search can only work in the special case that the nodes have different values on each attribute, and the computation complexity degrades exponentially as the number of attributes increases. In this work, we turn our attention to the general scenario where multiple nodes may have the same attribute value. Specifically, we first present an algorithm, called MICS, which can find all skyline communities in a multi-valued network. To improve computation efficiency, we then propose a dimension reduction based algorithm, called P-MICS, using the maximum entropy method. Our algorithm can significantly reduce the skyline community searching time, while is still able to find almost all cohesive skyline communities. Extensive experiments on real-world datasets demonstrate the efficiency and effectiveness of our algorithms.

References

[1]
G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society,Nature, vol. 435, no. 7043, pp. 814-818, 2005.
[2]
M. Sozio and A. Gionis, The community-search problem and how to plan a successful cocktail party, in Proc. 16th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2010, pp. 939-948.
[3]
F. Zhang, Y. Zhang, L. Qin, W. J. Zhang, and X. M. Lin, When engagement meets similarity: Efficient (k, r)-core computation on social networks,Proceedings of the VLDB Endowment, vol. 10, no. 10, pp. 998-1009, 2017.
[4]
V. Batagelj and M. Zaversnik, An O(m) algorithm for cores decomposition of networks, arXiv preprint arXiv: cs/0310049, 2003.
[5]
S. Borzsony, D. Kossmann, and K. Stocker, The skyline operator, in Proc. 17th Int. Conf. Data Engineering, Heidelberg, Germany, 2001, pp. 421-430.
[6]
K. Q. Zhang, H. Gao, X. X. Han, Z. P. Cai, and J. Z. Li, Modeling and computing probabilistic skyline on incomplete data, IEEE Trans. Knowl. Data Eng., .
[7]
R. H. Li, L. Qin, F. H. Ye, J. X. Yu, X. K. Xiao, N. Xiao, and Z. B. Zheng, Skyline community search in multi-valued networks, in Proc. 2018 Int. Conf. Management of Data, Houston, TX, USA, 2018, pp. 457-472.
[8]
Y. X. Fang, X. Huang, L. Qin, Y. Zhang, W. J. Zhang, R. Cheng, and X. M. Lin, A survey of community search over big graphs, arXiv preprint arXiv: 1904.12539, 2019.
[9]
S. Fortunato, Community detection in graphs, arXiv preprint arXiv: 0906.0612, 2009.
[10]
S. Fortunato and D. Hric, Community detection in networks: A user guide, arXiv preprint arXiv: 1608.00163, 2016.
[11]
W. Y. Cui, Y. H. Xiao, H. X. Wang, and W. Wang, Local search of communities in large graphs, in Proc. 2014 ACM SIGMOD Int. Conf. Management of Data, Snowbird, UT, USA, 2014, pp. 991-1002.
[12]
N. Barbieri, F. Bonchi, E. Galimberti, and F. Gullo, Efficient and effective community search, Data Min. Knowl. Discov., vol. 29, no. 5, pp. 1406-1433, 2015.
[13]
Y. X. Fang, Z. R. Wang, R. Cheng, H. Z. Wang, and J. F. Hu, Effective and efficient community search over large directed graphs (extended abstract), in IEEE 35th Int. Conf. Data Engineering, Macao, China, 2019, pp. 2157-2158.
[14]
N. Wang, D. X. Yu, H. Jin, C. Qian, X. Xie, and Q. S. Hua, Parallel algorithm for core maintenance in dynamic graphs, in Proc. 37th IEEE Int. Conf. Distributed Computing Systems, Atlanta, GA, USA, 2017, pp. 2366-2371.
[15]
H. Jin, N. Wang, D. X. Yu, Q. S. Hua, X. H. Shi, and X. Xie, Core maintenance in dynamic graphs: A parallel approach based on matching, IEEE Trans. Parallel Distrib. Syst., vol. 29, no. 11, pp. 2416-2428, 2018.
[16]
Q. Luo, D. X. Yu, F. Li, Z. H. Dou, Z. P. Cai, J. G. Yu, and X. Z.Cheng, Distributed core decomposition in probabilistic graphs, in Proc. 8th Int. Conf. Computational Data andSocial Networks, Ho Chi Minh City, Vietnam, 2019, pp. 16-32.
[17]
Q. S. Hua, Y. L. Shi, D. X. Yu, H. Jin, J. G. Yu, Z. P. Cai, X. Z. Cheng, and H. H. Chen, Faster parallel core maintenance algorithms in dynamic graphs, IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 6, pp. 1287-1300, 2020.
[18]
E. Akbas and P. X. Zhao, Truss-based community search: A truss-equivalence based indexing approach, Proceedings of the PVLDB Endowment, vol. 10, no. 11, pp. 1298-1309, 2017.
[19]
X. Huang, H. Cheng, L. Qin, W. T. Tian, and J. X. Yu, Querying k-truss community in large and dynamic graphs, in Proc. 2014 ACM SIGMOD Int. Conf. Management of Data, Snowbird, UT, USA, 2014, pp. 1311-1322.
[20]
Y. Wang, X. Jian, Z. H. Yang, and J. Li, Query optimal K-Plex based community in graphs, Data Science and Engineering, vol. 2, no. 4, pp. 257-273, 2017.
[21]
D. N. Yang, Y. L. Chen, W. C. Lee, and M. S. Chen, On social-temporal group query with acquaintance constraint, Proceedings of the PVLDB Endowment, vol. 4, no. 6, pp. 397-408, 2011.
[22]
L. Yuan, L. Qin, W. J. Zhang, L. J. Chang, and J. Y. Yang, Index-based densest clique percolation community search in networks (extended abstract), in IEEE 35th Int. Conf. Data Engineering, Macao, China, 2019, pp. 2161-2162.
[23]
Y. X. Fang, R. Cheng, S. Q. Luo, and J. F. Hu, Effective community search for large attributed graphs, Proceedings of the PVLDB Endowment, vol. 9, no. 12, pp. 1233-1244, 2016.
[24]
Y. X. Fang, R. Cheng, X. D. Li, S. Q. Luo, and J. F. Hu, Effective community search over large spatial graphs, Proceedings of the PVLDB Endowment, vol. 10, no. 6, pp. 709-720, 2017.
[25]
K. Wang, X. Cao, X. M. Lin, W. J. Zhang, and L. Qin, Efficient computing of radius-bounded k-cores, in IEEE 34th Int. Conf. Data Engineering, Paris, France, 2018, pp. 233-244.
[26]
Q. J. Zhu, H. B. Hu, C. Xu, J. L. Xu, and W. C. Lee, Geo-social group queries with minimum acquaintance constraints, The VLDB Journal, vol. 26, no. 5, pp. 709-727, 2017.
[27]
R. H. Li, L. Qin, J. X. Yu, and R. Mao, Influential community search in large networks, Proceedings of the PVLDB Endowment, vol. 8, no. 5, pp. 509-520, 2015.
Big Data Mining and Analytics
Pages 171-180
Cite this article:
Yu D, Zhang L, Luo Q, et al. Fast Skyline Community Search in Multi-Valued Networks. Big Data Mining and Analytics, 2020, 3(3): 171-180. https://doi.org/10.26599/BDMA.2020.9020002

886

Views

49

Downloads

13

Crossref

14

Web of Science

16

Scopus

0

CSCD

Altmetrics

Received: 29 February 2020
Accepted: 07 March 2020
Published: 16 July 2020
© The author(s) 2020

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return