Fixed Points of Graph PeelingReport as inadecuate

Fixed Points of Graph Peeling - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 DIMACS - Center for Discrete Mathematics and Theoretical Computer Science Rutgers 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : Degree peeling is used to study complex networks. It corresponds to a decomposition of the graph 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 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 in this context a method to partition the edges of a graph into fixed points of degree peeling, called the iterative-edge-core decomposition. Information from this decomposition is used to formulate a notion of vertex diversity based on Shannon-s entropy. We illustrate the usefulness of this decomposition in social network analysis. Our method can be used for community detection and graph visualization.

Keywords : degree peeling graph decompositions fixed points influence ranking

Author: James Abello - François Queyroi -



Related documents