NDLI: Incremental k-core decomposition: algorithms and evaluation

Content Provider	Springer Nature Link
Author	Sarıyüce, Ahmet Erdem Gedik, Buğra Jacques Silva, Gabriela Wu, Kun Lung Çatalyürek, Ümit V.
Copyright Year	2016
Abstract	A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. For a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.
Starting Page	425
Ending Page	447
Page Count	23
File Format	PDF
ISSN	10668888
Journal	The VLDB Journal
Volume Number	25
Issue Number	3
e-ISSN	0949877X
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2016-02-15
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	k-Core Streaming graph algorithms Dense subgraph discovery Incremental graph algorithms Database Management
Content Type	Text
Resource Type	Article
Subject	Information Systems Hardware and Architecture

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

Dense subgraph maintenance under streaming edge weight updates for real-time story identification

I/O efficient ECC graph decomposition via graph reduction

Scalable subgraph enumeration in MapReduce: a cost-oriented approach

Efficient distributed subgraph similarity matching

Graph similarity search on large uncertain graph databases

The Core Decomposition of Networks: Theory, Algorithms and Applications

High-performance parallel frequent subgraph discovery

AutoG: a visual query autocompletion framework for graph databases

High efficiency and quality: large graphs matching

Incremental k-core decomposition: algorithms and evaluation

Similar Documents

Dense subgraph maintenance under streaming edge weight updates for real-time story identification

I/O efficient ECC graph decomposition via graph reduction

Scalable subgraph enumeration in MapReduce: a cost-oriented approach

Efficient distributed subgraph similarity matching

Graph similarity search on large uncertain graph databases

The Core Decomposition of Networks: Theory, Algorithms and Applications

High-performance parallel frequent subgraph discovery

AutoG: a visual query autocompletion framework for graph databases

High efficiency and quality: large graphs matching

Incremental k-core decomposition: algorithms and evaluation