Network decomposition into fixed points of degree peeling

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-01103366
Contributor : Administrateur Hal-Upmc <>
Submitted on : Wednesday, January 14, 2015 - 3:32:00 PM
Last modification on : Friday, May 24, 2019 - 5:24:00 PM
Long-term archiving on : Saturday, April 15, 2017 - 5:32:15 PM

File

Abello_2014_Network.pdf
Files produced by the author(s)

Identifiers

Citation

James Abello, François Queyroi. Network decomposition into fixed points of degree peeling. Social Network Analysis and Mining, Springer, 2014, 4 (1), pp.191. ⟨10.1007/s13278-014-0191-7⟩. ⟨hal-01103366⟩

Share

Metrics

Record views

228

Files downloads

624