NDLI: Uncertain Graph Processing through Representative Instances

Content Provider	ACM Digital Library
Author	Bonchi, Francesco Gullo, Francesco Papadias, Dimitris Parchas, Panos
Copyright Year	2015
Abstract	Data in several applications can be represented as an uncertain graph whose edges are labeled with a probability of existence. Exact query processing on uncertain graphs is prohibitive for most applications, as it involves evaluation over an exponential number of instantiations. Thus, typical approaches employ Monte-Carlo sampling, which (i) draws a number of possible graphs (samples), (ii) evaluates the query on each of them, and (iii) aggregates the individual answers to generate the final result. However, this approach can also be extremely time consuming for large uncertain graphs commonly found in practice. To facilitate efficiency, we study the problem of extracting a single $\textit{representative}$ instance from an uncertain graph. Conventional processing techniques can then be applied on this representative to closely approximate the result on the original graph. In order to maintain data utility, the representative instance should preserve structural characteristics of the uncertain graph. We start with representatives that capture the expected vertex degrees, as this is a fundamental property of the graph topology. We then generalize the notion of vertex degree to the concept of $\textit{n}-clique$ cardinality, that is, the number of cliques of size $\textit{n}$ that contain a vertex. For the first problem, we propose two methods: Average Degree Rewiring (ADR), which is based on random edge rewiring, and Approximate B-Matching (ABM), which applies graph matching techniques. For the second problem, we develop a greedy approach and a game-theoretic framework. We experimentally demonstrate, with real uncertain graphs, that indeed the representative instances can be used to answer, efficiently and accurately, queries based on several metrics such as shortest path distance, clustering coefficient, and betweenness centrality.
Starting Page	1
Ending Page	39
Page Count	39
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2818182
Volume Number	40
Issue Number	3
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-10-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Uncertain graph N-clique cardinality Possible world Representative
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Uncertain Graph Processing through Representative Instances

The pursuit of a good possible world: extracting representative instances of uncertain graphs

Uncertain Graph Processing through Representative Instances and Sparsification

Uncertain Graph Processing through Representative Instances and Sparsification

The pursuit of a good possible world: extracting representative instances of uncertain graphs.

Computing rarity on uncertain data

Rule induction for uncertain data

A clique-superposition model for social networks

Understanding cardinality estimation using entropy maximization

Uncertain Graph Processing through Representative Instances

Similar Documents

Uncertain Graph Processing through Representative Instances

The pursuit of a good possible world: extracting representative instances of uncertain graphs

Uncertain Graph Processing through Representative Instances and Sparsification

Uncertain Graph Processing through Representative Instances and Sparsification

The pursuit of a good possible world: extracting representative instances of uncertain graphs.

Computing rarity on uncertain data

Rule induction for uncertain data

A clique-superposition model for social networks

Understanding cardinality estimation using entropy maximization

Uncertain Graph Processing through Representative Instances