Fast Skyline Community Search in Multi-Valued Networks
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 (d⩾1) numerical attributes, almost all existing algorith...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Tsinghua University Press
2020-09-01
|
| Series: | Big Data Mining and Analytics |
| Subjects: | |
| Online Access: | https://www.sciopen.com/article/10.26599/BDMA.2020.9020002 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832573609080520704 |
|---|---|
| author | Dongxiao Yu Lifang Zhang Qi Luo Xiuzhen Cheng Jiguo Yu Zhipeng Cai |
| author_facet | Dongxiao Yu Lifang Zhang Qi Luo Xiuzhen Cheng Jiguo Yu Zhipeng Cai |
| author_sort | Dongxiao Yu |
| collection | DOAJ |
| description | 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 (d⩾1) 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. |
| format | Article |
| id | doaj-art-305ff948b3164814a1ee5ade69ee9f76 |
| institution | Kabale University |
| issn | 2096-0654 |
| language | English |
| publishDate | 2020-09-01 |
| publisher | Tsinghua University Press |
| record_format | Article |
| series | Big Data Mining and Analytics |
| spelling | doaj-art-305ff948b3164814a1ee5ade69ee9f762025-02-02T03:45:08ZengTsinghua University PressBig Data Mining and Analytics2096-06542020-09-013317118010.26599/BDMA.2020.9020002Fast Skyline Community Search in Multi-Valued NetworksDongxiao Yu0Lifang Zhang1Qi Luo2Xiuzhen Cheng3Jiguo Yu4Zhipeng Cai5<institution content-type="dept">School of Computer Science and Technology</institution>, <institution>Shandong University</institution>, <city>Qingdao</city> <postal-code>266237</postal-code>, <country>China</country>.<institution content-type="dept">School of Computer Science and Technology</institution>, <institution>Shandong University</institution>, <city>Qingdao</city> <postal-code>266237</postal-code>, <country>China</country>.<institution content-type="dept">School of Computer Science and Technology</institution>, <institution>Shandong University</institution>, <city>Qingdao</city> <postal-code>266237</postal-code>, <country>China</country>.<institution content-type="dept">School of Computer Science and Technology</institution>, <institution>Shandong University</institution>, <city>Qingdao</city> <postal-code>266237</postal-code>, <country>China</country>.<institution content-type="dept">School of Computer Science and Technology</institution>, <institution>Qilu University of Technology</institution>, <city>Jinan</city> <postal-code>250353</postal-code>, <country>China</country>.<institution content-type="dept">Department of Computing Science</institution>, <institution>Georgia State University</institution>, <city>Atlanta</city>, <state>GA</state> <postal-code>30303</postal-code>, <country>USA</country>.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 (d⩾1) 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.https://www.sciopen.com/article/10.26599/BDMA.2020.9020002multi-valued graphcommunity searchskyline community |
| spellingShingle | Dongxiao Yu Lifang Zhang Qi Luo Xiuzhen Cheng Jiguo Yu Zhipeng Cai Fast Skyline Community Search in Multi-Valued Networks Big Data Mining and Analytics multi-valued graph community search skyline community |
| title | Fast Skyline Community Search in Multi-Valued Networks |
| title_full | Fast Skyline Community Search in Multi-Valued Networks |
| title_fullStr | Fast Skyline Community Search in Multi-Valued Networks |
| title_full_unstemmed | Fast Skyline Community Search in Multi-Valued Networks |
| title_short | Fast Skyline Community Search in Multi-Valued Networks |
| title_sort | fast skyline community search in multi valued networks |
| topic | multi-valued graph community search skyline community |
| url | https://www.sciopen.com/article/10.26599/BDMA.2020.9020002 |
| work_keys_str_mv | AT dongxiaoyu fastskylinecommunitysearchinmultivaluednetworks AT lifangzhang fastskylinecommunitysearchinmultivaluednetworks AT qiluo fastskylinecommunitysearchinmultivaluednetworks AT xiuzhencheng fastskylinecommunitysearchinmultivaluednetworks AT jiguoyu fastskylinecommunitysearchinmultivaluednetworks AT zhipengcai fastskylinecommunitysearchinmultivaluednetworks |