.png){kind=icon}
返回
Efficient Community Search in Edge-Attributed Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2023.3267550.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given a graph, searching for a community containing a query vertex is a fundamental problem and has found many applications. Most existing community search models are based on non-attributed or vertex-attributed graphs. In many real-world graphs, however, the edges carry the richest information to describe the interactions between vertices; hence, it is important to take the information into account in community search. In this paper, we conduct a pioneer study on the community search on edge-attributed graphs. We proposed the Edge-Attributed Community Search (EACS) problem, which aims to extract a subgraph that contains the given query vertex while its edges have the maximum attribute similarity. We prove that the EACS problem is NP-hard and propose both exact and 2-approximation algorithms to address EACS. Our exact algorithms run up to 2320.34 times faster than the baseline solution. Our approximate algorithms further improve the efficiency by up to 2.93 times. We conducted extensive experiments to demonstrate the efficiency and effectiveness of our algorithms.
Keyword:
Artificial intelligence
Approximation algorithms
Search problems
Image edge detection
Motion pictures
Computer science
Indexes
Community search
edge-attributed graphs
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
Theoretical investigation of halide perovskites for solar cell and optoelectronic applications*
PREAI
分享收藏
查看更多内容