Home
Lectures
On Uncertain Graphs Modeling and Queries

On Uncertain Graphs Modeling and Queries

Speaker: Arijit Khan – Aalborg, Denmark
Topic(s): Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science

Abstract

Uncertainty is evident in graph data due to a variety of reasons, such as noisy measurements, inconsistent, incorrect, and possibly ambiguous information sources, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. In these cases, data is represented as an uncertain network: A graph whose nodes, edges, and attributes are accompanied with a probability of existence. With the popularity of uncertain data, uncertain graphs are increasingly becoming important in many emerging application domains including biological networks, knowledge bases, social networks, viral marketing, road networks, crowd-sourcing, among many others. While many classical graph algorithms such as reachability and shortest path queries become #P-complete, and hence, more expensive in uncertain graphs, various complex queries are also emerging over uncertain networks, such as influence maximization as a service provided by the social network host. In this talk, I shall give an overview of our work on reliability, shortest path, and densest subgraph queries, influence and opinion maximization over large, uncertain networks.

About this Lecture

Number of Slides: 40
Duration: 60 minutes
Languages Available: English
Last Updated:

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.