Journal Home > Volume 3 , Issue 3

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.


menu
Abstract
Full text
Outline
About this article

Fast Skyline Community Search in Multi-Valued Networks

Show Author's information Dongxiao YuLifang Zhang( )Qi Luo( )Xiuzhen ChengJiguo YuZhipeng Cai
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.

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.

Keywords: multi-valued graph, community search, skyline community

References(27)

[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.
DOI
[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.
DOI
[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.
DOI
[9]
S. Fortunato, Community detection in graphs, arXiv preprint arXiv: 0906.0612, 2009.
DOI
[10]
S. Fortunato and D. Hric, Community detection in networks: A user guide, arXiv preprint arXiv: 1608.00163, 2016.
DOI
[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.
DOI
[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.
DOI
[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.
DOI
[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.
DOI
[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.
DOI
[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.
DOI
[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.
DOI
[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.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 29 February 2020
Accepted: 07 March 2020
Published: 16 July 2020
Issue date: September 2020

Copyright

© The author(s) 2020

Acknowledgements

This work was partially supported by the National Key R&D Program of China (No. 2019YFB2102600) and the National Natural Science Foundation of China (Nos. 61971269, 61832012, 616727321, and 61771289).

Rights and permissions

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