The K-peak Decomposition: Mapping the global structure of graphs

Priya Govindan, Chenghong Wang, Chumeng Xu, Hongyu Duan, Sucheta Soundarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected. To resolve this issue, we propose the k-peak graph decomposition method, based on the k-core algorithm, which finds the centers of distinct regions in the graph. Our contributions are as follows: (1) We present a novel graph decomposition- the k-peak decomposition- and corresponding algorithm, and perform a theoretical analysis of its properties. (2) We describe a new visualization method, the ‘Mountain Plot’, which can be used to better understand the global structure of a graph. (3) We perform an extensive empirical analysis of real-world graphs, including technological, social, biological, and collaboration graphs, and show how the k-peak decomposition gives insight into the structures of these graphs. (4) We demonstrate the advantage of using the k-peak decomposition in various applications, including community detection, contagion and identifying essential proteins.

Original languageEnglish (US)
Title of host publication26th International World Wide Web Conference, WWW 2017
PublisherInternational World Wide Web Conferences Steering Committee
Pages1441-1450
Number of pages10
ISBN (Print)9781450349147
DOIs
StatePublished - Jan 1 2017
Event26th International World Wide Web Conference, WWW 2017 - Perth, Australia
Duration: Apr 3 2017Apr 7 2017

Other

Other26th International World Wide Web Conference, WWW 2017
CountryAustralia
CityPerth
Period4/3/174/7/17

Fingerprint

Decomposition
Complex networks
Visualization
Proteins
Defects

Keywords

  • Graph visualization
  • Graphs
  • K-core
  • K-peak

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Govindan, P., Wang, C., Xu, C., Duan, H., & Soundarajan, S. (2017). The K-peak Decomposition: Mapping the global structure of graphs. In 26th International World Wide Web Conference, WWW 2017 (pp. 1441-1450). [3052635] International World Wide Web Conferences Steering Committee. https://doi.org/10.1145/3038912.3052635

The K-peak Decomposition : Mapping the global structure of graphs. / Govindan, Priya; Wang, Chenghong; Xu, Chumeng; Duan, Hongyu; Soundarajan, Sucheta.

26th International World Wide Web Conference, WWW 2017. International World Wide Web Conferences Steering Committee, 2017. p. 1441-1450 3052635.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Govindan, P, Wang, C, Xu, C, Duan, H & Soundarajan, S 2017, The K-peak Decomposition: Mapping the global structure of graphs. in 26th International World Wide Web Conference, WWW 2017., 3052635, International World Wide Web Conferences Steering Committee, pp. 1441-1450, 26th International World Wide Web Conference, WWW 2017, Perth, Australia, 4/3/17. https://doi.org/10.1145/3038912.3052635
Govindan P, Wang C, Xu C, Duan H, Soundarajan S. The K-peak Decomposition: Mapping the global structure of graphs. In 26th International World Wide Web Conference, WWW 2017. International World Wide Web Conferences Steering Committee. 2017. p. 1441-1450. 3052635 https://doi.org/10.1145/3038912.3052635
Govindan, Priya ; Wang, Chenghong ; Xu, Chumeng ; Duan, Hongyu ; Soundarajan, Sucheta. / The K-peak Decomposition : Mapping the global structure of graphs. 26th International World Wide Web Conference, WWW 2017. International World Wide Web Conferences Steering Committee, 2017. pp. 1441-1450
@inproceedings{46d4c6f05133425590af63ae4300e91e,
title = "The K-peak Decomposition: Mapping the global structure of graphs",
abstract = "The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected. To resolve this issue, we propose the k-peak graph decomposition method, based on the k-core algorithm, which finds the centers of distinct regions in the graph. Our contributions are as follows: (1) We present a novel graph decomposition- the k-peak decomposition- and corresponding algorithm, and perform a theoretical analysis of its properties. (2) We describe a new visualization method, the ‘Mountain Plot’, which can be used to better understand the global structure of a graph. (3) We perform an extensive empirical analysis of real-world graphs, including technological, social, biological, and collaboration graphs, and show how the k-peak decomposition gives insight into the structures of these graphs. (4) We demonstrate the advantage of using the k-peak decomposition in various applications, including community detection, contagion and identifying essential proteins.",
keywords = "Graph visualization, Graphs, K-core, K-peak",
author = "Priya Govindan and Chenghong Wang and Chumeng Xu and Hongyu Duan and Sucheta Soundarajan",
year = "2017",
month = "1",
day = "1",
doi = "10.1145/3038912.3052635",
language = "English (US)",
isbn = "9781450349147",
pages = "1441--1450",
booktitle = "26th International World Wide Web Conference, WWW 2017",
publisher = "International World Wide Web Conferences Steering Committee",

}

TY - GEN

T1 - The K-peak Decomposition

T2 - Mapping the global structure of graphs

AU - Govindan, Priya

AU - Wang, Chenghong

AU - Xu, Chumeng

AU - Duan, Hongyu

AU - Soundarajan, Sucheta

PY - 2017/1/1

Y1 - 2017/1/1

N2 - The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected. To resolve this issue, we propose the k-peak graph decomposition method, based on the k-core algorithm, which finds the centers of distinct regions in the graph. Our contributions are as follows: (1) We present a novel graph decomposition- the k-peak decomposition- and corresponding algorithm, and perform a theoretical analysis of its properties. (2) We describe a new visualization method, the ‘Mountain Plot’, which can be used to better understand the global structure of a graph. (3) We perform an extensive empirical analysis of real-world graphs, including technological, social, biological, and collaboration graphs, and show how the k-peak decomposition gives insight into the structures of these graphs. (4) We demonstrate the advantage of using the k-peak decomposition in various applications, including community detection, contagion and identifying essential proteins.

AB - The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected. To resolve this issue, we propose the k-peak graph decomposition method, based on the k-core algorithm, which finds the centers of distinct regions in the graph. Our contributions are as follows: (1) We present a novel graph decomposition- the k-peak decomposition- and corresponding algorithm, and perform a theoretical analysis of its properties. (2) We describe a new visualization method, the ‘Mountain Plot’, which can be used to better understand the global structure of a graph. (3) We perform an extensive empirical analysis of real-world graphs, including technological, social, biological, and collaboration graphs, and show how the k-peak decomposition gives insight into the structures of these graphs. (4) We demonstrate the advantage of using the k-peak decomposition in various applications, including community detection, contagion and identifying essential proteins.

KW - Graph visualization

KW - Graphs

KW - K-core

KW - K-peak

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

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

U2 - 10.1145/3038912.3052635

DO - 10.1145/3038912.3052635

M3 - Conference contribution

AN - SCOPUS:85051519824

SN - 9781450349147

SP - 1441

EP - 1450

BT - 26th International World Wide Web Conference, WWW 2017

PB - International World Wide Web Conferences Steering Committee

ER -