On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

Ricky Laishram; Sucheta Soundarajan

doi:10.1109/ICDM54844.2022.00124

On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

Ricky Laishram, Sucheta Soundarajan

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

2 Scopus citations

Abstract

In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the 'skeletal' structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.

Original language	English (US)
Title of host publication	Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022
Editors	Xingquan Zhu, Sanjay Ranka, My T. Thai, Takashi Washio, Xindong Wu
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1017-1022
Number of pages	6
ISBN (Electronic)	9781665450997
DOIs	https://doi.org/10.1109/ICDM54844.2022.00124
State	Published - 2022
Event	22nd IEEE International Conference on Data Mining, ICDM 2022 - Orlando, United States Duration: Nov 28 2022 → Dec 1 2022

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
Volume	2022-November
ISSN (Print)	1550-4786

Conference

Conference	22nd IEEE International Conference on Data Mining, ICDM 2022
Country/Territory	United States
City	Orlando
Period	11/28/22 → 12/1/22

Keywords

graph
k-core
structure

ASJC Scopus subject areas

General Engineering

Access to Document

10.1109/ICDM54844.2022.00124

Cite this

Laishram, R., & Soundarajan, S. (2022). On Finding and Analyzing the Backbone of the k-Core Structure of a Graph. In X. Zhu, S. Ranka, M. T. Thai, T. Washio, & X. Wu (Eds.), Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022 (pp. 1017-1022). (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2022-November). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDM54844.2022.00124

On Finding and Analyzing the Backbone of the k-Core Structure of a Graph. / Laishram, Ricky; Soundarajan, Sucheta.
Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022. ed. / Xingquan Zhu; Sanjay Ranka; My T. Thai; Takashi Washio; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2022. p. 1017-1022 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2022-November).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Laishram, R & Soundarajan, S 2022, On Finding and Analyzing the Backbone of the k-Core Structure of a Graph. in X Zhu, S Ranka, MT Thai, T Washio & X Wu (eds), Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022. Proceedings - IEEE International Conference on Data Mining, ICDM, vol. 2022-November, Institute of Electrical and Electronics Engineers Inc., pp. 1017-1022, 22nd IEEE International Conference on Data Mining, ICDM 2022, Orlando, United States, 11/28/22. https://doi.org/10.1109/ICDM54844.2022.00124

Laishram R, Soundarajan S. On Finding and Analyzing the Backbone of the k-Core Structure of a Graph. In Zhu X, Ranka S, Thai MT, Washio T, Wu X, editors, Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022. Institute of Electrical and Electronics Engineers Inc. 2022. p. 1017-1022. (Proceedings - IEEE International Conference on Data Mining, ICDM). doi: 10.1109/ICDM54844.2022.00124

Laishram, Ricky ; Soundarajan, Sucheta. / On Finding and Analyzing the Backbone of the k-Core Structure of a Graph. Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022. editor / Xingquan Zhu ; Sanjay Ranka ; My T. Thai ; Takashi Washio ; Xindong Wu. Institute of Electrical and Electronics Engineers Inc., 2022. pp. 1017-1022 (Proceedings - IEEE International Conference on Data Mining, ICDM).

@inproceedings{d7ca305ea28e4c079af7ffa994d6b172,

title = "On Finding and Analyzing the Backbone of the k-Core Structure of a Graph",

abstract = "In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the 'skeletal' structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.",

keywords = "graph, k-core, structure",

author = "Ricky Laishram and Sucheta Soundarajan",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 22nd IEEE International Conference on Data Mining, ICDM 2022 ; Conference date: 28-11-2022 Through 01-12-2022",

year = "2022",

doi = "10.1109/ICDM54844.2022.00124",

language = "English (US)",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1017--1022",

editor = "Xingquan Zhu and Sanjay Ranka and Thai, {My T.} and Takashi Washio and Xindong Wu",

booktitle = "Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022",

}

TY - GEN

T1 - On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

AU - Laishram, Ricky

AU - Soundarajan, Sucheta

PY - 2022

Y1 - 2022

N2 - In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the 'skeletal' structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.

AB - In many network applications, dense subgraphs have proven to be extremely useful. One particular type of dense subgraph known as the k-core has received a great deal of attention. k-cores have been used in a number of important applications, including identifying important nodes, speeding up community detection, network visualization, and others. However, little work has investigated the 'skeletal' structure of the k-core, and the effect of such structures on the properties of the overall k-core and network itself. In this paper, we propose the Skeletal Core Subgraph, which describes the backbone of the k-core structure of a graph. We show how to categorize graphs based on their skeletal cores, and demonstrate how to efficiently decompose a given graph into its Skeletal Core Subgraph. We show both theoretically and experimentally the relationship between the Skeletal Core Subgraph and properties of the graph, including its core resilience.

KW - graph

KW - k-core

KW - structure

UR - http://www.scopus.com/inward/record.url?scp=85147730629&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85147730629&partnerID=8YFLogxK

U2 - 10.1109/ICDM54844.2022.00124

DO - 10.1109/ICDM54844.2022.00124

M3 - Conference contribution

AN - SCOPUS:85147730629

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 1017

EP - 1022

BT - Proceedings - 22nd IEEE International Conference on Data Mining, ICDM 2022

A2 - Zhu, Xingquan

A2 - Ranka, Sanjay

A2 - Thai, My T.

A2 - Washio, Takashi

A2 - Wu, Xindong

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 22nd IEEE International Conference on Data Mining, ICDM 2022

Y2 - 28 November 2022 through 1 December 2022

ER -

On Finding and Analyzing the Backbone of the k-Core Structure of a Graph

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this