Chenhao Ma
LINC: a motif counting algorithm for uncertain graphs
Ma, Chenhao; Cheng, Reynold; Lakshmanan, Laks V. S.; Grubenmann, Tobias; Fang, Yixiang; Li, Xiaodong
Authors
Reynold Cheng
Laks V. S. Lakshmanan
Tobias Grubenmann
Yixiang Fang
Xiaodong Li
Abstract
In graph applications (e.g., biological and social networks), various analytics tasks (e.g., clustering and community search) are carried out to extract insight from large and complex graphs. Central to these tasks is the counting of the number of motifs, which are graphs with a few nodes. Recently, researchers have developed several fast motif counting algorithms. Most of these solutions assume that graphs are deterministic, i.e., the graph edges are certain to exist. However, due to measurement and statistical prediction errors, this assumption may not hold, and hence the analysis quality can be affected. To address this issue, we examine how to count motifs on uncertain graphs, whose edges only exist probabilistically. Particularly, we propose a solution framework that can be used by existing deterministic motif counting algorithms. We further propose an approximation algorithm. Extensive experiments on real datasets show that our algorithms are more effective and efficient than existing solutions.
Journal Article Type | Article |
---|---|
Online Publication Date | Oct 1, 2019 |
Publication Date | 2019-10 |
Deposit Date | Jun 8, 2023 |
Journal | Proceedings of the VLDB Endowment |
Print ISSN | 2150-8097 |
Publisher | VLDB Endowment |
Peer Reviewed | Peer Reviewed |
Volume | 13 |
Issue | 2 |
Pages | 155-168 |
DOI | https://doi.org/10.14778/3364324.3364330 |
You might also like
Core-selecting payment rules for combinatorial auctions with uncertain availability of goods
(2016)
Presentation / Conference Contribution
A framework for differentially-private knowledge graph embeddings
(2021)
Journal Article
Make restaurants pay your server bills
(2018)
Presentation / Conference Contribution
Spatial concept learning and inference on geospatial polygon data
(2022)
Journal Article
Challenges of Source Selection in the WoD
(2017)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search