An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding
Community search is a query-oriented variant of community detection problem, and the goal is to retrieve a single community from a given set of nodes. Most of the existing community search methods adopt handcrafted features, so there are some limitations in applications. Our idea is motivated by the...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/6673444 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547619898916864 |
|---|---|
| author | Jinglian Liu Daling Wang Shi Feng Yifei Zhang |
| author_facet | Jinglian Liu Daling Wang Shi Feng Yifei Zhang |
| author_sort | Jinglian Liu |
| collection | DOAJ |
| description | Community search is a query-oriented variant of community detection problem, and the goal is to retrieve a single community from a given set of nodes. Most of the existing community search methods adopt handcrafted features, so there are some limitations in applications. Our idea is motivated by the recent advances of node embedding. Node embedding uses deep learning method to obtain feature representation of nodes directly from graph structure automatically and offers a new method to measure the distance between two nodes. In this paper, we propose a two-stage community search algorithm with a minimum spanning tree strategy based on node embedding. At the first stage, we propose a node embedding model NEBRW and map nodes to the points in a low-dimensional vector space. At the second stage, we propose a new definition of community from the distance viewpoint, transform the problem of community search to a variant of minimum spanning tree problem, and uncover the target community with an improved Prim algorithm. We test our algorithm on both synthetic and real-world network datasets. The experimental results show that our algorithm is more effective for community search than baselines. |
| format | Article |
| id | doaj-art-1a549f8852104fd8bd5146b6026d33ec |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-1a549f8852104fd8bd5146b6026d33ec2025-02-03T06:43:56ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/66734446673444An Approach of Community Search with Minimum Spanning Tree Based on Node EmbeddingJinglian Liu0Daling Wang1Shi Feng2Yifei Zhang3School of Computer Science and Engineering, Northeastern University, Shenyang 110169, ChinaSchool of Computer Science and Engineering, Northeastern University, Shenyang 110169, ChinaSchool of Computer Science and Engineering, Northeastern University, Shenyang 110169, ChinaSchool of Computer Science and Engineering, Northeastern University, Shenyang 110169, ChinaCommunity search is a query-oriented variant of community detection problem, and the goal is to retrieve a single community from a given set of nodes. Most of the existing community search methods adopt handcrafted features, so there are some limitations in applications. Our idea is motivated by the recent advances of node embedding. Node embedding uses deep learning method to obtain feature representation of nodes directly from graph structure automatically and offers a new method to measure the distance between two nodes. In this paper, we propose a two-stage community search algorithm with a minimum spanning tree strategy based on node embedding. At the first stage, we propose a node embedding model NEBRW and map nodes to the points in a low-dimensional vector space. At the second stage, we propose a new definition of community from the distance viewpoint, transform the problem of community search to a variant of minimum spanning tree problem, and uncover the target community with an improved Prim algorithm. We test our algorithm on both synthetic and real-world network datasets. The experimental results show that our algorithm is more effective for community search than baselines.http://dx.doi.org/10.1155/2021/6673444 |
| spellingShingle | Jinglian Liu Daling Wang Shi Feng Yifei Zhang An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding Complexity |
| title | An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding |
| title_full | An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding |
| title_fullStr | An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding |
| title_full_unstemmed | An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding |
| title_short | An Approach of Community Search with Minimum Spanning Tree Based on Node Embedding |
| title_sort | approach of community search with minimum spanning tree based on node embedding |
| url | http://dx.doi.org/10.1155/2021/6673444 |
| work_keys_str_mv | AT jinglianliu anapproachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT dalingwang anapproachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT shifeng anapproachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT yifeizhang anapproachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT jinglianliu approachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT dalingwang approachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT shifeng approachofcommunitysearchwithminimumspanningtreebasedonnodeembedding AT yifeizhang approachofcommunitysearchwithminimumspanningtreebasedonnodeembedding |