Network decomposition into fixed points of degree peeling

James Abello, François Queyroi

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Degree peeling is used to study complex networks. It is a decomposition of the network into vertex groups of increasing minimum degree. However, the peeling value of a vertex is non-local in this context since it relies on the number of connections the vertex has to groups above it. We explore a different way to decompose a network into edge layers such that the local peeling value of the vertices on each layer does not depend on their non-local connections with the other layers. This corresponds to the decomposition of a graph into subgraphs that are invariant with respect to degree peeling, i.e., they are fixed points. We introduce a general method to partition the edges of an arbitrary graph into fixed points of degree peeling called the iterative edge core decomposition. Information from this decomposition is used to formulate a novel notion of vertex diversity based on Shannon’s entropy. We illustrate the usefulness of this decomposition on a variety of social networks including weighted graphs. Our method can be used as a preprocessing step for community detection and graph visualization.

Original languageEnglish (US)
Article number191
Pages (from-to)1-14
Number of pages14
JournalSocial Network Analysis and Mining
Volume4
Issue number1
DOIs
StatePublished - Jan 1 2014

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications

Keywords

  • Degree peeling
  • Fixed points
  • Graph decompositions
  • Influence ranking

Fingerprint

Dive into the research topics of 'Network decomposition into fixed points of degree peeling'. Together they form a unique fingerprint.

Cite this