.png){kind=icon}
返回
Uncertain Graph Sparsification
.png){kind=icon}
OA
AI
DOI：10.1109/TKDE.2018.2819651.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Uncertain graphs are prevalent in several applications including communications systems, biological databases, and social networks. The ever increasing size of the underlying data renders both graph storage and query processing extremely expensive. Sparsification has often been used to reduce the size of deterministic graphs by maintaining only the important edges. However, adaptation of deterministic sparsification methods fails in the uncertain setting. To overcome this problem, we introduce the first sparsification techniques aimed explicitly at uncertain graphs. The proposed methods reduce the number of edges and redistribute their probabilities in order to decrease the graph size, while preserving its underlying structure. The resulting graph can be used to efficiently and accurately approximate any query and mining tasks on the original graph. An extensive experimental evaluation with real and synthetic datasets illustrates the effectiveness of our techniques on several common graph tasks, including clustering coefficient, page rank, reliability, and shortest path distance.
Keyword:
Uncertainty
fuzzy and probabilistic reasoning
user Interfaces
information interfaces and representation (HCl)
information technology and systems
database management
graphs and networks
data structures
data graph algorithms
graph theory
discrete mathematics
mathematics of computing
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
查看更多内容