On uncertain graphs
by Khan, Arijit
Large-scale, highly interconnected networks, which are often modeled as graphs, pervade both our society and the natural world around us. Uncertainty, on the other hand, is inherent in the underlying data due to a variety of reasons, such as noisy measurements, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, or probabilistic, graphs are increasingly used to represent noisy linked data in many emergin…
Read More ↓Title Statements
- Full title :On uncertain graphs / Arijit Khan, Yuan Ye, Lei Chen.
Summary
Large-scale, highly interconnected networks, which are often modeled as graphs, pervade both our society and the natural world around us. Uncertainty, on the other hand, is inherent in the underlying data due to a variety of reasons, such as noisy measurements, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, or probabilistic, graphs are increasingly used to represent noisy linked data in many emerging application scenarios, and they have recently become a hot topic in the database and data mining communities. Many classical algorithms such as reachability and shortest path queries become #P-complete and, thus, more expensive over uncertain graphs. Moreover, various complex queries and analytics are also emerging over uncertain networks, such as pattern matching, information diffusion, and influence maximization queries. In this book, we discuss the sources of uncertain graphs and their applications, uncertainty modeling, as well as the complexities and algorithmic advances on uncertain graphs processing in the context of both classical and emerging graph queries and analytics. We emphasize the current challenges and highlight some future research directions.
Read More ↓Edition Statements
- Publication Date:©2018
Publication Statements
- Publisher(s):Springer
- Place of Publication:Cham, Switzerland
- Language:eng
- Publication Date:©2018
The Physical Object
- Description:1 online resource (xiii, 80 pages) : : illustrations
Edition Identifiers
- ISBN:9781681730387, 1681730383, 9783031018602, 3031018605
- DOI:10.1007/978-3-031-01860-2
- oclc:on1047603341
- LC Classification:Q375
- Dewey Decimal:003.54
Table of Contents
1. Introduction to uncertain graphs -- 1.1 Data as uncertain graphs -- 1.2 Modeling of uncertain graphs -- 1.3 Challenges in processing uncertain graphs
2. Reliability queries -- 2.1 Reliability -- 2.2 Shortest path -- 2.3 Nearest neighbors
3. Graph pattern matching queries -- 3.1 The pattern matching problem -- 3.2 Filtering-and-verification framework -- 3.3 Probabilistic pruning -- 3.4 Verification -- 3.4.1 Basic sampling -- 3.4.2 Tree-based sampling -- 3.4.3 Hybrid sampling
4. Graph similarity search queries -- 4.1 The similarity search problem -- 4.2 Probabilistic subgraph similarity query processing -- 4.3 Probabilistic supergraph similarity query processing
5. Influence maximization -- 5.1 Information diffusion models -- 5.2 The influence maximization problem -- 5.3 Competitive influence maximization -- 5.4 Influence maximization as a service -- 5.5 Topic-aware influence maximization
6. Major open problems -- Bibliography -- Authors' biographies.
Rate & Review