Graph Waves

James Abello; Daniel Nakhimovich

doi:10.1016/j.bdr.2022.100327

Graph Waves

James Abello
, Daniel Nakhimovich

School of Arts and Sciences, Computer Science

Rutgers, The State University

Research output: Contribution to journal › Article › peer-review

Abstract

We present efficient algorithmic mechanisms to partition graphs with up to 1.8 billion edges into subgraphs which are fixed points of degree peeling. We are able to process graphs with tens of millions of edges in seconds and hundreds of millions of edges in minutes. For fixed points that turn out to be larger than a desired interactivity parameter we further decompose them with a novel (to our knowledge) linear algorithm into what we call “graph waves and fragments”. This decomposition is used to create spanning views of fixed points that we call “DAG Covers”. We illustrate these decompositions by presenting intuitive and interactive visualizations of the meta-structures of a variety of publicly available data sets including social, web, and citation networks.

Original language	American English
Article number	100327
Journal	Big Data Research
Volume	29
DOIs	https://doi.org/10.1016/j.bdr.2022.100327
State	Published - Aug 28 2022

ASJC Scopus subject areas

Management Information Systems
Information Systems
Computer Science Applications
Information Systems and Management

Keywords

Graph decomposition
Graph visualization
Waves
k-core

Access to Document

10.1016/j.bdr.2022.100327

Cite this

@article{2acfdb514dbf4c5bb48323f842aa222c,

title = "Graph Waves",

abstract = "We present efficient algorithmic mechanisms to partition graphs with up to 1.8 billion edges into subgraphs which are fixed points of degree peeling. We are able to process graphs with tens of millions of edges in seconds and hundreds of millions of edges in minutes. For fixed points that turn out to be larger than a desired interactivity parameter we further decompose them with a novel (to our knowledge) linear algorithm into what we call “graph waves and fragments”. This decomposition is used to create spanning views of fixed points that we call “DAG Covers”. We illustrate these decompositions by presenting intuitive and interactive visualizations of the meta-structures of a variety of publicly available data sets including social, web, and citation networks.",

keywords = "Graph decomposition, Graph visualization, Waves, k-core",

author = "James Abello and Daniel Nakhimovich",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = aug,

day = "28",

doi = "10.1016/j.bdr.2022.100327",

language = "American English",

volume = "29",

journal = "Big Data Research",

issn = "2214-5796",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Graph Waves

AU - Abello, James

AU - Nakhimovich, Daniel

PY - 2022/8/28

Y1 - 2022/8/28

N2 - We present efficient algorithmic mechanisms to partition graphs with up to 1.8 billion edges into subgraphs which are fixed points of degree peeling. We are able to process graphs with tens of millions of edges in seconds and hundreds of millions of edges in minutes. For fixed points that turn out to be larger than a desired interactivity parameter we further decompose them with a novel (to our knowledge) linear algorithm into what we call “graph waves and fragments”. This decomposition is used to create spanning views of fixed points that we call “DAG Covers”. We illustrate these decompositions by presenting intuitive and interactive visualizations of the meta-structures of a variety of publicly available data sets including social, web, and citation networks.

AB - We present efficient algorithmic mechanisms to partition graphs with up to 1.8 billion edges into subgraphs which are fixed points of degree peeling. We are able to process graphs with tens of millions of edges in seconds and hundreds of millions of edges in minutes. For fixed points that turn out to be larger than a desired interactivity parameter we further decompose them with a novel (to our knowledge) linear algorithm into what we call “graph waves and fragments”. This decomposition is used to create spanning views of fixed points that we call “DAG Covers”. We illustrate these decompositions by presenting intuitive and interactive visualizations of the meta-structures of a variety of publicly available data sets including social, web, and citation networks.

KW - Graph decomposition

KW - Graph visualization

KW - Waves

KW - k-core

UR - https://www.scopus.com/pages/publications/85133951636

UR - https://www.scopus.com/pages/publications/85133951636#tab=citedBy

U2 - 10.1016/j.bdr.2022.100327

DO - 10.1016/j.bdr.2022.100327

M3 - Article

SN - 2214-5796

VL - 29

JO - Big Data Research

JF - Big Data Research

M1 - 100327

ER -

Graph Waves

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this